Форум » Логические выражения » Решение одной задачи на побитную конъюнкцию в Алгебре Предикатов {E(k)} » Ответить
Решение одной задачи на побитную конъюнкцию в Алгебре Предикатов {E(k)}
dbaxps: Алгебра Предикатов {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} Например
Ответов - 1
dbaxps: В противном случае решение получается просто в одну строку. m v ( E(N(j) => E(A) ) ≡ 1 j=1
полная версия страницы