Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Глава 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].
Теорема о полноте. Всякая тавтология является теоремой исчисления высказываний.
Следствие. Множество всех теорем исчисления высказываний совпадает с множеством всех тавтологий.
Теорема дедукции позволяет строить выводы многих формул в исчислении высказываний.
В Содержание.
|