Basic predicates technique per Helen Mironchick and pushing challenging problem #18 of DEL(X) type (EGE Informatics 2019) to community

April 27, 2019

Denote by DEL (n, m) the statement “a natural number n is divided without a remainder by a positive integer m”. For what is the smallest natural number A, the formula is
(Del (x, 35) ⊕ Del (x, 56))→(¬ Del (x, A)^Del (x, 14))+¬ Del (x,4)
is identically true (that is, it takes the value 1 for any natural value of the variable x)?

(D(35)≡D(56)) + ¬D(a)*D(2)*D(7) + ¬D(4) ≡ 1

D(35)*D(56) + ¬D(35)*¬D(56) + ¬D(A)*D(7) + ¬D(4) ≡ 1
D(35)*D(56) = D(7)*D(5)*D(8)

¬D(35)*¬D(56) = (¬D(5) + ¬D(7))*(¬D(8) + ¬D(7) =
                                            = ¬D(5)*¬D(8) + ¬D(7)

D(7)*D(5)*D(8) + ¬D(5)*¬D(8) + ¬D(7) +
                     + ¬D(A)*D(7) + ¬D(4) ≡ 1

D(5)*D(8) + ¬D(5)*¬D(8) +
                  + ¬D(7) + ¬D(A) + ¬D(4) ≡ 1

D(40) + ¬D(5)*¬D(8) + ¬D(28) + ¬D(A) ≡ 1

Thus A(min) = 40