Практика

Исчисление высказываний

---

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

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

1. Большие латинские буквы . Эти символы мы будем называть переменными высказываниями.

2. Логические связки: &  знак конъюнкции (или логического умножения);  дизъюнкции (или логического сложения);  импликации (или логического следования) и  знак отрицания.

3. Скобки: ( ).

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

1. Переменное высказывание есть формула.

2. Если и  формулы, то слова , , и  также формулы.

Переменные высказывания называются также элементарными формулами.

Пример 1. Доказать, что слово есть формула.

Решение. Т.к. А и В – формулы (элементарные), то  формула; С и D – формулы, то   формула. Следовательно выражение является формулой.

Определение части формулы представляет собой следующую рекурсию:

1. Частью каждой элементарной формулы является только она сама.

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

Пример 2. Выписать все части формулы примера 1.

Решение. Согласно определению, частями рассматриваемой формулы являются формулы: A, B, C, D, , , .

В исчислении высказываний можно выделить некоторый класс формул, которые мы будем называть выводимыми в исчислении высказываний.

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

АКСИОМЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

I

1. .

2. .

II

1. .

2. .

3. .

III

1. .

2. .

3. .

IV

1. .

2. .

3. .

Операция подстановки формулы  в формулу  при заданной букве А ( ) определяется следующим образом:

где А и В – переменные высказывания.

Операция подстановки обладает следующими свойствами.

1. есть формула ;

2. есть формула ;

3. есть формула ;

4. есть формула .

ПРАВИЛА ВЫВОДА

1. Правило подстановки. Если  выводимая формула, то  также выводимая формула, каковы бы ни были переменное высказывание А и формула :

.

2. Правило заключения. Если и  выводимые формулы исчисления высказываний, то   также выводимая формула:

.

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

Решение. Рассмотрим A.I.2: . В ней по правилу подстановки заменим С на А: . Так как посылка полученной импликации есть A.I.1, то, применив правило заключения, получим:

,

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

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

---

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

Решение. Выводом формулы является последовательность формул: { }, т.к. обе эти формулы являются аксиомами, а формула получена применением правила заключения.

Некоторые дополнительные правила исчисления высказываний

	Правило силлогизма
	Правило перестановки посылок
	Правило соединения посылок
	Правило разъединения посылок

; ;

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

Т.1. .

Т.2. .

Т.3. .

Т.4. .

Т.5. .

Т.6. , (a)

(b)

Т.7. .

Т.8. .

Определение выводимости формулы из формул , называемых исходными:

1. каждая формула выводима из формул;

2. каждая выводимая в исчислении высказываний формула выводима из ;

3. если формулы и выводимы из , то формула также выводима из .

Утверждение, что формула выводима из , мы будем обозначать так:

. (1)

Если n=0, т.е. когда формул вовсе нет, мы будем считать, что является просто выводимой формулой исчисления высказываний. Выражение (1) в этом случае, естественно, превращается в

.

Пример 5. Выписать из списка { } те формулы, которые выводимы из следующей последовательности формул { } .

Решение. Во-первых, если следовать определению по порядку, то это формулы: , т.к. они присутствуют в последовательности формул .

Во-вторых, мы видим, что среди формул списка имеется аксиома III.1, т.е. выводимая в исчислении высказываний формула, следовательно (по второму пункту определения) она тоже выводима из формул .

В-третьих, формула выводима из формул , т.к. среди них присутствуют формулы А и (пункт 3 определения). По той же причине выводима С (если рассматривать формулы А и ).

Таким образом, окончательно получим, что из последовательности формул можно вывести формулы .

Теорема дедукции. Если формула , то  выводимая формула.

Пример 6. Доказать, что .

Решение. Рассмотрим формулы , и . Из этих формул при помощи правила заключения можно вывести формулу С:



.

Тогда по теореме дедукции, окончательно получаем:

.

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

Будем говорить, что формулы a и b эквивалентны, если имеет место

~b.

Основные свойства соотношения эквивалентности:

1. Если  эквивалентно , то и  эквивалентно  (симметричность).

2. Если  эквивалентно  и  эквивалентно , то  эквивалентно .

Теореме эквивалентности. Если в формуле  заменить какую-нибудь ее часть эквивалентной формулой , то вновь полученная формула будет эквивалентна прежней, именно:

 .

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

Т.9. .

Т.10. .

Т.11. .

Т.12. .

Т.13. .

Т.14. .

Т.15. .

---

Задания

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

а) ;

б) ;

в) .

2. Являются ли выводами в исчислении высказываний следующие последовательности формул:

а) ;

б) , , ;

в) , , B?

3. Вывести в исчислении высказываний формулы:

а) ;

б) ;

в) ;

г) ;

д) .

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

а) ;

б) ?

5. Доказать, что имеют место следующие выводимости:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

6. Доказать, что в исчислении высказываний:

а) ;

б) ;

в) ;

г) ;

д) .

7. Доказать, что следующие формулы выводимы в исчислении высказываний:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и) ;

к) ;

л) ;

м) ;

н) ;

о) ;

п) ;

р) ;

с) ;

т) ;

у) .

---

Смотрите также файлы

• история билеты(все).docx

• Текст 10000 символов (транспорт Британии).docx

• Курсовой проект.Производство сварных конструкций.Метод STT.docx

• Ekzamen_po_anatomii_otvety.doc

• Все лекции по хирургии.doc