- •Мова логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Інтерпретації формули логіки висловлень
- •Контрольні питання
- •Задачі та вправи
- •Еквівалентні формули логіки висловлень. Нормальні форми
- •Контрольні питання
- •Задачі та вправи
- •Логічне слідування
- •Контрольні питання
- •Задачі та вправи
- •Методи перевірки тотожної хибнОсті й тОтожної істинНості формул логіки висловлень
- •Метод перевірки суперечності й тавтологічності формул шляхом зведення до диз’юнктивної та кон’юнктивної нормальної форми
- •Контрольні питання
- •Метод Девіса й Патнема
- •Контрольні питання
- •Метод резолюцій
- •Контрольні питання
- •Метод двійкових діаграм рішень
- •Контрольні питання
- •Задачі та вправи
- •Приклади перевірки логічної правильності міркування
- •Перевірка правильності міркування за допомогою таблиць істинності
- •Перевірка правильності міркування шляхом побудови диз’юнктивної нормальної форми або кон’юнктивної нормальної форми
- •Перевірка правильності міркування методом Девіса й Патнема
- •Перевірка правильності міркування методом резолюцій
- •Перевірка правильності міркування шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Приклади перевірки сумісності сукупності тверджень
- •Перевірка сумісності сукупності тверджень за допомогою таблиць істинності
- •Перевірка сумісності сукупності тверджень шляхом побудови диз’юнктивної нормальної форми
- •Перевірка сумісності сукупності тверджень методом Девіса й Патнема
- •Перевірка сумісності сукупності тверджень методом резолюцій
- •Перевірка сумісності сукупності тверджень шляхом побудови двійкової діаграми рішень
- •Контрольні питання
- •Скорочення, символи та позначення
- •Слова іншомовного походження
Контрольні питання
1. Як перевірити правильність міркування за допомогою таблиць істинності?
2. Як перевірити правильність міркування методом: а) Девіса й Патнема, б) резолюцій?
3. Які нормальні форми формул логіки висловлень й яким чином можна використати, щоб перевірити правильність міркування?
Приклади перевірки сумісності сукупності тверджень
Розглянемо таку сукупність тверджень.
«Петро складе на “добре” екзамен з фізики тоді і тільки тоді, коли він не пропустить останню лекцію. Петро пропустить останню лекцію або не поїде на екскурсію до Рима. Якщо Петро не складе на “добре” екзамен з фізики, він не поїде на екскурсію до Рима. Петро складе на “добре” екзамен з фізики або поїде на екскурсію до Рима.»
Перевіримо сумісність цих тверджень, тобто перевіримо, чи можуть ці твердження бути одночасно істинними. Використаємо для цього формальні методи, описані вище.
Для перекладу речень мовою логіки висловлень спочатку проаналізуємо кожне твердження й виділимо у ньому прості висловлення. Кожне нове просте висловлення, яке зустрінемо при розборі тверджень, позначимо атомом. Маємо:
А – Петро складе на добре екзамен з фізики;
В – Петро пропустить останню лекцію;
С – Петро поїде на екскурсію до Риму.
Отже, подаємо дані твердження у вигляді формул:
A B, B C, (A C), A C.
Сукупність тверджень буде сумісною, якщо ці формули мають спільну модель, або формула F=(AB) (BC) (AC) (AC) має хоча б одну модель, тобто не є тотожно хибною. Отже, застосувавши описані вище методи для перевірки суперечності формули F, дістанемо відповідь.
Перевірка сумісності сукупності тверджень за допомогою таблиць істинності
Перевіримо суперечність формули F за допомогою таблиць істинності. Будуватимемо інтерпретації формули F й обчислюватимемо істинносне значення формули F при кожній інтерпретації. Якщо знайдеться інтерпретація, при якій F приймає значення 1, то F несуперечна, а тоді можна зробити висновок, що подана сукупність тверджень сумісна. Інтерпретації й результати обчислень подамо у вигляді таблиці. Обчислення будемо спрощувати, користуючись такою властивістю операції : якщо принаймні один операнд виразу XY має значення 0, то й вираз XY має значення 0. Отже, якщо формула F має вигляд F1…Fn (nN+), й при деякій інтерпретації h Fi (1i<n) приймає значення 0, то можна стверджувати, що F приймає значення 0 при h, не обчислюючи істинносні значення Fi+1,…,Fn при h.
A |
B |
C |
AB |
BC |
AC |
AC |
F |
0 0 0 0 1 |
0 0 1 1 0 |
0 1 0 1 0 |
0 0 1 1 1 |
1 1 1 |
1 0 1 |
0
1 |
0 0 0 0 1 |
Таким чином, знайдено інтерпретацію h (h(A)=1, h(B)=h(С)=0), при якій формула F приймає значення 1, отже, F несуперечна, а подана сукупність тверджень сумісна. Зауважимо, що ми не обчислювали значення формули F при кожній з восьми інтерпретацій, що має дана формула, адже нам потрібно лише знати, чи має формула F модель. Отже, як тільки модель формули F знайдено, обчислення доцільно припинити.