Интерпретация формул

Правила построения формул

Словарь исчисления высказываний дает возможность строить составные высказывания из простых высказываний, соединяя их логическими связками. Правила построения S описывают выражения, являющиеся объектами языка. Такие высказывания называются формулами.

Совокупность правил построения формул выглядит так:

· Всякий атом (высказывание) является формулой;

· Если X и Y - формулы, то Ш X, (X Щ Y), (X Ъ Y), (X ® Y) и (X « Y) – формулы;

· Никаких формул, кроме порожденных применением указанных выше правил, нет.

Круглые скобки позволяют указать порядок, в котором применялись правила. Если в третьем примере утверждений, приведенных выше, обозначим высказывание «идет дождь» буквой P, а высказывание «дорога мокрая» буквой Q, то, используя правила построения, все утверждение будет выглядеть следующим образом:

(P ® Q) ®(ШQ ® ШP).

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

Введем семантическую область {И, Л}. Интерпретировать формулу - это, значит, приписать ей одно из двух значений истинности: И или Л. Значение истинности формулы зависит только от структуры этой формулы и от значений истинности составляющих ее высказываний. Таблица истинности логических связок исчисления высказываний приведена ниже.

P	Q	Ш P	P Щ Q	P Ъ Q	P ® Q	P « Q
И	И	Л	И	И	И	И
И	Л	Л	Л	И	Л	Л
Л	И	И	Л	И	И	Л
Л	Л	И	Л	Л	И	И

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

Рассмотрим формулу: (P Щ Q) ® (ШR). Таблица истинности для нее будет выглядеть следующим образом:

P	Q	R	ШR	P Щ Q	(P Щ Q) ® (ШR)
И	И	И	Л	И	Л
И	И	Л	И	И	И
И	Л	И	Л	Л	И
И	Л	Л	И	Л	И
Л	И	И	Л	Л	И
Л	И	Л	И	Л	И
Л	Л	И	Л	Л	И
Л	Л	Л	И	Л	И

Определение 1: интерпретацией формулы исчисления высказываний называется такое приписывание истинностных значений атомам формулы, при котором каждому из атомов приписано либо И, либо Л.

Определение 2: Формула истинна при некоторой интерпретации тогда и только тогда, когда она получает значение И в этой интерпретации, в противном случае формула ложна.

Определение 3: Формула является общезначимой (тавтологией) тогда и только тогда, когда она истинна при всех возможных интерпретациях. Формула является необщезначимой тогда и только тогда, когда она не является общезначимой.

Определение 4: Формула является противоречивой (невыполнимой) тогда и только тогда, когда она ложна при всех возможных интерпретациях. Формула является непротиворечивой (выполнимой) тогда и только тогда, когда она не является противоречивой.