- •Ахметова Наиля Абдулхамитовна
- •Введение
- •1. Элементы комбинаторики
- •1.1. Перестановки. Размещения. Сочетания
- •Теорема.
- •1.2. Задачи по комбинаторике
- •2. Функции алгебры логики
- •2.1. Элементарные функции алгебры логики
- •Пример 2.
- •2.2. Формульное задание функций алгебры логики
- •Упрощение записи формул:
- •Теорема о замене подформул на эквивалентные
- •Некоторые свойства элементарных функций
- •Следствия из свойств элементарных функций
- •Пример 3:
- •2.3 Принцип двойственности
- •Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
- •Пример 3. Покажем, что функция х1х2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.
- •Принцип двойственности
- •Лемма о несамодвойственной функции
- •2.4 Разложение булевой функции по переменным
- •Теорема о разложении функции по переменным
- •2.5. Полнота, примеры полных систем
- •Полные системы
- •Представление функции в виде полинома Жегалкина
- •Теорема Жегалкина
- •2.6. Замыкание и замкнутые классы
- •Важнейшие замкнутые классы в р2
- •Теорема Поста о полноте
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1,x1x2,x1x2}.
- •Теорема о достаточности четырех функций.
- •2.7. Функции k - значной логики
- •Теорема о полной в Рk системе функций
- •2.8. Задачи и упражнения по функциям алгебры логики
- •1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :
- •2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
- •3. Минимизация булевых функций
- •3.1. Минимизация нормальных форм
- •Алгоритм Квайна построения сокращенной днф.
- •Метод Блейка
- •Алгоритм построения сокращенной днф с помощью кнф (метод Нельсона)
- •Построение всех тупиковых днф.
- •Алгоритм минимизации функций в классе днф
- •Алгоритм минимизации функций в классе кнф
- •Алгоритм минимизации функций в классе нормальных форм
- •3.2 Минимизация частично определенных функций
- •Алгоритм минимизации частично определенных функций в классе днф
- •Алгоритм минимизации частично определенных функций в классе кнф
- •Метод минимизирующих карт Карно
- •3.3 Задачи по минимизации и доопределению булевых функций
- •4. Логика высказываний
- •4.1. Введение в логику высказываний
- •4.2. Задачи по алгебре высказываний
- •Список литературы
2.8. Задачи и упражнения по функциям алгебры логики
При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
–коммутативность связки , где символ является общим обозначением для связок &, , , ~, |, .
–ассоциативность связки , где – общее обозначение для связок &,,,~.
Дистрибутивность
а) – дистрибутивность конъюнкции относительно дизъюнкции;
б) – дистрибутивность дизъюнкции относительно конъюнкции;
в) – дистрибутивность конъюнкции относительно сложения по mod 2.
4. а); б)суть правила де Моргана;
5. а); б)суть правила поглощения;
6. а); б);
7. а); б);
в); г); д);
8. а);
б); в);
9. а); б).
1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :
, ;
,
, ;
, ;
, ;
, ;
, ;
, ;
, ;
, .
Ответы: 2), 6), 9), 10) – эквивалентны; 3), 7) – не эквивалентны.
2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
;
;
;
;
;
;
;
;
;
;
.
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. Используя дистрибутивный закон и эквивалентностии перейти от заданной ДНФ функции к ее КНФ:
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. Доказать, что:
Указание: если тоеслито
34. Выяснить, является ли множество А базисом в классе К:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
Ответы: 1)да. Имеем ;
2) А не является базисом в T1,так как ;
А не является базисом в T1,так как ;
А не является базисом в T1,так как ;
А не является базисом в T1,так как ;
А – базис в .
35. По вектору значений выяснить, является ли функцияf монотонной:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы: 2),3),5),8) – является; 1),4),6),7) – не является.
36. Проверить, является ли функция f монотонной:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы: 1),2),4),6),7) – является; 3),5),8) – не является.
37. Выяснить, полна ли система функций:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 2),4),6) – полна; 1)нет,3)нет,5)нет,
38. Выяснить, полна ли система А функций, заданых векторами своих значений:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 3),5) – полна; 1)нет,2)нет,4)нет,6)нет,
39. Выяснить, полна ли система А:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответы: 1),4),6) – полна; 2)нет,3)нет,5)нет,
40. Проверить,является ли система функций А базисом в Р2:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы:1) нет, так как подсистема полна; 2) является; 3) не является,4)нет, можно удалить
41. Из полной в Р2 системы А выделить всевозможные базисы:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы: 1)где
2)
42. Используя теоретико- множественные операции, выразить через известные замкнутые классы T0, T1, L, S, M и P2 замыкания множества А:
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
Ответы: 1)P2; 2) 3) 4) 5) 6)
43. Выяснить, можно ли расширить до базиса в Р2 множество А:
1)
2)
3)
4)
5)
6)
7)
8)
Ответы: 1) можно, – базис; 2) нельзя, функцияx входит во все предполные классы; 3) можно, – базис; 4) нет, функцииипринадлежат одним и тем же предполным классам.
44. Выяснить, полна ли система функций
1)
2)
3)
4)
Ответы: 1)вообще говоря, нет. Рассмотреть
2)да, имеем
3) вообще говоря, нет. Рассмотреть
4) вообще говоря, нет. Рассмотреть