6. Выводимость формул f→ f и ⌐f → (f → f'). Теорема о дедукции и ее следствие.

Какова бы ни была формула D, формула D→D является теоремой:

Теорема дедукции:

Если Г - множество формул, А,В - фор-мулы и Г,А├ В, то Г ├ А⇒В. В частности, если А ├ В, то ├ А⇒В.

Доказательство. Пусть В₁,В₂,...,В_n есть вывод формулы В из Г∪{А}, где В_n=В. Индукцией по i (1 ≤ i ≤ n) докажем, что Г ├ А⇒В_i.

Пусть i=1. Покажем, что Г ├ А⇒В₁. Так как В₁ является первой из формул в выводе В из Г ∪ {A}, то имеем следующие возможности:

В₁ ∈Г,

В₁ - является аксиомой,

В₁=А.

По схеме аксиом А1 формула В₁⇒(А⇒ В₁) есть аксиома. Поэтому в пер-вых двух случаях (когда В₁ аксиома или формула из Г) по МР получим

Г ├ А⇒В₁.

В третьем случае, т.е. когда В₁ совпадает с А (В₁=А), по лемме 4.1 имеем

├ А⇒В₁,

следовательно, Г ├ А⇒В₁. Тем самым случай i=1 исчерпан.

Допустим теперь, что Г ├ А⇒В_k для любого k<i. Для В_i имеем четыре воз-можности:

В_i есть аксиома,

В_i ∈Г,

В_i =A,

В_i - следствие по МР из некоторых В_j и В_m, где j<i, m<i и B_m имеет вид B_j⇒B_i.

В первых трех случаях то, что Г ├ А⇒В_i доказывается так же, как для i=1. В последнем случае применим индуктивное предположение, согласно которо-му

1) Г ├ А⇒В_j,

2) Г ├ А⇒(В_j⇒B_i).

По схеме аксиом А2:

3) ├ (А⇒(В_j⇒B_i))⇒((A⇒B_j)⇒(A⇒B_i));

далее применяя правило MP, из 3) и 2) получим:

4) Г ├ (A⇒B_j)⇒(A⇒B_i);

снова по МР из 4) и 1) имеем:

Г ├ А⇒В_i.

Таким образом, доказательство по индукции завершено и для i=n получе-но требуемое утверждение. Теорема доказана.

Следствие 1: A⇒B, B⇒C ├ A⇒C.

Доказательство.

1) A⇒B - гипотеза,

2) B⇒C - гипотеза,

3) А - гипотеза,

4) В - по МР из 1) и 3),

5) С - по МР из 2) и 4).

Таким образом, A⇒B, B⇒C, A ├ C. Отсюда по теореме дедукции A⇒B,B⇒C ├ A⇒C. Что и требовалось доказать.

Следствие 2: A⇒(B⇒C),B ├ A⇒C.

Доказательство.

1) A⇒(B⇒C) - гипотеза,

2) А - гипотеза,

3) B⇒C - по МР из 1) и 2),

4) В - гипотеза,

5) С - по МР из 3) и 4).

Таким образом, A⇒(B⇒C),B,A ├ C, тогда по теореме дедукции A⇒(B⇒C),B ├ A⇒C. Что и требовалось доказать.

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

Теорема о корректности (исчисления высказываний):

Всякая теорема исчисления высказываний есть тавтология (тожд. Истинна)

Доказательство:

докажем от противного, что самая длинная аксиома является тавтологией:

Чтобы выражение было ложным, надо чтобы первое слагаемое было истинно, а второе ложно. Чтобы второе слагаемое было ложно, надо чтобы А→В было истинно, а А→С ложно. Значит по такому предположению А-истинно, С-ложно. Значит А. А→В и (А→(В→С)) истинны. Отсюда следует, что В и В→С истинны, а значит С — истинна. Противоречие. Значит формула не бывает ложной.

Теорема о полноте (исчисления высказываний):

Всякая тавтология есть теорема исчисления высказываний.

8. Непротиворечивость исчисления высказываний. Невозможность добавления в исчислении высказываний новых аксиом.

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

9. Независимость схем аксиом исчисления высказываний.

Независимость аксиом. Отдельная аксиома дедуктивной теории, в том числе и исчисления высказываний, является независимой, если эту аксиому нельзя вывести в этой теории из остальных аксиом. Система аксиом является независимой, если каждую из них нельзя вывести из остальных.

10. Предикаты. Множества истинности предикатов. Логические операции над предикатами. Навешивания кванторов на предикаты. Геометрический смысл квантора существования.

Предикатом называется повествовательное предложение об элементах некоторого заданного множества M, которое (предложение) становится высказыванием, если все переменные в нем заменить фиксированными элементами из M; высказывание тоже будем считать предикатом - нульместным предикатом. Часто вместо "предикат от n переменных " говорят "n-местный предикат".

Операции над предикатами

Предикаты, так же, как высказывания, принимают два значения истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Логические операции

Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката А(х) В(х), х Х является пересечение множеств истинности предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х – четное число», В(х): « х кратно 3». А(х) В(х) – «х – четное число и х кратно 3». Т.е. предикат «х делится на 6».

Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката А(х) В(х) является объединение областей истинности предикатов А(х) В(х).

Отрицанием предиката А(х) называется новый предикат , который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката , х Х является дополнение Т' к множеству Т в множестве Х.

Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката А(х) В(х) является объединение множества Т2 – истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).

Кванторы

Пусть M - множество, Р(х) - определенный на M одноместный предикат.

Тогда выражение ∀хР(х) читается: "для всех х Р(х)" или "для всех х выполняется Р(х)", или "для любого х Р(х)", или "для каждого х Р(х)". Под выражением "∀хР(х)" будем подразумевать высказывание истинное, когда Р(х) истинно для каждого х из M и ложное - в противном случае. Символ ∀х называется квантором всеобщности.

Выражение ∃хР(х) читается "существует х такое, что Р(х)" или "хотя бы для одного х Р(х)", или "для некоторого (некоторых) х Р(х)". Под выражением "∃хР(х)" будем подразумевать высказывание, которое истинно, если Р(х) принимает значение И хотя бы для одного значения переменной х∈ M, и ложно, если Р(х) для всех значений переменной х принимает значение Л. Символ ∃х называется квантором существования. Квантор ∃х будем называть двойственным к квантору ∀х, и наоборот.

11. Критерий полноты системы предикатов от одной переменной на конечном множестве.

12. Модели. Формулы в модели. Свободные и связанные переменнные. Значение формулы в модели. Интерпритации.

Множесто M называется моделью для множества формул Г, если существует интерпретация формул из Г в M, в которой все эти формулы истины.

Всякое вхождение буквы x в область действия квантора по x называется связанным вхождением буквы x. Буква x имеющая свободные вхождения в формулу b, называется свободной предметной переменной в формуле b. Если буква x имеет лишь связанные вхождения в формулу b, то x – связанная предметная переменная в формуле b.

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

13. Формулы, истинные в модели, на множестве. Тождественно истинные формулы. Формулы, эквивалентные модели, на множестве. Эквивалентные формулы.

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

Законы де Моргана:

1)  ;

2)  ;