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

2. Т. в теории L : А│₋ В→А. Док-во:

1) А – гипотеза по условию .

2) из (1) и аксиомы (Ⅱ.1) по правилу MP получим выводимость В→А при гипотенузе А.

Полученную выводимость можно вместе с правилом подстановки рассматривать как новое произв. Правило вывода – правило введения импликации:α⁄β→α для β.

1.Теорема дедукции: Если Г,α│⁻β, то Г│₋α→β, и наоборот.

2.следствие из т. Дедукции – правило силлогизма: А→В, В→С, │₋ А→С( в теории L).

Док-во: построим вывод из этих гипотез:

1. А→В- гипотеза по условию,

2. В→С – гипотеза по условию

3. А- гипотеза

4. Из (3) и (1) по правилу МР получим: А, А→В │₋В

5. Применим МР для (4) и (2): В, В→С │₋С

6. Из (1),(3) и (5) имеем :А→В, В→С, А │₋С

7. Из (6) по теореме дедукции: А→В, В→С │₋А→С.

3. Правило введения отрицания (метод док-ва от противного): Если Г,А│₋В и Г,А│₋ , то Г|-

1) по т. Дедукции, если Г,А │₋В и Г,А│₋ , то Г│₋А→В и Г│→А→

2)из (1) и (Ⅰ.9) двойным применением МП получим Г│₋ .

6. Определение предиката. Свободные и связанные переменные.

Определение. Предикат – это функция , которая может принимать значения «Истина» (И) или «Ложь» (Л) , а могут принимать значение из некоторой области M.

Пр. “x – четное число” –унарный предикат (одноместный), “x/y – четное число” – бинарный (двухместный)

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

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

В предикате переменная х называется свободной, в высказываниях х называется связанной.

7. Основные равносильности (законы) логики предикатов.

Основные равносильности:

1. Перестановка кванторов (одноименных)

квантор всеобщности

квантор существования

Однако разноименные кванторы переставлять нельзя, пример:

1)

2)

Пусть на мн-ве M=N*N.

Тогда 1е высказывание означает, что какое бы натуральное число мы не взяли, всегда найдется натуральное число еще больше этого. Это высказывание истинно.

2е высказывание означает, что существует самое большое натуральное число. Оно ложно на М.

2. Переименование связанных переменных

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

8. Основные правила вывода исчисления предикатов.

Правила вывода

1) «не разобрал слово» как в ИВ

2) Правило обобщения: то

3) Правило введения квантора существования: C(x) – содержит свободные вхождения х, F- не содержит.

9. Производные правила вывода в исчислении предикатов: правила переименования связанных переменных, правило связывания квантором.

Правило переименования связанных переменных

1. 

2. 

F(x) не содержит свободных вхождений y,но содержит свободные вхождения х, ни одно из которых не входит в область действия квантора по у.

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

1. – гипотеза

2. По аксиоме (Р1) справедлива формула

3. К шагу 2 применим правило обобщения

4. MP для (1) и (3):

Для квантора существования доказать самостоятельно!

Правило связывания кванторов.

_K

1. F(x) – гипотеза по условию

2. По т.2 ИВ _L , то есть формула доказуема для любого В, в том числе и для доказуемов формуле В. Значит _K

3. По правилу обощения , B не содержит свободных вхождений х.

4. Из (3) по правилу заключения МР (для В и ) следует доказуемость _K .