Математическая логика
Исчисление высказываний ИВ
жүктеу/скачать 0.93 Mb.
|
| 1. Исчисление высказываний ИВ
Всякую математическую теорему можно записать в виде импликации, выделив условие и заключение. При доказательстве теоремы из ее условия по определенным правилам получают заключение, при этом говорят, что заключение является логическим следствием условия или что оно выводимо из условия. Алгебра высказываний дает точное определение понятия выводимости. Однако чтобы непосредственно применять алгебру высказываний к высказываниям математики, нужно предположить, что для каждого высказывания выполняется закон исключенного третьего. Поэтому возникла необходимость в построении математической логики, как формально-аксиоматической (синтаксической) теории, которая ставит себе, в частности, задачу обосновать этот закон, доказав, что использование его не приводит к противоречию. Такой аксиоматической теорией, адекватной алгебре высказываний, является исчисление высказываний. Исчисление высказываний – это аксиоматическая логическая система, адекватная алгебре высказываний. Опишем это исчисление. В качестве алфавита исчисления высказываний возьмем следующее множество символов: счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них; символы логических операций ; скобки ( , ). Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами. Множество формул обычно задается индуктивным определением. Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения определяют элементарные формулы, а п. 3 – механизм образования новых формул. Следует заметить, что в исчислении высказываний не разрешается опускать скобки для операций с большим приоритетом, что допустимо в алгебре высказываний. Так, например, формула алгебры высказываний не является формулой исчисления высказываний, ее следует записать, как , в дальнейшем изложении мы будем опускать лишь внешние скобки. Следующим шагом в описании исчисления высказываний будет выделение класса формул, которые будем называть истинными или доказуемыми в исчислении высказываний. Это определение имеет такой же рекуррентный характер, как и определение формулы. Сначала определим исходные истинные формулы, называемые аксиомами. В качестве системы аксиом примем следующие формулы (аксиоматика П.С.Новикова). После этого определим правила, позволяющие из истинных формул образовывать новые. Эти правила, мы будем называть правилами вывода. Образование истинной формулы из исходных истинных формул или аксиом путем применения правил вывода будем называть выводом данной формулы из аксиом. Определим правила вывода, которые являются отношениями на множестве формул. Правило подстановки. Пусть U – формула, содержащая высказывательную переменную A. Тогда если U – истинная формула в исчислении высказываний, то, заменяя в ней переменную A всюду, куда она входит, произвольной формулой B, мы также получим истинную формулу. Правило заключения (modus ponens). Если U и UB истинные формулы в исчислении высказываний, то B также истинная формула. В виде схемы правило заключения запишется как . Задание 1. Показать, что формулы: ; истинны в исчислении высказываний. Решение. 1) Формула является результатом подстановки в аксиому 2 высказывательной переменной A вместо C. Так как посылка полученного следования есть аксиома 1, то, применяя правило заключения, получим, что истинная формула. 2) В соответствии с правилом подстановки, заменив все вхождения переменной A в аксиоме 5 на формулу , получим . Так как посылка этой аксиомы является аксиомой 4, то по правилу заключения формула является истинной формулой. Заменим в этой формуле высказывательную переменную C на A . Снова воспользовавшись правилом заключения, что возможно, так как посылка истинной формулы является аксиомой 3, получим требуемую формулу . Замечание. Рассмотренная нами аксиоматика не является единственно возможной. Приведем и другие, эквивалентные данной, системы аксиом. I. Операции: (аксиоматика С.Клини (1952)). II. Операции: (аксиоматика Россера (1953)). III. Операции: (аксиоматика Д.Гильберта и Аккермана (1938)). IV. Операции: , (аксиоматика Лукасевича). Рассмотрим пример вывода формулы. Задание 2. Доказать, что A . Решение. Для данного примера система посылок содержит 1 формулу U1=A, а выводимая формула B = . Построим вывод этой формулы. жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|