- •Синтаксис метамови у системі s1 представлений правилами утворення. Правила утворення включають в себе: алфавіт і визначення правильно побудованої фомули.
- •І отримуємо 3 рядок аналітичної таблиці:
- •1) Формалізувати всі засновки міркування і його висновок;
- •2) Поєднати засновки міркування за допомогою логічного сполучника “” (конюнкція), а висновок приєднати за допомогою - “” (імплікації).
- •3) Створену формулу перевірити за допомогою таблиць істинності, чи логічно слідує із кон’юнкції засновків міркування висловлювання, яке відповідає висновку міркування.
- •1) За допомогою відповідних законів послідовно звільнитися від сильної диз’юнкції “” , еквіваленції “”, імплікації “” , якщо вони є у вихідній формулі ;
- •2) За допомогою законів де Моргана позбавитися загального заперечення;
- •3) До отриманої формули застосувати «закон дистрибутивності кон'юнкції по відношенню до диз'юнкції».
- •Спочатку приведемо її до днф, тобто позбавимося імплікації відповідно до «закону виключення імплікації» а в а в:
- •1) Виписати одну із аксіом;
- •2) Послідовно застосувати правило підстановки (п/п) і правило відділення (мр)
- •1. P q - припущення 1
- •4. P (q r) - припущення 2
- •Доведіть вивідність формул:
- •A є змінною квантора, який входить до цієї формули;
- •A знаходиться в області дії квантора який входить до цієї формули.
1) Виписати одну із аксіом;
2) Послідовно застосувати правило підстановки (п/п) і правило відділення (мр)
3) доведення є закінченим, якщо останнім виразом у послідовності формул буде формула F.
Розглянемо структуру доведення на прикладі доказу теореми:
р р.
Доведення.
Спочатку обираємо із запропонованого списку аксіом аксіому консеквент якої нагадує формулу, яку необхідно довести. У нашому випадку це
аксіома 1: А (В А). Замість символів метамови (А і В) підставляємо пропозиційні змінні об’єкт-мови і отримуємо таку формулу:
1. р (q p) - Ах.1
Оскільки у формулі, яку необхідно довести немає пропозиційної змінної q, нам необхідно застосувати правило підстановки і замість q підставимо p p :
2. p ((p p) p) - q/p p за п/п до 1
Далі застосуємо аксіому 2: (А (В С) ((А В) (А С)) антецедент, якої нагадує формулу 2 рядка. Здійснюємо підстановку пропозиційних змінних об’єкт-мови замість символів метамови отримуємо формулу:
3. (р (q r)) (( p q) (p r)) - Ax. 2
Очевидно, що вихідна фомула немає у своєму складі пропозиційних змінних q і r, отже необхідно знову застосувати правило підстановки, тобто замість q підставити q/p p, а замість r підставити р:
4. (p ((p p) p)) ((p (p p)) (p p) - q/p p, r/p за п/п до 3
Якщо порівняти 2 і 4 рядки нашого доведення, то можна помітити, що антецедент формули 4 рядка (виділений) і формула 2 рядка співпадають. Отже, це дає нам право застосувати правило відділення (МР):
5. (p (p p)) (р р) - за МР, до 2, 4
Консеквент (виділений)отриманої формули відповідає формулі, яку необхідно довести. Тобто, далі необхідно обрати таку аксіому, яка допоможе застосувати правило відділення, щоб отримати формулу p p. Такою аксіомою
є аксіома 1: А (В А):
6. p (q p) - Ax 1
Застосуємо правило підстановки і замість q підставимо р:
7. p (p р) - q/p за п/п до 6
І врешті-решт використовуємо правило відділення (МР) і отримуємо формулу, яку потрібно було довести:
8. р р - за МР до 7, 5
Наведене доведення називається доведенням із аксіом. Але існує ще доведення із деякого кінцевого числа довільних формул, які називаються припущеннями або гіпотезами.
Те, що формула В доказується із гіпотез А1, …, Аn записується так:
А1, …, Аn B.
Наприклад, побудуємо доведення формули r із гіпотез p q, p (q r).
p q, p (q r) r
Спочатку виписуємо перше припущення:
1. P q - припущення 1
Потім із списку аксіом обираємо необхідну нам аксіому. У нашому випадку застосуємо аксіому 3: (А В) А, оскільки антецедент цієї аксіоми нагадує формулу першого припущення. Замінюємо символи метамови на пропозиційні змінні об’єкт-мови:
2. (p q) p - аксіома 3
Очевидно, що формула припущення першого рядка і антецедент (виділений) формули другого рядка співпадають. Отже, ми можемо до них застосувати правило відділення (МР) :
3. p - МР до 1 і 2
Далі виписуємо друге припущення: