Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Хід заняття



Задача 1. Знайти всі нерівносильні між собою і не тотожно хибні формули алгебри висловлень, для яких наступна формула є логічним наслідком (за виключенням власне даної формули):

X«Y

 

Розв’язування.

Знайдемо досконалу кон’юнктивну нормальну форму (ДКНФ) для даної формули. Побудувати ДКНФ для формули алгебри висловлень, якщо вона не є тавтологією, можна двома способами. Або за допомогою рівносильних перетворень, або за допомогою її таблиці істинності. Виберемо рівносильні перетворення:

X«Y =(X®Y)Ù(Y®X) =(ØXÚY)Ù(Y®X) =(ØXÚY)Ù(ØYÚX)

Вираження еквiваленцiї через iмплiкацiю та кон'юнкцiю (25°)

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

ДКНФ для формули алгебри висловлень X « Y: (ØXÚY)Ù(ØYÚX).

Досконалими диз’юнктивними одночленами, які не входять до ДКНФ являються (XÚY) і (ØXÚØY). Тоді шуканими посилками для даної формули являються формули X«Y Ù(XÚY), X«Y Ù(ØXÚØY) i X«Y Ù(XÚY)Ù(ØXÚØY).

За допомогою рівносильних перетворень перейдемо до більш простих формул:

1. X«Y Ù (XÚY) º YÙX

Cпрощення формули:

((ØXÚY)Ù(ØYÚX))Ù(XÚY) =

Закон комутативностi диз'юнкцiї (3°)

(ØXÚY)Ù(XÚØY)Ù(XÚY) =

Закон дистрибутивностi диз'юнкцiївiдносно кон'юнкцiї (8°)

(ØXÚY)Ù(XÚØYÙY) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(ØXÚY)Ù(XÚ0) =

Закон нуля вiдносно диз'юнкцiї (14°)

(ØXÚY)Ù(X) =

Закон дистрибутивностi кон'юнкцii вiдносно диз'юнкцiї (7°)

ØXÙXÚYÙX =

Вираження нуля через кон'юнкцiю та заперечення (15°)

0ÚYÙX =

Закон нуля вiдносно диз'юнкцiї (14°)

YÙX

2. X«Y Ù (ØXÚØY)ºØXÙØY

Cпрощення формули:

((ØXÚY)Ù(ØYÚX))Ù(ØXÚØY) =

Закон комутативностi диз'юнкцiї (3°)

(ØXÚY)Ù(XÚØY)Ù(ØXÚØY) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(ØXÚY)Ù(XÙØXÚØY) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(ØXÚY)Ù(0ÚØY) =

Закон нуля вiдносно диз'юнкцiї (14°)

(ØXÚY)Ù(ØY) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

ØXÙØYÚYÙØY =

Вираження нуля через кон'юнкцiю та заперечення (15°)

ØXÙØYÚ0 =

Закон нуля вiдносно диз'юнкцiї (14°)

ØXÙØY

3. X«Y Ù (XÚY)Ù(ØXÚØY) º 0

Cпрощення формули:

((ØXÚY)Ù(ØYÚX))Ù(XÚY)Ù(ØXÚØY) =

Закон комутативностi диз'юнкцiї (3°)

(ØXÚY)Ù(XÚØY)Ù(XÚY)Ù(ØXÚØY) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(ØXÚY)Ù(XÚØYÙY)Ù(ØXÚØY) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(ØXÚY)Ù(XÚ0)Ù(ØXÚØY) =

Закон нуля вiдносно диз'юнкцiї (14°)

(ØXÚY)Ù(X)Ù(ØXÚØY) =

Закон комутативностi кон'юнкцiї (2°)

(ØXÚY)Ù(ØXÚØY)ÙX =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї(8°)

(ØXÚYÙØY)ÙX =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(ØXÚ0)ÙX =

Закон нуля вiдносно диз'юнкцiї (14°)

(ØX)ÙX =0

Вираження нуля через кон'юнкцiю та заперечення (15°) (остання посилка являє собою тотожно хибну формулу, з якої логічно слідує люба формула алгебри висловлень, в тому числі і X«Y).

Люба формула, для якої формула X«Y являється логiчним наслiдком, рiвносильна або формулі YÙX, або формулі ØXÙØY за виключенням тотожно хибних.