Шпоры по МЛТА / 1-13.doc

1. Исчисление высказываний. Формулы. Теорема о единственности представления формулы ИВ в виде конъюнкции, дизъюнкции, отрицания или импликации других высказываний.

Алфавит ИВ содержит следующие символы:

1)   пропозициональные переменные  — они обозначают элементарные высказывания — это “кирпичики”, из которых будут формироваться другие, более сложные высказывания;

2)   логические связки:

3)   служебные символы: “(“, “)”, “,” (левая скобка, правая скобка, запятая);

4)   символ

Формула ИВ (высказывание) определяется индуктивно по следующей схеме:

1)   атомарные формулы (простейшие) — это пропозициональные переменные;

2)   если  и  — формулы, то     — формулы.

Итак, формулами ИВ называются только те слова, записанные в алфавите ИВ, которые получаются по вышеприведённой схеме. Например, если  — пропозициональные переменные, то    — формулы, а     — не формулы.

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

Лемма 1. Если  и  — формулы и  — начало  то  Доказательство проведём индукцией по длине формулы  т.е. по количеству символов, входящих в  Если длина равна 1, то  — атомарная формула, тогда  тоже атомарная; очевидно, что  Если  не атомарна, то  начинается либо с  либо с  Пусть  начинается с символа  Тогда  где  — формула. Так как  — начало  то  также начинается с  поэтому  где  — формула. Очевидно,  — начало  Значит, по предположению индукции  Отсюда следует, что  Наконец, разберём случай, когда  начинается с левой скобки. Тогда  где  — один из символов  а  и  — формулы. Так как  — начало  то  также начинается с левой скобки, а значит,  где  а  и  — формулы. Так как  — начало  то либо  — начало  либо  — начало  В обоих случаях по предположению индукции получаем  Но тогда  и  Отсюда следует, что

Теорема 1. Всякая неатомарная формула  единственным образом представима в одном из следующих видов:    где  и  — формулы. Доказательство. Существование такого представления следует из определения формулы. Надо лишь доказать единственность. Понятно, что если  представима в виде  то её нельзя представить в виде  и надо лишь применить предположение индукции к формуле  Пусть  представима в виде  неоднозначно. Тогда  Одна из формул  является началом другой. Значит, по лемме 1  Но тогда  и  Это доказывает единственность.

Следствие. Пусть  — формула ИВ. Тогда с каждым вхождением символа или символа в эту формулу однозначно связывается вхождение в  подформулы, начинающейся с этого символа. Доказательство. Действительно, если в  есть символ  то при построении формулы  ранее была построена формула  начинающаяся с этого символа, причём  — тоже формула. Формула  как раз и является подформулой, начинающейся с данного вхождения символа  Единственность следует из леммы 1. Аналогично разбираются случаи вхождения в  символа (.

Теорема 2. Пусть — формула, а  и  — вхождения в  каких-либо подформул. Тогда либо  и  не пересекаются, либо одно из них является подсловом другого. Доказательство. Пусть  и  пересекаются. Тогда либо первый символ из  входит в  либо наоборот . Пусть, например, первый символ из  входит в  Если  атомарно, то  — подслово слова  если  начинается с  то по следствию из теоремы 1 в  есть подформула  начинающаяся с этого символа. По лемме 1  совпадает с  Тогда  — подслово слова  Аналогично разбирается случай, когда  начинается с (

2. Правила вывода. Секвенции. Доказательства.

Секвенциями мы будем называть записи (последовательности значков) одного из следующих видов:

(1)   (2) (3) (4)

Здесь  — формулы ИВ, знакчитается “выводится”. Секвенция (1) расшифровывается так: из формул  выводится формула Секвенция (2) означает, что совокупность формул  противоречива. Секвенция (3) означает, что формула  выводима.

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

Правила вывода (здесь  — какие-либо последовательности формул, возможно, пустые):

1.		7.
2.		8.
3.		9.
4.		10.
5.		11.
6.		12.

Аксиомами ИВ называются секвенции вида  где  — формула (не обязательно атомарная).

Доказательством  называется последовательность секвенций

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

Пример. Докажем, что  Имеем:

Здесь  — аксиома;  получена из  по правилу 12;  — аксиома;  получается из  по 12;

 — из  по 11 (считаем  — из  и  с помощью правила 1.

Лемма 2. Если секвенция  доказуема (доказуема = выводима = существует для нее доказательство), то секвенция  также доказуема.

Доказательство. Из  по прав.7 получаем:  Из аксиомы  по правилам 11, 12 (применённым, возможно, несколько раз) получаем:  Затем из  и  по правилу 8 получаем:

Допустимые правила вывода.

(а)
(б)
(в)		(з)
(г)		(и)
(д)		(к)
(е)		(л)
(ж)		(м)

Докажем некоторые из этих правил:

(а) Доказательство этого правила получается применением правил 11 и 12.

(в)

Здесь (1) и (2) даны, (3) получается из (2) по правилу 7, а (4) — из (1) и (3) по правилу 8.

Заметим, что из (в) следует

(надо лишь в секвенции дописать слева формулы из

(г) Докажем это правило в упрощённом виде: когда

(1)		(аксиома);
(2)		(из (1) по 2);
(3)		(из (1) по 3);
(4)		(из (3) по 12);
(5)		(дано);
(6)		(из (5) по 11, 12);
(7)		(из (4) и (6) по (в));
(8)		(из (2) и (7) по (в)).

 (д)

(1)		(дано);
(2)		(из (1) по 2);
(3)		(из (1) по 3);
(4)		(из (2) и (3) по 10).

 (ж) Для доказательства этого правила докажем лемму.

Лемма 3.

Доказательство. С помощью аксиом  и  по правилам 11, 12 нетрудно получить, что  и  Отсюда по правилу 10 получаем:

Вернёмся к доказательству правила (ж). Нам надо доказать, что если секвенция  имеет доказательство, то также имеет доказательство (оба доказательства должны основываться на правилах 1 — 12). Заметим, что получить секвенцию  можно только по правилу 10. Значит, ранее были доказаны секвенции  и  для некоторой формулы  Пропуская предыдущие шаги доказательства, будем иметь:

(1)
(2)
(3)		(из (1) по 12);
(4)		(из (3) по 11);
(5)		(из (4) по 7);
(6)		(по лемме 3);
(7)		(из (6) по 9);
(8)		(из (5) и (7) по 8);
(9) — (13)	шаги, аналогичные шагам (3) — (7), где вместо (1) взято (2);
(14)		(аналогично (8));
(15)		(из (8) и (14) по10);
(16)		(из (15) по 9).

 (б) Докажем один частный случай правила (б), а именно,

(1)		(дано);
(2)		(из (1) по (ж));
(3)		(из (2) по 11, 12);
(4)		(аксиома);
(5)		(из (4) по 12);
(6)		(из (3) и (5) по 10).

Важная секвенция (1). Для любой формулы доказуема секвенция

(1)		(аксиома);
(2)		(из (1) по 5);
(3)		(аксиома);
(4)		(из (2) по 12);
(5)		(из (3) по 11,12);
(6)		(из (4),(5) по 10);
(7)		(из (6) по 9, 11);
(8)		(из (7) по 4);
(9)		(из (3) и (8) по 10);
(10)		(из (9) по 9).

Важная секвенция (2). Для любой формулы  доказуема секвенция

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

(1)		(аксиома);
(2)		(из (1) по 2);
(3)		(из (1) по 3);
(4)		(из (2) и (3) по 10).

3. Эквивалентные формулы. Приведение формулы к нормальному виду.

Две формулы  и  называются эквивалентными (обозначается:  если доказуемы секвенции  и Символ  не принадлежит языку исчисления высказываний. Он принадлежит метаязыку, т.е. языку, на котором мы описываем исчисление высказываний.

 Утверждение 1. Отношение  является отношением эквивалентности.

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

Лемма 1 (о замене). Если  и  то    

Доказательство. Докажем утверждение о конъюнкции:

(1)		(дано);
(2)		(дано);
(3)		(дано);
(4)		(дано);
(5)		(аксиома);
(6)		(из (5) по 3)
(7)		(из (5) по 3);
(8)		(из (6) и (1) по );
(9)		(из (7) и (3) по );
(10)		(из (8) и (9) по 1).