Изначально техника, используемая ниже была введена
в работе 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) и (¬A+A*B) = (¬A+B)
Рассмотрим классический пример задачи ЕГЭ №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 не удается
Перейдем к более сложным примерам
(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
при х = х(А)
Рассмотрим Пример 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,
а остальные заполняем нулями тогда
(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
(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
в работе 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) и (¬A+A*B) = (¬A+B)
Рассмотрим классический пример задачи ЕГЭ №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 не удается
Перейдем к более сложным примерам
(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
при х = х(А)
Рассмотрим Пример 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,
а остальные заполняем нулями тогда
(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
(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
No comments:
Post a Comment