Задачі для самостійного розв’язування. Тема: Спрощення систем висловлень

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

Тема: Спрощення систем висловлень.

Мета: Сформувати вміння та навички застосування рівносильних перетворень для спрощення систем висловлень.

 

План

¨ Спрощення систем висловлень.

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

Спрощення сукупності висловлень засновано на тому, що в залежності від умови задачі, необхідно скласти кон’юнкцію або диз’юнкцію вихідних висловлень, а потім привести її еквівалентними перетвореннями до кон’юнкції або диз’юнкції більш простого виду, тим самим можна отримати більш просту систему висловлень, еквівалентну до даної.

Хід заняття

Задача 1. Спростити систему висловлень, якщо всі висловлення, що входять до системи, істинні. Спростити систему, це означає знайти логічно еквівалентну їй систему, що складається з меншої кількості не більш складних висловлень:

A®B, C®B, (BÙC)®A

 

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

Спрощення даної сукупності висловлень спирається на те, що кожне з висловлень буде істинним тоді і тільки тоді, коли істинна кон’юнкція всіх цих висловлень. Тому, склавши кон’юнкцію з даних висловлень і приводячи її еквівалентними перетвореннями до кон’юнкції більш простого виду, можна отримати більш просту систему висловлень, еквівалентну даній:

A®B,C®B,(BÙC)®A

Об'єднуємо висловлення знаком кон'юнкцiї.

(A®B)Ù(C®B)Ù((BÙC)®A) =

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

(A®B)Ù(C®B)Ù( ÚA) =

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

(A®B)Ù(C®B)Ù( Ú ÚA) =

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

(A®B)Ù(C®B)Ù( Ú ÚA) =

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

(A®B)Ù( ÚB)Ù( Ú ÚA) =

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

(A®B)Ù( ÚBÚ 0)Ù( Ú ÚA) =

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

(A®B)Ù( Ú BÚAÙ )Ù( Ú ÚA) =

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

(A®B)Ù =

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

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

ÚA) =

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

( ÚA) =

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

( ÚA) =

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

( ) =

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

( ) =

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

A) =

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

( ÚBÚC)Ù( Ú ÚB)Ù( ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

( ÚBÚC)Ù( Ú ÚB)Ù( ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

( ÚBÚC)Ù ( ÚBÚ )Ù( ÚBÚ ) Ù( ÚBÚA)Ù( Ú ÚA) =

Закон iдемпотентностi кон'юнкцiї (12°)

( Ú BÚC)Ù( ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

( ÚC ÚB)Ù( ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

(CÚ ÚB)Ù( ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

(CÚBÚ )Ù( ÚBÚ ) Ù( ÚBÚA)Ù( Ú ÚA) =

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

((CÚB)Ù( ÚB) Ú )Ù( ÚBÚA)Ù( Ú ÚA) =

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

((CÙ )ÚBÚ )Ù( ÚBÚA)Ù( Ú ÚA) =

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

((0)ÚB Ú )Ù ÚBÚA)Ù( Ú ÚA) =

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

(BÚ )Ù ( ÚBÚA)Ù( Ú ÚA) =

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

(BÚ )Ù(( ÚB)Ù( Ú ) ÚA) =

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

(BÚ )Ù( Ú BÙ ÚA) =

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

(BÚ )Ù( Ú0 ÚA) =

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

(BÚ )Ù( ÚA) =

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

(BÚ )Ù(C®A) =

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

(A®B)Ù(C®A)

Вихiдна система висловлень A®B,C®B,(BÙC)®A логiчно еквiвалентна наступнiй

A®B, C®A

Всі висловлення даної системи будуть істинні тоді і тільки тоді, коли будуть істинні висловлювання А®В і С®А.

Тому дана система висловлювань A®B,C®B,(BÙC)®A є логічно еквівалентною більш простій системі двох висловлень А®В,С®А.

Задача 2. Спростити систему висловлень, якщо відомо, що з висловлень, які входять до неї, що найменше одне з них істинне:

AÙBÙ , Ù , Ù()

 

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

AÙBÙ , Ù , Ù ( )

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

AÙBÙ , Ù , Ù ( )

Об'єднуємо висловлення знаком диз'юнкцiї

(A Ù B Ù )Ú(( ) Ù )Ú( Ù ) =

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

(A Ù B Ù )Ú(( ) Ù )Ú( Ù ( )) =

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

(A Ù B Ù )Ú(( B) Ù )Ú( Ù ( )) =

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

(A Ù B Ù )Ú((A Ù ) Ù )Ú( Ù ( )) =

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

(A Ù B Ù )Ú((A Ù ) Ù )Ú( Ù ( )) =

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

(A Ù B Ù )Ú((A Ù ) Ù )Ú( Ù ( Ù )) =

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

(A Ù B Ù ) Ú((A Ù ) Ù )Ú( Ù (B Ù )) =

Закон iдемпотентностi диз'юнкцiї (11°)

((A Ù B) Ù )Ú ((A Ù B) Ù )Ú((A Ù ) Ù ) Ú( Ù (B Ù )) =

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

((A Ù B) Ù )Ú(((A Ù B)Ú(A Ù )) Ù )Ú( Ù (B Ù )) =

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

((A Ù B) Ù )Ú((A Ù (BÚ )) Ù )Ú( Ù (B Ù )) =

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

((A Ù B) Ù )Ú((A Ù (1)) Ù )Ú( Ù (B Ù )) =

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

((A Ù B) Ù )Ú ((A) Ù )Ú( Ù (B Ù )) =

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

((A Ù B) Ù )Ú( Ù (B Ù ))Ú(A Ù ) =

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

((A Ù B) Ù )Ú(( Ù B) Ù ) Ú(A Ù ) =

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

(((A Ù B)Ú( Ù B)) Ù )Ú(A Ù ) =

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

(((AÚ ) Ù B) Ù )Ú(A Ù ) =

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

(((1) Ù B) Ù )Ú(A Ù ) =

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

((B) Ù )Ú(A Ù ) =

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

(A Ù )Ú(B Ù )

Вихiдна система висловлень A Ù B Ù ,( ) Ù , Ù ( ) логiчно еквiвалентна наступнiй

(A Ù ), (B Ù )

Таким чином, що найменше одне висловлення даної системи буде істинне тоді і тільки тоді, коли буде істинне одне із висловлень А Ù або В Ù . Тому дана система трьох висловлювань A Ù B Ù , ( ) Ù , Ù ( ) є логічно еквівалентною більш простій системі двох висловлень А Ù , В Ù .

Задачі для самостійного розв’язування

4.1. Спростіть наступні системи висловлень, якщо відносно них відомо, що всі висловлення, що входять до системи, істинні:

1. A®B, C®B, (BÙC)®A

2. C®(AÚB), (BÙC)®A, (AÙB)®C

3. A®(BÚC), B®(AÚC), (AÙB)®C

4. A®B, A®(BÚC), B®C

5. P®(QÚR), W®(SÚT), R®(QÚ ), (WÙT)®

6. W®(MÚS), R®T, ®T, M®(SÚW), P®(TÚR)

7. ®(BÚC), B®(), C®(AÚ )

8. A®(BÚC), (AÙC)®B,( Ù )®C

4.2. Спростіть наступні системи висловлень, якщо відносно них відомо, що з усіх висловлень, що входять до системи, що найменше одне з них істинне:

1. AÙBÙ , ()Ù , Ù()

2. (), ÙA, ÙC, ()

3. AÙBÙC, Ù Ù , AÙBÙ , ()

4. A®B, A®C, B®(AÙC)

5. XÙYÙZ, XÙ(), ()ÙZ,()ÙZ

6. XÙY, (), ()

7. ÙYÙZ, ,YÙZ

8. PÙR, (), QÙR, ÙQÙR