Автор: Исчисление высказываний ИВ – это аксиоматическая логическая система гильбертовского типа, адекватная алгебре высказываний. Опишем это исчисление. В качестве алфавита исчисления высказываний возьмем следующее множество символов: 1) счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них; 2) символы логических операций; 3) скобки ( , ). Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами. Множество формул обычно задается индуктивным определением. Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения определяют элементарные формулы, а п. 3 – механизм образования новых формул.
-
Лекция 3 исчисление высказываний
-
Правила вывода исчисления высказываний
-
Исчисление высказываний
-
Правило образование форм исчисление высказываний
-
Исчисление высказываний ив.
-
Исчисление высказываний как формальная система
-
Исчисление высказываний ив
-
Математический форум math help planet
Лекция 3 исчисление высказываний
Это множество формул называется схемой формулы U и обозначается выражением, полученным заменой в формуле U всех входящих в нее высказывательных переменных метасимволами . Например, из формулы возникает схема формул . (5) Этой схеме принадлежит формула . Новые схемы формул можно получить заменой ее метасимволов схемами формул.
Эти схемы выделяют некоторое подмножество формул из множества формул, принадлежащих исходной схеме. Например, из схемы (5) можно получить схему формул . (6) Формула принадлежит как схеме формул (5), так и (6). Для формул, являющимися аксиомами или теоремами, схемы формул называются соответственно схемами аксиом или схемами теорем.
Правила вывода исчисления высказываний
- 1)
Внимание
B1 = A - 2) B2 = — аксиома 1
- 3) B3 = B = — получено из B1 и B2 в силу правила заключения.
Заметим, что если посылки являются аксиомами или теоремами исчисления высказываний, то класс выводимых из них формул совпадает с классом всех истинных формул, выводимых из любой системы посылок. Выводимость формулы из системы посылок отличается от доказательства теоремы в исчислении высказываний тем, что здесь допускается использование только правила заключения. Но при выводе формулы разрешается использовать любую теорему исчисления высказываний, для получения которой может применяться правило подстановки.
Из каждой формулы U с помощью правила подстановки, производящего замену высказывательных переменных в этой формуле любыми формулами, может быть получено бесконечное множество формул.
Исчисление высказываний
Так как доказательство большинства правил непосредственно следует из определения выводимости и аксиом ИВ, то приведём только их формулировки, доказав лишь ключевое правило 5 – в форме теоремы дедукции. 1. Правило повторения посылки. T,|- 2. Правило введения посылки. ЕслиT |-, тоT,|-. 3. Правило удаления посылки. Если T,|-и T |-, то T |-.
4.
Если |- B, то |-. Доказательство. Пусть (1) есть вывод формулы B из. Индукцией по t докажем вспомогательное утверждение |-. (4) 10. Пусть. Тогда по определению выводимой формулыявляется либо посылкой, либо теоремой.
Правило образование форм исчисление высказываний
Важно
Отсюда и из (8) по правилу силлогизма 4 следует утверждение теоремы. 6. Правило удаления импликации. ЕслиT |-, тоT,|-. 7. Правило введения конъюнкции. T,|-. 8. Правило удаления конъюнкции. T,|-, T,|-. 9.
Правило введения дизъюнкции. T,|-, T,|-. 10. Правило удаления дизъюнкции. Если T,|-и T,|-, то T,|-. 11. Правило введения отрицания. Если T,|-и T,|-, то T |-. 12. Правило удаления отрицания.
T,|- 13. Правило контрапозиции. Если T,|-, то T,|-. Правила 1-13 называют обычно правилами естественного вывода, а вывод формулы из системы посылок, при котором используются эти правила, — естественным выводом. Рассмотрим примеры вывода формул с использованием правил естественного вывода.
Исчисление высказываний ив.
Всюду далее, строя вывод формулы, будем рядом с каждой формулой последовательности указывать применяемое правило (его номер), а затем, в круглых скобках, номера формул исходных посылок, к которым применялось данное правило. Задание 3. Доказать выводимость следующих формул: 1) |-; 2) |-. Решение. Покажем вначале справедливость формулы 1). 1.
A |- 2. B |- 3.|- 13 (1) 4.|- 13 (2) 5.,|- 6.|- 4 (3, 4, 5) 7. |- 5 (6) Построим теперь вывод формулы 2). Предыдущая45678910111213141516171819Следующая Дата добавления: 2016-06-13; просмотров: 956; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ ПОСМОТРЕТЬ ЕЩЕ: Поделитесь с друзьями: ПОИСК ПО САЙТУ: Поиск по сайту: При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию. Поделитесь с друзьями: Если вам понравился данный ресурс вы можете рассказать о нем друзьям.
Сделать это можно через соц.
Исчисление высказываний как формальная система
В качестве алфавита исчисления высказываний возьмем следующее множество символов: 1) счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них; 2) символы логических операций ; 3) скобки ( , ). Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами. Множество формул обычно задается индуктивным определением.
Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения (см. методические указания “Алгебра высказываний. Булевы функции”) определяют элементарные формулы, а п. Приведем и другие, эквивалентные данной, системы аксиом. I. Операции: (аксиоматика С. Клини (1952)). 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. II.
Исчисление высказываний ив
Следует заметить, что в исчислении высказываний не разрешается опускать скобки для операций с большим приоритетом, что допустимо в алгебре высказываний. Так, например, формула алгебры высказываний не является формулой исчисления высказываний, ее следует записать, как , в дальнейшем изложении мы будем опускать лишь внешние скобки. Следующим шагом в описании исчисления высказываний будет выделение класса формул, которые будем называть истинными или доказуемыми в исчислении высказываний.
Это определение имеет такой же рекуррентный характер, как и определение формулы. Сначала определим исходные истинные формулы, называемые аксиомами. В качестве системы аксиом примем следующие формулы (аксиоматика П.С. Новикова).
Инфо
Из каждой формулы U с помощью правила подстановки, производящего замену высказывательных переменных в этой формуле любыми формулами, может быть получено бесконечное множество формул. Это множество формул называется схемой формулы U и обозначается выражением, полученным заменой в формуле U всех входящих в нее высказывательных переменныхметасимволами. Например, из формулы возникает схема формул . (5) Этой схеме принадлежит формула .
Новые схемы формул можно получить заменой ее метасимволов схемами формул. Эти схемы выделяют некоторое подмножество формул из множества формул, принадлежащих исходной схеме. Например, из схемы (5) можно получить схему формул . (6) Формулапринадлежит как схеме формул (5), так и (6). Для формул, являющимися аксиомами или теоремами, схемы формул называются соответственно схемами аксиом или схемами теорем. Схемами аксиом являются: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Математический форум math help planet
III. Операции:(аксиоматика Д.Гильберта и Аккермана (1938)). 1. 2. 3. 4. IV. Операции: ®, Ø (аксиоматика Лукасевича). 1. 2. 3. Приведём примеры доказательства теорем в ИВ. Задание 1. Показать, что формулы: 1) 2) истинны в исчислении высказываний ИВ. Решение. I) 1. Формула является результатом подстановки в аксиому 2 высказывательной переменной A вместо C. 2.– аксиома 1 3. Применяя правило заключения к формулам 1 и 2, получим, что истинная формула. II) 1. В соответствии с правилом подстановки, заменив все вхождения переменной A в аксиоме 5 на формулу, получим . 2.– аксиома 4 3. Применяя правило заключения к формулам 1 и 2, получим, что является истинной формулой. 4. Заменим в этой формуле высказывательную переменную C на A . 5.– аксиома 3 6. Снова воспользовавшись правилом заключения к формулам 4, 5 получим требуемую формулу . Рассмотрим пример вывода формулы. Задание 2. Доказать, что A |-.
