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

 

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

3) ;

4) .

 

Логическая равносильность. Законы логики

Два высказывания равносильны, если они одновременно истинны или одновременно ложны.

Две формулы равносильны если их эквиваленция является тавтологией (общезначима).

F₁↔F₂≡1.

Равносильность – это отношение между формулами и как отношение обладает свойствами рефлексивности, симметричности, транзитивности.

Равносильности логики высказываний называют законами логики.

Основные законы логики и основные тавтологии: законы Аристотеля, де Моргана, идемпотентности, а также остальные равносильности, рассмотренные нами в дискретной математике.

Иногда доказывают равносильность формул А и В, если они являются следствием друг друга.

А→В, В→А. Тогда А≡В.

В логике часто используется прием подстановки.

Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и ту же формулу, то полученные формулы останутся равносильными. Это обозначается так:

(Х||У) или (Х,У) – «вместо Х подставить У».

Принцип двойственности.

Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными, если каждую из них можно получить из другой заменой символов конъюнкции, дизъюнкции, «0», «1» на символы дизъюнкции, конъюнкции, «1», «0», соответственно.

Принцип двойственности утверждает, что если две формулы равносильны, то и двойственные им формулы тоже равносильны.

Иногда законами логики называют только тавтологии, т.е. тождественно истинные формулы. Рассмотрим такие законы [1]:

1) PQ→P – «конъюнкция сильнее каждого из его членов»;

2) P→(PÚQ) – «дизъюнкция слабее каждого из её членов»;

3) P→(Q→P) – «истина из чего угодно»;

4) P→(P→Q) – «из ложного всё что угодно»;

5) [P→(Q→R)]↔[Q→(P→R)] «перестановка посылок»;

6) [P→(Q→R)]↔[(PQ)→R] «объединение и разъединение посылок»;

7) [(P→R)(Q→R)]↔[(PÚQ)→R] «правило разбора случаев»;

8) [(P→Q)→[(P→`Q)→`P] «правило приведения к противоречию»;

9) [(P→Q)(Q→R)]→(P→R) «цепное заключение».

Эти законы можно, например, доказать путем использования формул равносильных преобразований или путем построения дерева редукции формулы.

Например: PQ→P= .