Спирина, М.С. Дискретная математика

Заметим, что символы или - , обозначающие отрицание, эквивалентны, но использование черты позволяет компактно и более понятно описать отрицание сложных выражений, а уголок позволяет правильно оценить длину полученного слова. Напри­ мер, В —> С —> D и б —>—,((—!С7) -э D) — суть одно и то же слово, состоящее из 11 букв, где связка -> есть импликация. В исчисле­ нии высказываний множество аксиом теории Т и множество пра­ вил вывода бесконечны, так как зависят от бесконечного числа различных высказываний-переменных, хотя задаются соответствен­ но тремя и одним правилом. Пусть А,, А2, ..., А„, В — составные высказывания. Говорят, что высказывание б является логическим следствием высказываний А,, А2, ..., А„, если при всех значениях элементарных высказываний, при которых все А,, Аъ А„ истинны (в любой интерпретации), будет истинным и высказывание б. Символическая запись логиче­ ского следования б из А,, А2, ..., А„ имеет вид Ах, А2, ..., А„ =* В и читается так: «Если (выполнены) Аи Аъ ..., А„, то (выполнено) б». Два утверждения ^ и б называются логически эквивалентными, если А => б и б => А. Сформулируем некоторые теоремы, доказываемые в исчисле­ нии высказываний: 1 . | - А - > А . 2. А |— В -> А — введение импликации. 3. Ф, А \— б <=>Ф |—Д -> б — теорема дедукции. 4. А \— б <=> [—Д -> б — следствие из теоремы дедукции (при Ф = 0 ) . 5 . / 4 - >б , б -» С |— А С — правило транзитивности. 6. А -> (б -» С), б \—А -» С — правило сечения. 7 Ш\ - А - > А . 7 ' . \ - А -> А. 8. | - А_-> (А-> В). 9; |-_(Я -± А) -» (А -> б ) . 9'. (б -э Л) (А -> б ) — противопоставление обратному. Кроме правила тр должно быть такое правило, которое по­ зволило бы обращаться со сложными высказываниями, как с про­ стыми. Ранее было показано, как это удобно, когда сложные бу­ левы формулы назывались одной пропозиционной переменной, что позволяло производить операции над столбцами для нахожде­ ния таблицы значений булевой функции. Например, ( f l - > i ) v r = = у v х, где (а -э Ь) = у. Можно показать, что такое правило — правило подстановки — является производным от основных правилом вывода и логически мотивировано. Правило выводов обычно включает в себя два правила, доста­ точных для проведения формальных умозаключений. 220