Зведемо цю формулу до КНФ:
1. (C |
|
|
|
|
|
|
|
|
|
) [(A B) C] C |
|||||||||||||||||||||||||||||||
A |
B |
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
) [(A B) |
|
|
|
|
|
] C |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
2. ( |
|
|
|
|
|
A |
B |
||||||||||||||||||||||||||||||||||
C |
C |
||||||||||||||||||||||||||||||||||||||||
3. ( |
|
|
|
|
А В) [( |
|
|
|
|
|
|
) |
|
|
|
|
] C |
||||||||||||||||||||||||
C |
A |
B |
|
|
C |
||||||||||||||||||||||||||||||||||||
4. ( |
|
|
|
|
А В) [( |
|
|
|
|
|
|
|
С) ( |
|
C)] |
||||||||||||||||||||||||||
C |
A |
B |
C |
||||||||||||||||||||||||||||||||||||||
5. ( |
|
|
|
|
|
|
|
|
C) ( |
|
|
|
|
C) ( |
|
|
|
|
C A) |
||||||||||||||||||||||
C |
A |
B |
C |
C |
A |
B |
|||||||||||||||||||||||||||||||||||
( |
|
C A) ( |
|
|
|
|
|
C B) ( |
|
C B). |
|||||||||||||||||||||||||||||||
C |
A |
|
B |
C |
|||||||||||||||||||||||||||||||||||||
Отримана КНФ показує, що вихідна формула є тавтоло- гією, а це означає, що формула С A B є гіпотезою для формули
((A B) C) C.
Розглянемо ще один приклад.
Знайдемо прості гіпотези для формули
((A B ) C) (C B).
1. |
((A |
|
|
|
|
|
) |
C) (C B) |
|
|
|
|
|||||||||
|
|
B |
|
|
|
|
|||||||||||||||
2. ((A |
|
|
|
|
) C) C B |
|
|
|
|
||||||||||||
|
|
B |
|
|
|
|
|||||||||||||||
3. ((A |
|
|
|
|
) |
|
|
|
|
|
) C B |
|
|
|
|
||||||
|
|
B |
|
C |
|
|
|
|
|||||||||||||
4. (А |
|
|
|
|
) С В |
|
|
|
|
||||||||||||
B |
C |
|
|
|
|
||||||||||||||||
5. (А |
|
|
|
) С В (А |
|
) (А |
|
) |
|||||||||||||
B |
C |
B |
C |
||||||||||||||||||
6. (А |
|
|
|
) С В (А |
|
) (А |
|
) А |
|||||||||||||
B |
C |
B |
C |
||||||||||||||||||
7. С В (А |
|
|
|
|
|
|
) (А |
|
) А |
|
|
||||||||||
|
|
B |
C |
|
|
||||||||||||||||
8. С В (А |
|
|
|
|
) А |
|
|
|
|
||||||||||||
|
|
C |
|
|
|
|
|||||||||||||||
9. С В А.
Остання формула є СДНФ, яка містить всі прості гіпо- тези вихідної формули.
Ознайомленням із нормальними формами завершується аналіз характерних особливостей S1 і тих завдань, які вони розв’язують.
? |
Контрольні питання та вправи |
|
1.Поняття алгебри логіки висловлювань.
2.Структура мови алгебраїчної системи логіки висловлювань.
3.Поняття змінної та метазмінної.
340 |
А. Є. Конверський. ЛОГІКА |
4.Синтаксис метамови в S1.
5.Семантика метамови в S1.
6.Характеристика завдань, які розв’язуються засобами S1.
7.Структура алфавіту S1.
8.Визначення нелогічних термінів.
9.Характеристика логічних символів.
10.Дефініція формули.
11.Типологія формул за синтаксичними ознаками.
12.Поняття підформули.
13.Поняття степеня формули.
14.Способи розстановки дужок у формулі.
15.Визначення головного логічного знака у формулі.
16.Порядок виконання дій над формулою.
17.Фіксація логічної форми висловлювань природної мови за- собами словника S1.
18.Характерні особливості бездужкової логічної мови Я. Лу- касевича.
19.Семантика метамови.
20.Поняття інтерпретації.
21.Правила інтерпретації Sem ML в S1.
22.Таблиці істинності.
23.Порядок побудови таблиці істинності.
24.Типологія формул за семантичними ознаками.
25.Тавтології і логічні закони.
26.Поняття рівносильної формули.
27.Характеристика відношення рівносильності.
28.Основні закони логіки та їх функції.
29.Відношення сумісності за істинністю між формулами.
30.Відношення сумісності за хибністю між формулами.
31.Відношення логічного слідування.
32.Поняття нормальної форми логіки висловлювань.
33.Проблема розв’язання в S1.
34.КНФ, способи її отримання, і задачі, які вона розв’язує.
35.ДКНФ, способи її отримання і задачі, які вона розв’язує.
36.Характерні особливості СКНФ, способи отримання і задачі, які вона розв’язує.
37.ДНФ, способи отримання і задачі, які вона розв’язує.
38.ДДНФ, способи її отримання і задачі, які вона розв’язує.
39.СДНФ, способи її отримання і задачі, які вона розв’язує.
40.Перевірити, чи є формулами логіки висловлювань такі ви-
рази:
а) (p |
q) r ; |
|||||
б) (p |
|
|
|
)) ( q ) p; |
||
r |
||||||
в) ( |
|
|
|
|||
p |
q) r. |
|||||
41. |
Побудувати таблиці істинності для таких формул: |
|||||
а) |
((( q p) q) q); |
|||||
Книга друга. СУЧАСНА ЛОГІКА |
341 |
б) (((p q) |
|
|
r) |
|
|
|
|
( q |
|
|
r)); |
|
|
|||||||||||||||||||
в) (r |
((p q) r)). |
|
|
|
|
|
|
|
||||||||||||||||||||||||
42. |
|
|
За допомогою таблиць істинності перевірити, чи є рівно- |
|||||||||||||||||||||||||||||
сильними формули: |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
а) (p q) i p |
|
|
|
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
q |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
б) ( |
|
q) i (p |
|
|
|
|
|
|
); |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
p |
|
|
|
q |
|
|
|
|
|
|
|
|||||||||||||||||||||
в) p |
(q r) i (p q) |
r; |
|
|||||||||||||||||||||||||||||
|
|
i (p |
|
|
|
|
) |
|
|
|
||||||||||||||||||||||
г) (p q) r |
|
|
|
|
|
. |
|
|||||||||||||||||||||||||
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; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
б) ( |
|
q), (q |
r), (r p). |
|
|
|||||||||||||||||||||||||||
p |
|
|
||||||||||||||||||||||||||||||
46. |
|
|
Знайти всі прості наслідки із засновків: |
|||||||||||||||||||||||||||||
а) p q, q r, |
|
|
|
c; |
|
|
|
|
|
|
|
|||||||||||||||||||||
p |
|
|
|
|
|
|
|
|||||||||||||||||||||||||
б) p |
q, p |
|
|
c, |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|||||||||||||||
q |
|
c |
|
|
|
|
||||||||||||||||||||||||||
47. |
|
|
Звести формулу до ДНФ: |
|
||||||||||||||||||||||||||||
((p q) ( |
|
|
r)) |
|
. |
|
|
|
|
|||||||||||||||||||||||
q |
r |
|
|
|
|
|||||||||||||||||||||||||||
48. |
|
|
Привести до ДДНФ формулу: |
|||||||||||||||||||||||||||||
((p q) (r s)) |
( |
|
s). |
|
||||||||||||||||||||||||||||
p |
|
|||||||||||||||||||||||||||||||
49. |
|
|
За допомогою СДНФ знайти всі прості гіпотези формул: |
|||||||||||||||||||||||||||||
а) ((p q) (p q); |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
б) ((p |
|
|
) |
|
|
r) (r q). |
|
|
|
|
||||||||||||||||||||||
|
q |
|
|
|
|
|
||||||||||||||||||||||||||
342 |
А. Є. Конверський. ЛОГІКА |
РОЗДІЛ ІІ
ЧИСЛЕННЯ ЛОГІКИ ВИСЛОВЛЮВАНЬ
Із загальнонаукової точки зору числення можна визна-
чити як формальний апарат оперування зі знаками пев- ного виду, що дозволяє описати деякий клас задач, а для окремих підкласів цього класу – і алгоритм розв’язання.
Улогіці поняття числення уточнюється і конкретизу- ється засобами суворої формалізації. Тут логічне числення задається на базі деякої формалізованої мови. Спочатку визначається набір вихідних положень, із яких за допомо- гою чітких правил перетворення отримують нові положен- ня (їх називають теоремами).
Якщо до техніки числень додати інтерпретацію, яка надає значення вихідним символам і формулам, то чис- лення перетворюються у мову, що описує конкретну предметну область. Це можуть бути числення висловлю- вань або числення предикатів, або числення класів тощо.
Упершому розділі розглядалася алгебраїчна система логі- ки висловлювань, яка позначалася символом S1. Характер- ною особливістю цієї системи є те, що в синтаксисі метамови
єлише один вид правил – правила утворення (ПУ).
Мова числення логіки висловлювань, окрім правил утворення, включає і правила перетворення (ПП). Тоб-
то, до складу мови числення логіки висловлювань входять усі засоби S1, але тут вони отримують нове звучання і ви- конують інші функції.
Виходячи із вищезазначеного, структуру числень можна представити у вигляді такої схеми:
S2 |
Sem-частина |
|||
Sin-частина |
|
|
|
|
|
ML |
|
|
|
OL 1) |
ПУ |
Sin ML |
||
2) ПП |
||||
|
|
|||
правила |
|
|
||
інтерпре- |
Sem ML |
|||
тації |
||||
|
|
|||
|
|
|
||
Книга друга. СУЧАСНА ЛОГІКА |
|
|
343 |
|