Система традиционно решается методом битовых масок, так как для Х-ов это хорошо известная верхнетреугольная матрица и остается подсчитать число решений для каждой из ее строк , что не представляет особой трудности.
Ниже следует решение основанное на построении полного графа системы с последующим примением техники предложенной Е.А.Мирончик [
1 ] . Построение полного графа для данной системы[
(x1->x2)^(x2->x3)^(x3->x4) =1
(¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1) =1
(¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2) =1
(¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3) =1
(¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4) =1
Конвертируем систему следующим образом
(x1=>x2)^((¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1)) =1
(x2=>x3)^((¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2)) =1
(x3=>x4)^((¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3)) =1
(¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4) =1
Когда х1=0 есть лишь одна пара y=1 ; z1=1
иначе есть две пары
y1=0 ; z1 =1
y1=1 ; z1=0
Стандартное решение чез битовую маску для {х}
дает тот же результат 31
Рассмотрим систему, где использование битовых масок потребует большего количества вычислений и конвертируем ее следующим образом
(x1=>x2)^(x2=>x3)^(x3=>x4)(x4=>x5)^(x5=>x6)^(x6=>x7)=1
((¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1)) =1
((¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2)) =1
((¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3)) =1
((¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4)) =1
((¬x5^y5^z5) v (x5^¬y5^z5) v (x4^y5^¬z5)) =1
((¬x6^y6^z6) v (x6^¬y6^z6) v (x6^y6^¬z6)) =1
((¬x7^y7^z7) v (x7^¬y7^z7) v (x7^y7^¬z7)) =1
Конвертированная система
(x1=>x2)^((¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1)) =1
(x2=>x3)^((¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2)) =1
(x3=>x4)^((¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3)) =1
(x4=>x5)^((¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4)) =1
(x5=>x6)^((¬x5^y5^z5) v (x5^¬y5^z5) v (x4^y5^¬z5)) =1
(x6=>x7)^((¬x6^y6^z6) v (x6^¬y6^z6) v (x6^y6^¬z6)) =1
((¬x7^y7^z7) v (x7^¬y7^z7) v (x7^y7^¬z7)) =1
Строим полный граф для последней системы.В отличие от битовых масок увеличение размеров матрицы обрабатывется без длинных вычислений.
Поведение графа системы при ее увеличение числа
импликации, например до 7:-
Тестируем ответ на Сервере Полякова
Другой пример.
В этом случае битовая маска для Х отнюдь не очевидна
(x1+x2)^(x2+x3)^(x3+x4)=1
((¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1)) =1
((¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2)) =1
((¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3)) =1
((¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4)) =1
Конвертируем систему
(x1+x2)*((!x1*y1*z1) + (x1*!y1*z1) + (x1*y1*!z1)) =1
(x2+x3)*((!x2*y2*z2) + (x2*!y2*z2) + (x2*y2*!z2)) =1
(x3+x4)*((!x3*y3*z3) + (x3*!y3*z3) + (x3*y3*!z3)) =1
((!x4*y4*z4) + (x4*!y4*z4) + (x4*y4*!z4)) =1
Контроль
Сравним с образцом Р-34 из ege23.doc. Думаю,что текст конвертированной системы Р-34 содержит опечатку либо случайную неточность.
Думаю, что правильная версия системы в образце - следующая
Протестируем уравнение Р-34, конвертированное несколько иначе
чем на первом снапшоте вверху :-
(x1=>x2)^(¬x1vy1vz1)^(x1v¬y1vz1)^(x1vy1v¬z1)=1
(x2=>x3)^(¬x2vy2vz2)^(x2v¬y2vz2)^(x2vy2v¬z2)=1
(x3=>x4)^(¬x3vy3vz3)^(x3v¬y3vz3)^(x3vy3v¬z3)=1
(¬x4vy4vz4)^(x4v¬y4vz4)^(x4vy4v¬z4)=1
Результат сервера подтверждает, что поданная на вход система корректна.Рассмотрим систему №150 из ege23.doc
Конвертируем ее следующим образом ( отличным от Р-34 )
(x1=>x2)^(¬x1vy1vz1)^(x1v¬y1vz1)^(x1vy1v¬z1)=1
(x2=>x3)^(¬x2vy2vz2)^(x2v¬y2vz2)^(x2vy2v¬z2)=1
(x3=>x4)^(¬x3vy3vz3)^(x3v¬y3vz3)^(x3vy3v¬z3)=1
(x4=>x5)^(¬x4vy4vz4)^(x4v¬y4vz4)^(x4vy4v¬z4)=1
(¬x5vy5vz5)^(x5v¬y5vz5)^(x5vy5v¬z5)=1
Построим диаграмму следуя Е.А. Мирончик
Проверим систему на сервере Полякова
Литература
1.
http://kpolyakov.spb.ru/download/mea-2016-8.pdf
