Жар холодных числ и пафос бесстрастной логики

Ознакомимся подробнее с тем, как «работает» данное определение. Докажем, например, что слово (A1 & ~(A2 V A1) не есть формула. Предположим противное: это слово — формула. Тогда знак & мог возникнуть в ней лишь в результате применения пункта (в) определения формулы. Но это значит, что A1 и ~(А2 V А1 должны быть формулами. Однако хотя А1 и есть формула (по пункту (а) определения), слово ~(A2 V A1 формулой не является, ибо для того, чтобы слово, начинающееся со знака ~, было формулой, необходимо, чтобы справа от него стояла формула. Но слово (A2 V A1 не представляет собой формулы, так как оно могло бы быть формулой только по пункту (в), но тогда в нем крайним справа знаком должна была бы быть правая скобка, чего в действительности нет. Таким образом, (А2 V А1 — не формула, а значит, ~(A2 V A1 не формула и, следовательно, исследуемое выражение в целом — не формула. Однако если бы мы рассмотрели, скажем, слово (А1 & (A2 V A1)), то применяя аналогичное рассуждение, убедились бы, что оно является формулой.

III. Равенства.

Если α и β — формулы, то α = β — равенство. Ничто иное равенством не является.

Условимся о сокращении: вместо двух равенств α = β и β = γ разрешается писать просто

α = β = γ («цепочка равенств»)

Аналогично будут пониматься и более длинные цепочки. Так, запись

α = β = γ = δ имеет смысл

α = β, β = γ, γ = δ[5]

IV. Постулаты.

[а]. Схемы аксиом.

1. (α & β) = (β & α) (закон коммутативности для конъюнкции).

2. (α V β) = (β V α) (закон коммутативности для дизъюнкции).

3. ((α & β) & γ) = (α & (β & γ)) (закон ассоциативности, или сочетательности, для конъюнкции).

4. ((α V β) V γ) = (α V (β V γ)) (закон ассоциативности для дизъюнкции).

5. (α & (β V γ)) = ((α & β) V (α & γ)) (закон дистрибутивности, или распределительности, конъюнкции относительно дизъюнкции).

6. (α V (β & γ)) = ((α V β) & (α V γ)) (закон дистрибутивности дизъюнкции относительно конъюнкции).

7. (α & (α V β)) = α (первый закон поглощения).

8. (α V (α & β)) = α (второй закон поглощения).

9. ~(α & β) = (~α V ~β) (первый закон Де Моргана).

10. ~(α V β) = (~α & ~β) (второй закон Де Моргана).

11. (α & α) = α (закон идемпотентности для конъюнкции).

12. (α V α) = α (закон идемпотентности для дизъюнкции).

13. ~~α = α (закон снятия двойного отрицания).

14. (α & 1) = α (закон отбрасывания единицы).

15. (α V 0) = α (закон отбрасывания нуля).

16. (α & ~α) = 0 (закон противоречия, выраженный в форме приравнивания противоречия нулю).

17. (α & ~α)=1 (закон исключенного третьего, выражений в форме равенства).

Перечисленные постулаты[6] являются не аксиомами, а схемами аксиом. Это значит, что, каждый постулат задает бесконечное множество аксиом определенной структуры. Так, схема аксиом 1 задает аксиомы: (А1 & А2) = (A2 & A1), ((А1 V ~A2) & ~A1) = (~A1 & (A1 V ~A2)) и т.д.; аксиомы — это равенства, принимаемые в качестве исходных.

Схемы аксиом 1 и 2 задают свойство перестановочности членов в конъюнктивных и дизъюнктивных формулах. Схемы аксиом 3 и 4 выражают ассоциативные законы, подобные ассоциативным законам школьной алгебры, где, как известно, (а • b) • с = а - (b • с) и (а + b) + с = a + (b + с). В школьной алгебре имеется только один дистрибутивный закон — закон дистрибутивности умножения относительно сложения: A • (b + с) = a • b + A • с, так как обычное сложение чисел не дистрибутивно относительно обычного умножения (то есть неверно, что для любых чисел а, b и с

а + (b • с) = (а + b) • (а + с)).

В данной же системе обе операции, конъюнкция и дизъюнкция, дистрибутивны одна относительно другой (схемы аксиом 5 и 6). Смысл законов Де Моргана[7] (схемы аксиом 9 и 10) можно передать фразами: «Отрицание конъюнктивной формулы означает дизъюнкцию отрицаний ее членов»; «Отрицание дизъюнктивной формулы означает конъюнкцию отрицаний ее членов». Смысл схем аксиом, выражающих остальные законы, непосредственно ясен. Заметим лишь, что они служат эффективным средством упрощения формул рассматриваемой формальной системы, то есть построения по данной формуле таких равных ей формул, которые проще, чем исходная (в том смысле, что содержат меньшее число вхождений логических связок); ср. ниже, с. 75—76.

[b]. Правила вывода.

Если верно равенство α = β, то верно и равенство Ф[α] = Ф[β]. Здесь Ф[α] есть произвольная формула, содержащая в качестве своей части, формулу α (аналогично понимается и Ф[β]). Это — правило замены равным (ср. выше с. 42), но «приуроченное» специально к нашему формальному аппарату. Смысл правила состоит в том, что в произвольной формуле Ф[α], в которую входит α, можно α в любом ее вхождении заменить на какую угодно равную ей формулу β и в результате получится формула Ф[β], равная формуле Ф[α][8].