4.3. Числення висловлень. Аксіоми і правила виводу

У численні висловлень ми знову зустрічаємося з об'єктами, з якими якось уже мали справу - з формулами алгебри логіки. Проте тут формули розглядаються не як спосіб представлення функцій, а як складові висловлення, утворені з елементарних висловлень (змінних) за допомогою логічних операцій  , ¯ , . Наприклад ХY. Остання операція читається: "якщо X, то Y". При цьому особлива увага приділяється тотожньо-істинним висловленням, оскільки, як уже відзначалося, вони повинні входити в будь-яку теорію як загальнологічні закони. Їхнє породження і є основною задачею числення висловлень. Числення висловлень визначається в такий спосіб.

Алфавіт числення висловлень складається зі змінних висловлень (пропозиційних букв): А, В, С, ... , знаків логічних зв'язків ,  , ¯ ,  і скобок ( , ).

Формули:

а) змінна висловлення є формула;

б) якщо 2τ і 2 - формули, то (2τ 2   і  2τ - формули;

в) інших формул немає.

Зовнішні скобки у формулах звичайно домовляються опускати: наприклад, замість (2τ   пишуть 2 Замість синтаксично більш зручного знака ┐ часто вживається риска над формулою.

Аксіоми. Наведемо тут дві системи аксіом. Перша з них безпосередньо використовує всі логічні зв'язки:

Система аксіом І.

І 1. A(BA);

І 2. (AB)  ((A (BC))  (AC));

І 3. (A&B) A;

Ι 4. (A&B) B;

І 5. A (B (A&B));

Ι 6. A (AB);

І 7. B (AB);

І 8. (AC)  ((BC)((AB) C));

І 9. (AB)((A┐B) A);

І 10. ┐┐AA.

Інша система використовує тільки дві зв'язки ┐ і  ; при цьому скорочується алфавіт числення ( викидаються знаки , &) і відповідно визначені формули. Операції , & розглядаються не як зв'язки числення висловлень, а як скорочення ( уживати які зручно, але не обов'язково ) для деяких його формул: АВ заміняємо ┐А В, А&У заміняємо ┐( А  ┐В). У результаті система аксіом стає набагато компактніше.

Система аксіом II.

ІI 1. A(BA);

II 2. (A(BC))((AB)(AC);

II 3. (AB)((AB)A).

Наведені системи аксіом рівносильні в тому сенсі, що породжують ту саму множину формул. Яка із систем краще? Це залежить від точки зору. Система II компактніше й більш наглядна; відповідно більш компактні і докази різноманітних їх властивостей. З іншого боку, у більш багатій системі I коротше виведення різноманітних формул.

Правила виведення:

1) правило підстановки. Якщо u - виведена формула, що містить букву А (позначимо цей факт u ( А ) ), то виведена формула u(β), що утворюється з u заміною усіх входжень А на довільну формулу,

u(A)

u : ;

u(β)

2) правило висновку (Modus Ponens). Якщо u і u  β виведені формули, то β виведена:

u, u  β

u: .

β

У цьому описі числення висловлень аксіоми є формулами числення (відповідному визначенню формули); формули ж, використані в правилах виведення (u, u  β і т.д.), - це ”метаформули“ або схеми формул. Так, схема формул, u  β позначає множину всіх тих формул числення, що утворюються, якщо її метазмінні замінити формулами числення: наприклад, якщо u замінити на А, а β - на A&B, то зі схеми формул u  β одержимо формулу А  A&B.