Лекция 4_3гр

1. Метод семантических таблиц в алгебре высказываний

2.

Оценкой
переменных
в
формуле
= (X1,…,Xn) называется отображение
множества { X1,…,Xn } в множество {0,1}.
Обозначения: | и | .
n
Всего оценок 2 .

3.

Альтернативный
подход
к
проверке
тождественной истинности формулы
основывается на попытке построения оценки,
опровергающей данную формулу. Если из
предположения существования такой оценки
получается противоречие, то формула Ф
тождественно истинна.

4.

Семантической
таблицей
называется
упорядоченная пара множеств формул | .
|
Семантическая таблица
называется
выполнимой, если существует такая оценка
переменных , что
1)
для любой формулы
2)
для любой формулы

5.

Примеры.
1. Семантическая таблица
выполнима для оценки (X)=1, (Y)=0;
2. Семантическая таблица
невыполнима.

6.

Основная
теорема
семантических таблиц.
метода
Для любой формулы условие |
выполняется тогда и только тогда, когда
|
семантическая
таблица
невыполнима.

7.

Семантическая таблица Γ|Δ называется:
невыполнимой, если для любой оценки
переменных