Some issues related with Unified State Examination in Informatics in Russian Federation: Метод Отображений (графы и системы логических уравнений) vs Метод битовых масок на примере одной известной системы из новостной ленты ВК

Система традиционно решается методом битовых масок, так как для Х-ов это хорошо известная верхнетреугольная матрица и остается подсчитать число решений для каждой из ее строк , что не представляет особой трудности.

Ниже следует решение основанное на построении полного графа системы с последующим примением техники предложенной Е.А.Мирончик [ 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

    Построим диаграмму следуя Е.А. Мирончик