Дерево

Построение дерева - один из самых наглядных способов увидеть все наборы, особо не напрягая мозги. Однако является довольно длительным процессом.

Пример 1

( ¬(x1)→x2)∧( ¬(x2)→x3)∧( ¬(x3)→x4)∧( ¬(x4)→x5)=1
( ¬(y1)→y2)∧( ¬(y2)→y3)∧( ¬(y3)→y4)∧( ¬(y4)→y5)=1
x1∨y1=1

(x1∨x2)∧(x2∨x3)∧(x3∨x4)∧(x4∨x5)=1
(y1∨y2)∧(y2∨y3)∧(y3∨y4)∧(y4∨y5)=1
x1∨y1=1

Довольно простое дерево. Рассматриваем начальное значение 0 или 1 для первой переменной, а затем идём по логическим операциям уравнения, исходя из таблиц истинностей.

Ответ получим, сложив полученные решения и возведя сумму в квадрат (так как два ряда переменных).

Ответ: 169

Пример 2

x1→x2∨x3∧¬(x4)=1
x3→x4∨x5∧¬(x6)=1
x5→x6∨x1∧¬(x2)=1

¬(x1)∨x2∨x3∧¬(x4)=1
¬(x3)∨x4∨x5∧¬(x6)=1
¬(x5)∨x6∨x1∧¬(x2)=1

Используем формулу (следствие из законов Де-Моргана):

¬A∨B= ¬(A∧¬B)


¬(x1∧¬(x2))∨x3∧¬(x4)=1
¬(x3∧¬(x4))∨x5∧¬(x6)=1
¬(x5∧¬(x6))∨x1∧¬(x2)=1

Сделаем замену:


y1=x1∧¬(x2) y2=x3∧¬(x4) y3=x5∧¬(x6)

¬(y1)∨y2=1
¬(y2)∨y3=1
¬(y3)∨y1=1

y1→y2=1
y2→y3=1
y3→y1=1

Казалось бы ничего трудного, но последнее уравнение цепляется за первую переменную. Строим дерево:

Так как последнее уравнение цепляется за первое, то решением могут быть либо все нули (1→0=0), либо все единицы.

При возврате замены заметим, что каждый игрек имеет по 3 варианта решений для набора нулей и 1 вариант для единиц. Значит ответ мы получим, возведя 3 в куб и прибавив единицу.

Ответ: 28

Пример 3

(x1∧x2)∨(¬(x1)∧¬(x2))∨(x1≡x3)=1
(x2∧x3)∨(¬(x2)∧¬(x3))∨(x2≡x4)=1

(x8∧x9)∨(¬(x8)∧¬(x9))∨(x8≡x10)=1


Упростим систему, воспользовавшись формулой:

(A∧B)∨(¬A∧¬B) равносильно (A≡B)


(x1≡x2)∨(x1≡x3)=1
(x2≡x3)∨(x2≡x4)=1

(x8≡x9)∨(x8≡x10)=1

Очень важно обратить внимание на то, какие скобки присутствуют в системе и рассматривать данное дерево как бы парами.

Ответ получим, сложив количество решений с каждой стороны и сложив каждую из полученных сумм (т.к. уравнения не пересекаются).

Ответ: 20

© Денис Филипцев
Яндекс.Метрика
Besucherzahler mail order brides
счетчик посещений
счётчик тиц и pr