- •Мова логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Інтерпретації формули логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Еквівалентні формули логіки висловлень. Нормальні форми
- •Контрольні питання
- •Задачі та вправи
- •Логічне слідування
- •Контрольні питання
- •Задачі та вправи
- •Методи перевірки тотожної хибнОсті й тОтожної істинНості формул логіки висловлень
- •Метод перевірки суперечності й тавтологічності формул шляхом зведення до диз’юнктивної та кон’юнктивної нормальної форми
- •Контрольні питання
- •Метод Девіса й Патнема
- •Контрольні питання
- •Метод резолюцій
- •Контрольні питання
- •Метод двійкових діаграм рішень
- •Контрольні питання
- •Задачі та вправи
- •Приклади перевірки логічної правильності міркування
- •Перевірка правильності міркування за допомогою таблиць істинності
- •Перевірка правильності міркування шляхом побудови диз’юнктивної нормальної форми або кон’юнктивної нормальної форми
- •Перевірка правильності міркування методом Девіса й Патнема
- •Перевірка правильності міркування методом резолюцій
- •Перевірка правильності міркування шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Приклади перевірки сумісності сукупності тверджень
- •Перевірка сумісності сукупності тверджень за допомогою таблиць істинності
- •Перевірка сумісності сукупності тверджень шляхом побудови диз’юнктивної нормальної форми
- •Перевірка сумісності сукупності тверджень методом Девіса й Патнема
- •Перевірка сумісності сукупності тверджень методом резолюцій
- •Перевірка сумісності сукупності тверджень шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Скорочення, символи та позначення
- •Слова іншомовного походження
Контрольні питання
1. Що таке розгалуження?
2. Що таке перевірний вираз?
3. Що таке нормальна форма розгалуження?
4. Які формули логіки висловлень можна подати у нормальній формі розгалуження?
5. Як подати логічні зв’язки , , , , за допомогою оператору розгалуження й логічних констант 0 та 1?
6. Що таке двійкова діаграма рішень?
7. Яка двійкова діаграма рішень називаєтья: а) упорядкованою, б) приведеною?
8. Як побудувати формулу у нфр за ПУДДР?
9. Як визначити за ПУДДР, побудованою за формулою F, чи є F: а) тотожно істинною, б) тотожно хибною?
Задачі та вправи
І. Перевірити суперечність поданих формул: а) шляхом побудови днф, б) методом Девіса й Патнема, в) методом резолюцій, д) шляхом побудови ПУДДР.
1. (PQ)QP 2. (PQ)(PQ)(RQ)(RQ)
3. (PQ)Q(PQR) 4. (PQR)(PQ)PRT
5. PQRS(PQRS) 6. (PQ)(PQ)(QR)(QR)
7. (PQ)(RQ)RQ 8. (PQ)(PQ)(RQ)(RQ)
9. (ABCD)(DEG)(AG)
10. (PQ)(QR)(RS)(RP)(SQ)(QR)
11. (A(BC))(DEG)(G(HI))(CEH)
12. (AB)(CD)(BD)(CA)(EG)(GD)(EE)
13. (ABC)(DBE)((GA)HI)((HI)GD)(CE).
ІІ. Побудувати приклади суперечних множин диз’юнктів, для яких не існує вхідних виведень порожнього диз’юнкту.
IIІ. Знайти усі моделі формули F шляхом побудови: а) днф, б) ПУДДР.
1. (С(А(ВС)))(ВС) 2. (A(BC))(CA)
3. (А(ВС)В) 4. (А(В(СА)))
5. С(((АВ)С)) 6. А(С(ВА))
7. (С(А(ВС)))А 8. (А(ВС))(АС)
9. (АВ)((СА)В) 10. (В(А(СА)))А.
IV. Нехай F – формула логіки висловлень. Як, використавши метод Девіса й Патнема, дізнатися, чи є F тавтологією? Чи можна встановити тавтологічниість формули F за допомогою методу резолюцій?
V. Чи однаковими є ПУДДР, побудовані за формулою (А1В1)(А2В2) з використанням різних лінійних порядків на множині атомів (A1<B1<A2<B2 та А1<А2<В1<В2 відповідно)?
VI. Нехай S – множина диз’юнктів, до якої застосовне правило тавтології методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна S1 суперечна.
VII. Нехай S – множина диз’юнктів, до якої застосовне правило розщеплення методу Девіса й Патнема, й S1 та S2 – результат застосування цього правила до S. Довести, що S суперечна S1 та S2 суперечні.
VIII. Нехай S – множина диз’юнктів, до якої застосовне правило чистих літер методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна S1 суперечна.
IX. Нехай S – множина диз’юнктів, до якої застосовне правило однолітер-них диз’юнктів методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна S1 суперечна.
Х. Нехай існує доведення несуперечності формули F методом Девіса й Патнема. Сформулюйте правило побудови моделі F за цим доведенням.
Приклади перевірки логічної правильності міркування
Розглянемо приклади використання описаних вище методів для перевірки логічної правильності міркування. Нехай задано міркування:
«Ліворуч підеш – коня загубиш, праворуч підеш – загибель знайдеш, прямо підеш – у неволю потрапиш. Але йти можна або ліворуч, або праворуч, або прямо. Отже можна або загинути, або коня загубити, або потрапити у неволю.»
Щоб перевірити його правильність формальними методами, треба спочатку звести задачу перевірки правильності міркування, записаного природною мовою, до задачі перевірки логічного слідування для формул. Для цього необхідно перекласти твердження-посилки та твердження-висновок заданого міркування мовою логіки висловлень, тобто подати їх як формули логіки висловлень. Щоб здійснити переклад, проаналізуємо твердження у заданому міркуванні й виділимо у кожному з них прості висловлення. Для кожного простого висловлення уведемо коротке позначення – атом. Наприклад, розглянемо перше твердження нашого міркування: «Ліворуч підеш – коня загубиш, праворуч підеш – загибель знайдеш, прямо підеш – у неволю потрапиш». З метою виділення у ньому простих висловлень розглянемо його як речення й виконаємо його розбір. Це речення – складносурядне, отже, можна розбити його на більш короткі речення:
Ліворуч підеш – коня загубиш.
Праворуч підеш – загибель знайдеш.
Прямо підеш – у неволю потрапиш.
Тепер можна продовжувати аналіз, розглядаючи кожне з побудованих речень окремо. Оскільки наші речення є висловленнями, ми можемо допустити їх переформулювання до такої міри, щоб суть висловлення не змінювалася. Отже, замість, скажімо, висловлення «Ліворуч підеш – коня загубиш» можемо розглядати висловлення «Якщо ліворуч підеш, то коня загубиш» Це речення – складнопідрядне, його складові – речення «ліворуч підеш» та «коня загубиш» – є простими висловленнями, що з’єднуються за допомогою звороту «якщо …, то». Уведемо атоми, що позначатимуть щойно виділені прості висловлення. Маємо:
А – ліворуч підеш,
B – коня загубиш.
Пам’ятаючи про те, що аналогом «якщо …, то» служить у мові логіки висловлень зв’язка , будуємо переклад твердження «Ліворуч підеш – коня загубиш» («Якщо ліворуч підеш, то коня загубиш») мовою логіки висловлень: АВ. Продовжуючи переклад решти тверджень нашого міркування, уводимо нові атоми для простих висловлень:
C – праворуч підеш,
D – загибель знайдеш,
G – прямо підеш,
H – у неволю потрапиш.
Використовуючи уведені символи та логічні зв’язки, побудуємо для кожного речення заданого міркування формулу логіки висловлень. При цьому враховуємо те, що логічна зв’язка є аналогом частки «не», зв’язка – аналогом сполучника «та», зв’язка – аналогом сполучника «або», зв’язка – аналогом звороту «якщо…, то…». Зрештою маємо такі формули:
AB, CD, GH, ACG, BDH.
Остання формула є перекладом твердження-висновку, а інші – перекладами тверджень-посилок заданого міркування. Отже, початкова задача (перевірки правильності заданого міркування) зводиться до перевірки того, чи є формула BDH логічним наслідком формул AB, CD, GH, ACG. Таким чином, замість початкової задачі (щодо тверджень) маємо таку задачу щодо формул логіки висловлень:
Чи виконується AB, CD, GH, ACG ╞═ BDH? (2)
Здійснивши зведення початкової задачі перевірки правильності міркування до задачі перевірки логічного слідування (2), можемо застосовувати викладені вище формальні методи для розв’язання задачі (2). Зазначимо, що метод Девіса й Патнема, метод резолюцій та метод ДДР застосовні для розв’язання задач великого обсягу, застосовність решти методів, що розглядаються, обмежене.