14.2. Синтаксис логики высказываний. Формулы логики высказываний

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

Искусственные языки, создаваемые для научных целей, например, для науки логики, называются формализованными языками. При этом задается алфавит, где каждая последовательность символов называется словом. Затем вводится синтаксис – правила, позволяющие определять правильные слова, которые называются формулами [29].

Алфавит логики высказываний состоит из:

высказывательных или пропозициональных переменных (X, Y, Z, …, W);
логических констант (0 – ложь, 1 – истина);
символов логических операций (, |, ,  ,, …);
служебных символов, например, символов скобок ( [, ], {, }, (, )).

Определение формулы:

всякая высказывательная переменная – формула;
всякая логическая константа – формула;
если F₁ и F₂ – формулы, то формулами являются F₁F₂, F₁F₂, F₁F₂, ,…(т.е. при наличии знака операции над формулами).

Для обозначения переменных и формул, в математической логике приняты прописные буквы

Язык, служащий для объяснения другого языка, называется метаязыком. На таком языке (на естественном русском) написан этот подраздел.

14.3. Формализация высказываний

Формализация высказывания – это представления сложного высказывания формулой. В сложных высказываниях нужно выделить элементарные высказывания, знаки операций и представить все это формулой.

Пример. «Если студент Зыков не присутствует на лекции и не является больным, то он находится в казино».

, где X – студент Зыков присутствует на лекции, Y – студент Зыков болен, Z – студент Зыков в казино.

Формула может быть представлена графом, где каждая вершина будет обозначать операцию (рис. 116).

Пример. X(YZ).

Рис. 116. Граф представления формулы X(YZ)

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

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

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

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

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

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

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

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

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

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

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