Определение 2

а) Р, Q, R,..., X, Y, Z, P₁, P₂,..., Z₁, Z₂,... — формулы.

б) Если А — формула, то (ØА) — формула.

в) Если А и В — формулы, то (А Ù В), (АÚ В), (А É В), (А ~ В) — формулы.

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

Формулы, указанные в пункте а), называются элемен­тарными формулами, или атомами, а полученные по правилам пунктов б), в), — сложными формулами, или молекулами.

Следует иметь в виду, что в определении 2 буквы А и В являются метазнаками, с помощью которых обозначены любые формулы.

Определения 1 и 2 составляют синтактику языка логики высказываний.

Определение 2 является эффективным, т. е., поль­зуясь этим определением, можно за конечное число шагов относительно любого слова алфавита А_а.в. уста­новить, является оно формулой или нет. Рассмотрим некоторые примеры.

Пример 1. Слово (P Ú (QÉ R)) — формула. Действительно,

1. Р — формула

2. Q и R — формулы

3. (QÉ R) — формула

4. (P Ú (QÉ R)) — формула

1. Опр. 1.2а

2. Опр. 1.2а

3. Опр. 1.2в(1)

4. Опр. 1.2в(3,2)

Записи в правом столбце являются обоснованиями утверждений из левого столбца. Например, запись «Опр. 1.2в(3, 2)» означает «По определению 1.2, пункт в), примененному к утверждениям из строк 3 и 2».

Пример 2. Слово (P Ú (QÉ R) не является формулой. Применяя пункт в) определения 1.2 к формулам Р и (QÉ R), получаем формулу (P Ú (QÉ R)), а не слово (P Ú (QÉ R) так как в нем не хватает одной правой скобки. Значит, применение определения 1.2 не может привести к слову (P Ú (QÉ R), а по пункту г) этого определения других формул нет.

Для упрощения записей формул примем следующее соглашение об опу­скании скобок: опускать внешние скобки (первую левую и последнюю правую), а также все те скобки, которые становятся необязательными, если считать, что логиче­ские операции выполняются в таком порядке: отрица­ние Ø, конъюнкция Ù, дизъюнкция Ú, импликация É, эквиваленция ~.