Конверський А. Є. Логіка (традиційна та сучасна)

Подождите немного. Документ загружается.

Книга друга. СУЧАСНА ЛОГІКА

341

4. Синтаксис метамови в S

5. Семантика метамови в S

6. Характеристика завдань, які розв’язуються засобами S

7. Структура алфавіту S

8. Визначення нелогічних термінів.

9. Характеристика логічних символів.

10. Дефініція формули.

11. Типологія формул за синтаксичними ознаками.

12. Поняття підформули.

13. Поняття степеня формули.

14. Способи розстановки дужок у формулі.

15. Визначення головного логічного знака у формулі.

16. Порядок виконання дій над формулою.

17. Фіксація логічної форми висловлювань природної мови за-

собами словника S

18. Характерні особливості бездужкової логічної мови Я. Лу-

касевича.

19. Семантика метамови.

20. Поняття інтерпретації.

21. Правила інтерпретації Sem ML в S

22. Таблиці істинності.

23. Порядок побудови таблиці істинності.

24. Типологія формул за семантичними ознаками.

25. Тавтології і логічні закони.

26. Поняття рівносильної формули.

27. Характеристика відношення рівносильності.

28. Основні закони логіки та їх функції.

29. Відношення сумісності за істинністю між формулами.

30. Відношення сумісності за хибністю між формулами.

31. Відношення логічного слідування.

32. Поняття нормальної форми логіки висловлювань.

33. Проблема розв’язання в S

34. КНФ, способи її отримання, і задачі, які вона розв’язує.

35. ДКНФ, способи її отримання і задачі, які вона розв’язує.

36. Характерні особливості СКНФ, способи отримання і задачі,

які вона розв’язує.

37. ДНФ, способи отримання і задачі, які вона розв’язує.

38. ДДНФ, способи її отримання і задачі, які вона розв’язує.

39. СДНФ, способи її отримання і задачі, які вона розв’язує.

40. Перевірити, чи є формулами логіки висловлювань такі ви-

рази:

а) (p ⊃ q) ∨ r ∧;

б) (p ∨

r )) ⊃ ( q ∧) ∨ p;

в) (p ⊃ q) ⊃ r.

41. Побудувати таблиці істинності для таких формул:

а) (((



q ⊃ p) ∨ q) ∾ q);

А. Є. Конверський. ЛОГІКА

342

б) (((p ∨ q) ∨ r) ⊃ (



q ⊃ r));

в) (r ⊃ ((p ∨ q) ∧



r)).

42. За допомогою таблиць істинності перевірити, чи є рівно-

сильними формули:

а) (p ∧ q) i p ⊃

q ;

б) (

p ∨ q) i (p ⊃ q );

в) p ⊃ (q ⊃ r) i (p ∧ q) ⊃ r;

г) (p ∧ q) ∨ r i (p ⊃

q ) ∧ r .

43. Встановити, чи є тотожно-істинними формули:

а) p ⊃ (q ⊃ (p ∧ q));

б) (p ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃ (p ⊃ r));

в) (p ⊃ (q ⊃ r) ⊃ ((q ⊃ p) ⊃ (r ⊃ p)).

44. Наведені формули звести до КНФ:

а) p ⊃ ((p ⊃ q) ⊃ q);

б) ((p ⊃ q) ∧ (r ⊃ s)) ⊃ ((p ∧ r) ⊃ (q ∧ s));

в) ((p ⊃ q) ∨ (p ⊃ r)) ⊃ (p ⊃ (p ∨ r)).

45. Знайти всі наслідки із засновків:

а) (p ∧ q), q, r;

б) (

p ⊃ q), (q ⊃ r), (r ⊃ p).

46. Знайти всі прості наслідки із засновків:

а) p ∨ q, q ∨ r,

p ∧ c;

б) p ⊃ q, p ⊃ c,

q ∨ c .

47. Звести формулу до ДНФ:

((p ∨ q) ⊃ (

q ∧ r)) ∾ r .

48. Привести до ДДНФ формулу:

((p ⊃ q) ∨ (r ∾ s)) ⊃ (

p ∧ s).

49. За допомогою СДНФ знайти всі прості гіпотези формул:

а) ((p ∨ q) ∨ (p ∧ q);

б) ((p ∧

q ) ⊃ r) ⊃ (r ∨ q).

Книга друга. СУЧАСНА ЛОГІКА

343

РОЗДІЛ ІІ

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

Із загальнонаукової точки зору числення можна визна-

чити як формальний апарат оперування зі знаками пев-

ного виду, що дозволяє описати деякий клас задач, а для

окремих підкласів цього класу – і алгоритм розв’язання.

У логіці поняття числення уточнюється і конкретизу-

ється засобами суворої формалізації. Тут логічне числення

задається на базі деякої формалізованої мови. Спочатку

визначається набір вихідних положень, із яких за допомо-

гою чітких правил перетворення отримують нові положен-

ня (їх називають теоремами).

Якщо до техніки числень додати інтерпретацію, яка

надає значення вихідним символам і формулам, то чис-

лення перетворюються у мову, що описує конкретну

предметну область. Це можуть бути числення висловлю-

вань або числення предикатів, або числення класів тощо.

У першому розділі розглядалася алгебраїчна система логі-

ки висловлювань, яка позначалася символом S

. Характер-

ною особливістю цієї системи є те, що в синтаксисі метамови

є лише один вид правил – правила утворення (ПУ).

Мова числення логіки висловлювань, окрім правил

утворення, включає і правила перетворення (ПП). Тоб-

то, до складу мови числення логіки висловлювань входять

усі засоби S

, але тут вони отримують нове звучання і ви-

конують інші функції.

Виходячи із вищезазначеного, структуру числень можна

представити у вигляді такої схеми:

правила

інтерпре-

тації

ПУ

Sin

Sem-частина

ПП

Sem ML

Sin-частина

А. Є. Конверський. ЛОГІКА

344

1. Аксіоматичне числення логіки висловлювань

Аналізуючи пропозиційну логіку на рівні алгебраїчної

системи, ми розглядали кожну формулу як вираз, що

може прийняти одне із двох значень: «істина» або «хиба».

Завдяки цьому засобами даної системи можна було

розв’язувати такі задачі:

1) проводити демаркацію між тавтологіями і нета-

втологіями;

2) визначати відношення логічного слідування між

двома формулами;

3) здійснювати перевірку формул на рівносильність.

Однак складніші задачі засобами S

розв’язати немож-

ливо. Для цього необхідно залучати більш ефективні логі-

чні засоби.

а) Мова аксіоматичного числення

логіки висловлювань

Позначається аксіоматичне числення логіки вислов-

лювань символом S

До складу синтаксису (Sin ML) S

входять окрім

правил утворення (як уже зазначалося) правила пере-

творення (ПП).

Зупинимося на характеристиці правил утворення (ПУ).

Алфавіт S

включає такі самі символи, що й алфавіт S

1) пропозиційні символи: p, q, r, s, p

, q

, r

, s

,...;

2) логічні символи: &

∨

⊃

∾

.

Як бачимо, за назвою це ті ж самі об’єкти, що і в алфа-

віті S

, але у S

вони розглядаються з іншої, більш форма-

льної, сторони. Тут p, q, r, s – це вже не сутності, які зда-

тні приймати значення «і» (істина) або «х» (хиба) при

різних наборах значень, а певні об’єкти, які чітко відріз-

няються один від одного, і властивості яких явно не ви-

значаються. Стосовно логічних символів зауважимо, що

тут уже не йдеться про їх табличне визначення.

Єдиним способом визначення пропозиційних символів і

пропозиційних зв’язок є способи поводження з ними у від-

повідності до правил висновку.

Дефініція формули така сама, як і в S

. Але формула в

характеризується не таблицями істинності, а си-

Книга друга. СУЧАСНА ЛОГІКА

345

туацією виводу (випливання). Тому тут відбувається

диференціація формул не на тавтології, протиріччя і

нейтральні (виконувані), а на теореми і аксіоми. Маєть-

ся на увазі, що саме ця типологія висувається на передній

план, а не те, що в об’єкт-мові S

відсутні тотожно-хибні

(або протиріччя, або L-x) формули і нейтральні (або вико-

нувані, або F – i) формули.

Усередині тотожно-істинних (або тавтологій, або L-i)

формул відбувається розшарування на теореми і ак-

сіоми.

Вищезазначене можна проілюструвати схемою мови S

Sin ML

ПУ

2) ПП

L-i

Теорема

L-х

ПІ

Sem ML

F-i

Ось так можна охарактеризувати ПУ в S

. Очевидно, що

вони співпадають із ПУ в S

, але тут вони, природно, на-

бувають певної специфіки.

Розглянемо правила перетворення (ПП).

До складу ПП входять:

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

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

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

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

а) правило відділення або правило модус поненс (МР);

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

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

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

Дефініція: «Аксіомою в S

називають підмножину

тавтологій, які визначаються вихідними при побудові

доведення».

А. Є. Конверський. ЛОГІКА

346

Зауважимо, що не треба розглядати аксіому S

у тради-

ційному розумінні як «очевидну істину» або як «істину,

що не потребує доведення».

У логічному численні всі формули, в тому числі і ак-

сіоми, розглядаються безвідносно до їх можливих зна-

чень «очевидно» або «неочевидно». Тут значення фор-

мул враховується опосередковано.

Дефініція: «Теоремами в S

називають підмножину

тавтологій, для яких існує доведення».

Аксіоми і теореми вичерпують всю множину тавто-

логій в S

. Враховуючи це, аксіоматичні числення будують

так, щоб клас теорем співпадав із класом тавтологій. Іншими

словами, S

своїми засобами забезпечує можливість охарак-

теризувати всю множину тавтологій. Саме цій змістовній

вимозі підпорядкований вибір аксіом і правил висновку у S

Набір аксіом у S

може бути різним, але він повинен

бути достатнім для доведення теорем у S

Як зразок візьмемо набір аксіом, запропонований німе-

цьким вченим Давидом Гільбертом:

1. А ⊃ (В ⊃ А)

2. (А ⊃ (В ⊃ С) ⊃ ((А ⊃ В) ⊃ (А ⊃С))

3. (А ∧ В) ⊃ А

4. (А ∧ В) ⊃ В

5. А ⊃ (В ⊃ (А ∧ В))

6. А ⊃ (А ∨ В)

7. В ⊃ (А ∨ В)

8. (А ⊃ С) ⊃ ((В ⊃ С) ⊃ ((А∨ В) ⊃ С))

9. (А ⊃ В) ⊃ ((А ⊃ В) ⊃

)

10. (А ⊃ В) ⊃ (

⊃

Застосовуючи до наведеного набору аксіом правила до-

ведення, можна вивести будь-яку теорему в S

Визначимо правила доведення.

Дефініція правила відділення (МР): «Якщо А і А ⊃ В

істинні, то В також істинне». Записується правило у

вигляді схеми:

⊃

Зрозуміло, що тут маються на увазі аксіомні схеми.

Книга друга. СУЧАСНА ЛОГІКА

347

Дефініція правила підстановки (п/п): «Нехай А, фор-

мула, яка містить змінні х

, х

, ... х

. Тоді, якщо А –

істинна формула в численні висловлювань, то, заміня-

ючи в ній змінні x

, x

, ... x

всюди, де вони входять дові-

льними змінними x

′, x

′, ... x

′, отримаємо формулу А′,

яка також буде істинною».

Це правило має вигляд:

()

xxxA

′′′′

...,,,

Дефініція доведення: «Доведенням називається послі-

довність формул А

, ... А

, де кожна із формул є або ак-

сіомою, або доказаною раніше формулою, або отримана

за правилами доведення; остання формула послідовно-

сті А

є виразом, який потрібно було довести».

Дефініція доказової формули: «Формула А назива-

ється доказовою тоді, коли є можливість побудувати

доведення, останньою формулою якого є формула А».

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

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

Розглянемо структуру доведення на прикладі доказу

теореми:

|− р ⊃ р.

Доведення.

1. р ⊃ (q ⊃ p) – Ax. 1

2. p ⊃ ((p ⊃ p) ⊃ p) – q/p ⊃ p за п/п до 1

3. (р ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃

⊃(p ⊃ r))

– Ax. 2

4. (p ⊃ ((p ⊃ p) ⊃ p)) ⊃

⊃ ((p ⊃ (p ⊃ p)) ⊃ (p ⊃ p) –

⊃

, r/

за п/п до 3

5. (p ⊃ (p ⊃ p)) ⊃ (p ⊃ p) за МР, до 1, 4

6. p ⊃ (q ⊃ p) – Ax 1

7. p ⊃ (p ⊃ p) – q/p за п/п до 6

8. |− р ⊃ р за МР до 7, 5.

Дамо деякі пояснення до структури доведення.

Послідовність у доведенні зліва утворює, власне, дове-

дення теореми р ⊃ р. Послідовність справа – є аналізом

цього доведення, тобто тут вказані підстави, за якими ко-

жен рядок включається в доведення. Треба мати на ува-

А. Є. Конверський. ЛОГІКА

348

зі, що аналіз доведення не є його частиною і може бути

опущеним.

Опишемо хід доведення із аксіом.

Для того щоб побудувати доведення формули F, не-

обхідно здійснити такі дії:

1) виписати одну із аксіом;

2) послідовно застосувати правило підстановки (п/п)

і правило відділення (МР);

3) доведення є закінченим, якщо останнім виразом у

послідовності формул буде F.

Розглянемо приклад побудови доведення теореми:

|− (p ⊃ q) ⊃ ((p ∨ q) ⊃ q).

1. Візьмемо аксіому 8:

(p ⊃ r) ⊃ ((q ⊃ r) ⊃ ((p ∨ q) ⊃ r)).

2. Застосовуємо правило підстановки і підставляємо

замість r/q:

(p ⊃ q) ⊃ ((q ⊃ q) ⊃ ((p ∨ q) ⊃ q)).

3. Беремо аксіому 2:

(p ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃ (p ⊃ r)).

4. За правилом підстановки підставляємо замість p/p

⊃ q, замість q/q ⊃ q, замість r/(p ∨ q) ⊃ q:

((p ⊃ q) ⊃ ((q ⊃ q) ⊃ ((p ∨ q) ⊃ q)) ⊃

⊃ (((p ⊃ q) ⊃ (q ⊃ q)) ⊃ ((p ⊃ q) ⊃ (p ∨ q) ⊃ q))).

5. Застосовуємо правило відділення (МР) до 2 і 4 ряд-

ків і отримуємо:

((p ⊃ q) ⊃ (q ⊃ q)) ⊃ ((p ⊃ q) ⊃ (p ∨ q) ⊃ q)).

6. Візьмемо формулу, раніше доведену в S

p ⊃ p.

7. Застосуємо правило підстановки і підсталяємо за-

мість p/q:

q ⊃ q.

8. Беремо аксіому 1:

p ⊃ (q ⊃ p).

Книга друга. СУЧАСНА ЛОГІКА

349

9. Використовуємо правило підстановки і підставляємо

замість p/q ⊃ q i замість q/p ⊃ q:

(q ⊃ q) ⊃ ((p ⊃ q) ⊃ (q ⊃ q)).

10. Застосовуємо правило відділення (МР) до 6 і 8 ряд-

ків і отримуємо:

(p ⊃ q) ⊃ (q ⊃ q).

11. Використовуючи правило МР до 9 і 4, отримуємо:

|− (p ⊃ q) ⊃ ((p ∨ q) ⊃ q).

Одинадцятий рядок співпадає з формулою, яку потрібно

було довести, отже доведення закінчено.

Наведені доведення є доведеннями із аксіом. Ці дове-

дення можна розширити в тому смислі, що воно стане до-

веденням не лише із аксіом, але й з деякого кінцевого чи-

сла довільних формул, які називаються припущеннями,

або гіпотезами.

Дефініція: «Доведенням із гіпотез А

,... А

формули В

називається кінцева послідовність формул В

,... В

, ко-

жна з яких є або аксіома, або гіпотеза, або раніше дове-

дена формула в S

, або отримана із двох попередніх фо-

рмул за правилом МР; причому В

є В ».

Факт, що формула В доказується із гіпотез А

,... А

, за-

писується так:

, ..., А

|− В.

Іноді в науковій літературі зустрічається, що доведен-

ням із гіпотез називають дедукцію (вивідність) із гіпотез,

залишаючи термін «доведення» для позначення доведення

із порожньої множини гіпотез, або доведення із аксіом.

Наведемо приклад щодо цього виду доведення.

Маємо гіпотези: p ∧ q, p ⊃ (q ⊃ r).

Необхідно побудувати доведення із них формули r:

p ∧ q, p ⊃ (q ⊃ r) |− r.

Доведення.

1. p ∧ q – припущення 1

2. (p ∧ q) ⊃ p – аксіома 3

3. p – МР до 1 і 2

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

5. q ⊃ r – МР до 3 і 4

А. Є. Конверський. ЛОГІКА

350

6. (p ∧ q) ⊃ q – аксіома 4

7. q – МР до 1 і 6

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

Отже, існує вивід r із p ∧ q, p ⊃ (q ⊃ r).

Зауважимо, що треба розрізняти терміни «теорема» і

«метатеорема».

Теоремами називаються доказувані формули числен-

ня, тоді як метатеореми – це доказувані змістовні

твердження про властивості числення.

До таких фундаментальних властивостей числень

відносяться:

 вивідність;

 розв’язуваність;

 несуперечливість;

 повнота;

 незалежність.

Кожна із цих властивостей описується відповідними

метатеоремами:

 про дедукцію;

 про несуперечливість;

 про розв’язуваність;

 про повноту;

 про незалежність.

Розглянемо їх по порядку.

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

Вперше ця теорема була сформульована у 1930 р. Ер-

браном. Тому іноді її називають теоремою Ербрана. Але

як загальний методологічний принцип, що характеризує

аксіоматично-дедуктивні системи, вона з’явилася у

А. Тарського.

Формулюється метатеорема про дедукцію так:

«Якщо А

,... А

n-1

, А

|− В, то А

,... А

n-1

|− А

⊃ В».

Тобто, якщо із формул А

,... А

n-1

і А

виводиться В, то із

формул А

, ... А

n-1

виводиться імплікація А

⊃ В.

Іншими словами: «Якщо дано доведення В із А

,... А

n-1

, то можна побудувати висновок А

⊃ В на підставі

цього доведення».