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

Updated as of 15/02/2019

Изначально техника, используемая ниже была введена
в работе 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"

Заметим (¬A = > ¬B ) = (A + ¬B) = (B => A)

(E(A)*¬E(12) => ¬E(A)*E(21)) + ¬E(21)*¬E(12) ≡ 1
¬E(A) + E(12) + ¬E(A)*E(21) +  ¬E(21)*¬E(12) ≡ 1

Применяем принцип поглощения
¬E(A) + E(12) + ¬E(21)*¬E(12) ≡ 1

и подавляем ¬E(12) в конъюнкции
¬E(A) + E(12) + ¬E(21) ≡ 1
¬(¬E(12)) + ¬E(A) + ¬E(21) ≡ 1

Используем дистрибутивность импликации
по отношению к дизъюнкции
¬E(12) => ¬E(A) + ¬E(21) ≡ 1
(¬E(12) => ¬E(A)) + (¬E(12) => ¬E(21)) ≡ 1

Согласно замечанию получаем
(E(A) => E(12)) + (E(21) => E(12)) ≡ 1

21=10101 (binary)
12=1100 (binary)

По Теореме 1
E(21) => E(12) ! ≡ 1
Таким образом нам необходимо, чтобы
E(A) => E(12) ≡ 1
По Теореме 1 окончательно имеем :-
А(мах) = 12

((E(13) + E(A)) => E(13) + E(A)*¬E(39) ≡ 1
¬E(13)*¬E(A) + E(13) + E(A)*¬E(39) ≡ 1

Подавляем E(А) в конъюнкции
¬E(A) + E(13) + E(A)*¬E(39) ≡ 1
¬E(A) + E(13) + ¬E(39) ≡ 1

Используем дистрибутивность импликации
по отношению к дизъюнкции
¬(¬E(13)) + ¬E(A) + ¬E(39) ≡ 1
¬E(13) => ¬E(A) + ¬E(39) ≡ 1

Согласно замечанию
(¬E(13) => ¬E(A)) + (¬E(13) => ¬E(39)) ≡ 1
(E(A) => E(13)) + (E(39) => E(13)) ≡ 1

По Теореме 1
E(39) => E(13) !≡ 1
Таким образом нам необходимо, чтобы 
E(A) => E(13) ≡ 1
По Теореме 1 окончательно имеем :-
А(мах) = 13

***************
Теорема 2
***************
Полученное выше А(мах) увеличить невозможно
не потеряв тождественной истинности  
(E(A)=>E(T)) + (E(P)=>E(T)) ≡ 1
где смысл Т и Р ясен из контекста выше. 

Доказательство
Определим  $(C)  как множество единичных бит в С ∈ N , идущих
строго в порядке убывании разрядов  {j(1),j(2),....,j(k)}

Рассмотрим тождество (E(A)=>E(T)) + (E(P)=>E(T)) = 1
раносильное исходному уравнению
Пусть А(mах) = Т и А > A(max)

Существует единица из $(A) не входящая в $(A(max))
Определим х(А) имеющим нули в всех позициях $(A(max))
и единицу в позиции единицы в $(A),не входящей в $(A(max))

P также как и А должно иметь единицу не входящую в $(A(max))
В х(А) поставим единицу на той же позиции, что и единица из Р,
не входящая в $(A(max))

Тогда
 T&x(A) = 0
 A&x(A) = 1
 P&x(A) = 1

Получаем
 E(A,x(A)) = 1
 E(T,x(A)) = 0  
 E(P,x(A)) = 1

E(A,x(A)) => E(T,x(A)) = 0
E(P,x(A)) => E(T,x(A)) = 0
Предикат (E(A)=>E(T)) + (E(P)=>E(T)) = 0
при х = х(А)

************
Задача 2
************
Найти максимальное А удовлетворяющее
уравнению ¬E(10) + ¬E(A) + E(17)  ≡ 1


¬E(10) + ¬E(A) + ¬(¬E(17))  ≡ 1
¬E(17) => ¬E(10) + ¬E(A)  ≡ 1
(¬E(17)=> ¬E(10)) + (¬E(17)=> ¬E(A)) ≡ 1

Лекго  доказать
¬E(17)=> ¬E(10) !≡ 1
так как
E(17) + ¬E(10) = E(10) => E(17) !≡ 1  по Теореме 1

Поскольку E(10) => E(17) !≡ 1
Таким образом нам необходимо, чтобы Е(А) =>E(17) ≡ 1
E(17) + ¬E(A) = E(A) => E(17) ≡ 1  

По Теореме 1

A(max) = 17