Задачи и упражнения по функциям алгебры логики
При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
1. – коммутативность связки *, где символ * является общим обозначением для связок &, Ú, Å, ~, |, ¯.
2. – ассоциативность связки *, где *– общее обозначение для связок &,Ú,Å,~.
3. Дистрибутивность
а) – дистрибутивность конъюнкции относительно дизъюнкции;
б) – дистрибутивность дизъюнкции относительно конъюнкции;
в) – дистрибутивность конъюнкции относительно сложения по mod 2.
4. а) ; б)
суть правила де Моргана;
5. а) ; б)
суть правила поглощения;
6. а) ; б)
;
7. а) ; б)
;
в) ; г)
; д)
;
8. а) ;
б) ; в)
;
9. а) ; б)
.
1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и
:
1) ,
;
2) ,
3) ,
;
4) ,
;
5) ,
;
6) ,
;
7) ,
;
8) ,
;
9) ,
;
10) ,
.
Ответы: 2), 6), 9), 10) – эквивалентны; 3), 7) – не эквивалентны.
2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
9) ;
10) ;
11) .
3. Используя приведенные выше основные эквивалентности и соотношения докажите эквивалентность формул V и U:
1) ,
;
2) ,
;
3) ,
;
4) ,
;
5) ,
;
6) ,
;
7) ,
;
8) ,
;
9) ,
;
10) ,
.
Ответы:
4)
;
9)
4. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g двойственной к функции f:
1) ,
;
2) ,
;
3) ,
;
4) ,
;
5) ,
;
6) ,
;
7) ,
;
8) ,
;
9) ,
;
10) ,
;
11) ,
;
12) ,
.
Ответы: 4) ,
. Значит, g не двойственна к f. 6) – не является; 8),9),11) – является.
5. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции f, и убедитесь в том, что полученная формула эквивалентна формуле V:
1) ,
;
2) ,
;
3) ,
;
4) ,
;
5) ,
;
6) ,
;
7) ,
;
8) ,
;
9) ,
;
10) ,
.
Ответы:
1)
2) ; 5)
; 10)
.
6. Указать все фиктивные переменные у функции f:
1)
2)
3)
4)
5)
6)
Ответы:1)две фиктивные переменные; 3)одна фиктивная переменная; 5)фиктивные переменные x1 и x3.
7. Показать, что x1 – фиктивная переменная у функции f (реализовав для этой цели функцию f формулой, не содержащей явно переменную x1):
1) ;
2) ;
3) ;
4) 5)
6)
7)
8) 9)
10)
Ответы: 4),8),10) 9)
8. Выяснить, можно ли из функции f , отождествляя и переименовывая в ней переменные, получить функцию g:
1) ,
2) ,
3) ,
4) ,
5) ,
6) ,
7) ,
;
8) ,
;
9) ,
;
10) ,
.
Ответы: 1),2),5),7),8),9),10)можно. 3),4),6)нельзя.
9. Представить в СДНФ следующие функции:
1) ;
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 2) ; 4)
, 7)
10. Представить в СКНФ следующие функции:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 1) ; 2)
; 6)
; 8)
11. С помощью эквивалентных преобразований построить ДНФ функции
:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы:
4)
10)
12. Используя эквивалентные преобразования, построить КНФ функции
:
1)
2) ;
3)
4)
5)
6)
7)
Ответы:
1)
3)
6)
13. Применяя преобразования вида и
построить из заданной ДНФ функции
ее совершенную ДНФ:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы:
2)
5)
14. С помощью преобразований вида и
построить из данной КНФ функции
ее совершенную КНФ:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы:
1)
5)
15. Используя дистрибутивный закон и эквивалентности
и
перейти от заданной КНФ функции
к ДНФ:
1)
2)
3)
4)
5)
6)
7)
Ответы:
3)
6)
16. Используя дистрибутивный закон и эквивалентности
и
перейти от заданной ДНФ функции
к ее КНФ:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы:
2)
5)
17. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы:
1)
3)
6)
10)
18. Методом треугольника Паскаля построить полином Жегалкина для этой функции, если:
1) 2)
3) 4)
5) 6)
7) 8)
9) 10)
Ответы:
1) 4)
7)
19. Представив функцию формулой над множеством связок {&,
}, преобразуйте полученную формулу в полином Жегалкина функции
(используя эквивалентности
):
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы:
1)
3)
9)
20. Построить множество всех функций, зависящих от переменных x1,x2 и принадлежащих замыканию множества А:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1) 2)
3)
4) 5)
6)
21. Покажите, что , выразив
формулой над множеством А:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1) 2)
3)
4)
5)
6)
7)
22. Выписать все попарно неконгруэнтные функции , принадлежащие замыканию множества А:
1) 2)
3)
4)
5) 6)
7)
8)
9)
10)
Ответы: 1) 2)
3)
4)
5)
23. Из полной для класса [A] системы выделить базис:
1) 2)
3)
4)
5) 6)
7) 8)
9)
10)
Ответы: 1) 2)
3)
4)
5)
24. Сведением к заведомо полным системам в P2 показать, что множество А является полной системой в P2:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 1)система является полной в P2, поскольку всякая
может быть представлена в виде ДНФ или КНФ. С другой стороны,
2) имеем
Система
полна, поскольку
3) имеем ;
4) имеем ;
5) имеем ;
25. Выяснить, является ли функция f самодвойственной:
1)
3)
5)
7)
2)
4)
6)
8)
9)
11)
13)
15)
10)
12) 14)
Ответы: 1),3),4),8),10) – является; 2),5),6),7),9) – не является.
26. Выяснить, является ли самодвойственной функция f, заданная векторно:
1)
3)
5)
7)
9)
11)
13)
15)
2)
4)
6)
8)
10)
12)
14)
Ответы: 1),3),5),6),7),8) – является; 2),4),9),10) – не является.
27. Выяснить, является ли множество А самодвойственным:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1),3),5-7),10) – является; 2),4),8),9) – не является.
28. Представив функцию f полиномом, выяснить, является ли она линейной:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 2),3),5),6),8),9)–является. 1),4),7),10)–не является.
29. Выяснить, является ли линейной функция f, заданная векторно:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1),3),4),5),7),8),9),10) – является; 2),6) – не является.
30. Доказать, что система А полна в L. Выяснить, является ли система A базисом в L:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1)с помощью суперпозиции из функции можно получить любую функцию вида
, путем подстановки 1-любую функцию вида
Система А является базисом;
2),3),4),5),7),8),9) – является; 6),10) – не является.
31. Выяснить, принадлежит ли функция f множеству T1\T0:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 1),3),4),6),8),9) – является; 2),5),7),10) – не является.
32. Подсчитать число функций, зависящих от переменных x1,…,xn и принадлежащих множеству А:
1) ;
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
16)
17)
18)
19)
20)
21)
22)
23)
24)
25)
26)
27)
28)
29)
30)
31)
32)
33)
34)
35)
36)
37)
38)
39)
40)
41)
42)
43)
44)
45)
Ответы: 1) ; 2)
; 3)22n; 4)
; 5)
6)2n; 7)
; 8)
; 9)
; 10)
; 15) 0.
33. Доказать, что:
1)
2)
Указание: если то
если
то
34. Выяснить, является ли множество А базисом в классе К:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1)да. Имеем ;
2) А не является базисом в T1,так как ;
3) А не является базисом в T1,так как ;
4) А не является базисом в T1,так как ;
5) А не является базисом в T1,так как ;
6) А – базис в .
35. По вектору значений выяснить, является ли функция f монотонной:
1)
2)
3)
4)
Дата добавления: 2016-03-27; просмотров: 1846;