1. Язык и метаязык

Логика, которая излагается, называется предметной логикой или просто логикой; логика, с помощью которой ведется это изложение, называется логикой исследователя или металогикой. Соответственно, язык, на которой ведется изложение предметной логики, называется предметным языком; и язык, который является формой существования металогики, называется языком исследователя или метаязыком.

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

2. Высказывание

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

а) оно не может одновременно быть и правильным, и ложным (принцип непротиворечивости).

б) исключено, чтобы оно было и неправильным, и неложным (принцип исключения третьей возможности).

Например, предложения «1+2=3», «СА. Рыбаков написал роман «Дети Арбата»» — истинные высказывания, а предложения «1+2 = 4», «С А. Платонов напи­сал «Дети Арбата»» —ложные.

Таким образом, все высказывания разбиваются на два класса — класс И (истинных высказываний) и класс Л (ложных высказываний). Классы И и Л называются истинностными значениями. Часто вместо «высказывание принадлежит классу И (классу Л)» говорят «высказы­вание принимает (истинностное) значение И (значе­ние Л)».

Следует заметить, что хотя всякое высказывание обязательно имеет одно из двух значений И или Л, однако не всегда это значе­ние известно. Примерами таких высказываний являются недоказанные или неопровергнутые гипотезы: теорема Ферма, проблема Гольд­баха и пр.

3. Алфавит и формулы алгебры высказываний

Допустим, что в предметном языке имеются предло­жения, внутренняя структура которых безразлична. Требуется только, чтобы их можно было распознавать и различать. Такие предложения предметного языка назовем элементарными формулами, или, следуя С. К. Клини, атомами. Атомы обозначаются через прописные буквы латинского алфавита, начиная с буквы Р и в случае необходимости используются нату­ральные индексы: Р, Q, R, ..., X, Y, Z, P1, P2 ..., Z1, Z2, ... Разные буквы обозначают раз­ные атомы (по содержанию).

В предметном языке есть такие предложения, что некоторая часть их — также предложение. Например, теорема школьной геометрии «Если в треугольнике два угла равны, то он равнобедренный» имеет части «В тре­угольнике два угла равны», «Он [треугольник] равнобед­ренный», каждая из которых сама является предложе­нием. Подобные предложения предметного языка в алгеб­ре высказываний описываются сложными формулами, или молекулами. Молекулы строятся из атомов с по­мощью некоторых слов и оборотов предметного языка, которым в алгебре высказываний соответствуют логи­ческие операторы , , , , ~. Обозначения атомов, логические операторы и еще два символа (, ), называемые скобками, составляют алфавит алгебры высказываний.

Определение 1. Алфавитом алгебры высказываний называется множество

A_а.в. = {P, Q, R, ..., X, Y, Z, Р₁, P₂, ..., Z₁, Z₂, ....,, , , , , (, )}, элементы которого называются буквами. Конечные после­довательности букв алфавита А_а.в. называются словами в этом алфавите.

Некоторые слова в алфавите А_а.в являются формулами алгебры высказываний.

Определение 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)

Опр. 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) , а по пункту г) этого определения других формул нет.

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