Интерпретации, разрешимость, выполнимость, общезначимость

Интерпретация – это сопоставления каждому элементарному высказыванию некоторых значений истинности.

Интерпретация, при которой значение формулы истинно называется моделью формулы.

Формула называется выполнимой, если имеется ее модель, в противном случае формула является невыполнимой.

(001 в порядке следования переменных XYZ – модель формулы).

Те формулы, которые всегда истинны или тождественно истинны, называются общезначимыми, или тавтологиями. Поиск этих формул – одна из основных задач логики. Для этого необходимо провести в общем случае 2ⁿ проверок, где n – общее число пропозициональных переменных.

Алгоритм проверкиобщезначимости для логики высказываний существует, поэтому говорят, что логика высказываний разрешима, что нельзя сказать о логике предикатов.

Пример. Проверка общезначимости путем построения дерева редукции (рис. 117) [32].

[(Х×Y®Z)×(Х®Y)]®(Х®Z), где: Х, Y, Z – пропозициональные переменные.

Пусть Х=1, тогда (Y®Z)×Y®Z (это частный случай формулы).

Пусть Х=0, тогда формула обращается в 1.

Рис. 117. Граф проверки общезначимости формулы

При получении частных случаев формул необходимо помнить:

1) , т.е. импликация с истинным консеквентом всегда истинна;

2) , т.е. импликация с ложным антецедентом всегда истинна;

3) ;

4) .