- •Раздел II. Математическая логика
- •Глава 1. Алгебра логики
- •1.1. Объекты изучения алгебры логики. Булевы константы, переменные и векторы
- •1.2. Булевы функции, способы их задания. Элементарные функции. Алгебра логики, ее формулы
- •Задание функции при помощи вектора истинности
- •Матричный способ
- •Задание с помощью полного бинарного дерева
- •Формульное задание
- •1.3. Моделирование составных высказываний при помощи формул алгебры логики
- •1.4. Эквивалентность формул. Тавтологии. Законы логики. Двойственность
- •1.5. Специальные формульные представления булевых функций
- •1.5.1. Конъюнкции и дизъюнкции над множеством переменных. Нормальные формы
- •1.5.2. Конституенты единицы. Совершенные дизъюнктивные и веббовы нормальные формы
- •1.5.3. Конституенты нуля. Совершенные конъюнктивные и шефферовы нормальные формы
- •1.5.4. Полиномы Жегалкина
- •1.6. Минимизация нормальных форм булевых функций
- •1.5.1. Метод покрытий
- •1.6.2. Метод минимизирующих карт
- •1.7. Частично определенные функции. Их минимальное доопределение
- •Контрольные задания по теме функции алгебры логики. Нормальные формы. Полином жегалкина
Контрольные задания по теме функции алгебры логики. Нормальные формы. Полином жегалкина
В. 1. 1. Ввести булевские высказывания-переменные и составить при помощи элементарных булевых функций формулу составного высказывания: ”четырёхугольник является квадратом тогда и только тогда, когда у него равны между собой все стороны и равны между собой все углы”.
2. Построить методом неопределенных коэффициентов полином Жегалкина функции f = (10101011).
В. 2. 1. Имеются некоторые простые высказывания x,y,z. Известно, что (x y ) = И, (x y ) = И,( z x)=Л. Найти истинность составного высказывания (х у) (у z).
2. Найти МДНФ и МВНФ (в базисах {,} и {}) функции f = у (х/ z).
В.3. 1. Найти существенные и фиктивные переменные булевой функции f =х уz (х ,у, z).
2. Построить при помощи СДНФ полином Жегалкина для функции f = (10010001).
В.4. 1. Ввести простые булевские высказывания-переменные и составить формулу высказывания: ”для того, чтобы четырехугольник был ромбом, необходимо и достаточно, чтобы длины его сторон были равны либо он был параллелограммом и его диагонали пересекались под прямым углом”.
2. Построить для булевой функции f = (0001001001010001) СДНФ и СВНФ в базисе {,}.
В. 5. 1. Проверить (доказать или опровергнуть), будет ли формула f = ху z (x у ) противоречием.
2. Построить СкШНФ функции f =(1101011010111101).
В. 6. 1. Имеются некоторые простые высказывания x, y, z. Известно, что (x y ) = Л, (x y ) = Л, z x = Л. Найти истинность составного высказывания (х/у) (у z).
2. Построить СкДНФ функции f = (0001000100110011).
В.7.1. Проверить справедливость правила: (x y) (x y) (y x).
2. Построить СкКНФ и СкШНФ (в базисах {,/} и {/}) функции f =(0111011110111011).
В.8. 1. Доказать справедливость дистрибутивного закона алгебры логики х у z = ( х у) (х z).
2. Построить при помощи СДНФ полином Жегалкина для функции f = у (х/z).
В. 9. 1. Ввести простые булевские высказывания-переменные и составить формулу высказывания: ”для того, чтобы треугольник с длинами сторон a, b, c был прямоугольным, необходимо и достаточно, чтобы квадрат длины какой-либо из его сторон был равен сумме квадратов длин двух остальных сторон”.
2. Построить СкДНФ функции f =(0001000110101000).
В.10. 1. Имеются простые высказывания x, y, z, u. Известно, что высказывания х у и z у истинны, а высказывание х у z - ложно. Определить истинность высказывания ху z u.
2. Найти МКНФ и МШНФ (в базисах {,/} и {/} ) функции f = х уz.
В.11. 1. Найти существенные и фиктивные переменные булевой функции f =(0100010010111011).
2. Построить СкКНФ и СкШНФ (в базисах {,} и {}) функции f = (01100111).
В.12. 1. Система блокировки некоторого устройства принимает сигналы от датчиков А, В, С. Блокировка должна срабатывать при одновременном получении сигналов от А и В либо только одного сигнала - от датчика С. Ввести необходимые обозначения, булевские высказывания-переменные и построить таблицу истинности, описывающую функционирование данной системы.
2. Построить минимальное доопределение частично определённой функции f = (01??01?1).
В.13. 1. Имеются простые высказывания x,y,z,u. Известно, что высказывания х у и /(y,z,u) являются истинными. Определить истинность высказывания хуzu.
2. Найти МКНФ и МШНФ (в базисах { ,/} и {/}) функции f = х у z.
В.14. 1. Найти существенные и фиктивные переменные булевой функции f = х у (х , у, z) (х , у,z).
2. Построить СкДНФ и СкВНФ (в базисах { ,} и {} ) функции f = (0110011101101010).
В.15. 1. Будут ли формулами записи x y (у z), (х ,у,z ), x y у. В правильных указать порядок выполнения операций.
2. Построить минимальное доопределение частично определённой функции f = (0??011?1).
В.16. 1. Имеются некоторые простые высказывания x,y,z. Известно, что (xy ) = И, (x y ) = И,( z x)=Л. Найти истинность составного высказывания (х у)(у/z).
2. Построить при помощи СДНФ полином Жегалкина для функции f = у (х xz).
В.17. 1. Система управления имеет три входных и один выходной канал. Выходной сигнал в системе должен вырабатываться при отсутствии сигналов на входе либо поступлении ровно двух сигналов. Ввести необходимые обозначения, булевские высказывания-переменные и построить таблицу истинности, описывающую функционирование данной системы .
2. Построить минимальное доопределение частично определённой функции f = (10?1?0?1).
В.18. 1. Доказать с помощью метода математической индукции обобщённый дистрибутивный закон алгебры логики, справедливый для любого числа переменных n 2 :
х у1 у2 . . . уn = (х у1) (х у2) . . . (х у n).
2. Построить СкШНФ и СкШНФ (в базисах {,/} и {/} ) функции f = /(у, z ) (х у z) .
В.19. 1. Доказать с помощью метода математической индукции обобщённое правило де Моргана, справедливое для любого числа переменных n 2 :
(х1 х2 . . . х n ) =х1 х2 . . . хn .
2. Найти МКНФ и МШНФ (в базисах {,/} и {/} ) функции f = х уz.
В.20. 1. Ввести булевские высказывания-переменные и составить при помощи элементарных булевых функций формулу составного высказывания: ”если четырёхугольник является параллелограммом, то у него равны противолежащие углы и равны противолежащие стороны”.
2. Построить методом неопределенных коэффициентов по-лином Жегалкина функции f = (01010010).
В.21. 1. Проверить, будет ли тавтологией формула х у z (х у z).
2. Построить при помощи СДНФ полином Жегалкина для функции f =(01001100).
В. 22. 1. Имеются некоторые простые высказывания x,y,z,u. Известно, чтоx y = Л, x z = Л, x/u = Л. Найти истинность составного высказывания (х u) (у z).
2. Найти МДНФ и МВНФ (в базисах {,} и {} ) функции f = х уz.
В.23. 1. Найти существенные и фиктивные переменные функции f = (x/y) (х (у z))(x у z ).
2. Построить минимальное доопределение частично определённой функции f = (10?1?0?1).
В.24. 1. Ввести булевские высказывания-переменные и составить при помощи элементарных булевых функций формулу составного высказывания: ”если задача решена неправильно, то ответ неверный, следовательно, из правильного ответа следует правильность решения задачи”.
2. Построить методом неопределенных коэффициентов полином Жегалкина функции f = (х у).
В.25. 1. Доказать с помощью метода математической индукции обобщённое правило де Моргана, справедливое для любого числа переменных n 2 :
(х1 х2 . . . х n ) =х1 х2 . . . хn .
2. Найти МДНФ и МВНФ (в базисах {,} и {} ) функции f = х уz.
В.26. 1. Определить существенные и фиктивные переменные функции f =(00110011).
2. Построить СКНФ и СШНФ функции: f = (ху) z .
В.27. 1. Система управления главным двигателем аппарата включает четыре аварийных датчика - х, у, z, u. Автоматическое отключение главного двигателя происходит при срабатывании не менее трех из них. Ввести булевские высказывания-переменные и построить таблицу истинности для управляющей функции .
2. Найти МДНФ и МВНФ (в базисах {,} и {} ) функции f = х уz.
В.28. 1. Найти существенные и фиктивные переменные в функции f = хz у z х у z .
2. Построить СДНФ и СВНФ функции f = (01101000).