Алгебра базисных предикатов по Е.А. Мирончик (2017) versus Bitwise2 (II)

Изначально техника, используемая ниже была введена
в работе http://kpolyakov.spb.ru/download/mea18bit.pdf   
Существует также статья в журнале "Информатика в школе"
№7 2017 несколько более удобная для первого чтения, но только 
как твердая копия, он-лайн версии нет.

**************
Теорема 1
**************
Для выполнения  ∀ x∈N: E(k,x) => E(m,x) = True 
необходимо и достаточно, чтобы множество единичных битов "k" полностью входило во множество единичных битов "m"

Достаточность
Пусть j(1),..,j(s) - номера единичных битов "k" ,
упорядоченное по убыванию (например),тогда
¬E(k) = ¬E(j(1))*....*¬E(j(s)) покажем,что
        ¬E(k) + E(m) = 1
Имеем
¬E(k)=¬E(j(1)*....*¬E(j(s)
E(m) = E(j(1)) + ... + E(j(s)) + E(rest)
Последовательно подавляем все множители в конъюнкции
¬E(k)+E(m)=¬E(j(1))*....*¬E(j(s)) + E(j(1)) + ... + E(j(s)) + E(rest) = 1

Необходимость
Если есть хоть один единичный бит "к" (c номером "р"), не входящий в единичные биты "m",то k&2^p !=0  и в тоже время номера единичных битов "m" не содержат "р",тогда 2^p с единицей на месте "р" в двоичном представлении 1000...0 (считая от 0 справа налево) будет умножаться на 0 в р-ой позиции "m",то есть m&2^p=0
В этом случае  k&2^p !=0 то есть Е(к,2^p)=1 если при этом 
m&2^p =0 тогда Е(m,2^p)=0
В этом случае  Е(к,2^p) => Е(m,2^p) =0 то есть условие теоремы не выполнено для всех "x"

Рассмотрим классический пример задачи ЕГЭ №18 на побитную конъюнкцию

Запишем в терминах алгебры {E(k)}
      E(49)=> (¬E(33)=> E(A))  ≡ 1
Разложим Е(49) и Е(33) по базисным предикатам
     Е(49) = Е(32) + Е(16) + Е(1)
     Е(33) = Е(32) +Е(1)
По Де Моргану :-
    ¬Е(49) = ¬Е(32)*¬Е(16)*¬Е(1)
Избавимся от импликаций в исходном уравнении
и получим
  ¬Е(32)*¬Е(16)*¬Е(1) + Е(32) +Е(1) +Е(А) ≡ 1
Подавим ¬Е(32) и ¬Е(1) в конъюнкции (помня,что ¬X*Y+X = Y+X)
   ¬Е(16) + Е(33) + Е(А) ≡ 1
и конвертируем обратно в импликацию
   (Е(16)=>E(A)) + (E(16)=>E(33)) ≡ 1
Допустим, что  Е(16)=>E(A) ≡ 1

Применяя Теорему 1,положим A(min) = 16 
  33=100001
  16=010000  
Возьмем любое А < A(min) тогда в четвертом бите
это А имеет 0 положим х(А) = 10000
  16&x(A) =  1
  A&x(A)  =  0
  33&x(A) = 0
Таким образом рассматриваемый предикат ложен
при значении аргумента х(А) :-
(Е(16)=>E(A)) + (E(16)=>E(33))(х(А)) = 0
Дествительно, уменьшить А(min)=16 не удается

Перейдем к более сложным примерам
Рассмотрим Пример 7 
из http://kpolyakov.spb.ru/download/bitwise2.pdf

Можно сформулировать и так :-
Найти максимальное А, чтобы предикат 
    (¬E(46) + ¬E(18)) => (E(115) => ¬E(A))
был тождественно истинным

Определим  $(C)  как множество единичных бит в С ∈ N , идущих
строго в порядке убывании разрядов  {j(1),j(2),....,j(k)}
(¬E(46) + ¬E(18)) => (E(115) => ¬E(A)) ≡ 1
(¬E(46) + ¬E(18)) => (¬E(115) + ¬E(A)) ≡ 1
E(46)*E(18) + ¬E(115) + ¬E(A) ≡ 1

Поскольку импликация дистрибутивна как по отношению к дизъюнкции так и конъюнкции

(E(A) => E(46)*E(18)) + (E(A) => ¬E(115)) ≡ 1
(E(A) => E(46))*(E(A) => E(18))  + (E(A) => ¬E(115)) ≡ 1

Найдем А(мах) такое ,что
(E(A) => E(46))*(E(A) => E(18)) ≡ 1

По Теореме 1
$(A) ⊂ $(46&18) = $(2)
46 = 101110
&
18 = 010010
=============
2 =  000010

Откуда А(мах) = 2
Рассмотрим любое А > 2
Тогда А имеет единичный бит вне $(46) либо вне $(18)
в числе х(А) поставим на это место 1, а остальные 
заполняем нулями, что повлечет
(E(A,х(А)) => E(46,х(А))*(E(A,х(А)) => E(18,х(А)) = 0  ;
Далее нужно, чтобы х(А) ∈ Е(115)
115 = 1110011
                                                          6543210
В 0-ой из единичных разрядов 1110011 ставим 1, 
а остальные заполняем нулями кроме тех где уже
стоят "1".
(E(A,х(А)) => ¬E(115,x(A)) = 0

Таким образом, действительно А(мах) = 2

************************
Второе решение
************************
(¬E(46) + ¬E(18))=> (E(115)=> ¬(E(A)) = 1
E(46)*E(18) + ¬E(115) + ¬E(A) = 1
E(46) =E(44) + E(2)
E(18) =E(16) + E(2)
E(46)*E(18) = E(44)*E(16) + E(44)*E(2) + E(2)*E(16) + E(2)
E(46)*E(18) = E(44)*E(16) + E(2)
E(44)*E(16) + E(2) + ¬E(A) = 1
(E(A)=>E(2)) + (E(A)=>E(44))*(E(A)=>E(16)) = 1
(E(A)=>E(2)) + (E(A)=>E(44&16)) =1

44=101100
&
16=010000
=======
0 =000000

(E(A)=>E(2)) + (E(A)=>E(0)) =1
(E(A)=>E(2))  =1

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

Рассмотрим Пример 4
из http://kpolyakov.spb.ru/download/bitwise2.pdf

(E(28)+E(45)) => (¬E(48)=> E(A)) ≡ 1
¬E(28)*¬E(45) + E(48) + E(A) = 1
¬E(32)¬E(16)*¬E(8)*¬E(4)*¬E(1) + E(32) + E(16) + E(A)  ≡ 1
Подавляем два первых множителя конъюнкции
 ¬E(8)*¬E(4)*¬E(1) + E(32) + E(16) + E(A)  ≡ 1
¬E(13) + E(48) + E(A) ≡ 1
(E(13)=> E(A)) + (E(13) => E(48)) ≡ 1
(E(13)=> E(A)) ≡ 1

Положим А(min) = 13
Возьмем любое A < A(min)
48=110000
13=001101
Тогда в одном из разрядов содержащих  1 в 1101
А будет иметь 0. В числе х(А) на это место ставим 1
(либо 0-ой либо 2-ой либо 3-ий разряды)  остальные 
разряды в х(А) нулевые.
13&x(A)  = 1
А&x(A)   = 0
48&x(A) = 0
Откуда
(E(13,x(A)=> E(A,x(A)) + (E(13,x(A)=> E(48,x(A)) =0
Действительно,  A(min) =13