Хід заняття

Задача 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 за виключенням тотожно хибних.

Поиск по сайту: