Отправлено: 15.10.19 21:30. Заголовок: Решение одной задачи на побитную конъюнкцию в Алгебре Предикатов {E(k)}

Алгебра Предикатов {E(k}} определена в http://kpolyakov.spb.ru/download/mea18bit.pdf

Пусть {N(j)} j=1,2,...,m - конечное множество натуральных чисел.
Найти наименьшее А при котором имеет место следующее тождество
(E(N(1) =>(E(N(2) =>(E(N(3 )=> . . . .=>(E(N(m)) =>E(A)) . . . . ))) ≡1

Решение.
Преобразуем исходное выражение к виду:-
m
v (¬E(N(j) ) v E(A) ≡ 1
j=1
----m-----------------------------
¬( ^ E(N(j) ) v E(A) ≡ 1
----j=1---------------------------
---m--------------------------------
( ^ E(N(j) ) => E(A) ≡ 1
-- j=1-----------------------------
Эквивалентно
-------------------- m-----------------
¬E(A) => ¬( ^ E(N(j) ) ≡ 1
--------------------j=1----------------
Далее
----------------- m------------------
¬E(A) => ( v ¬E(N(j) ) ≡ 1
---------------- j=1----------------
В силу дистрибутивности импликации
по отношению к дизъюнкции :-
m
v (¬E(A) => ¬E(N(j) ) ≡ 1
j=1
Эквивалентно
m
v ( E(N(j) => E(A) ) ≡ 1
j=1
По теореме 1 в https://mapping-metod.blogspot.com/2019/02/2017-versus-bitwise2-1-2.html
получаем A(min) = min{N(j); j=1,2,..,m}
Если нет ни одного N(j) все биты которого входят в А то последняя дизъюнкция не может быть равна тождественно 1 , так как каждое слагаемое дает бит, не входящий в А, строим двоичное число z0 , содержащие все эти биты (наличие совпадающих только упрощает ситуацию)
Тогда
m
( v (E(N(j) => E(A))(z0) = 0
j=1
то есть, если А < A(min), то каждое N(j) имеет такой бит и найденное А(min) действительно минимально.
Следствие
Любая задача вида Е(M)=>(E(N)=>E(A)) ≡ 1 тривиальна A=min{M,N}

Например

 Отправлено: 15.10.19 21:47. Заголовок: (m-1) копия Е(А) не добавлены к исходному уравнения умышленно

В противном случае решение получается просто в одну строку.
m
v ( E(N(j) => E(A) ) ≡ 1
j=1