- •Мова логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Інтерпретації формули логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Еквівалентні формули логіки висловлень. Нормальні форми
- •Контрольні питання
- •Задачі та вправи
- •Логічне слідування
- •Контрольні питання
- •Задачі та вправи
- •Методи перевірки тотожної хибнОсті й тОтожної істинНості формул логіки висловлень
- •Метод перевірки суперечності й тавтологічності формул шляхом зведення до диз’юнктивної та кон’юнктивної нормальної форми
- •Контрольні питання
- •Метод Девіса й Патнема
- •Контрольні питання
- •Метод резолюцій
- •Контрольні питання
- •Метод двійкових діаграм рішень
- •Контрольні питання
- •Задачі та вправи
- •Приклади перевірки логічної правильності міркування
- •Перевірка правильності міркування за допомогою таблиць істинності
- •Перевірка правильності міркування шляхом побудови диз’юнктивної нормальної форми або кон’юнктивної нормальної форми
- •Перевірка правильності міркування методом Девіса й Патнема
- •Перевірка правильності міркування методом резолюцій
- •Перевірка правильності міркування шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Приклади перевірки сумісності сукупності тверджень
- •Перевірка сумісності сукупності тверджень за допомогою таблиць істинності
- •Перевірка сумісності сукупності тверджень шляхом побудови диз’юнктивної нормальної форми
- •Перевірка сумісності сукупності тверджень методом Девіса й Патнема
- •Перевірка сумісності сукупності тверджень методом резолюцій
- •Перевірка сумісності сукупності тверджень шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Скорочення, символи та позначення
- •Слова іншомовного походження
Контрольні питання
1. Як визначаються операції , , , , на множині істинносних значень {0,1}?
2. Що таке інтерпретація формули логіки висловлень?
3. Що таке модель формули логіки висловлень?
4. Яка формула називається тотожно істинною? тотожно хибною?
5. Що таке тавтологія?
6. За якої умови формула логіки висловлень має модель?
7. Скільки інтерпретацій має формула, що містить n попарно різних атомів?
8. Чи може формула логіки висловлень мати непарну кількість: а) моделей, б) інтерпретацій?
Задачі та вправи
І. Для кожної з поданих формул визначити, чи є вона: а) тотожно істинна, б) тотожно хибна, в) несуперечна. Обчислити кількість моделей для кожної з формул.
1. (P)P 2. P(PQ)
3. (PQ)Q 4. (PQ)P
5. (PQ)(QP) 6. (PQ)(QP)
7. PP 8. PP
9. P(PQ) 10. (P(QP))P
11. P(QP) 12. (PQ)(PQ)
13. P((PQ)) 14. (PQ)(PQ)
15. (PQ)(PQ) 16. (PQ)(PQ)
17. P(QR)(PQ)R 18. ((PQ)(PR)(QR))R
19. RS(PQS) 20. (PQ)R(SP).
ІІ. Нехай при інтерпретації h формула F приймає значення 1. Що можна сказати про істинносне значення формули F1 при інтерпретації h?
1. F = PQ, F1= PQPQ
2. F = PQ, F1= PQ
3. F = (PQ), F1= PQ
4. F = PQ, F1= (PQ)(PQ)
5. F = PQ, F1= PQ.
III. Довести твердження.
1. Формула F є тавтологією тоді й тільки тоді, коли формула F тотожно хибна.
2. Формула F тотожно хибна тоді й тільки тоді, коли формула F є тавтологією.
3. Якщо формула тотожно істинна, то вона несуперечна, але не навпаки.
4. Якщо формула суперечна, то вона не є тавтологією, але не навпаки.
IV. Записати детальне доведення твердження 1.
V. Нехай формули F1 та F1F2 є тотожно істинними. Довести, що F2 тотожно істинна.
VІ. Нехай формула F є тавтологією, A1, A2,…,An – атоми, що входять у F. Нехай формула F0 утворюється у результаті підстановки у F деяких формул F1,F2,…,Fn замість атомів A1,A2,…,An. Довести, що F0 є тавтологією.
Еквівалентні формули логіки висловлень. Нормальні форми
Формули F1 й F2 називаються еквівалентними, або рівносильними (позначається F1 = F2 ), якщо істинносні значення F1 й F2 збігаються при кожній інтерпретації F1 й F2.
Можна показати, що виконуються такі співвідношення (символи 1, 0 означають відповідно тотожно істинну й тотожно хибну формули):
1) F1 F2 = (F1F2) (F2F1);
2) F1 F2 = F1 F2;
3) F1 F2 = F2 F1; F1 F2 = F2 F1; (закони комутативності)
4) F1 (F2 F3) = (F1 F2) F3; (закони
5) F1 (F2 F3) = (F1 F2) F3; асоціативності)
6) F1 (F2 F3) = (F1 F2) (F1 F3); (закони
7) F1 (F2 F3) = (F1 F2) (F1 F3); дистрибутивності)
8) F1 F1 = F1; F1 F1 = F1; (закони ідемпотентності)
9) F1 (F1 F2) = F1; F1 (F1 F2) = F1; (закони поглинання)
10) (F1 F2) = F1 F2; (F1 F2) = F1 F2;
11) (F1) = F1; 1=0; 0=1;
12) 1F1=1; 1 F1 = F1; 0 F1 =F1; 0F1=0, F1F1=0, F1F1=1.
Внаслідок законів асоціативності дужки у формулах виду F1 (F2 F3) або (F1 F2) F3, а також у F1 (F2 F3) або (F1 F2) F3 можна опускати й писати F1 F2 F3 та F1 F2 F3. Отже, якщо F1, F2, …, Fn – формули, nN+, будемо писати F1 F2 … Fn й F1 F2 … Fn замість F1 (F2 (… Fn)…) й F1 (F2 (… Fn)…). Вираз F1 … Fn (F1 … Fn) називається диз’юнкцією (кон’юнкцією) формул F1,…, Fn.
Літерою називається формула, що має вигляд A або A, де A – атом. Літера, що не містить знак “”, називається позитивною, інакше – негативною.
Формула F є у кон’юнктивній нормальній формі (кнф, або КНФ), якщо F=F1…Fn, де F1,…,Fn – формули, кожна з яких є літерою або диз’юнкцією літер, nN+.
Диз’юнкт є диз’юнкція літер або літера.
Надалі будемо іноді вважати вирази “множина літер” та “диз’юнкт” синонімами. Наприклад, QPR={Q,P,R}. Диз’юнкт, що містить r літер, називається r-літерним диз’юнктом. Однолітерний диз’юнкт називається одиничним диз’юнктом. Диз’юнкт, що не містить жодної літери, називається порожнім (пустим) диз’юнктом (позначається ). Оскільки не містить літер, які могли б бути істинними при якихось інтерпретаціях, то він є тотожно хибним.
Нехай A – атом. Будемо називати літери A та A контрарними, а множину {A, A} – контрарною парою.
Зауважимо, що диз’юнкт, який містить контрарну пару, є тавтоло-гією. Будемо називати такий диз’юнкт тавтологічним.
Нехай S – множина диз’юнктів. Будемо вважати, що множині S відповідає формула, яка є кон’юнкцією усіх диз’юнктів з S. За кнф виду F1…Fn побудуємо множину диз’юнктів {F1,…,Fn}. Отже, кнф будь-якої формули може бути подана у вигляді множини диз’юнктів, й навпаки, за множиною диз’юнктів може бути побудована формула у кон’юнктивній нормальній формі.
Непорожню множину диз’юнктів S будемо називати суперечною, якщо формула, що є кон’юнкцією усіх диз’юнктів з S, є суперечною. Порожня множина диз’юнктів несуперечна, оскільки вона не містить диз’юнктів, які б могли приймати значення 0 при якихось інтерпретаціях.
Формула F є у диз’юнктивній нормальній формі (днф, або ДНФ), якщо F=F1…Fn, де F1,…,Fn – формули, кожна з яких є літерою або кон’юнкцією літер, nN+.
Кон’юнкт є кон’юнкція літер або літера.
Наприклад, нехай P, Q, R – атоми. Тоді (PR)(QRP) є формула у диз’юнктивній нормальній формі. Для цієї формули F1 = PR, F2 = QRP; F1 є кон’юнкція літер P й R, а F2 є кон’юнкція літер Q, R, P. (QRP)(RQ) – формула у кон’юнктивній нормальній формі. Для цієї формули F1 = QRP, F2 = RQ; F1 – диз’юнкція літер Q, R, P, а F2 – диз’юнкція літер R та Q.
Твердження 2. Будь-яка формула логіки висловлень може бути перетворена у кнф та днф за допомогою співвідношень 1-12.
Дійсно, для перетворення формули у кнф або днф слід послідовно та за потребою застосувати: співвідношення 1) F1 F2 = (F1F2) (F2F1) для вилучення зв’язки , співвідношення 2) F1 F2 = F1 F2 для вилучення зв’язки , тотожність 11) (F1) = F1 для спрощення формули, співвідношення 10) (F1 F2) = F1 F2; (F1 F2) = F1 F2 для того, щоб перенести знак заперечення безпосередньо до атомів (зменшити область дії заперечення), закони комутативності, асоціативності та дистрибутивності, щоб побудувати кнф або днф, тотожності 8,9,12, щоб здійснити спрощення формули.
Розглянемо приклад. Побудуємо кон’юнктивну нормальну форму для формули Q(P(RS)). Використовуючи співвідношення 1-12, маємо: Q(P(RS))=Q(P(RS))=Q(P(RS))=(QP)(Q(R S))=(QP)(QR)(QS). Отже, кнф формули Q(P(RS)) є формула (QP)(QR)(QS).