Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






В) Принцип полноты






Полнота в исчислении предикатов рассматривается в двух аспектах:

Полнота в узком смысле;

2) полнота в широком смысле.

Дадим определение полноты в узком смысле:

Логическая система называется полной в узком смысле, если присоединение к ее системе аксиом какой-либо невыводимой формулы превращает систему в противоречивую.

Аксиоматическое исчисление высказываний полно в узком смысле, но этого нельзя сказать об исчислении предикатов.

Если присоединить к системе аксиом S5 формулу, недоказуемую в ней, но выполнимую, то противоречия мы не получим.

Для примера можно взять следующую формулу:

$х Р(х) É " х Р(х) (І).

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

Как известно, в логических аксиомах исчисления предикатов ничего не говорится о природе и количестве объектов, образующих предметную область М. А, значит, из общих логических положений нельзя сделать вывод, что область М содержит более одного элемента. Но в области М, состоящей из одного элемента, формула (І) является истинной, как и все остальные аксиомы и доказуемые формулы. Поэтому противоречие в подобной системе возникнуть не может. В то же время из истинности (І) вытекает невозможность существования в области М более чем одного элемента, что в логике предикатов недоказуемо. Поэтому формула (І) не выводима из аксиом исчисления предикатов.

Однако можно построить и достаточно строгое доказательство того, что формула (І) не выводима формально из аксиом исчисления предикатов. Для этого возьмем предметную область М, состоящую из двух элементов (скажем, а и в). Поставим в соответствие каждой формуле исчисления предикатов формулу А*, в которой операция связывания квантором заменяется следующим образом:

" х А(х) заменяется на А(а) & А(в),

$х А(х) заменяется на А(а) Ú А(в).

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

Покажем, что для каждой выводимой формулы А в исчислении предикатов соответствующая ей формула А* является выводимой в исчислении высказываний.

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

Рассмотрим аксиому 12:

" х F(x) É F(y).

Заменим антецедент конъюнкцией:

F(a) & F(в) É F(y).

Данная формула правильная, так как является выводимой формулой логики высказываний при замене переменной у константами а и в.

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

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

Возьмем для примера правило связывания консеквента квантором общности.

Предположим, что формула А É В(х), где А не содержит переменной х, является выводимой, а соответствующая ей формула является правильной формулой исчисления предикатов. Последняя имеет вид:

А* É В*(х) (ІІ)

где А* и В* - формулы соответствующие А и В.

Так как формула (ІІ) по предположению правильная, то формулы:

А* É В*(а) и А* É В*(в) – тожеправильные.

Но тогда следует признать правильной и формулу:

А* É В*(а) & В*(в),

а она является формулой, которая соответствует формуле:

А É " х В(х).

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

Рассмотрим теперь формулу, соответствующую формуле (І):

Р(а) Ú Р(в) É Р(а) & Р(в) (ІІІ)

Поскольку формула (І) не содержит свободных переменных, то формула (ІІІ), если она правильная, должна быть выводимой формулой исчисления высказываний. Однако легко убедиться в том, что (ІІІ) не является выводимой. В самом деле, для предиката Р, для которого Р(а) имеет значение «и», а P(в) - значение «л», формула (ІІІ) перейдет в «и» Ú «л» É «и» & «л», то есть примет значение «л». Отсюда вытекает невыводимость формулы (І) в исчислении предикатов, что и следовало доказать.

Известно, что любая доказуемая формула исчисления предикатов является тождественно истинной (общезначимой). Отсюда возникает вопрос: будет ли любая тождественно истинная формула доказуемой в исчислении предикатов?

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

Примем во внимание еще одно обстоятельство технического характера – соотношение дедуктивнрой эквивалентности[25]1 и тождественной истинности формул. Из дедуктивной эевивалентности вытекает такая зависимость:


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал