Определение доказуемой формулы.

а) Всякая аксиома является доказуемой формулой.

б) Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х произвольной формулы В есть доказуемая формула.

в) Формула В. полученная из доказуемых формул А и А ®В путем применения правила заключения, есть доказуемая формула.

г) Никакая другая формула исчисления высказываний не считается доказуемой.

Процесс получения доказуемых формул будем называть доказательством.

Приведем примеры доказательств.

1. Доказать, что A ® А (рефлективность импликации).

Воспользуемся аксиомой I2:

И выполним подстановку вместо переменной z формулы В=х Тоrда получим

(1)

Применяя правило заключения к аксиоме I1 и формуле (1). получим

. (2)

В формуле (2) осуществим подстановку вместо переменной y подставим

в результате получим доказуемую формулу

. (3)

Применим правило заключения к аксиоме IV 3 и формуле (3). Это приводит к доказуемой формуле x® х.

Наконец, осуществив подстановку в формуле (4) вместо х формулы А. получим A®A.

Докажите самостоятельно: