Задания для самостоятельной работы

Лабораторная работа № 125.

Равносильность формул.

Цель работы. Изучить логические операции и основные равносильности алгебры логики, научиться преобразовывать формулы, используя основные равносильности и правила поглощения.

Логические операции

 - отрицание, Ú - дизъюнкция,  Ù (&) - конъюнкция,

«(~) - эквиваленция, ® - импликация

Приоритет операций:

 конъюнкция, дизъюнкция, эквиваленция и импликация

 

Таблица истинности

 

A	B		A Ú B	A & B	A «B	A ® B
0	0	1	0	0	1	1
0	1	1	1	0	0	1
1	0	0	1	0	0	0
1	1	0	1	1	1	1

 

 

Основные равносильности алгебры логики:

 

1.  º A                                         2. A & B º B & A

3. A Ú B º B Ú A                            4. (A & B) & C º A & (B & C)

5. (A Ú B) Ú C º A Ú (B Ú C)          6. A & (B Ú C) º (A & B) Ú (A & C)

7. A Ú (B & C) º (A Ú B) & (A Ú C)        8. A & A º A

9. A Ú A º A                                        10. (A & B) Ú A º A

11. (A Ú B) & A º A                            12. A & B º  Ú

13. A Ú B º  &                              14. A & 1 º A

15. A & 0 º 0                                       16. A Ú 1 º 1

17. A Ú 0 º A                                       18. A Ú  º 1

19. A &  º 0                                      20. A ® B º  Ú B

21. A «B º (A ® B) & (B ® A) º AB Ú

22. A Ú B º A Ú B

 

Студенты с четными номерами по списку группы выполняют 2, 4, 6, 8, 10 задания, с нечетными номерами выполняют задания 1, 3, 5, 7, 9.

Задание 1. Используя основные равносильности алгебры логики, упростить формулы:

1) ; 2) ; 3) ; 4) ;

5) ;   6) ;    7) ;

8) ;

9) .

 

Методические указания.

Пример 1.  Используя основные равносильности алгебры логики, а также равносильности    и ,

упростить формулу: .

Решение.

Ответ:

 

Логическую операцию конъюнкция в формулах алгебры логики можно опускать, т.е. выражение A&B можно записывать в виде АВ.

 

  Пример 2. Для заданного высказывания

1) построить таблицу истинности;

2) упростить высказывание, используя равносильные преобразования;

3) полученный результат проверить, построив для него таблицу истинности.

Решение.

1) Таблица истинности. Пусть

 

Х	Y	Z		YZ			U
0	0	0	1	0	0	1	1
0	0	1	1	0	0	1	1
0	1	0	1	0	0	0	0
0	1	1	1	1	1	0	1
1	0	0	0	0	1	0	1
1	0	1	0	0	1	0	1
1	1	0	0	0	1	1	1
1	1	1	0	1	1	1	1

 

2) Выполним равносильные преобразования, используя  и , имеем:

в последнем преобразовании для первого и третьего слагаемых использовали правило поглощения АВÚАºА, далее используем другое правило поглощения , получаем

 

Еще раз использовали правило поглощения.

3) Для полученного выражения построим таблицу истинности

 

Х	Y	Z
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	0	0	0
0	1	1	0	0	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	1	1
1	1	1	0	1	1

 

Результирующие (последние) столбцы в двух таблицах совпали, следовательно, выполненные преобразования верны.

 

Задания для самостоятельной работы

Для заданного логического выражения (высказывания):

1) построить таблицу истинность;

2) упростить высказывание, используя равносильные преобразования;

3) полученный результат проверить, построив для него таблицу истинности.

 

Вариант		Вариант
1	(A «C) Ú A  Ú B	2	(A ® B) Ú A  Ú BC
3	(AB ® C) Ú A	4	C Ú (AB «C)
5	(  ® C) (B  Ú AC)	6	(A ~ B) Ú C Ú AB
7	(A ® B) Ú A  Ú AC	8	(A ~ B) Ú A  Ú AC
9	(AC ® B) Ú B	10	(AC ® B) Ú A
11	(  ® B) (  Ú AC)	12	(  «C) (A  ® BC)
13	(A ® C) Ú A  Ú B	14	(C ® A ) Ú  Ú BC
15	(BC ® ) ÚAB	16	C Ú (AB «C) Ú B
17	(AB ® C) Ú AB	18	( ~ B) (A  ® CB)
19	(B ® AC) Ú (AB ® C)	20	( B ® C) Ú B Ú C
21	(A «B) Ú (A  ® BC)	22	( C ® ) Ú BC
23	(AB ® C) Ú A	24	( B ® C) (A ~ C)
25	(  «BC) (A  ® BC)	26	(A ® B) ( B ® C)
27	(A  «C) Ú A C Ú B	28	(A ® B) Ú A  Ú BC
29	(  ® AC) Ú A	30	C Ú (AB «C)
31	(  ® BC) (  Ú AB)	32	(A ~ B) Ú C Ú AB
33	(A  ® BC) Ú C Ú AB	34	(A ~ B) Ú A  Ú AC

Контрольные вопросы.

1. Какие основные логические операции вам известны?

2. Перечислите основные равносильности алгебры логики.