Saturday, August 25, 2018

Метод Отображений (графы и системы логических уравнений) vs Метод битовых масок .Решение одной системы логических уравнений по Е.А.Мирончик (mea-2016-8.pdf)


(x1vx2)^(x2vx3)^(x3vx4)^(x4vx5)=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 (x5^y5^¬z5)) =1

Конвертируем систему

(x1vx2)^((!x1^y1^z1) v (x1^!y1^z1) v (x1^y1^!z1)) =1
(x2vx3)^((!x2^y2^z2) v (x2^!y2^z2) v (x2^y2^!z2)) =1
(x3vx4)^((!x3^y3^z3) v (x3^!y3^z3) v (x3^y3^!z3)) =1
(x4vx5)^((!x4^y4^z4) v (x4^!y4^z4) v (x4^y4^!z4)) =1
((!x5^y5^z5) v (x5^!y5^z5) v (x5^y5^!z5)) =1

Строим полный граф системы, следуя
http://kpolyakov.spb.ru/download/mea-2016-8.pdf


   Контроль на сервере Полякова


     Рассмотрим еще один пример эффективности метода


 
Конвертируем систему :-

(x1=>x2)^(x2=>x3)^(x3=>x4)^(x4=>x5)^(x5=>x6)^(x6=>x7)^
^(x7=>x8)^(x8=>x9)^(x9=>x10)=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 (x6^¬y6^z7) v (x7^y7^¬z7)) =1
((¬x8^y8^z8) v (x8^¬y8^z8) v (x8^y8^¬z8)) =1
((¬x9^y9^z9) v (x9^¬y9^z9) v (x9^y9^¬z9)) =1
((¬x10^y10^z10) v (x10^¬y10^z10) v (x10^y10^¬z10)) =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=>x8)^((¬x7^y7^z7) v (x6^¬y6^z7) v (x7^y7^¬z7)) =1
  (x8=>x9)^((¬x8^y8^z8) v (x8^¬y8^z8) v (x8^y8^¬z8)) =1
  (x9=>x10)^((¬x9^y9^z9) v (x9^¬y9^z9) v (x9^y9^¬z9)) =1
  ((¬x10^y10^z10) v (x10^¬y10^z10) v (x10^y10^¬z10)) =1


No comments:

Post a Comment