Хід заняття

Задача 1. Довести, що відношення рівносильності є відношенням еквівалентності.

Задача 2.Вивести наступні рівносильності із зазначених (при цьому поряд із зазначеною рівносильністю можуть бути використані інші рівносильності, крім виведеної, і, можливо, деякі твердження типу: якщо A º B, то ØA ºØB):

Задача 3. Довести, що пропозиційні формули, що містять тільки символ «, або, інакше кажучи, формули у мові{«} є тавтологією тоді і тільки тоді, коли кожна змінна входить до неї парне число разів.

Задача 4. Довести, що ніяка пропозиційна формула у мові {Ù, Ú} не є: 1) тавтологією; 2) суперечністю.

Задача 5.Наступну формулу перетворіть рівносильним чином так, щоб вона містила тільки операції Ø, Ú, Ù і, щоб заперечення відносились тільки до пропозиційних змінних і не стояло б перед дужками:

(XÚY) « (ØX® Z)

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

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

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

XÚY«ØØXÚZ =

Закон подвiйного заперечення (1°)

XÚY«XÚZ =

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

(XÚY®XÚZ) Ù (ZÚX®YÚX) =

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

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

Закон де Моргана для диз'юнкцiї (10°)

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

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

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

Закон де Моргана для диз'юнкцiї (10°)

(ØXÙØYÚXÚZ)Ù(ØZÙØXÚYÚX)

Задача 6. Проводячи рівносильні перетворення з використанням основних рівносильностей, доведіть, що формула є тавтологією:

(P®Q) ® ((P® (Q® R)) ® (P® R))

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

(P®Q) ® ((P® (Q® R)) ® (P® R))

Покажемо, що ця формула рівносильна 1 (істинному висловленню):

(P®Q)®((P®(Q®R))®(P®R)) =

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

(P®Q)®((P®(Q®R))® ØPÚR) =

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

(P®Q)®((P®ØQÚR)® ØPÚR) =

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

(P®Q)®( ØPÚØQÚR®ØPÚR) =

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

(P®Q)® Ø (ØPÚØQÚR)Ú ØPÚR =

Закон де Моргана для диз'юнкцiї (10°)

(P®Q)®Ø(ØPÚØQ) ÙØRÚØPÚR =

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

ØPÚQ®Ø(ØPÚØQ) ÙØRÚØPÚR =

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

Ø(ØPÚQ)ÚØ(ØPÚØQ) ÙØRÚØPÚR =

Закон де Моргана для диз'юнкцiї (10°)

ØØPÙØQÚØ(ØPÚØQ)ÙØRÚØPÚR =

Закон подвiйного заперечення (1°)

PÙØQÚØ(ØPÚØQ)ÙØRÚØPÚR =

Закон де Моргана для диз'юнкцiї (10°)

PÙØQÚØØPÙØØQÙØRÚØPÚR =

Закон подвiйного заперечення (1°)

PÙØQÚPÙØØQÙØRÚØPÚR =

Закон подвiйного заперечення (1°)

PÙØQÚPÙQÙØRÚØPÚR =

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

PÙØQÚPÙQÙØRÚRÚØP =

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

PÙØQÚ(PÙQÚR)Ù(ØRÚR)ÚØP =

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

PÙØQÚ(PÙQÚR)Ù(1)ÚØP =

Закон одиницi вiдносно кон'юнкцiї (13°)

PÙØQÚPÙQÚRÚØP =

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

PÙ(ØQÚQ)ÚRÚØP =

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

PÙ(1)ÚRÚØP =

Закон одиницi вiдносно кон'юнкцiї (13°)

PÚRÚØP =

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

PÚØPÚR =

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

1ÚR =1

Закон одиницi вiдносно диз'юнкцiї (17°)

Задача 7. Застосовуючи рівносильні перетворення, приведіть наступну формулу до можливо більш простої форми:

Ø((PÚQ) Ù (PÙ ØR))

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

Для того щоб привести дану формулу до можливо більш простої форми, необхідно знайти логічно еквівалентну їй формулу, яка містить менше число символів:

Ø ((PÚQ)Ù(PÙØR)) =

Закон де Моргана для кон'юнкцiї(9°)

Ø (PÚQ)Ú Ø (PÙØR) =

Закон де Моргана для кон'юнкцiї (9°)

Ø (PÚQ)Ú ØPÚØØR =

Закон подвiйного заперечення (1°)

Ø (PÚQ)Ú ØPÚR =

Закон де Моргана для диз'юнкцiї (10°)

ØPÙØQÚØPÚR =

Закон поглинання вiдносно кон'юнкцiї (27°)

ØpÚR

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

(X®Y) Ù (Y®X) Ù ((XÙ ØY) (ØXÙ Y))

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

(X®Y) Ù (Y®X) Ù ((XÙ ØY) (ØXÙ Y))

Покажемо, що ця формула рівносильна 0 (хибному висловлюванню):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закон подвiйного заперечення (1°)

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

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

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

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

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

Закон подвiйного заперечення (1°)

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

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

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

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

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

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

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

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

0Ù(ØXÙY)Ù0 =

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

0Ù0 =0

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

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