Глава 3. Исчисление высказываний.
Исчисление высказываний (теория L) определяется следующими компонентами.
1. Алфавит составляют:
· Пропозициональные буквы (от англ. proposition – высказывание) – заглавные буквы латинского алфавита (иногда с индексами – натуральными числами): , , , , ,…
· Логические связки: .
· Скобки: (, ).
Иногда в исчислении высказываний допускаются формулы с другими логическими связками, но при этом учитывается, как они выражаются через инверсию и импликацию. Так, , . Такие записи являются удобными сокращениями.
2. Формулыопределяются так же, как в главе 1.
Определение.1) Всякая пропозициональная буква есть формула.
2) Если , – формулы, то формулами являются также , .
3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).
3. Аксиомы задаются тремя схемами аксиом:
А1. .
А2. .
А3. .
Существуют исчисления высказываний с другим набором логических связок и другими схемами аксиом, но в данном пособии они не рассматриваются. Желающие могут ознакомиться с ними в [12].
4. Правило вывода Modus ponens (сокращенно MP) – правило отделения (лат.).
├ .
Здесь , – любые формулы. Таким образом, множество аксиом исчисления высказываний, заданное тремя схемами аксиом, бесконечно. Множество правил вывода задано одной схемой, и также бесконечно.
Теорема.Все теоремы исчисления высказываний – тавтологии.
Доказательство. Докажем сначала, что аксиомы А1 – А3 являются тавтологиями.
Предположим, что
Полученное противоречие доказывает, что аксиома А1 – тавтология.
Предположим, что
Полученное противоречие доказывает, что аксиома А2 – тавтология.
Предположим, что
Полученное противоречие доказывает, что аксиома А3 – тавтология.
Таким образом, все аксиомы исчисления высказываний представляют собой тавтологии. Теоремы выводятся по правилу вывода MP, следовательно, по ранее полученным результатам (см. Глава 1. Высказывания, формулы, тавтологии.), также являются тавтологиями, что и требовалось доказать.
Следствие.Исчисление высказываний непротиворечиво.
Доказательство.Предположим противное, то есть в исчислении есть теоремы и . По доказанной теореме, и являются тавтологиями (тождественно истинными формулами), следовательно, формула одновременно является тождественно истинной и тождественно ложной, что является противоречием.
Лемма. ├ .
Доказательство. Построим вывод формулы .
1. . А1 с подстановкой вместо – .
2. . А1 с подстановкой вместо – .
3.
А2 с подстановкой вместо – , а вместо – .
4. . МР 2,3.
5. . МР 1,4.
Что и требовалось доказать.
Теорема дедукции.Пусть – множество формул, , – формулы. Тогда , ├ ├ .
В частности, если , то если ├ ├ .
Доказательство. Пусть , , …, , – вывод из и . Методом математической индукции докажем, что ├ , .
1) Проверим, что утверждение ├ справедливо при , то есть ├ .
Для возможны три варианта: , – аксиома, .
а) Пусть или – аксиома. Построим вывод:
1. .
2. . А1 с подстановкой вместо – , вместо – .
3. . МР 1, 2.
Таким образом, ├ .
б) Пусть . По лемме, ├ . Таким образом, ├ .
2) Пусть утверждение ├ верно при , . Докажем утверждение для , то есть ├ .
Для формулы есть следующие возможности: , – аксиома, , которые рассматриваются аналогично предыдущему пункту, и новая возможность: получается из предыдущих формул , , …, , по правилу Modus ponens. Последний случай рассмотрим подробно.
Среди формул , , …, есть формулы (может быть, и не одна) вида , , такие, что имеет место формула (которая также присутствует в выводе), поэтому и возможно применение правила Modus ponens.
По предположению индукции, ├ , ├ .
Построим вывод:
1. .
2. .
3. . А2 с подстановкой вместо – , вместо – .
4. . МР 2, 3.
5. .
Таким образом, доказано, что ├ , следовательно, по методу математической индукции, ├ , то есть ├ . Теорема доказана.
Справедлива и обратная теорема.
Теорема. ├ , ├ .
Доказательство.Построим вывод:
1. .
2. .
3. . По условию теоремы, эта формула выводима из .
4. . МР 2, 3.
Теорема доказана.
На основании теоремы дедукции получена теорема о полноте исчисления высказываний. Доказательство этой теоремы довольно громоздко, поэтому желающие могут ознакомиться с ним в [12].
Теорема о полноте.Всякая тавтология является теоремой исчисления высказываний.
Следствие. Множество всех теорем исчисления высказываний совпадает с множеством всех тавтологий.
Теорема дедукции позволяет строить выводы многих формул в исчислении высказываний.
В Содержание.
Дата добавления: 2022-02-05; просмотров: 324;