[ЛиТА] РК3 Вопросы и ответы

Определения:

Формальная аксиоматическая теория ; V – алфавит, F – множество формул, A – аксиом, P – правил вывода, . Алфавит V может быть бесконечным, но не более чем счётным. Элементы Р: , где . Фи – посылки, Пси – заключение.Вывод в теории Т – конечная или бесконечная последовательность формул , где , где Г – фиксированное множество формул (гипотез).

• Высказывание – повествовательное выражение, которое может быть охарактеризовано как истина или ложь. Формула над теорией : Любая логическая переменная есть формула; Если – формулы, то – тоже формулы. Других формул нет.

В теории ИП алфавит состоит из Х – предметных переменных; С – предметных констант; F – функциональных символов; P – предикатных символов; логических символов ; вспомогательных символов Aux. Терм: всякая переменная или константа, ; если t1..tn – термы, а – терм; других термов нет.Атомарная формула: выражение вида . Формула: всякая атомарная формула; если формулы, то также формулы; если xi предметная переменная и Ф – формула, то – формула; других нет.

Интерпретация . Каждый функциональный и предикатный символ привязывается к какой-то операции или предикату.

Определить исчисление высказываний, доказать его непротиворечивость.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

Исчисление высказывания – теория .

Теорема: Каждая теорема теории Л есть тавтология.

Доказательство: Можно показать, что любая формула, полученная из схемы аксиом, является тавтологией. Любую формулу можно вывести из аксиом с использования правила MP. Покажем, что из двух тавтологий после примения МР получится тавтология.

Пусть – тавтологии, и существует набор Тогда, . Однако, Получаем что – противоречие. Следовательно, МР по двум тавтологиям даёт тавтологию.

Следствие из теормы: теория L непротиворечива, т.е. в ней недоказуема . Т.к. эта конъюнкция всегда =Л, то она не может являться теоремой.

Доказать теорему дедукции.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

Теорема: Если из множества гипотез , то

Доказательство: Докажем методом математической индукции по L – длине вывода В из Г,А.

Базис: l=0, т.е. возможны три случая:

1) . Тогда строим вывод из Г без А:

2) B – аксиома. Тогда

3) B=A. Тогда

Предположение: Пусть утверждение теоремы справедливо, те. Если

Переход: пусть теперь l=m, т.е. В получается в выводе из Г,А применением МП к формулам Ф, Ф->В. Причем, , где l1,l2 Продолжаем вывод из Г:

Таким образом, , ч.т.д.

Сформулировать теорему Кальмара (в доказательстве теоремы полноты); доказать полноту ИВ.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

Теорема: Если Ф=Ф(х1…хn), то имеет место секвенция .

Теорема: Теория L полна, т.е. любая тавтология доказуема в этой теории.



Доказательство: Пусть формула Ф – тавтология, По лемме Кальмара, из литералов . Компоненты можно изменять: возьмём . По следствию из теоремы о девяти секвенциях, т.к. Ф выводится из , n-ю гипотезу можно отбросить, Из оставшихся литералов аналогичным образом убираем остальные гипотезы,в конце концов получаем что т.е. Ф – теорема.

Доказать свойства дизъюнкции (следствие из теоремы о 9 секвенциях).

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

Теорема:

Доказательство: Докажем 1)

Докажем 2)

Докажем 3). А-В, поэтому А->В – теорема

Доказать свойства конъюнкции.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

Теорема: 1)

Доказательство: Докажем 1)

Докажем 2) , по правилу контрапозиции

А&BB доказывается по аналогии.

Докажем 3) по правилу контрапозиции

. Ч.т.д.

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

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

• Состояние , где А – область интерпретации, Х – множество переменных.теорема. а ым образом убираем остальные ях, т.к. Ф выводится из Ф выполнима в интерпретации I, если для некоторого состояния .Ф истинна в I, если для всякого состояния Ф логически общезначима, если она истинна в любой интерпретации.

Схемы аксиом и правила вывода в ИП. Доказать логическую общезначимость формулы, полученной из схемы аксиом 4 в ИП.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

• Схемы аксиом:

Докажем логическую общезначимость (4), приведя контрпример: , где . t несвободен для х1 в А: имеем Пусть область интерпретации содержит два неравных элемента, а р2 – равенство, рефлексивное отношение. В таком случае, . Имеем И->Л, следовательно, t должен быть ограничен.Зафиксируем некоторую интерпретацию В, в котрой должно выполняться Следовательно, – т.к. структура свободных и связанных вхождений н изменится; может изменяться только значение xi при данном ограничении на терм.

Доказать, что ограничения на термы и переменные в схемах 4 и 5 существенны, приведя соответствующие контрпримеры.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

. Докажем логическую общезначимость, приведя контрпример: , где . t несвободен для х1 в А: имеем Пусть область интерпретации содержит два неравных элемента, а р2 – равенство, рефлексивное отношение. В таком случае, . Имеем И->Л, следовательно, t должен быть ограничен.Зафиксируем некоторую интерпретацию В, в котрой должно выполняться Следовательно, – т.к. структура свободных и связанных вхождений н изменится; может изменяться только значение xi при данном ограничении на терм.

при . Контрпример: Пусть – атомарная формула . Тогда, , т.е. – противоречие, следовательно ограничение существенно.

Метод резолюций для ИВ и ИП.

~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~

фыв.




Предыдущий:

Следующий: