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

Тема: Рівносильність формул.

Мета: Засвоїти поняття рівносильності формул. Познайомити з основними рівносильностями алгебри висловлень. Сформувати вміння та навички застосування основних рівносильностей для перетворення формул.

План

• Рівносильність формул алгебри висловлень.

• Основні рівносильності алгебри висловлень.

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

Дві пропозиційні формули А (Х₁, Х₂, ..., Х_n) і В (Х₁, Х₂, ..., Х_n) назвемо рівносильними (або еквівалентними), якщо для будь-яких наборів значень змінних Х₁, Х₂, ..., Х_n вони приймають однакові значення. У цьому випадку будемо писати А (Х₁, Х₂, ..., Х_n) º В (Х₁, Х₂, ..., Х_n) (або А º В ). Символ “º” не є символом операції алгебри висловлень, а означає певне відношення між формулами, які знаходяться ліворуч та праворуч від символу “º”.

Беручи до уваги означення операції “«”, а також означення тавтології і рівносильності, можна зробити висновок, що кожну тавтологію, в якої головна операція еквіваленція, можна записати як рівносильність двох відповідних формул. Інакше кажучи, ця тавтологія породжує певну рівносильність. Так, тавтології (ІІ) |=ØØp«p (закон подвійного заперечення) відповідає рівносильність (1°) ØØAºA; законам ідемпотентності (ІІІ) і (ІV) відповідають рівносильності (10°) і (11°). Зазначимо, що кожна з таких рівносильностей отримує назву відповідної тавтології.

Перелічимо найважливіші рівносильності алгебри висловлень де A, B і C є будь-якою пропозиційною формулою:

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

( 2°)

(3°) (закони комутативності)

(4°)

( 5°) (закони асоціативності)

(6°)

(7°) (закон дистрибутивності Ù відносно Ú)

(8°) (закон дистрибутивності Ú відносно Ù)

( 9°) (закони де Моргана)

(10°)

( 11°) (закони ідемпотентності)

(12°)

(13°)

(14°)

(15°)

(16°)

(17°) (властивості 0 та 1)

(18°)

(19°)

(20°)

(21°)

(22°)

(23°) (вираження одних операцій через інші)

(24°)

(25°)

(26°) (закони поглинання)

(27°)

Використовуючи основні рівносильності алгебри висловлень, можемо від однієї формули переходити до рівносильної їй формули. Так само в будь-якій пропозиційній формулі можна замінити довільну її частину, що є пропозиційною формулою, рівносильною і при цьому одержати пропозиційну формулу, рівносильну даній. Такий перехід називається рівносильним перетворенням вихідної формули. У тих питаннях, у яких дану пропозиційну формулу можна замінити на рівносильну їй, основні рівносильності алгебри висловлень дозволяють приводити формули до більш простого (по числу символів) або більш зручного вигляду.

Хід заняття

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