1.3Конъюнктивная нормальная формула

Конъюнктивной нормальной формой данной формулы называется равносильная ей формула, представляющая собой произведение элементарных сумм.

Докажем, что для каждой формулы существует конъюнктивная нормальная форма. Пусть сначала X — произвольная формула, содержащая только операции &, V и. Рассмотрим двойственную X формулу X. Пусть B* — дизъюнктивная нормальная форма формулы X*, а B — формула, двойственная B*. Так как X* и B* равносильны, то по закону двойственности X и B также равносильны. Формула B*, будучи дизъюнктивной нормальной формой, представляет собой сумму элементарных произведений. Легко видеть, что двойственная B* формула B является произведением элементарных сумм. И так как B равносильна X, то, следовательно, она является конъюнктивной нормальной формой формулы X. Так как для каждой формулы существует равносильная ей формула, содержащая только операции &, V, то, следовательно, для каждой формулы существует конъюнктивная нормальная форма, что и требовалось доказать.

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

Для того чтобы формула была тождественно истинной, необходимо достаточно, чтобы каждый множитель ее конъюнктивной нормальной формы имел по крайней мере два слагаемых, из которых одно является какой-нибудь переменной, а другое — ее отрицанием.

В силу симметричности операций сложения и умножения в логическом исчислении можно аналогичным образом показать, что: Для того чтобы формула была тождественно ложной, необходимо и достаточно, чтобы каждое слагаемое ее дизъюнктивной нормальной формы содержало по крайней мере одну пару множителей, из которых один есть какая-нибудь переменная, а другой — ее отрицание. Полученные критерии дают полное решение проблемы разрешения.

1.4 Непротиворечивость исчисления высказываний

Проблема непротиворечивости возникает при рассмотрении любого исчисления; это одна из кардинальных проблем математической логики. Дадим определение непротиворечивости логического исчисления, которое относится не только к исчислению высказываний, но и ко всем логическим системам, изучаемым в математической логике. Мы назовем логическое исчисление непротиворечивым, если в нем не выводимы никакие две формулы, из которых одна является отрицанием другой. Иными словами, непротиворечивое исчисление — это такое исчисление, что, какова бы ни была формула никогда формулы и не могут быть одновременно выведены из аксиом этого исчисления с помощью указанных в нем правил.

Проблема непротиворечивости состоит в следующем: является данное исчисление непротиворечивым или нет?

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

Все сказанное об исчислении высказываний оказывается справедливым и для всех тех логических исчислений, которые мы будем рассматривать далее. То обстоятельство, что в противоречивом исчислении всякая формула выводима, может быть использовано для доказательства непротиворечивости. Для этого достаточно показать, что существует по крайней мере одна не выводимая формула. Отсюда будет следовать непротиворечивость исчисления. Непротиворечивость исчисления высказываний устанавливается, однако, очень просто и без этого.

Теорема.

Исчисление высказываний непротиворечиво. Как мы уже говорили выше, каждую формулу исчисления высказываний можно рассматривать в то же время как формулу алгебры высказываний. Покажем, что все формулы, выводимые в исчислении высказываний и рассмотренные как формулы алгебры высказываний, являются тождественно истинными, т. е. принимают значение И при всех значениях переменных высказываний.

Легко непосредственно проверить, что аксиомы исчисления высказываний таковы. Покажем, что если формула Х (Л), содержащая переменное высказывание Л, тождественно истинна, то и формула Х получаемая из Х (А) подстановкой, также тождественно истинна. В самом деле, Х (А) при всех значениях переменных высказываний принимает значение Я. В таком случае Х (И) и Х (Л) имеют значение И, каковы бы ни были значения других переменных высказываний. Но при любых значениях переменных высказываний может иметь только значение И или Л. Отсюда ясно, что Х всегда будет иметь значение И.

Докажем, что если формулы X и X → B тождественно истинны, то формула B также тождественно истинна. Если X тождественно истинна, то она всегда имеет значение И. Так как формула X → B также всегда принимает значение И, то B не может принять значение Л ни при каких значениях переменных высказываний, иначе формула X → B приняла бы значение И → Л, которое, по определению следования в алгебре высказываний, есть Л.

Итак, мы показали, что: 1) все аксиомы суть тождественно истинные формулы, 2) применяя к тождественно истинным формулам правила вывода, мы получаем также тождественно истинные формулы. Отсюда следует, что все выводимые формулы исчисления высказываний, рассматриваемые как формулы алгебры высказываний, являются тождественно истинными. В таком случае ясно, что если формула Х выводима в исчислении высказывании, то формула Х не может быть выводима, так как Х — тождественно истинная формула, а Х тогда, наоборот, принимает значение Л при всех значениях входящих переменных высказываний. Итак, непротиворечивость исчисления высказываний доказана.