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

1.1. Випишіть всі можливі підформули кожної з наступних формул (згідно до домовленості зовнішні дужки у формул опущені):

1. ((A Ù B) «C)®ØD

2. (A Ù (ØB®C)) Ú((ØA «C) ÙØB)

3. ((A «B) ÙØC) ® (((AÚB) ® A) ®ØC)

4. ((AÚB) ÚØC) Ù (ØAÚ (ØBÚC))

5. (A®B) ® ((A® ØB) ® (AÙB))

6. ((A®B) Ù (C®D)) ® (ØBÚD)

7. (A®B) ® ((A® ØB) ®ØB)

8. (A ® (B ÙØC)) « (AÙ (B ® C))

9. ØAÚ (B « ((AÙB) ÙØC))

10. ((C ÚB) ÙA) ® (((CÚA) ® B) « (A «B))

11. ((AÚ (B ®ØC)) ÚD) Ù (ØDÚ (ØBÚC))

12. ((A® ØD) ÚB) ® ((C «ØD) ® (ØAÙC))

13. ((A®B) Ù ((ØAÚ (ØBÚC)) ®D)) ® (ØBÚD)

14. B« ((A®ØB) ® Ø (( ØA« C) ÙØB))

15. ((D® ((C ÚB) ÙA)) Ù (CÙA)) ® (ØBÚD)

1.2. Складіть таблиці істинності для наступних формул і вкажіть, які з формул є виконуваними, які спростовними, які тотожно істинними (тавтологіями) і які тотожно хибними (запереченнями):

1. (P®Q) ®((P®ØQ) ®ØP)

2. (PÙ (QÚØP)) Ù ((ØQ®P) ÚQ)

3. ((PÙØQ) ®Q) ® (P®Q)

4. ((PÚØQ) ®Q) Ù (ØPÚQ)

5. (P®Q) Ú (P® (QÙP))

6. (ØP®Ø (QÙP)) ® (PÚR)

7. ((PÙØQ) ®Q) ® (P®Q)

8. (P® (Q® R)) ® (P® Q)

9. (PÙ (QÚØP)) Ù ((ØQ®P) ÚQ)

10. (Q® (PÙR)) ÙØ (( PÚR) ® Q)

11. (PÙQ) ® ((RÚQ) ® (QÙØQ))

12. ((QÙR) ® (Q®Ø P)) ®ØQ

13. ((PÚQ) ÚR) ® ((PÚQ) Ù (PÚR))

14. (PÚQ) ® ((QÚØR) Ù (RÚP))

15. (PÚQ) ® ((ØPÙQ) Ú (PÙØQ))

1.3. Складіть таблиці істинності для наступних формул:

1. a)

б)

2. а)

б)

3. а)

б)

4. а)

б)

5. а)

б)

6. а)

б)

7. а)

б)

8. а)

б)

9. а)

б)

10. а)

б)

11. а)

б)

12. а)

б)

13. а)

б)

14. а)

б)

15. а)

б)

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

Тема: Тавтології алгебри висловлень.

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

План

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

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

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

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

Перелічимо деякі основні тавтології. Будемо писати |= A для позначення того, що пропозиційна формула А є тавтологія.

(I)      |=        (закон виключеного третього)

(II)    |=   (закон подвійного заперечення)

(III)    |=   (закони ідемпотентності)

(IV)    |=   

(V)     |= (VI)    |=

(VII)   |=   (закони комутативності)

(VIII) |=   

(IX)    |=   (закони асоціативності)

(X)     |=  

(XI)    |=    (закони дистрибутивності)

(XII)   |=

(XIII)  |=   (закони де Моргана)

(XIV)  |=

(XV)   |= (закон контрапозиції)

(XVI)  |= (закон транзитивності імплікації)

(XVII) |=   (закон непрямого доказу)

(XVIII)|= (закон розбору випадків)

(XIX)  |= (закон транзитивності еквіваленції)

(XX)    |= (закон протилежності)

(XXI)   |= , |=   (вираження 1 через Ø, Ú і ®)

(XXII)  |= , |= (вираження 0 через Ø, Ù і Ú,®)

(XXIII) |= (вираження ® через Ø і Ú)

(XXIV) |= (вираження « через Ù і ®)

(XXV)  |=   (вираження Ù через Ø і ®)

(XXVI) |= (вираження Ú через Ø і ®)