Решение. Операцию отрицания можно представить полиномом Жегалкина в виде , следовательно, функция отрицания линейна

Операцию отрицания можно представить полиномом Жегалкина в виде , следовательно, функция отрицания линейна. Функция отрицания является самодвойственной, не сохраняет), не сохраняет 1(определяется с использованием таблицы истинности), немонотонна. Импликация является нелинейной функцией, так как её полином Жегалкина имеет вид , она несамодвойственна, не сохраняет 0, сохраняет 1 (можно определить по таблице истинности), немонотонна. Следовательно, для каждого класса Поста в данной системе имеется хотя бы одна функция, которая этому классу Поста не принадлежит. По теореме Поста такая система булевых функций является функционально полной.

Вопросы

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. Дайте определение терминам «импликанта», «имплицента», «простая импликанта», простая «имплицента».

46. Что представляет собой сокращенная ДНФ и сокращенная КНФ?

47. Дайте определение тупиковой ДНФ. Сколько тупиковых ДНФ может иметь булева функция?

48. Какая из ДНФ (КНФ) называется минимальной ДНФ (минимальной КНФ)?

49. Что представляют собой карты Карно (диаграммы Вейча)?

50. Назовите правило склеивания ячеек и записи минимальной ДНФ при использовании карт (диаграмм) Карно.

51. Как осуществляется построение карты Карно для функции пяти переменных?

52. Опишите особенности минимизации булевых функций на множестве КНФ с использованием минимизирующих карт.

53. Каким образом осуществляется минимизация частично определенных функций?

54. Перечислите основные типы булевых функций.

55. Дайте определение булевых функций, сохраняющих 0 и 1.

56. Какое количество всех функций переменных сохраняет константу 0 и константу 1?

57. Какая функция называется монотонной?

58. Как по виду ДНФ булевой функции можно определить, монотонна функция или нет?

59. Поясните структуру алгебры Жегалкина.

60. Перечислите основные законы и тождества алгебры Жегалкина.

61. Определите понятие полинома Жегалкина.

62. Дайте определение линейности булевой функции.

63. Приведите примеры линейных и нелинейных функций двух переменных.

64. Перечислите важнейшие замкнутые классы булевых функций.

65. Какая система булевых функций называется функционально полной?

66. Сформулируйте теорему о полноте двух систем булевых функций.

67. Дайте определение функциональной полноты в слабом смысле.

68. Какая полная система булевых функций является несократимой.

69. Сформулируйте теорему Поста.

Поиск по сайту: