ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Система аксиом исчисления высказываний

Лабораторная работа № 4

ПРИЛОЖЕНИЯ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

К ТЕОРИИ ДОКАЗАТЕЛЬСТВ

СОДЕРЖАНИЕ ЗАНЯТИЯ

Вступительная часть

Исчисление высказываний – это одна из аксиоматических логических систем, интерпретацией которой является алгебра высказываний. Эта теория строится без использования понятий истинности и ложности, без применения законов логики высказываний. Исчисление высказываний строится по общим правилам построения формальных аксиоматических систем.

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

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

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

На занятии рекомендуется решить задачи №№1.1.1.1 – 1.1.1.8, 1.1.2.4, 1.2.2, 1.2.4, 1.3.1.1, 1.3.1.4, 1.3.2.1, 1.3.2.2, 2.1.1, 2.1.4, 2.2.

Вопросы для проверки готовности студентов к занятию

1. Сформулировать основные принципы построения формальной теории (исчисления).

2. Из чего состоит алфавит исчисления высказываний?

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

4. Дать определение подформулы данной формулы.

5. Записать систему аксиом исчисления высказываний. Что такое схема аксиом?

6. Сформулировать основные правила вывода исчисления высказываний (правило заключения и правило подстановки).

7. Дать определение выводимой формулы, теоремы.

8. Что такое производные правила вывода. Сформулировать несколько таких правил.

9. Понятие вывода из совокупности формул – это определение или теорема?

10. Сформулировать теорему дедукции.

11. Какими теоремами выражается связь между алгеброй высказываний и исчислением высказываний?

1. Доказуемость формул

1.1. Определение формулы и подформулы исчисления высказываний

Определение формулы:

1. Всякая переменная x, y, z,… является формулой.

2. Если А и В – формулы, то формулами являются и следующие комбинации символов: (A&B), .

3. Никакая другая комбинация символов формулой не является.

Определение подформулы:

1. Подформулой переменного высказывания x, y, … является только эта переменная.

2. Если формула имеет вид , то ее подформулами являются она сама, формула А и все подформулы формулы А.

3. Если формула имеет один из видов то ее подформулами являются она сама, формулы А и В и все подформулы формул А и В.

Задача 1.1.1. Какие из следующих выражений являются формулами исчисления высказываний:

1.1.1.1.

1.1.1.2.

1.1.1.3.

1.1.1.4.

1.1.1.5.

1.1.1.6.

1.1.1.7.

1.1.1.8.

Ответ: выражения 1.1.1.2, 1.1.1.5 и 1.1.1.8 формулами не являются.

Задача 1.1.2. Выписать все подформулы формул:

1.1.2.1.

1.1.2.2. ;

1.1.2.3. ;

1.1.2.4. ;

1.1.2.5. ;

1.1.2.6.

Выпишем, например, все подформулы формулы 1.1.2.4: , x&y, x₁y; подформулой не является, поскольку операция слабее операции &).

1.2. Система аксиом и основные правила вывода исчисления высказываний

Система аксиом исчисления высказываний

Первая группа аксиом:

I₁.

I₂.

Вторая группа аксиом:

II₁.

II₂. ;

II₃.

Третья группа аксиом:

III₁. ;

III₂. ;

III₃.

Четвертая группа аксиом:

IV₁. ;

IV₂. ;

IV₃.

Правило заключения (modus ponens):

или

на языке доказуемых формул.

Правило подстановки:

Определение доказуемой формулы:

1. Каждая аксиома является доказуемой формулой.

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

3. Никакая другая формула исчисления высказываний доказуемой не является.

Установление доказуемости той или иной формулы исчисления высказываний часто требует использования обобщения правила заключения – правила сложного заключения:

Это правило мы тоже будем относить к основным, поскольку оно легко получается последовательным применением правила заключения. Действительно, так как ├А₁ и ├ то доказуемой будет и формула ; из │ и │ следует │ и так далее. На последнем шаге ввиду конечности формул А₁, А₂, …, A_n, получим │ │ и, следовательно │

Задача 1.2. Установить доказуемость формул:

1.2.1. ; 1.2.2.

1.2.3. ;

1.2.4.

1.2.5.

Решение 1.2.1. В аксиоме III₁ осуществим подстановку вместо x , вместо y – C.

Решение 1.2.2. К доказуемости приводит постановка в аксиому I₂ вместо x, y, z соответственно формул

Решение 1.2.3. В аксиоме III₃ сделаем подстановку вместо x, y, z формулы А. Получим доказуемую формулу

Как было доказано на лекции №3, Поэтому, применяя правило сложного заключения, получим

Решение 1.2.4. В аксиоме II₃ осуществим подстановку вместо x, y, z соответственно B, A, Получим Снова применяя правило сложного заключения, получим доказуемость формулы 1.2.4.

Решение 1.2.5. В аксиоме III₃ следует осуществить подстановку вместо x, y, z соответственно A, B, , и воспользоваться правилом сложного заключения.

1.3. Производные правила вывода

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

Задача 1.3.1. Доказать следующие производные правила вывода:

1.3.1.1.Правило силлогизма.

1.3.1.2.

1.3.1.3.

1.3.1.4.

1.3.1.5.

1.3.1.6. ;

Решение 1.3.1.1. В аксиоме I₁ сделаем подстановку вместо x, y соответственно формул и А, а в аксиоме I₂ вместо x, y, z подставим формулы А, В и С соответственно. Получим доказуемые формулы:

(1)

(2)

Так как по условию доказуемы формулы и . По правилу заключения из формулы (1) получаем

, (3)

а из формул (2), (3) и получаем по правилу сложного заключения .

Решение 1.3.1.2. По условию | а из аксиомы II₁ имеем | Применим к последней формуле правило контрапозиции:

а по правилу заключения и из условия получаем окончательно |

Решение 1.3.1.3. Используем аксиому II₁:

Так как по условию , то по правилу заключения получим .

Решение 1.3.1.4. По условию │ , │ Тогда легко показать │ и затем | . Остается применить правило заключения.

Решение 1.3.1.5. Элементарно.

Указание к решению 1.3.1.6. Воспользоваться доказуемой формулой

Задача 1.3.2. Используя производные правила вывода показать, что доказуемы следующие формулы:

1.3.2.1.

1.3.2.2.

1.3.2.3. .

Решение 1.3.2.1. В аксиоме III₃ вместо x, y, z подставим соответственно Получим (1)

Из аксиом II₁ и II₂ получим:

(2)

. (3)

К (2) и (3) применим правило контрапозиции:

(4)

. (5)

Из (1), (4), (5) по правилу сложного заключения получаем доказуемость формулы 1.3.2.1.

Решение 1.3.2.2. В аксиоме I₂ сделаем подстановку вместо x, y, z соответственно :

(1)

В аксиоме II₂ сделаем подстановку вместо x, y соответственно и :

(2)

(3)

где (3) – правило контрапозиции.

В аксиоме II₁ сделаем подстановку вместо x, y соответственно и :

. (4)

Из (3) и (4) получим

(5)

Из (1), (2), (5) по правилу сложного заключения получим |

Решение 1.3.2.3. В аксиоме III₃ сделаем подстановку, заменяя в ней z на :

или

. (1)

Из аксиом II₁ и II₂ имеем :

Используя правило контрапозиции к (2) и (3) получим:

(4)

(5).

Используя правило снятия двойного отрицания, получим:

, (6)

(7).

Применяя к формулам (1), (6) и (7) правило сложного заключения, получим (8).

Применяя к формуле (8) правило контрапозиции, а затем правило снятия двойного отрицания, получим последовательно:

, что и требовалось.

2. Построение выводов

Выводом формулы В из совокупности формул Г={А₁, А₂, …, А_n} называется последовательность формул F₁, F₂,…, F_m такая, что F_m=B, а любая из формул F₁, F₂,…, F_m является либо аксиомой, либо одной из исходных формул А₁, А₂, …, А_n, либо непосредственно выводима из формул, предшествующих ей в последовательности F₁, F₂,…, F_m по правилам вывода.

Если существует вывод формулы В из совокупности формул Г, то говорят, что формула В выводима из Г и записывают Г или А₁, А₂, …, А_n . Формулы

А₁, А₂, …, А_n называются гипотезами или посылками вывода.

Задача 2.1. Записать вывод для следующих формул:

2.1.1. Н= , Н ;

2.1.2. Г= Г ;

2.1.3. Г= Г ;

2.1.4. Н= , Н .

Решение 2.1.1. Запишем последовательность формул F₁, F₂,…, F_m, то есть вывод из Н:

(подстановка в аксиому II₃ вместо x, y, z соответственно А, В, А);

(как доказуемая формула); (по правилу заключения из F₃ и F₄; (подстановка в I₁ вместо x, y соответственно В и А); (по правилу заключения из F₂ и F₆); (по правилу заключения из F₅ и F₇); (по правилу заключения из F₁ и F₈).

Решение 2.1.2.

Решение 2.1.3.

Решение 2.1.4.

Задача 2.2. Доказать, что если Г= , то Г

Доказательство. По правилу силлогизма

Обозначим через Г₁ = . Тогда Г₁| По теореме дедукции, которая имеет вид , получим Г | .

Заключение

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

Использованная при подготовке к занятию литература

1. Лихтарников Л.М., Сукачева Т.Г. Математическая логика/Курс лекций.- СПб.: Изд-во «Лань», 1998, с. 204-213.

2. Лавров Н.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975, с. 64-74.