TA&Ml_ukr_1

Содержание

Слайд 2

Зміст лекції.

Основні поняття та означення.
Висловлювання та логічні зв'язки.
Інтерпретація формул логіки

Зміст лекції. Основні поняття та означення. Висловлювання та логічні зв'язки. Інтерпретація формул
висловлювань.
Проблема вирішення та функціональна повнота.
Дедуктивні висновки.

Слайд 3

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

Логіка
предикатів

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

Логіка висловлювань Логіка предикатів Між основними поняттями цих мов спостерігається взаємно однозначна
ці терміни не є синонімами.

Слайд 4

Логіка висловлювань як алгебра

логіка висловлювань – це наука про міркування, засновки і

Логіка висловлювань як алгебра логіка висловлювань – це наука про міркування, засновки
висновки яких складаються із висловлювань.
Означення 1.1. Висловлюванням називають осмислений вираз звичайної мови, якому можна приписати значення істинності.
Означення 1. 2. Значення істинності – це абстрактний об’єкт, що ставиться у відповід-ність висловлюванню: істина – коли висловлювання відповідає дійсності, хибність – коли висловлювання не відповідає дійсності.

Слайд 5

Означення 1.3. Логіка висловлювань – це алгебраїчна структура 〈{ X, I },

Означення 1.3. Логіка висловлювань – це алгебраїчна структура 〈{ X, I },
∧, ∨ , ¬ , → , ~ , X , I 〉 з носієм – двійковою множиною { X : “Хибність”,
I : “Істина”}, операціями – логічними зв’язками : “∧” - кон’юнкція, “∨” - диз’юнкція, “ ¬ ”– заперечення, “ → ” – імплікація, “ ~ ” – еквівалентність і константами : X – хибність та I – істина.

Означення 1. 4. Атомом (елементарним висловлюванням) називається таке висловлювання, яке є простим розповідним реченням, тобто не має складових частин.

Слайд 6

Означення 1.5. Правила побудови формул у логіці висловлювань визначають таким:
1. Атом є

Означення 1.5. Правила побудови формул у логіці висловлювань визначають таким: 1. Атом
формулою.
2. Якщо A і B – формули, то A ∧ B, A ∨ B,
A→ B, A~B, ¬ A – також формули.
3. Ніяких формул, крім породжених зазначеними вище правилами, не існує.

Означення 1.6. Інтерпретацією висловлювань називають приписування значень істинності атомам, із яких побудовані висловлювання.
Якщо висловлювання містить n атомів, то можна скласти 2n інтерпретацій.

Слайд 7

Приклад 1.1. Для висловлювання “Якщо іде дощ, то щоб не змокнути, я

Приклад 1.1. Для висловлювання “Якщо іде дощ, то щоб не змокнути, я
відкриваю парасольку над головою” записати формулу висловлювань і побудувати таблицю істинності.
Розв’язання. Для цього висловлювання введемо атоми :
A – “ йде дощ ”, B – “ щоб не змокнути, я відкриваю парасольку над головою ”.

Слайд 8

З умовним висловлюванням А→В зв’язані ще три висловлювання : конверсія, інверсія та

З умовним висловлюванням А→В зв’язані ще три висловлювання : конверсія, інверсія та
контрапозиція. Вони визначаються таким чином:В→А –конверсія висловлювання А→В;
¬А → ¬В – інверсія висловлювання А→В;
¬В →¬А – контрапозиція висловлювання А→В.

Приклад 1.2. Для висловлювання “ Якщо він добре грає у футбол, то він популярний ” знайти конверсію, інверсію та контрапозицію.

Слайд 9

Приклад 1.3. Речення “ Оскільки я ліг пізно спати, я проспав і

Приклад 1.3. Речення “ Оскільки я ліг пізно спати, я проспав і
через це не пішов на роботу ” записати у вигляді формули логіки висловлювань.

Розв’язання. У цьому складному реченні виділимо прості речення та візьмемо їх у дужки – “Оскільки (я ліг пізно спати), (я проспав) і через це не (пішов на роботу) ”.

(А → В) → ¬ С

Слайд 10

Інтерпретація формул логіки висловлювань

Означення 1. 7. Формулу називають тотожно істинною (тавтологією, або

Інтерпретація формул логіки висловлювань Означення 1. 7. Формулу називають тотожно істинною (тавтологією,
загальнозначущою), якщо вона набуде значення “ Істина ” на всіх інтерпретаціях (наборах значень змінних).

Слайд 11

Означення 1.8. Формулу називають тотожно хибною (суперечною, або нездійсненною ), якщо вона

Означення 1.8. Формулу називають тотожно хибною (суперечною, або нездійсненною ), якщо вона
набуває значення “ Хибність ” на всіх інтерпретаціях (наборах значень змінних).
(А→В)∧(¬А→¬В)∧¬В

Слайд 12

Означення 1.9. Формулу називають нейтральною (не загальнозначущою, або несуперечливою), якщо вона на

Означення 1.9. Формулу називають нейтральною (не загальнозначущою, або несуперечливою), якщо вона на
одних інтерпретаціях набуває значення “Істина”, а на інших “ Хибність ”.

Слайд 13

Особлива роль в алгебрі висловлень належить тотожно істинним формулам як способам правильних

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

Слайд 14

Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій

Проблема вирішення в

Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій Проблема вирішення
логіці висловлювань розглядається як відповідь на питання, чи існує алгоритм, який за скінченне число кроків дає змогу визначити тип будь-якої формули алгебри висловлювань. В алгебрі висловлювань ця проблема розв’язується позитивно. Зокрема можна запропонувати способи : 1) Складанням таблиць істинності формул; 2) Застосуванням методу міркувань від супротивного; 3) Зведенням формул до нормальних форм.

Слайд 15

Таблиця істинності – це табличне визначення істинності складного висловлювання при всіх

Таблиця істинності – це табличне визначення істинності складного висловлювання при всіх можливих
можливих (інтерпретаціях) значеннях змінних (атомів), що складають дане висловлювання.

Слайд 16

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

А.

Аналіз формул із застосуванням методу міркувань від супротивного базується на таких умовиводах:
Якщо припустимо, що для деякого набору значень атомів формула α(A1, A2, …, An) набуває значення
“ Хибність ”, а після аналізу формули прийдемо до суперечності, то відносно формули α робимо висновок, що вона є тавтологією.
Б. Якщо припустимо, що для деякого набору значень атомів формула α(A1, A2,…, An) набуває значення “Істина” і прийдемо до суперечності, то α є суперечною.
В. Якщо не одержимо суперечності ні при припущенні А) , ні при припущенні Б), то робимо висновок, що формула α є нейтральною.

Слайд 17

Приклад 1. 4. Визначити тип формули
α = ((A → B) →A)

Приклад 1. 4. Визначити тип формули α = ((A → B) →A)
→A.

Розв’язання. Припустимо, що α не є тотожно істинною формулою. Тоді повинен існувати такий набір значень атомів, на якому вона набуває значення “ Хибність ”. Формула α є імплікацією. Значення “ Хибність ” можливе лише за умови, що (A→B)→A набуває на цьому наборі значення “ Істина ”, а А – “ Хибність ”. Тоді випливає, що A→B повинне набувати значення
“ Хибність ”, що неможливо, оскільки А – “ Хибність ”. Отже, α є тавтологією.

Слайд 18

Перед тим як розв’язувати проблему вирішення, інколи корисно спочатку перетворити формулу логіки

Перед тим як розв’язувати проблему вирішення, інколи корисно спочатку перетворити формулу логіки
висловлювань за допомогою рівносильних перетворень до деякої стандартної форми. Такими формами є диз’юнктивна нормальна форма (ДНФ) та кон’юнктивна нормальна форма (КНФ).

Означення 1.10. Елементарною кон’юнкцією (диз’юнкцією) називається кон’юнкція ( диз’юнкція) скінченного числа попарно різних логічних змінних, узятих із запереченням або без нього.

Наприклад, є елементарними кон’юнкціями, є елементарними диз’юнкціями, а або вже такими не будуть.

Слайд 19

Означення 1.11. Диз’юнктивною (кон’юнктивною) нормальною формою називається диз’юнкція (кон’юнкція) скінченного числа попарно

Означення 1.11. Диз’юнктивною (кон’юнктивною) нормальною формою називається диз’юнкція (кон’юнкція) скінченного числа попарно
різних елементарних кон’юнкцій (диз’юнкцій).

Наприклад, є ДНФ, – КНФ.

Довільну формулу алгебри висловлювань можна перетворити в одну з нормальних форм. Для цього необхідно виконати ряд кроків:
Усунути логічні зв’язки “Імплікація” та “Еквіваленція” за формулами .
Використати закон подвійного заперечення та закони де Моргана для перенесення знака заперечення безпосередньо до атомів.
Використати відповідні закони дистрибутивності.

Имя файла: TA&Ml_ukr_1.pptx
Количество просмотров: 23
Количество скачиваний: 0