Жоден диз'юнкт не містить змінної і її заперечення.

Для того, щоб привести формулу до СДНФ необхідно виконати такі дії:

1) привести вихідну формулу до ДНФ;

2) співставити отриману ДНФ із ознаками СДНФ;

3) послідовно застосувати до отриманого виразу «закони виявлення» і «закони поглинання».

За допомогою СДНФ знаходять всі прості гіпотези довільної формули.

Наприклад, візьмемо формулу:

((A Ù B) Ú C) É C

Знайдемо всі її прості гіпотези, тобто приведемо її до СДНФ.

((A Ù B) Ú C) Ú C

((A Ù B) Ù`C) Ú C

((`A Ú`B) Ù`C) Ú C

(`А Ù`С) Ú (`В Ù`С) Ú С

Формула у останньому рядку є ДНФ вихідної формули. Співставляємо її з ознаками СДНФ. А потім приводимо її до СДНФ. Для цього спочатку застосовуємо «закон виявлення» (А Ù В) Ú (`А Ù С) º (А Ù В) Ú (`А Ù С) Ú (В Ù С) і отримуємо вираз :

(`А Ù`С) Ú (`В Ù`С) Ú С Ú`А Ú`В

Далі застосовуємо «закон поглинання»(А Ù В) Ú А º А:

(`А Ù`С) Ú (`В Ù`С) Ú С Ú`А Ú`В

Після застосування «закону поглинання» ми отримали таку формулу:

С Ú`А Ú`В

Тобто, вихідна формула має чотири прості гіпотези:

1. С;

2.`А;

3.`В;

4. С Ú`А Ú`В.

ТЕМА: ЧИСЛЕННЯ ЛОГІКИ ВИСЛОВЛЮВАНЬ

 

Лекція 6. Аксіоматичне числення логіки висловлювань (2 год.)

Загальна характеристика числення логіки висловлювань. Мова числення логіки висловлювань. Аксіоматичне числення логіки висловлювань. Мова аксіоматичного числення логіки висловлювань. Синтаксис системи S²: правила утворення та правила перетворення.

Алфавіт та дефініція формули у аксіоматичному численні. Характеристика правил перетворення: дефініція аксіоми, дефініція теореми, список аксіом Давида Гільберта, правила доведення із аксіом: правило відділення ("модус поненс") та правило підстановки, дефініція доведення, дефініція доказової формули.

Алгоритм доведення теореми із аксіом.

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

Семінарське заняття 6. (2 год.)

1. Визначення числення логіки висловлювань. Структура числення логіки висловлювань.

2. Характеристика синтаксису аксіоматичного числення логіки висловлювань:

а) правила утворення;

б) правила перетворення.

3. Побудова доведення у системі S² із аксіом.

4. Побудова доведення із припущень у аксіоматичному численні логіки висловлювань.

Контрольні запитання та вправи

1. У чому полягає різниця між афавітом системи S¹ та S²?

2. Чим характеризується формула у системі S²?

3. Що включають у себе правила перетворення мови аксіоматичного числення логіки висловлювань?

4. Що означає поняття «теорема» в аксіоматичному численні логіки висловлювань?

5. Як визначається поняття «аксіома» в системі S² ?

6. Як формулюється правило відділення в аксіоматичному численні логіки висловлювань?

7. Сформулюйте дефініцію доведення в системі S² .

8. Як будується доведення із аксіом в аксіоматичному численні логіки висловлювань?

9. Хто запропонував набір аксіом для доведення теорем у S²?

10. Як будується доведення із гіпотез в аксіоматичному численні логіки висловлювань?

11. Доведіть, що наведені формули є теоремами в аксіоматичному численні логіки висловлювань (з аксіомами):

• q É q;

• (p É q) É ((p Ú q) É q)

12. Побудуйте доведення із гіпотез:

• q Ù p, q É (p É r) |-`r

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 1: с.41-45; 2: с.113-121; 4: с. 343-350; 15: с. 184-193; 18: с. 47-64; 29: с. 72-87, 104-122; 44: с. 14-15; 121;165; 714; 45: с. 48-53, 101-108, 112-113, 142-143, 148-157.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(4 год.)

Конспект статей із словника

Філософський енциклопедичний словник. - К, 2002. - "Аксіома"; - "Гіпотеза";

- "Доведення"; - "Числення висловлювань".

-"Числення ";

Методичні вказівки

Вивчаючи дану тему студенти повинні засвоїти, що до синтаксису аксіоматичного числення логіки висловлювань (S²) входять окрім правил утворення правила перетворення.

Правила утворення характеризуються алфавітом та визначенням формули.

Алфавіт системи S² складається із тих самих символів, що і алфавіт системи S¹ (пропозиційних змінних, пропозиційних зв’язок). Але відмінність між алфавітами системи S¹ та системи S² полягає у тому, що у системі S² єдиним способом визначення пропозиційних змінних і пропозиційних зв’язок є способи поводження з ними у відповідності до правил висновку, тобто про табличне визначення пропозиційних зв’язок тут уже не йдеться.

Дефініція формули у системі S² така сама, як і у системі S¹. Різниця лише у тому, що фомула у системі S² характеризується не таблицями істинності, а ситуацією виводу. Тобто, тотожно-істинні формули (або тавтології) розподіляються на теореми і аксіоми.

 

Правила перетворення системи S² складаються із таких компонентів:

Дефініція аксіоми.

Дефініція теореми.

Список аксіом.

4) Правила доведення, які включають:

а) правило відділення, або правило “modus ponens” (МР);

б) правило підстановки (п/п).

Дефініція доведення.

6) Дефініція доведеної формули.

Список аксіом у системі S² повинен бути достатнім для доведення теорем у цій же системі. Як зразок візьмемо набір аксіом запропонований німецьким вченим Давидом Гільбертом:

1. А É (В É А)

2. (А É (В É С) É ((А É В) É (А ÉС))

3. (А Ù В) É А

4. (А Ù В) É В

5. А É (В É (А Ù В))

6. А É (А Ú В)

7. В É (А Ú В)

8. (А É С) É ((В É С) É ((АÚ В) É С))

9. (А É В) É ((А É В) É`А)

10. (А É В) É (`В É`А)

Якщо застосувати до наведеного набору аксіом правила доведення, то можна вивести будь-яку теорему в системі S² .

Правила виводу:

1. правило відділення або “ modus ponens” (МР) записується так:

А

А É В

В

2. правило підстановки (п/п) має вигляд:

А (x₁, x₂,... x_n)

А¢ (x₁¢, x₂¢,... x_n¢)

Дефініція доведення (виводу):Доведенням називається послідовність формул А₁,... А_n де кожна із формул є або аксіомою, або доказаною раніше формулою, або отримана за правилами доведення; остання формула послідовності А_n є виразом, який потрібно було довести.

Дефініція доказової формули: Формула А називається доказовою тоді, коли є можливість побудувати доведення, останньою формулою якого є формула А.

Якщо формула доказова, то записують так: |- А.

Якщо формула не доказова, то: -| А.

Для того щоб побудувати доведення формулиF, необхідно здійснити такі дії:

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

Наведене доведення називається доведенням із аксіом. Але існує ще доведення із деякого кінцевого числа довільних формул, які називаються припущеннями або гіпотезами.

Те, що формула В доказується із гіпотез А₁, …, А_n записується так:

А₁, …, А_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

Далі виписуємо друге припущення:

4. p É (q É r) - припущення 2

Формула 3 рядка і антецедент формули 4 рядка співпадають; отже, до них можна застосувати правило відділення (МР):

5. q É r - МР до 3 і 4

Із списку аксіом обираємо аксіому 4: (А Ù В) É В за принципом, щоб можна було застосувати МР до 1 і 6 рядків:

6. (p Ù q) É q - аксіома 4

Якщо співставити формулу 1 рядка і антецедент формули 6 рядка, то очевидно, що до них необхідно застосувати правило відділення:

7. q - МР до 1 і 6

І нарешті, застосовуємо правило відділення до 5 і 7 рядків:

8. r - МР до 5 і 7.

Отже, виходячи із цього доведення можна стверджувати, що із припущень p Ù q, p É (q É r) можна вивести r.

 

Лекція 7-8. Метатеорема про дедукцію. Металогічні принципи у S².

(4 год).

Поняття "теорема" і "метатеорема".

Метатеорема про дедукцію (теорема Ербрана) та її особливості.

Металогічні принципи в аксіоматичному численні логіки висловлювань: принцип роз'язання (формулювання метатеорем та побудова їх доведення); принцип несуперечливості (формулювання метатеореми відносно теорем, метатеореми відносно правил висновку, метатеореми відносно елементів алфавіту та побудова їх доведення); принцип повноти (функціональна і дедуктивна повнота мови, формулювання метатеореми та побудова її доведення); принцип незалежності аксіом у аксіоматичному численні.

 

Семінарське заняття 7. (2 год.)

1. Метатеорема про дедукцію.

2. Металогічні принципи аксіоматичного числення логіки висловлювань:

а) принцип розв'язання;

б) принцип несуперечливості;

в) принцип повноти;

г) принцип незалежності.

 

Контрольні запитання та вправи

1. Які фундаментальні властивості числень вам відомі?

2. Як формулюється мета теорема про дедукцію?

3. Які ви знаєте металогічні принципи?

4. Що означає «принцип розв’язання?

5. Скільки метатеорем описують «принцип розв’язання»?

6. Відносно яких компонентів доведення формулюється «принцип несуперечності»?

7. Які властивості формалізованих мов характеризує «принцип повноти»?

8. Що означає функціональна повнота мови?

9. Що означає дедуктивна повнота мови?

10. В якому сенсі в логіці вживається термін «незалежність»?

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 2: с. 116-121; 4: с. 350-359; 15: с. 184-193; 18: с. 47-64; 29: с. 72-87, 104-122; 44: с. 15,416-417.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(4 год.)

Конспект статей із словника

Філософський енциклопедичний словник. — К, 2002. - -"Аксіоматичний метод ";

- "Незалежність аксіом".

 

Методичні вказівки

Ознайомлення з цією темою дозволяє студенту з’ясувати, що необхідно розрізняти теорміни “теорема ” і “ метатеорема ”.

Теоремаминазиваються доказувані формули числення, тоді як метатеореми – це доказувані змістовні твердження про властивості числення.

До таких фундаментальних властивостей числень відносяться: вивідність, розв’язуваність, несуперечливість, повнота, незалежність. Кожна із цих властивостей описується метатеоремами: про дедукцію, про несуперечливість, про розв’язуваність, про повноту, про незалежність.

Студентам необхідно знати, що теорема про дедукцію формулюється так:

“Якщо А₁, …, А_n-1, А_n |- B, то А₁, …, А_n-1 |- А_n É B ”. Тобто, якщо із формул А₁, …, А_n-1 і А_n виводиться В, то із формул А₁, …, А_n-1 виводиться імплікація А_n É B. Іншими словами: “ Якщо дано доведення В із А₁, …, А_n-1, А_n, то можна побудувати заключення А_n É B на підставі цього доведення ”.

Вивідність формули на підставі метатеореми про дедукцію визначається трьома особливостями, які виражаються у вигляді таких правил:

а) із довільних формул А₁, …, А_n вивідна кожна із цих формул:

А₁, …, А_n |- А_і де n ³ i ³ 1;

б) із довільних формул А₁, …, А_n вивідна кожна формула, яка вивідна в S²:

А₁, …, А_n |- R (R – вивідна формула S²);

в) якщо із довільних формул А₁, …, А_n вивідна формула виду МР, то із них вивідний консеквент цього модусу.

Ці особливості вивідності (дедукції) на підставі метатеореми про дедукцію є очевидними на основі таких семантичних міркувань:

1. Особливість (а) виражає властивість рефлексивності слідування: “Із засновку випливає він сам”: А |= А, так як |= А É А.

2. Особливість (б) виражає властивість істинних (вивідних) формул. “Кожна істинна формула розглядається як консеквент L - É (логічно істинної імплікації) з довільним антецедентом”.

3. Особливість (в) фіксується так “ Якщо із А₁, …, А_n |-В¢ і із

А₁, …, А_n |- В¢ É В², то |= В¢ É В², але це можливо, коли |= В² ”

Властивості роз’язання, несуперечливості, повноти і незалежності називають металогічними принципами. І аналізуються вони через доведення відповідних метатеорем.

Теорію називають розв'язною, якщо існує алгоритм, який для довільної формули за скінченну кількість кроків встановлює, чи існує її виведення. Інакше теорію називають нерозв'язною.

Принцип розв’язання характеризується доведенням відповідних метатеорем. Їх всього чотири:

МТ₁ - |- А É |= А (формулюється: «якщо А – доказане, то тотожно-істинне А»)

МТ₂ - ù |= А É ù |- А (формулюється: «якщо А не тотожно-істинне, то і не доказане А»)

МТ₃ - |= А É |- А (формулюється: «якщо А тотожно-істинне, то доказане А»)

МТ₄ - ù |- А É ù |= А (формулюється: «якщо А не доказане, то не тотожно-істинне А»).

Теорію називають суперечливою, якщо всі її формули є теоремами. Інакше її називають несуперечливою.

Принцип несуперечливості формулюється відносно:

• теорем,

• правил висновку,

• елементів алфавіту.

Дефініція несуперечливості відносно теорем:

Логічна система несуперечлива, якщо, не всі правильно побудовані формули є теоремами. Це положення доводиться МТ_5..

Наслідком МТ₅ є семантичне формулювання несуперечливості:

«Якщо хоча б одна правильно побудована формула недоказувана, то жодна теорема не є логічним протиріччям».

Дефініція несуперечливості відносно правил висновку:

В синтаксичному смислі система S² несуперечлива відносно правил висновку, якщо в ній неможливо довести А і довести ù А».

Доведення цього положення здійснюється двома метатеоремами:

МТ₆ (пряма): |- А Éù|-ù А ( формулюється так: «Якщо вивідне А, то невірно, що вивідне ù А);

МТ_{7 –} (обернена): |- ù А É ù |- А (формулюється так: «Якщо в S² вивідне ùА, то невірно, що вивідне А»).

Дефініція несуперечливості відносно елементів алфавіту (пропозиційних змінних):

а) у синтаксичному розумінні – жодна окремо взята пропозиційна змінна не є теоремою та тавтологією, тобто не є доказуваною;

б) у семантичному розумінні: - жодна окремо взята пропозиційна змінна не є тавтологією.

Це означає, якщо формула складається із однієї пропозиційної змінної, яка набуває логічних значень «і» або «х», тобто є фактично істинною формулою, а отже не може бути теоремою, тобто не є доказуваною.

Принцип повноти характеризує дві властивості формалізованих мов:

По-перше, виразні можливості засобів мови;

По-друге, виразні можливості дедуктивних засобів мови.

У зв’язку з цим розрізняють:

а) функціональну повноту мови;

б) дедуктивну повноту мови.

Функціональна повнота засобів мови – це повнота логічних сполучників.

У системі S¹ група логічних сполучників повинна бути достатньою для вираження всіх п’яти сполучників, які використовуються у ППФ.

Однак, у групі сполучників (Ù, Ú, É, «,ù) виділяють певні базисні сполучники, до яких можна звести решту сполучників. Цю групу називають функціонально повною.

Дедуктивна повнота характеризує властивості засобів побудови доведення. В S² такими засобами є аксіоми і правила висновку.

МТ₈: «Система S² дедуктивно повна, якщо в ній для будь-якої формули В докузувано, що:

1) або В вивідне: |- В;