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

Содержание

Слайд 2

Л І Т Е Р А Т У Р А Конверський

Л І Т Е Р А Т У Р А
Конверський А.Є.

Логіка. – К.,2004. – с.321-327.
Мельников В. Н. Логические задачи. – К., 1989. – с. 154 – 177.
Тофтул М.Г. Логіка. – К., 2003. – с. 117 – 127.
Формальная логика. – Л., 1977. – с. 219 – 240.
Слайд 3

1. Тотожна істинність формул. Вся множина формул логіки висловлювань з огляду

1. Тотожна істинність формул.

Вся множина формул логіки висловлювань з огляду

на значення їх істинності поділяється на три класи:
тотожно істинні (завжди істинні, або тавтології);
тотожно хибні (завжди хибні, або суперечності);
 нейтральні формули.
Формула називається тотожно істинною, якщо вона має значення істинності в цілому лише істина, не залежно від значень істинності її складових змінних. До них відносяться всі еквівалентності (закони логіки) – завжди істинні подвійні імплікації; відношення логічного слідування – завжди істинна імплікація. Більш простий приклад : формула А ∨ ~ А – завжди істинна.
Слайд 4

Формула називається тотожно хибною, якщо вона має значення “хиба” при всіх

Формула називається тотожно хибною, якщо вона має значення “хиба” при

всіх наборах значень істинності її складових змінних. Так, формула А ∨ ~ А - є завжди хибною.
Ясно, що заперечення формули-суперечності є формулою-тавтологією і навпаки.
Формула називається нейтральною, якщо вона при одних наборах значень її складових має значення “істина”, а при інших – “хиба”.
В логіці висловлювань особливе місце займають Т. І. Ф., які виражають закони логіки. Можна сказати: закон логіки – це тавтологія.
Слайд 5

До найбільш суттєвих законів логіки висловлювань належать такі: 1. 1. Закон

До найбільш суттєвих законів логіки висловлювань належать такі:
1. 1. Закон тотожності:

А ≡ А (А еквівалентно А).
2. 2. Закон суперечності: ~ (А ∧ ~ А) (невірно, що А і не А).
3. 3. Закон виключеного третього: А ∨ ~ А (А або не А).
4. Комутативний закон:
А ∧ В ≡ В ∧ А (А і В те ж саме, що В і А).
А ∨ В ≡ В ∨ А (А або В те ж саме, що В або А).
5. Асоціативний закон:
(А ∧ В) ∧ С ≡ А ∧ (В ∧ С)
(А і В) і С є те ж саме, що А і (В і С).
(А ∨ В) ∨ С ≡ А ∨ (В ∨ С)
Слайд 6

6. Дистрибутивний закон: А ∧ (В ∨ С) ≡ (А ∧

6. Дистрибутивний закон:
А ∧ (В ∨ С) ≡ (А ∧

В) ∨ (А ∧ С)
А і (В або С) є те ж саме, що А і В або А і С.
А ∨ (В ∧ С) ≡ (А ∨ В) ∧ (А ∨ С)
7. Закон ідемпотентності:
А ∧ А ≡ А (А і А є тим же самим, що А)
А ∨ А ≡ А
8. Закон поглинання:
А ∧ (А ∨ В) ≡ А (А і (А або В), є тим же самим, що А).
А ∧ (А ∨ В) ≡ А
Слайд 7

9. – 12. Закони усунення констант: 9. А ∧ 1 ≡

9. – 12. Закони усунення констант:
9. А ∧ 1 ≡ А

(А і тавтологія є А)
10. А ∨ 1 ≡ 1 (А або тавтологія є тавтологією)
11. А ∧ 0 ≡ 0 (А і суперечність є суперечністю)
12. А ∨ 0 ≡ А (А або суперечність є А)
13. Закон подвійного заперечення:
~ ~ А ≡ А (не не-А є А)
14. Перший закон де Моргана:
~ (А ∧ В) ≡ ~ А ∨ ~ В (заперечення кон’юнкції є
диз’юнкцією заперечень атомів)
Слайд 8

15. Другий закон де Моргана: ~ (А ∨ В) ≡ ~

15. Другий закон де Моргана:
~ (А ∨ В) ≡ ~

А ∧ ~ В (заперечення диз’юнкції є
кон’юнкцією заперечень атомів).
16. – 21. Вираження складних сполучників через прості.
А ∧ В ≡ ~ (~ А ∨ ~ В) (А і В дорівнює не – (не-А або не-В))
А ∨ В ≡ ~ (~ А ∧ ~ В) (А або В дорівнює не-(не-А і не-В))
18. Закон усунення імплікації:
А → В ≡ ~ А ∨ В.
Слайд 9

19. Закон усунення подвійної імплікації: А ↔ В ≡ (А →

19. Закон усунення подвійної імплікації:
А ↔ В ≡ (А →

В) ∧ (В → А).
20. Скориставшись законом 18 дістанемо:
А ↔ В ≡ (~ А ∨ В) ∧ (~ В ∨ А)
21. Усунення сильної диз’юнкції закон:
А ∨ ∨ В ≡ (А ∨ В) ∧ (~ А ∨ ~ В)
22. Закон простої контрапозиції:
А → В ≡ ~ В → ~ А.
Слайд 10

23. Закон складної контрапозиції: (А ∧ В) → С ≡ (А

23. Закон складної контрапозиції:
(А ∧ В) → С ≡ (А

∧ ~ С) → ~ В
(А ∧ В) → С ≡ (В ∧ ~ С) → ~ А
24. Закон силогізму:
((А → В) ∧ (В → С)) → (А → С)
25. Закон виключення (склеювання):
АВ ∨ ~ АВ ≡ В
(А ∨ В) ∧ (А ∨ ~ В) ≡ А
26. Закон виявлення:
АС ∨ В ~ С ≡ АС ∨ В ~ С ∨ АВ
(А ∨ С) (В ∨ ~ С) ≡ (А ∨ С) (В ∨ ~ С) (А ∨ В)
Слайд 11

2. Еквівалентні перетворювання. Мінімізація. Еквівалентним перетворюванням даної формули називають заміну її

2. Еквівалентні перетворювання. Мінімізація.

Еквівалентним перетворюванням даної формули називають заміну її

іншою формулою, яка еквівалентна їй. Еквівалентні перетворювання слугують засобом спрощення (мінімізації) формул. Застосовуючи такі перетворювання можна замінити одну формулу іншою, еквівалентною їй з більш простою структурою.
Більш простою структурою порівняно з даною формулою називають формулу, яка не містить в собі знаків →, ↔ та ∨∨, заперечень молекул і подвійних заперечень і складається з меншого числа атомів, знаків операцій та пар дужок.
Слайд 12

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

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

в формулу, користуючись т законом (12). Так, можна ввести атом С в формулу А ∨ В, бо відомо, що F ∨ 0 ≡ F.
СПРОЩЕННЯ СИСТЕМИ ВИСЛОВЛЮВАНЬ.
Для спрощення системи висловлювань, кожне з яких є істинним, необхідно:
Записати кожне висловлювання в такій еквівалентній формі, в якій виключені знаки →, ↔ та ∨∨, а знаки заперечення стосуються лише атомів.
Записати всю систему висловлювань у вигляді їх кон’юнкції.
Застосувавши еквівалентні перетворювання, спростити цю кон’юнкцію.
Слайд 13

Для спрощення системи висловлювань, принаймні одне з яких є істинним, необхідно:

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

необхідно:
Записати кожне висловлювання в такій еквівалентній формі, яка б виключала складні сполучники, а знаки заперечення стосувались би лише атомів.
Записати всю систему висловлювань у вигляді їх диз’юнкції.
Застосувавши еквівалентні перетворювання, спростити цю диз’юнкцію.