VK Тренировочный КИМ от 01.05.2017 . Задача 23

Расставим скобки для ясности ( приоритет "^" над  "v")

(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

Битовая маска для  {x}
x1 x2 x3 x4
-------------------
1   1   1   1
0   1   1   1
0   0   1   1
0   0   0   1
0   0   0   0

Рассмотрим  вхождение {x1,x2,x3,x4} 1,1,1,1 - тогда первая скобка
в каждом уравнении из 4 -ех последних есть 0. Скобки же 2-ая,3-ья
содержат в коньюнкции х[j] = 1, которое можно просто опустить.
Применим отрицание к каждому из этих уравнений,дважды используя закон Де Моргана.

Первый раз :-

 ¬((¬y1 ^ z1) v (y1 ^ ¬z1))  =¬1
 ¬(¬y1 ^ z1) ^ ¬(y1 ^ ¬z1) =0

Второй раз для каждой скобки в коньюнкции :-

(y1 v ¬z1) ^ ( ¬y1 v z1) =0
. . . . . . . .

Исходная система  :-

(¬y1 ^ z1) v (y1 ^ ¬z1) =1
(¬y2 ^ z2) v (y2 ^ ¬z2) =1
(¬y3 ^ z3) v (y3 ^ ¬z3) =1
(¬y4 ^ z4) v (y4 ^ ¬z4) =1

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

(y1 v ¬z1) ^ (¬y1 v z1)=0
(y2 v ¬z2) ^ (¬y2 v z2)=0
(y3 v ¬z3) ^ (¬y3 v z3)=0
(y4 v ¬z4) ^ (¬y4 v z4)=0

Следующий шаг замена  ¬AvB на  A->B.
Применяя известную формулу булевой алгебры
мы получаем систему 4-ех тождеств , каждое из
которых имеет два решения.

(z1->y1)^(y1->z1)= (y1 <=> z1) =0
(z2->y2)^(y2->z2)= (y2 <=> z2) =0
(z3->y3)^(y3->z3)= (y3 <=> z3) =0
(z4->y4)^(y4->z4)= (y4 <=> z4) =0

Окончательно получаем  :-

 (y1 <=> z1) =0
 (y2 <=> z2) =0
 (y3 <=> z3) =0
 (y4 <=> z4) =0

Данная система имеет  2^4=16 решений

2. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,1,1,1 , в этом случае
    количество конвертируемых уравнений станет равно 3.
    
y1 ^ z1 = 1
(y2 <=> z2) =0
(y3 <=> z3) =0
(y4 <=> z4) =0

Имеем   2^3 =8 решений

3. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,1,1 , в этом случае
    количество конвертируемых уравнений станет равно 2.


y1 ^ z1 = 1
y2 ^ z2 = 1
(y3 <=> z3) =0
(y4 <=> z4) =0

Имеем 2^2 = 4 решения

3. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,0,1 , в этом случае
    количество конвертируемых уравнений станет равно 1.


y1 ^ z1 = 1
y2 ^ z2 = 1
y3 ^ z3 = 1
(y4 <=> z4) =0

Имеем  2 решения

4. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,0,0 , в этом случае
    количество конвертируемых уравнений станет равно 0.
    Их просто нет.

y1 ^ z1 = 1
y2 ^ z2 = 1
y3 ^ z3 = 1
y4 ^ z4 = 1

Одно решение

Ответ :  16 + 8 + 4 + 2 + 1 =31

Решение той же задачи Методом отображений. Построение полного графа следуя Е.А.Мирончик  для системы

(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

Официальные ответы от 09.05.17

  Well done.