ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.03.2019
Просмотров: 730
Скачиваний: 10
Практика
Исчисление высказываний
Исчисление высказываний это новая логическая система, которая адекватна алгебре высказываний, но здесь мы не будем рассматривать закон исключения третьего. Сами законы нас будут интересовать только в смысле выводимости. Т.е. мы будем себе ставить задачу обосновать тот или иной закон, показав, что пользование им не приведет к противоречию.
Символы исчисления высказываний состоят из знаков трех категорий.
1. Большие латинские буквы . Эти символы мы будем называть переменными высказываниями.
2. Логические связки: & знак конъюнкции (или логического умножения); дизъюнкции (или логического сложения); импликации (или логического следования) и знак отрицания.
3. Скобки: ( ).
В исчислении высказываний определение формулы представляет собой следующую рекурсию:
-
Переменное высказывание есть формула.
-
Если и формулы, то слова , , и также формулы.
Переменные высказывания называются также элементарными формулами.
Пример 1. Доказать, что слово есть формула.
Решение. Т.к. А и В – формулы (элементарные), то формула; С и D – формулы, то формула. Следовательно выражение является формулой.
Определение части формулы представляет собой следующую рекурсию:
-
Частью каждой элементарной формулы является только она сама.
-
Если определены все части формул и , то частями формулы ( ) будут все части формул и и сама формула. Аналогично определяются части формул , и .
Пример 2. Выписать все части формулы примера 1.
Решение. Согласно определению, частями рассматриваемой формулы являются формулы: A, B, C, D, , , .
В исчислении высказываний можно выделить некоторый класс формул, которые мы будем называть выводимыми в исчислении высказываний.
Правила, позволяющие из имеющихся выводимых формул получать новые, мы будем называть правилами вывода, а исходные выводимые формулы – аксиомами.
АКСИОМЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
I
-
.
-
.
II
-
.
-
.
-
.
III
-
.
-
.
-
.
IV
-
.
-
.
-
.
Операция подстановки формулы в формулу при заданной букве А ( ) определяется следующим образом:
где А и В – переменные высказывания.
Операция подстановки обладает следующими свойствами.
-
есть формула ;
-
есть формула ;
-
есть формула ;
-
есть формула .
ПРАВИЛА ВЫВОДА
1. Правило подстановки. Если выводимая формула, то также выводимая формула, каковы бы ни были переменное высказывание А и формула :
.
2. Правило заключения. Если и выводимые формулы исчисления высказываний, то также выводимая формула:
.
Пример 3. Доказать, что формула выводима в исчислении высказываний.
Решение. Рассмотрим A.I.2: . В ней по правилу подстановки заменим С на А: . Так как посылка полученной импликации есть A.I.1, то, применив правило заключения, получим:
,
т.е. выводимая формула в исчислении высказываний.
Выводом в исчислении высказываний называется конечная последовательность такая, что для каждого i ( ) есть либо аксиома, либо непосредственное следствие предыдущих формул, полученных применением правила заключения.
Пример 4. Какая последовательность формул примера 3 является выводом формулы в исчислении высказываний?
Решение. Выводом формулы является последовательность формул: { }, т.к. обе эти формулы являются аксиомами, а формула получена применением правила заключения.
Некоторые дополнительные правила исчисления высказываний
|
Правило силлогизма |
|
Правило перестановки посылок |
|
Правило соединения посылок |
|
Правило разъединения посылок |
; ;
Теоремы о выводимости формул исчисления высказываний
Т.1. .
Т.2. .
Т.3. .
Т.4. .
Т.5. .
Т.6. , (a)
(b)
Т.7. .
Т.8. .
Определение выводимости формулы из формул , называемых исходными:
-
каждая формула выводима из формул;
-
каждая выводимая в исчислении высказываний формула выводима из ;
-
если формулы и выводимы из , то формула также выводима из .
Утверждение, что формула выводима из , мы будем обозначать так:
. (1)
Если n=0, т.е. когда формул вовсе нет, мы будем считать, что является просто выводимой формулой исчисления высказываний. Выражение (1) в этом случае, естественно, превращается в
.
Пример 5. Выписать из списка { } те формулы, которые выводимы из следующей последовательности формул { } .
Решение. Во-первых, если следовать определению по порядку, то это формулы: , т.к. они присутствуют в последовательности формул .
Во-вторых, мы видим, что среди формул списка имеется аксиома III.1, т.е. выводимая в исчислении высказываний формула, следовательно (по второму пункту определения) она тоже выводима из формул .
В-третьих, формула выводима из формул , т.к. среди них присутствуют формулы А и (пункт 3 определения). По той же причине выводима С (если рассматривать формулы А и ).
Таким образом, окончательно получим, что из последовательности формул можно вывести формулы .
Теорема дедукции. Если формула , то выводимая формула.
Пример 6. Доказать, что .
Решение. Рассмотрим формулы , и . Из этих формул при помощи правила заключения можно вывести формулу С:
.
Тогда по теореме дедукции, окончательно получаем:
.
Для сокращения записи, формулу, имеющую вид , мы будем сокращенно записывать в виде ~ и называть эквивалентностью.
Будем говорить, что формулы a и b эквивалентны, если имеет место
~b.
Основные свойства соотношения эквивалентности:
-
Если эквивалентно , то и эквивалентно (симметричность).
-
Если эквивалентно и эквивалентно , то эквивалентно .
Теореме эквивалентности. Если в формуле заменить какую-нибудь ее часть эквивалентной формулой , то вновь полученная формула будет эквивалентна прежней, именно:
.
Теоремы о выводимости формул исчисления высказываний
Т.9. .
Т.10. .
Т.11. .
Т.12. .
Т.13. .
Т.14. .
Т.15. .
Задания
1. Доказать, что приведенные ниже выражения есть формулы исчисления высказываний. Выписать все части этих формул.
а) ;
б) ;
в) .
2. Являются ли выводами в исчислении высказываний следующие последовательности формул:
а) ;
б) , , ;
в) , , B?
3. Вывести в исчислении высказываний формулы:
а) ;
б) ;
в) ;
г) ;
д) .
4. Выводами из каких множеств формул Г являются следующие последовательности формул:
а) ;
б) ?
5. Доказать, что имеют место следующие выводимости:
а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) .
6. Доказать, что в исчислении высказываний:
а) ;
б) ;
в) ;
г) ;
д) .
7. Доказать, что следующие формулы выводимы в исчислении высказываний:
а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) ;
з) ;
и) ;
к) ;
л) ;
м) ;
н) ;
о) ;
п) ;
р) ;
с) ;
т) ;
у) .