Теоремы, устанавливающие связь между алгеброй высказываний и исчислением высказываний

Решение

Определим все подформулы формулы .

– подформулы первой глубины,

– подформулы второй глубины,

– подформулы третьей глубины,

– подформулы четвертой глубины.

Определим значения для всех подформул:

, , ,

, ,

, ,

,

,

.

Теорема 1. Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной в алгебре высказываний.

Доказательство этой теоремы основано на трех доказуемых положениях:

1. Каждая аксиома исчисления высказываний – тождественно истинная формула в алгебре высказываний.

Данное положение легко доказывается с помощью таблиц истинности или равносильных преобразований. Например, аксиома II₃ может быть подвергнута следующим равносильным преобразованиям:

то есть является тождественно истинной формулой.

Таким же образом или с помощью таблиц истинности можно доказать тождественную истинность и всех остальных аксиом исчисления высказываний.

2. Правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

Это значит, что если – тождественно истинная формула, – переменная, а – любая формула исчисления высказываний, то подстановка – тождественно истинная формула.

3. Правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

Это значит, что если и – тождественно истинные формулы, то и формула – также тождественно истинная формула.

Теорема 2. (О выводимости). Пусть – некоторая формула исчисления высказываний; – набор переменных, содержащий все переменные, входящие в формулу ; – произвольный фиксированный набор значений этих переменных. Тогда

а) если , то ├ ,

б) если , то ├ ,

где

Теорема 3. Каждая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний.

Это значит, что если – тождественно истинная формула в алгебре высказываний; – набор переменных, содержащий все переменные, входящие в формулу ; – произвольный фиксированный набор значений этих переменных, то

├ .

где

Дата добавления: 2017-02-01