Глава 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; просмотров: 339;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.018 сек.