- •Лабораторні заняття з дисципліни «Математична логіка»
- •Лабораторна робота1.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота2.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота3.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота4.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота5.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота6.
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота7.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота8.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Лабораторна робота9.
- •Короткі теоретичні відомості
- •Хід заняття
- •Лабораторна робота10.
- •Короткі теоретичні відомості
- •Застосування булевих функцій до аналізу і синтезу релейно-контактних схем
- •Хід заняття
- •Синтез релейно-контактних схем
- •Задачі для самостійного розв’язування
- •Лабораторна робота11.
- •1. Що таке дднф?
- •2. Як будується дкнф?
- •3. Що таке поліном Жегалкіна? Основний теоретичний матеріал
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Домашнє завдання
- •Лабораторна робота12.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Домашнє завдання
- •Лабораторна робота13.
- •Короткі теоретичні відомості
- •Хід заняття
- •Задачі для самостійного розв’язування
- •Домашнє завдання
- •Лабораторна робота14.
- •Методичні вказівки до виконання контрольної роботи
- •Використана література
- •Випуск № 217
Лабораторна робота8.
Тема: Знаходження наслідків з посилок.
Мета: Сформувати вміння та навички знаходження всіх нерівносильних формул-наслідків з формул-посилок.
План
Методи знаходження всіх формул, що є логічними наслідками даної сукупності формул-посилок.
Короткі теоретичні відомості
При розв’язуванні задач на знаходження всіх нерівносильних формул-наслідків з формул-посилок спираються на наступну теорему.
Теорема. Пропозиційна формула B(X1, X2, …,Xn), що не є тавтологією, тоді і тільки тоді буде логічним наслідком пропозиційних формул A1, A2, …, Am , не всі з яких є тавтологіями і також залежні від змінних X1, X2, …,Xn , коли всі досконалі диз’юнктивні одночлени з розкладання формули B в ДКНФ входять до ДКНФ формули A1Ù A2 Ù…Ù Am.
Ця теорема визначає правило для відшукання всіх (нерівносильних) формул, які є логічними наслідками формул-посилок A1, A2, …, Am:
скласти кон’юнкцію посилок A1Ù A2 Ù…Ù Am;
знайти ДКН-форму формули A1Ù A2 Ù…Ù Am;
виписати всі досконалі диз’юнктивні одночлени ДКНФ, а також усілякі можливі кон’юнкції цих одночленів по 2, по 3 і т. д., надавши їм більш зручну рівносильну форму.
Хід заняття
Задача 1. Знайти всі нерівносильні між собою і не тотожно істинні формули алгебри висловлень, які є логічними наслідками наступних формул (посилок):
X®(YÚZ), Z®Y
Розв’язування.
Об'єднуємо висловлення знаком кон'юнкцiї:
(X®(YÚZ))Ù(Z®Y)
Виписуємо ДКНФ форму даної формули. Побудувати ДКНФ для формули алгебри висловлень, якщо вона не є тавтологією, можна двома способами. Або за допомогою рівносильних перетворень, або за допомогою її таблиці істинності. Виберемо рівносильні перетворення:
(X®(YÚZ))Ù(Z®Y) =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
(ØXÚYÚZ)Ù(Z®Y) =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
(ØXÚYÚZ)Ù(ØZÚY) =
Закон нуля вiдносно диз'юнкцiї (14°)
(ØXÚYÚZ)Ù(YÚØZÚ0) =
Вираження нуля через кон'юнкцiю та заперечення (15°)
(ØXÚYÚZ)Ù(YÚØZÚXÙØX) =
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
(ØXÚYÚZ)Ù(YÚ(ØZÚX)Ù(ØZÚØX)) =
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
(ØXÚYÚZ)Ù(XÚYÚØZ)Ù(ØXÚYÚØZ)
ДКНФ для формули (X®(YÚZ))Ù(Z®Y)
(XÚYÚØZ)Ù(ØXÚYÚZ)Ù(ØXÚYÚØZ)
Логічними наслідками з даних посилок будуть всі досконалі диз’юнктивні одночлени, які входять до отриманої ДКНФ, а також усілякі можливі кон’юнкції цих одночленів по 2, по 3 і т. д. Виписуємо формули, які при цьому утворюються, надавши їм більш зручну рівносильну форму:
1. (ØXÚYÚZ) º (X®Y)ÚZ
Спрощення формули:
(ØXÚYÚZ) =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
(X®Y)ÚZ
2. (XÚYÚØZ) º XÚ(Z®Y)
Спрощення формули:
(XÚYÚØZ) =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
XÚ(Z®Y)
3. (ØXÚYÚØZ) º Z®(X®Y)
Cпрощення формули:
(ØXÚYÚØZ) =
Вираження iмплiкацii через диз'юнкцiю та заперечення (21°)
(X®Y)ÚØZ =
Вираження iмплiкацii через диз'юнкцiю та заперечення (21°)
Z®(X®Y)
4. (XÚYÚØZ)Ù(ØXÚYÚZ) º (Z«X)ÚY
Cпрощення формули:
(XÚØZÚY)Ù(ØXÚZÚY) =
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
(XÚØZ)Ù(ØXÚZ)ÚY =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
(Z®X)Ù(ØXÚZ)ÚY =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
(Z®X)Ù(X®Z)ÚY =
Вираження еквiваленцiї через iмплiкацiю та кон'юнкцiю (25°)
(Z«X)ÚY
5. (XÚYÚØZ)Ù(ØXÚYÚØZ) º Z®Y
Cпрощення формули:
(XÚYÚØZ)Ù(ØXÚYÚØZ) =
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
(XÙØX)ÚYÚØZ =
Вираження нуля через кон'юнкцiю та заперечення (15°)
(0)ÚYÚØZ =
Закон нуля вiдносно диз'юнкцiї (14°)
YÚØZ =
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
Z®Y
6. (ØXÚYÚZ)Ù(ØXÚYÚØZ) º X®Y
Cпрощення формули:
(ØXÚYÚZ)Ù(ØXÚYÚØZ) =ØXÚYÚZÙØZ =ØXÚYÚ0 =ØXÚY = X®Y
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
Вираження нуля через кон'юнкцiю та заперечення (15°)
Закон нуля вiдносно диз'юнкцiї (14°)
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
7. (XÚYÚØZ)Ù(ØXÚYÚZ)Ù(ØXÚYÚØZ) º ZÚX®Y
Cпрощення формули:
(XÚYÚØZ)Ù(ØXÚYÚZ)Ù(ØXÚYÚØZ) =(XÚYÚØZ)Ù(ØXÚYÚZÙØZ) =
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
Вираження нуля через кон'юнкцiю та заперечення (15°)
(XÚYÚØZ)Ù(ØXÚYÚ0) = (XÚØZÚY)Ù(ØXÚY) =(XÚØZ)ÙØXÚY =
Закон нуля вiдносно диз'юнкцiї (14°)
Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)
Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)
(XÙØX)ÚØZÙØXÚY =(0)ÚØZÙØXÚY =ØZÙØXÚY =Ø(ZÚX)ÚY = ZÚX®Y
Вираження нуля через кон'юнкцiю та заперечення (15°)
Закон нуля вiдносно диз'юнкцiї (14°)
Закон де Моргана для диз'юнкцiї (10°)
Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)
Логiчними наслiдками для даних посилок будуть наступнi формули:
1. (X®Y)ÚZ
2. XÚZ®Y)
3. Z®(X®Y)
4. (Z«X)ÚY
5. Z®Y
6. X®Y
7. ZÚX®Y
