Вопросы к главе II

1. В чём состоит закон "исключения третьего"?

2. Перечислите основные логические операции и укажите их таблицы истинности.

3. Дайте определение формулы логики высказываний.

4. Как устанавливается иерархия между операциями логики высказываний?

5. Дайте определение булевой функции. Сколько существует различных булевых функций, зависящих от n аргументов?

6. Какие формулы называются равносильными? тождественно истинными, ложными, выполнимыми?

7. Какая формула логики высказываний называется булевой формулой и какая приведенной булевой? Приведите примеры.

8. Для всякой ли формулы существует равносильная ей булева формула?

9. Какие булевы формулы равносильны формулам a®b и a«b?

10. Сформулируйте два правила равносильного преобразования формул.

11. Приведите основные равносильности булевых формул: законы коммутативности, ассоциативности, дистрибутивности, поглощения, идемпотентности, снятия двойного отрицания, законы де Моргана.

12. Дайте определение дизъюнктивной и конъюнктивной нормальных формул.

13. Для всякой ли формулы логики высказываний существуют равносильные ей ДНФ и КНФ?

14. Дайте определение совершенных ДНФ и КНФ.

15. Для всякой ли формулы существуют равносильные ей СДНФ и СКНФ?

16. Как построить СДНФ и СКНФ равносильные данной формуле?

17. В каком смысле можно говорить о единственности СДНФ и СКНФ для данной формулы?

18. Если формулы равносильны, всегда ли можно равносильными преобразованиями перейти от одной формулы к другой?

19. Для любой ли булевой функции существует равносильная ей формула?

20. Какие переменные в формуле называются фиктивными (несущественными)?

21. Сформулируйте необходимые и достаточные условия тождественной истинности (ложности) формулы. Что такое элементарная дизъюнкция (конъюнкция)?

22. Какие формулы называются двойственными?

23. Сформулируйте две основные теоремы двойственности.

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

25. Сформулируйте правило, позволяющее строить вектор значений двойственности формулы по заданному вектору значений данной формулы. Как это правило связано с законами двойственности?

26. Сформулируйте правило построения КНФ, равносильной данной формуле, если равносильная ДНФ построена.

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

28. Какая связь между булевой функцией и вершинами n -мерного куба?

29. Дайте определение n -куба. Что такое свободные и связанные координаты? Дайте определение комплекса кубов для данной функции.

30. Что такое покрытие, цена покрытия, минимальное покрытие комплексов кубов? Как связано покрытие комплекса кубов функции с равносильной ей ДНФ?

31. Дайте определение простых импликантов, экстремалей, отмеченных вершин.

32. Почему минимальное покрытие может состоять только из простых импликантов?

33. Почему каждая экстремаль принадлежит минимальному покрытию?

34. Всегда ли минимальное покрытие состоит только из экстремалей? Приведите пример.

35. Может ли комплекс кубов не содержать экстремалей? Приведите пример.

36. Расскажите о реализации булевых функций релейно-контактными схемами. Что такое двухполюсник? Дайте определение функции проводимости релейно-контактной схемы.