Задачи и упражнения по функциям алгебры логики

 

При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

1. – коммутативность связки *, где символ * является общим обозначением для связок &, ~, |, .

2. – ассоциативность связки *, где *– общее обозначение для связок &, ~.

3. Дистрибутивность

а) – дистрибутивность конъюнкции относительно дизъюнкции;

б) – дистрибутивность дизъюнкции относительно конъюнкции;

в) – дистрибутивность конъюнкции относительно сложения по mod 2.

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

в) ; г) ; д) ;

8. а) ;

б) ; в) ;

9. а) ; б) .

 

1. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) .

2. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g двойственной к функции f:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , .

 

Ответы: 4) , . Значит, g не двойственна к f. 6) – не является; 8),9) – является.

 

3. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции f, и убедитесь в том, что полученная формула эквивалентна формуле V:

1) , ;

2) , ;

3) , ;

4) , ;

5) , .

 

Ответы: 1)

2) ; 5) .

 

4. Указать все фиктивные переменные у функции f:

1)

2)

3)

4)

5)

6)

Ответы: 1) две фиктивные переменные; 3) одна фиктивная переменная; 5) фиктивные переменные x ₁ и x ₃.

 

5. Показать, что x ₁ – фиктивная переменная у функции f (реализовав для этой цели функцию f формулой, не содержащей явно переменную x ₁):

1) ;

2) ;

3) ;

4) 5) 6) 7)

8) 9) 10)

Ответы: 4), 8), 10) 9)

 

6. Представить в СДНФ следующие функции:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2) ;

4) ,

7)

7. Представить в СКНФ следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1) ; 2) ; 6) ; 8)

 

8. С помощью эквивалентных преобразований построить ДНФ функции :

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

4)

10)

 

9. Используя эквивалентные преобразования, построить КНФ функции :

1)

2) ;

3)

4)

5)

6)

7)

Ответы:

1)

3)

6)

 

10. Применяя преобразования вида и построить из заданной ДНФ функции ее совершенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

 

11. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

1)

5)

12. Используя дистрибутивный закон и эквивалентности , и перейти от заданной КНФ функции к ДНФ:

1)

2)

3)

4)

5)

6)

7)

 

Ответы:

3)

6)

 

13. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

 

 

Ответы:

2)

5)

14. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

1)	5)
2)	6)
3)	7)
4)	8) .

Ответы:

1) 3) 6)

 

15. Методом треугольника Паскаля построить полином Жегалкина для этой функции, если:

1) 2)

3) 4)

5) 6)

Ответы:

1) 4)

 

16. Представив функцию формулой над множеством связок {&, }, преобразуйте полученную формулу в полином Жегалкина функции (используя эквивалентности ):

1)

2)

3)

4)

5)

6)

7)

8)

 

 

Ответы:

1)

3)

 

17. Построить множество всех функций, зависящих от переменных x ₁, x ₂ и принадлежащих замыканию множества А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы:

1) 2) 3) 4) 5) 6)

 

18. Представив функцию 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)–не является.

 

19. Выяснить, принадлежит ли функция f множеству T ₁\ T ₀:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),3),4),6),8),9) – является; 2),5),7),10) – не является.

 

20. По вектору значений выяснить, является ли функция f монотонной, самодвойственной и линейной:

1)

2)

3)

4)

5)

6)

7)

8)

 

21. Проверить, является ли функция f монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1),2),4),6),7) – является; 3),5),8) – не является.

 

22. Выяснить, полна ли система функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2),4),6) – полна;1) нет, 3) нет, 5)нет,

 

23. Выяснить, полна ли система А функций, заданных векторами своих значений:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 3),5) – полна; 1)нет, 2)нет, 4)нет, 6)нет,

 

24. Выяснить, полна ли система А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),4),6) – полна; 2)нет, 3)нет, 5)нет,

 

25. Проверить, является ли система функций А базисом в Р ₂:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:1) нет, так как подсистема полна; 2) является; 3) не является, 4)нет, можно удалить

 

26. Из полной в Р ₂ системы А выделить всевозможные базисы:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1)

где

2)

 

27. Из заданного множества А элементарных конъюнкций выделить простые импликанты функции f:

1) A = , = (00101111);

2) A = , = (01111110);

3) A = , = (1010111001011110);

4) A = , = (1011);

5) A = , = (00111011);

6) A = , = (00101111).

 

28. По заданной ДНФ с помощью метода Блейка построить сокращенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

 

29. Построить сокращенную ДНФ по заданной КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

 

30. Найти сокращенную ДНФ функции f с помощью минимизирующей карты:

1) = (01010111); 2) = (11011011);

3) = (10110000); 4) = (11101111);

5) = (0001101111011111); 6) = (0011110111111101);

7) = (0011110111011110); 8) = (0010101111011111).

 

31. С помощью минимизирующих карт построить сокращенную ДНФ для частично определенной функции f, заданной векторно (прочерки соответствуют неопределенным значениям):

1) = (01--01-1);	5) = (10-1-011-0—1-01);
2) = (1-01--10);	6) = (0--1---0--1-1-01);
3) = (1---0-10);	7) = (--01-1-00----1-0);
4) = (0--10-1-);	8) = (-10-1-11-01-0---).