Непротиворечивость
и полнота

[предыдущая глава]  [оглавление]  [следующая глава]

[опровергнутая формула]: Если формула ~X - доказанная, то формула X называется опровергнутой.

Здесь символ "~" представляет собой операцию отрицания. Смысл операции отрицания не обязательно должен быть определен, лишь бы ДС содержала его в алфавите и допускала построение формул с этим символом.

[противоречие]: Противоречием называется ситуация, когда формулу можно и доказать, и опровергнуть (то есть, можно доказать X и ~X).

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

[непротиворечивость (сильная)]: Непротиворечивой называют дедуктивную систему, в которой нельзя доказать противоречие.

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

[непротиворечивость (слабая)]: Непротиворечивой называют дедуктивную систему, в которой нельзя доказать некоторые определенные формулы (ни одну из них).

Другое важное свойство, я бы даже сказал "модное",- это полнота. Многие слышали о теореме Геделя, хотя мало кто видел ее доказательство и помнит точную формулировку. Тем не менее, словосочетание "теорема Геделя о неполноте" на слуху и служит универсальным аргументом для разного рода болтунов.

[полнота (сильная)]: Полной называют дедуктивную систему, в которой всякую формулу можно доказать или опровергнуть.

[полнота (слабая)]: Полной называют дедуктивную систему, в которой можно доказать формулы определенного класса (все из них).

Как видите, приведено два различных варианта "полноты". На самом деле их еще больше - просто здесь нет смысла составлять полный список. Соответственно, и "неполнота" тоже бывает разная.

На этом мы завершим изложение общих принципов дедуктивных систем.