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


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

Хід заняття



Задача 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°)

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°)

(ØXÙY)Ù0 =

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

0Ù0 =0

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