Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
В) Принцип полноты
|
|
Полнота в исчислении предикатов рассматривается в двух аспектах:
Полнота в узком смысле;
2) полнота в широком смысле.
Дадим определение полноты в узком смысле:
Логическая система называется полной в узком смысле, если присоединение к ее системе аксиом какой-либо невыводимой формулы превращает систему в противоречивую.
Аксиоматическое исчисление высказываний полно в узком смысле, но этого нельзя сказать об исчислении предикатов.
Если присоединить к системе аксиом S5 формулу, недоказуемую в ней, но выполнимую, то противоречия мы не получим.
Для примера можно взять следующую формулу:
$х Р(х) É " х Р(х) (І).
На первый взгляд может показаться странным, что такую, явно неверную формулу можно без возникновения противоречия присоединить к аксиомам исчислеия предикатов. Но обратимся к содержательному смыслу данной формулы.
Как известно, в логических аксиомах исчисления предикатов ничего не говорится о природе и количестве объектов, образующих предметную область М. А, значит, из общих логических положений нельзя сделать вывод, что область М содержит более одного элемента. Но в области М, состоящей из одного элемента, формула (І) является истинной, как и все остальные аксиомы и доказуемые формулы. Поэтому противоречие в подобной системе возникнуть не может. В то же время из истинности (І) вытекает невозможность существования в области М более чем одного элемента, что в логике предикатов недоказуемо. Поэтому формула (І) не выводима из аксиом исчисления предикатов.
Однако можно построить и достаточно строгое доказательство того, что формула (І) не выводима формально из аксиом исчисления предикатов. Для этого возьмем предметную область М, состоящую из двух элементов (скажем, а и в). Поставим в соответствие каждой формуле исчисления предикатов формулу А*, в которой операция связывания квантором заменяется следующим образом:
" х А(х) заменяется на А(а) & А(в),
$х А(х) заменяется на А(а) Ú А(в).
Формулу исчисления предикатов, не содержащую кванторов, называют правильной, если при любых заменах свободных переменных константами а и в она остается выводимой формулой исчисления высказываний.
Покажем, что для каждой выводимой формулы А в исчислении предикатов соответствующая ей формула А* является выводимой в исчислении высказываний.
Для аксиом 1-11 это проверяется непосредственно. Они не содержат ни предметных переменных, ни кванторов, поэтому соответствующими им формулами будут они сами, то есть выводимые формулы исчисления высказываний.
Рассмотрим аксиому 12:
" х F(x) É F(y).
Заменим антецедент конъюнкцией:
F(a) & F(в) É F(y).
Данная формула правильная, так как является выводимой формулой логики высказываний при замене переменной у константами а и в.
Аналогичным образом можно убедиться в том, что и аксиоме 13 ставится в соответствие правильная формула.
Теперь покажем, что правила получения выводимых формул исчисления предикатов для соответствующих формул без кванторов можно рассматривать как правила, с помощью которых из правильных формул исчисления высказываний полуаются правильные формулы исчисления предикатов.
Возьмем для примера правило связывания консеквента квантором общности.
Предположим, что формула А É В(х), где А не содержит переменной х, является выводимой, а соответствующая ей формула является правильной формулой исчисления предикатов. Последняя имеет вид:
А* É В*(х) (ІІ)
где А* и В* - формулы соответствующие А и В.
Так как формула (ІІ) по предположению правильная, то формулы:
А* É В*(а) и А* É В*(в) – тожеправильные.
Но тогда следует признать правильной и формулу:
А* É В*(а) & В*(в),
а она является формулой, которая соответствует формуле:
А É " х В(х).
Если првести проверку всех правил исчисления предикатов, то легко заметить, что каждой выводимой формуле исчисления предикатов соответствует правильная формула.
Рассмотрим теперь формулу, соответствующую формуле (І):
Р(а) Ú Р(в) É Р(а) & Р(в) (ІІІ)
Поскольку формула (І) не содержит свободных переменных, то формула (ІІІ), если она правильная, должна быть выводимой формулой исчисления высказываний. Однако легко убедиться в том, что (ІІІ) не является выводимой. В самом деле, для предиката Р, для которого Р(а) имеет значение «и», а P(в) - значение «л», формула (ІІІ) перейдет в «и» Ú «л» É «и» & «л», то есть примет значение «л». Отсюда вытекает невыводимость формулы (І) в исчислении предикатов, что и следовало доказать.
Известно, что любая доказуемая формула исчисления предикатов является тождественно истинной (общезначимой). Отсюда возникает вопрос: будет ли любая тождественно истинная формула доказуемой в исчислении предикатов?
Ответ на данный вопрос связан с постановкой проблемы полноты в широком смысле. При решении данной проблемы исчисления предикатов нельзя ограничиться средствами рассуждения финитной логики. Дело в том, что в саму постановку проблемы входит понятие тождественно истинной (общезначимой) формулы, предполагающеерассмотрение всех возможных интерпретаций.
Примем во внимание еще одно обстоятельство технического характера – соотношение дедуктивнрой эквивалентности[25]1 и тождественной истинности формул. Из дедуктивной эевивалентности вытекает такая зависимость: