Практические приложения алгебры высказываний

F (0, 0) = 0.

Получаем F (X, Y) .

Задача 6. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

Составим таблицу истинности для формул, являющихся посылками:g width=12 height=23 src="images/referats/3105/image015.png">

Найдем такую формулу F (X, Y), для которой F (0, 0) = 1, которая будет логическим следствием трех данных посылок.

F (1, 0) = F (0, 1) = F (1, 1) = 0.

Получаем F (X, Y) .

Чтобы определить логическим следствием каких посылок является формула А (X1,X2,…,Xn), необходимо:

1) привести ее к СКНФ.

2) составить конъюнкции формулы А с недостающими в ее СКНФ элементарными дизъюнкциями, взятыми по одной, две, три и т.д. (всевозможные варианты). Полученные формулы и будут посылками, из которых следует данная формула А.

Найти все не тождественно ложные формулы алгебры высказываний, для которых следующая формула является логическим следствием:

Задача 1.

Решение:

Недостающие дизъюнкции:

Посылка:

Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.

Задача 2.

Решение:

Недостающие дизъюнкции:

Посылка:

Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.

Задача 3.

Решение:

Недостающие дизъюнкции:

Посылки:

;

;

;

;

;

;

.

Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.

Задача 4. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:

╞

Решение:

Составим таблицу истинности для формул, являющихся посылками и заключением:

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 12-я строка, в которой λ (Z) = 1 и λ (V) = 1. Ясно, что при этих значениях Z и V искомая посылка F (Z, V) должна принимать значение 0, так как в противном случае формула не будет логическим следствием формул . Будем считать, что на других наборах значений высказываний Z и V формула F (Z, V) принимает значение 1. Итак, для искомой посылки F (Z, V) получаем следующую таблицу истинности:

 Скачать реферат