Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Математична логіка.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
4 Мб
Скачать
☆

Лабораторна робота8.

Тема: Знаходження наслідків з посилок.

Мета: Сформувати вміння та навички знаходження всіх нерівносильних формул-наслідків з формул-посилок.

План

  • Методи знаходження всіх формул, що є логічними наслідками даної сукупності формул-посилок.

Короткі теоретичні відомості

При розв’язуванні задач на знаходження всіх нерівносильних формул-наслідків з формул-посилок спираються на наступну теорему.

Теорема. Пропозиційна формула B(X1, X2, …,Xn), що не є тавтологією, тоді і тільки тоді буде логічним наслідком пропозиційних формул A1, A2, …, Am , не всі з яких є тавтологіями і також залежні від змінних X1, X2, …,Xn , коли всі досконалі диз’юнктивні одночлени з розкладання формули B в ДКНФ входять до ДКНФ формули A1Ù A2 Ù…Ù Am.

Ця теорема визначає правило для відшукання всіх (нерівносильних) формул, які є логічними наслідками формул-посилок A1, A2, …, Am:

  1. скласти кон’юнкцію посилок A1Ù A2 Ù…Ù Am;

  2. знайти ДКН-форму формули A1Ù A2 Ù…Ù Am;

  3. виписати всі досконалі диз’юнктивні одночлени ДКНФ, а також усілякі можливі кон’юнкції цих одночленів по 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