Solution of challenging equation with mixed basic predicates of type E() && DEL() via technique proposed by Helen Mironchick

Posting as common article with Helen Mironchick.

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
    (D(34)⊕D(51) => ¬D(A)^D(272)) v Е(15) ≡ 1  
is identically true (that is, it takes the value 1 for any natural value of the variable x)?

Further notice belongs to Helen :-

D(16) = ¬E(1)*¬E(2)*¬E(4)*¬E(8) = 
   =  ¬(E(1) v E(2) v E(4) v E(8)) = ¬E(15)
E(15)=¬D(16)

Convert original equation from implication to disjunction

(D(34)≡D(51)) v ¬D(A)^D(272)) v ¬D(16) ≡ 1
D(34)^D(51) v ¬D(34)^¬D(51) v ¬D(A)^D(272)) v ¬D(16) ≡ 1
D(34)^D(51) v ¬D(34)^¬D(51) v ¬D(A)^D(17)^D(16) v ¬D(16) ≡ 1

Suppress D(17) in first and fourth terms via ¬D(17),
then suppress D(2^4) via ¬D(2^4) in fourth term

D(34) = D(2)^D(17)
D(51) = D(3)^D(17)
D(31)^D(51) = D(2)^D(3)^D(17)

¬D(34) = (¬D(2) v ¬D(17))
¬D(51) = (¬D(3) v ¬D(17))

¬D(34)^¬D(51) = ¬D(2)^¬D(3) v ¬D(17)

D(2)^D(3)^D(17) v ¬D(2)^¬D(3) v ¬D(17) v 
  v  ¬D(A)^D(17)^D(2^4) v ¬D(2^4) ≡ 1

D(6) v ¬D(2)^¬D(3) v ¬D(17) v ¬D(A) v ¬D(2^4) ≡ 1

Thus A(min) = 6

Refences 
1. A. Mironchik, ALGEBRA OF PREDICATES AND RELATED GEOMETRIC MODELS CREATION IN REGARDS OF UNIFIED STATE EXAMINATION IN INFORMATICS (RUSSIAN EGE) ,
Informatics at school №3 , 2019

Basic predicates technique developed by Helen Mironchick for problem #18 of DEL(X) type

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
    (D(34)⊕D(51) => ¬D(A)^D(425)) v ¬D(125) ≡ 1  
is identically true (that is, it takes the value 1 for any natural value of the variable x)?

Convert original equation from implication to disjunction

(D(34)≡D(51)) v ¬D(A)^D(425)) v ¬D(125) ≡ 1
D(34)^D(51) v ¬D(34)^¬D(51) v ¬D(A)^D(425)) v ¬D(125) ≡ 1

Supress D(17) in first and fourth terms via ¬D(17),
then supress D(5^2) via ¬D(5^3) in fourth term

D(34) = D(2)^D(17)
D(51) = D(3)^D(17)
D(31)*D(51) = D(2)^D(3)^D(17)

¬D(34) = (¬D(2) v ¬D(17))
¬D(51) = (¬D(3) v ¬D(17))

¬D(34)*¬D(34) = ¬D(2)*¬D(3) v ¬D(17)

D(2)^D(3)^D(17) v ¬D(2)^¬D(3) v ¬D(17) v 
  v  ¬D(A)^D(17)^D(5^2) v ¬D(5^3) ≡ 1

D(6) v ¬D(2)^¬D(3) v ¬D(17) v ¬D(A) v ¬D(5^3) ≡ 1

Thus A(min) = 6
 

Shooting Domogarov's problem with D(5940) via techique of expansion into basic predicates developed by Helen A. Mironchick

Key features of the technique are the suppression of
factors in conjunction having type D(k^n) and the absorption
of a logic factors of the same type or a logical terms
in disjunction of the type ¬D(k^s), when factors or terms 
belong to the same basic class
 
See for details "Informatics at School №3 2019"

Just remind core Helen's definition :-
Define predicate 
 D(a,x) ={ 1 : x mod a = 0; 
                0 : x mod a !=0 }

Notice that when n >= m we get
   ¬D(k^n) + D(k^m)*Whatever =
     (D(k^n)=>D(k^m)*(¬D(k^n) + Whatever) =
    ¬D(k^n) + Whatever

I omit the universal quantifier and the predicate's 
dependence on "x", due to using the sign of the identity  "≡"

Now proceed as follows 
¬D(6300) + D(5940) + ¬D(A) ≡ 1
¬(D(2^2)*D(3^2)*D(5^2)*D(7))  + 
            D(2^2)*D(3^3)*D(5)*D(11) + ¬D(A) ≡ 1

Apply De Morgan rules to  ¬(D(2^2)*D(3^2)*D(5^2)*D(7))
¬D(2^2) + ¬D(3^2) + ¬D(5^2) + ¬D(7) +
         + D(2^2)*D(3^3)*D(5)*D(11) + ¬D(A) ≡ 1
Here we clearly see that factor D(3^3) cannot be suppressed
Suppress D(2^2)*D(5) in conjunction D(2^2)*D(3^3)*D(5)*D(11)
Finally obtain :-
¬D(2^2) + ¬D(3^2) + ¬D(5^2) + ¬D(5)) + ¬D(7) + 
           + D(3^3)*D(11) + ¬D(A) ≡ 1
¬D(2^2) + ¬D(3^2) + ¬D(5^2) + ¬D(5)) + ¬D(7) + D(297) + ¬D(A) ≡ 1
(D(A) => D(297) + . . . . .  ≡ 1

Thus A(min) =297

Сравни с http://информатика23.рф/wp-content/uploads/2017/05/232-1.pdf 

Решение системы булевских уравнений №122 (файл ege23.pdf) методом отображений

Исходная система

(x1vx2)^(x1^x2=>x3)^¬(x1^y1) =1
(x2vx3)^(x2^x3=>x4)^¬(x2^y2) =1
(x3vx4)^(x3^x4=>x5)^¬(x3^y3) =1
(x4vx5)^(x4^x5=>x6)^¬(x4^y4) =1
(x5vx6)^(x5^x6=>x7)^¬(x5^y5) =1
(x6vx7)^¬(x6^y6) =1
x7^y7 =0

(x1vx2)^(x1^x2=>x3)^¬(x1^y1) =1
(x2vx3)^(x2^x3=>x4)^¬(x2^y2) =1
(x3vx4)^(x3^x4=>x5)^¬(x3^y3) =1
(x4vx5)^(x4^x5=>x6)^¬(x4^y4) =1
(x5vx6)^(x5^x6=>x7)^¬(x5^y5) =1
(x6vx7)^¬(x6^y6)^¬(x7^y7)   =1

   Оригинальная идея этого подхода  принадлежит Е.А. Мирончик
   Смотри Р-27 решение Е.А. Мирончик файл ege23.doc

    Контроль по Полякову
    

Метод Отображений vs Метод битовых масок при решении некоторых известных систем булевских уравнений

                              
                              "Любая система уравнений в булевских
                               переменных может быть решена методом
                               отображений, а кажущееся отсутствие пары
                               перехода не может служить препятствием 
                               для ее создания"                              
                                                                        Елена А. Мирончик
Смотри например 
https://mapping-metod.blogspot.com/2019/03/03032019.html

Стандартное решегие следующей системы (68 из ege23.doc)

Смотри, например

https://www.youtube.com/watch?v=iLLuSPdC44Y

Конвертируем систему

(х1 => x2)^(y1 => y2)^(y1 => x1) =1

(х2 => x3)^(y2 => y3)^(y2 => x2) =1 

(х3 => x4)^(y3 => y4)^(y3 => x3) =1 

(х4 => x5)^(y4 => y5)^(y4 => x4) =1 

(х5 => x6)^(y5 => y6)^(y5 => x5) =1 

y6 => x6 =1

   Система 213 из ege18.doc

   

   (x2 => x1)^(y1=>y2) =1
   (x3 => x2)^(y2=>y3) =1
   (x4 => x3)^(y3=>y4) =1 
   (x5 => x4)^(y4=>y5) =1
   (x6 => x5)^(y5=>y6) =1 
   y3 => x1 = 1

   

Рассмотрим задачу 18 из того же Видео разбора

Определим одноместные предикаты  P(x) , Q(x) следущим     образом

     A(x) = { 1; x ∈ [x1;x2];
                  0; x !∈ [x1;x2]
                 }
   P(x) =  { 1; x ∈  [20;50] ;
                 0; x !∈ [20;50]
                }
   Q(x) = { 1; x ∈  [30;65] ;
                 0; x !∈ [30;65]
               }
Определить наименьшую длину области истинности А(х)
чтобы   ∀ x: ¬A(x) => (P(x) => ¬Q(x)) =  1
Снимем импликации и продолжим, применяя последовательно
законы Де Моргана :-

    ∀ x:  A(x) v ¬P(x) v ¬Q(x) = 1 
    ∀ x:  A(x) v ¬(P(x)^Q(x)) = 1 
    ∀ x:  P(x)^Q(x) => A(x)  = 1  (*)

Пусть $(A),$(P),$(Q) - области истинности предикатов А,P, Q
тогда $(P^Q) = $(P)∩$(Q) должна быть вложена в $(A)
В противном случае

∃ y :  (P(y)^Q(y) = 1)^(A(y) = 0) = 1
∃ y :  P(Y)^Q(y) => A(y) = 0

Но последнее противоречит (*)
Таким образом минимальная область истинности предиката А
есть $(P^Q) = $(P)∩$(Q) = [20,50] ∩ [30;65] = [ 30;50]

Отметим , что использование идентификаторов P и Q  для обозначения отрезков и булевских переменных одновременно
лектора нисколько не смущает
Дословно "х" принадлежит А назовем А, "х" принадлежит Р назовем Р, "х" принадлежит Q  назовем  Q 

What could you possibly learn from Helen Mironchick's original works versus watching Videos on the Web?

Solve system of boolean equations

Here we go, attempting to understand core approach proposed in
http://kpolyakov.spb.ru/download/mea-2016-8.pdf

Traditional Solution (same author year 2013) via inter-connecting pairs.
Much more efforts and not much fun versus previous solution
implementing the core ideas from  08/2016

Элементарный подход к решению задач клонов 361 ЕГЭ Информатика 2019 для пространства R^3

Найти максимальное целое А такое что
(A < 2x1+4x2+x3)v( A < x1+7x2+4x3)v(A < 101 - (6x1+28x2+8x3))
было тождественно истинно для всех х1,х2,х3 => 0
 
Эквивалентная задача ЛП
Область Допустимых Решений
(1) 2*x1+4*x2+x3 <=A
(2) x1+7*x2+4*x3 <=A
(3) х1,х2,х3 => 0
Определить максимум F(x1,x2,x3) =6x1+28x2+8x3

Элеметарное решение,использующее параметризованное
уравнение прямой , лежащей в пересечении плоскостей
- линия PQ на рисунке ниже

(1) 2*x1+4*x2+x3 = A
(2) x1+7*x2+4*x3 = A

Положим х3 = t
2*x1 + 4*x2 + t  = A
x1  + 7*x2 + 4*t = A   | *2
10*x2 = A-7*t
x2 =(1/10)*(A-7*t)

2*x1 + (2/5)*(A-7*t) + t = A
10*x1 + 2*(A-7t) + 5*t = 5A
10*x1 - 9*t = 3A
x1 = (3/10)*(A+3*t)

Найдем точку пересечение прямой
x1 = (3/10)*(A+3*t)
x2 = (1/10)*(A-7*t)
х3 = t
с плоскостью уровня 6x1+28x2+8x3 = С,имеющую максимально
возможное С при заданном параметре А, меняя значение переменной "t".

Для этого подставим х1,х2,х3 как функции от "t"
в уравнение плоскости уровня (С) и уменьшая
текущий параметр "t" увеличиваем С как функцию параметра А
(9/5)*(A+3*t) + (14/5)*(A-7*t) + 8*t = C
(23/5)*A + ((27-98+40)/5)*t = C
(23/5)*A - (31/5)*t = C
C(max) = (23/5)*A ; t = 0
Проверим , что точки (А/2,0,0),(0,A/7,0),(0,0,А/4),((3/7)A,0,(1/7)A)
находятся в  полупространстве 6*х1+28*х2+8*х3 <(23/5)*A,
a в точке ((3/10)A,(1/10)A,0) имеет место равенство
6*х1+28*х2+8*х3 =(23/5)*A


(23/5)*A < 101 -A
(28/5)*A < 101
A < (505/28)
Откуда A(max)=18

Двойственная задача ЛП
   (1) 2*y1+y2 =>6
   (2) 4*y1+7*y2 =>28
   (3) y1+4*y2 => 8
   (4) y1,y2 => 0 
Определить минимум G(y1,y2) =A*y1+A*y2   

По-существу, все действия, описанные выше немедленно вытекают из 2-ой теоремы двойственности. Смотри
https://mapping-metod.blogspot.com/2019/04/361-ege18doc-3.html 
 

Метод Отображения и система №233 ЕГЭ Информатика 2019

Проверка знания законов Де Моргана ( 7 раз подряд )

   ((x1=>y1)=>x2)=>y2 =0
   ((¬x1+y1)=>x2)=>y2 =0
   (¬(¬x1+y1)+x2)=>y2 =0
¬(x1*¬y1)*¬x2 + y2 =0
  (¬x1 + y1)*¬x2 + y2=0
¬x1*¬x2 + y1*¬x2 + y2 =0
  (x1+x2)*(y1=>x2)*¬y2 =1

    Калькулятор Полякова

  

Двойственность в Линейном Программировании и клонирование задачи №361 ЕГЭ Информатика в простанства размерности 3 и выше

Оригинальная формулировка задачи 361

Найти наибольшее целое А чтобы
(A < x1+2*x2+x3 ) v (A < 2*x1+x2+5*x3) v (A < 101-4*x1-4*x2-5*x3)
было истинно для всех х1,х2,х3 => 0

Допустим
  (A < x1+2*x2+x3 ) v (A < 2*x1+x2+5*x3)  =False
что равносильно
  (x1+2*x2+x3 <=A )^(2*x1+x2+5*x3<= A) = True
Эквивалентная задача ЛП
  (1) x1+2*x2+x3 <= A
  (2) 2*x1+x2+5*x3 <= A
  (3) х1,x2,x3 => 0
Определить максимум F(x1,x2,x3) =4*x1+4*x2+5*x3
Двойственная задача ЛП
  y1+2*y2 => 4
  2*y1+y2 => 4
  y1+5*y2 => 5
  y1,y2 => 0
Определить минимум G(y1,y2) = A*y1+A*y2

======================================================
Теорема. (Первая основная теорема двойственности.)

Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны.Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
=====================================================
Смотри также
 https://1cov-edu.ru/lineynoe-programmirovanie/dvoystvennaya-zadacha/reshenie/

Строим область в плоскости соответствующую
двойственной задаче

Решаем систему

(1) y1+2*y2= 4
(2) 2*y1+y2= 4

Минимум достигается в точке у1=4/3; y2=4/3

G(4/3,4/3) = A*(8/3)
A*(8/3)+A < 101
A*(11/3) < 101
A < 303/11

Откуда  A(max)= 27

Подставим оптимальные значения у1 и у2 в 3-е уравнение
4/3+5*(4/3) = 24/3=8 > 5
По 2-ой теореме двойственности оптимальное х3 =0
Смотри  https://1cov-edu.ru/lineynoe-programmirovanie/dvoystvennaya-zadacha/reshenie/ 
касаемо 2-ой  теоремы двойственности , а также Пример 2
Вторая теорема двойственности

*****************************************
Рассмотрим еще одну задачу
*****************************************

Найти наибольшее целое А чтобы

 (A < x1+2*x2+4*x3 ) v (A < 2*x1+x2+11*x3) v (A < 101-4*x1-4*x2-20*x3)
было истинно для всех х1,х2,х3 => 0

Эквивалентная задача ЛП
  (1) x1+2*x2+4*x3 <= A
  (2) 2*x1+x2+11*x3 <= A
Определить максимум F(x1,x2,x3) =4*x1+4*x2+20*x3

Двойственная задача ЛП
  y1+2*y2 => 4
  2*y1+y2 => 4
  4*y1+11*y2 => 20
Определить минимум G(y1,y2) = A*y1+A*y2

Строим область в плоскости соответствующую двойственной задаче
 

Решаем систему

(1) y1+2*y2= 4
(2) 2*y1+y2= 4

Минимум достигается в точке у1=4/3; y2=4/3
G(4/3,4/3) = A*(8/3)
A*(8/3)+A < 101
A*(11/3) < 101
A < 303/11
Откуда  A(max)= 27

Подставим оптимальные значения у1 и у2 в 3-е уравнение
4*(4/3)+11*(4/3) = 60/3=20=20
Следовательно, оптимальное х3 для этой задачи не обязано 
вырождаться в 0 

 Найти максимальное целое А такое что
   (A < 2x1+4x2+x3)v( A < x1+7x2+4x3)v(A < 101 -(6x1+28x2+8x3))
было тождественно истино для всех х1,х2,х3 => 0

 Эквивалентная задача ЛП
   Область Допустимых Решений
     (1)  2*x1+4*x2+x3 <=A
     (2)  x1+7*x2+4*x3 <=A 
     (3) х1,х2,х3 => 0 
Определить максимум F(x1,x2,x3) =6x1+28x2+8x3

Двойственная задача ЛП
   (1) 2*y1+y2 =>6
   (2) 4*y1+7*y2 =>28
   (3) y1+4*y2 => 8
   (4) y1,y2 => 0 
Определить минимум G(y1,y2) =A*y1+A*y2 

         (23/5)*A <101 - A
         (28/5)*A <101
         A < (505/28)

        Откуда  A(max) =  18

    Элеметарное решение,использующее параметризованное
    уравнение прямой , лежащей в пересечении 
          (1)  2*x1+4*x2+x3 = A
          (2)  x1+7*x2+4*x3 = A

    Положим х3 = t
        2*x1 + 4*x2 + t = A
        x1 + 7*x2 + 4*t = A
       10*x2 = A-7*t
       x2 =(1/10)*(A-7*t)

       2*x1 + (2/5)*(A-7*t) + t = A
      10*x1 + 2*(A-7*t) + 5*t = 5A
      10*x1 - 9*t = 3A
      x1 = (3/10)*(A+3*t)

 Подставляем х1,х2,х3 как функции от "t"
 в уравнение плоскости уровня (С) и уменьшая
 текущий параметр  "t" увеличиваем С как функцию
 параметра А 

    (9/5)*(A+3*t) + (14/5)*(A-7*t) + 8*t = C
    (23/5)*A + ((27-98+40)/5)*t = C
    (23/5)*A - (31/5)*t = C
    C(max) = (23/5)*A  ; t = 0
    (23/5)*A < 101 -A
    (28/5)*A < 101
    A < (505/28)
 Откуда  A(max)=18  

Далее проверим , что точки (А/2,0,0),(0,A/7,0),(0,0,A/4),
((3/7)A,0,(1/7)A) находятся в  полупространстве 
6*х1+28*х2+8*х3 <(23/5)*A, а в точке ((3/10)A,(1/10)A,0) :  6*х1+28*х2+8*х3 =(23/5)*A

По-существу все действия последнего раздела являются следствием 2-ой теоремы двойственности
 
    

Problem 361 from ege18.doc revised

Исходная формулировка в ege18.doc

Покажем , что размерность пространства здесь не по существу
Сформулируем вопрос следующим образом

Для какого наибольшего целого числа А выражение
    (A < x) v (A < y) v (A < z) v (A <101 - x - y - z) = 1  
тождественно истинно при любых целых {x,y,z}∈R^3  

Допустим
   (A < x) v (A < y) v (A < z)=False
что равносильно
   (x<=A)^(y<=A)^(z<=A) = True
Иначе говоря
  (A<x)v(A<y)v(A< z)=False <=> (x<=A)^(y<=A)^(z<=A) = True
   
Вершина октaнта (x <= A)^(y<= A)^(z<=A) окажется 
в точке (А,А,А). Рассмотрим семейство плоскостей 
уровня x+y+z = C. Вектор градиента = {1,1,1}
Найдем наименьшее значение С(min), чтобы нижнее полупространство из двух на которые плоскость уровня
разбивает R^3 содержало октант (x<=A)^(y<=A)^(z<=A)

Тогда минимальное С(min), удовлетворяющее этому условию,
дает  плоскость x+y+z = C(min) проходящая через вершину
октанта (x <= A)^(y<=A)^(z<=A)
В точке (А,А,А) : С(min) = 3*А 
Тогда имеет место 
  3*А < 101 - A 
  4*A < 101
Откуда  A(max) = 25  

В действительности, можно вариировать вектор градиента 
как общей нормали к семейству плоскостей уровня 
принципиально это ничего не изменит.
Формулировка в разумной общности :- 

Для какого наибольшего целого числа А выражение
    (A < x) v (A < 2y) v (A < 4z) v (A <101 - x - 2y - 4z) = 1  
тождественно истинно при любых целых {x,y,z}∈R^3   

Вершина октaнта (x <= A)^(2*y<= A)^(4*z<=A) окажется 
в точке (А,А/2,А/4). Рассмотрим семейство плоскостей 
уровня x+2y+4z = C. Вектор градиента = {1,2,4}
Найдем наименьшее значение С(min), чтобы нижнее полупространство из двух на которые плоскость уровня
разбивает R^3 содержало октант (x<=A)^(2*y<=A)^(4*z<=A)
            A+2*(A/2)+4*(A/4) = 3*A => C(min)=3*A
Далее 
   3*A < 101 - {A+2*(A/2)+4*(A/4)}
   4*A < 101
Откуда 
  A(max) =25

*************************************************************
Just for fun consider case R^n  with n=4 for instance
************************************************************* 
Для какого наибольшего целого числа А выражение
    (A < x1) v (A < x2) v (A < x3) v (A < x4) v (A < 101-x1-x2 -x3-x4) = 1  
тождественно истинно при любых целых {x1,x2,x3,x4}∈R^4   
ОДР = { x1<=A; x2<=A; x3<=A; x4<=A}
Max F(x1,x2,x3,x4) = x1+x2+x3+x4 = 4*A
4*A < 101 -A
5*A < 101
A(max) =20