- •1.8. Анализ и синтез релейных управляющих схем
- •1.8.1. Релейные схемы. Связь их физической структуры и функций проводимости с алгеброй логики
- •1.8.2. Проектирование рс
- •1.9. Применение алгебры логики к анализу логических рассуждений
- •1.10. Замкнутость и полнота систем функций
- •1.10.1. Операции суперпозиции и замыкания. Полнота, базис системы функций
- •1.10.2 Функции, сохраняющие константы. Классы т0 и т1
- •1.10.3. Самодвойственность. Класс s
- •1.10.4. Монотонность. Класс м
- •1.10.5. Линейность. Класс l
- •1.10.6. Критерий Поста полноты системы функций в алгебре логики
- •Контрольные задания по теме
- •Операция суперпозиции.
- •Замыкание и полнота систем функций.
- •Предполные классы в алгебре логики
- •1.11. Анализ и синтез функциональных схем
- •Пример 1. В качестве фэ приняты { , , }. Произвести анализ фс, физическая структура которой дана на рис.1.19.
- •10. Оптимизировать фс из фэ { , , }, приведеную на рис.1.25.
- •Контрольные задания по теме применение алгебры логики к анализу и синтезу релейных и функциональных схем, проверке правильности высказываний
Контрольные задания по теме
Операция суперпозиции.
Замыкание и полнота систем функций.
Предполные классы в алгебре логики
В.1. 1. Проверить вхождение в класс M функций: а) х (y z), б) (01101011), в) x y z.
2. Проверить полноту в P2 системы функций {(1101),(1011), (1001)}.
В.2. 1. Найти мощность множества функций Ln Тn0 .
2. Существуют ли шефферовы функции, у которых вектор истинности начинается с 0 ? Ответ обосновать.
В.3. 1. Найти замыкание и базис множества функций {(0110), (10), (1001)}. Ответ обосновать.
2. Выяснить, можно ли с помощью операции суперпозиции получить из множества функций { , } функцию (0100). Ответ обосновать.
В.4. 1. Проверить вхождение в класс S функций: а) х1 х2 … хn (n>0), б) (00010111), в) х (у z).
2. Построить пример шефферовой функции, зависящей от трех переменных.
В.5. 1. Найти замыкание и все базисы множества функций: {(1010), (1100), (0111)}.
2. Проверить полноту в P2 системы функций {х у, х уz}.
В.6. 1. Проверить вхождение в классы Т0 и Т1 функций: а) x y z, б) х1 х2 …хn у1 у2 … уm (n0, m0), в) х (у1 у2 … уn )(n1).
2. Проверить полноту в P2 системы функций: {(11011101), (1010) }.
В.7. 1. Доказать, что классы S и L не совпадают.
2. Проверить, можно ли с помощью операции суперпозиции получить из функций {ху, х у, х у} функцию х. Ответ обосновать.
В.8. 1. Найти замыкание множества функций: {(1110), (1001), (0111)}.
2. Дополнить систему функций до полной в P2 при помощи функций, не являющихся шефферовыми: { f } = {х у z, (х у) z }.
В.9. 1. Проверить вхождение в класс L функций: а) х (y z), б) (00010111), в)х у ху.
2. Можно ли с помощью операции суперпозиции получить при помощи функций {(1110),(1010)} функцию (1000)?
В.10. 1. Найти число функций в множестве Тn0 Тn1 .
2. Проверить полноту в P2 системы функций {х у, х у, х у}.
В.11. 1. Найти замыкание и базис множества функций {(1110), (10), (0101) }. Ответ обосновать.
2. Проверить полноту в P2 системы функций {(1101),(1011)}. Ответ обосновать
В.12. Доказать, что множества функций SnТn1 и SnТn0 совпадают.
2. Проверить, можно ли с помощью операции суперпозиции получить из функции {1110} функцию {1011}. Ответ обосновать.
В.13. 1. Проверить вхождение в классы Т0 и Т1 функций: а) х1 х2 … хn (n>0), б) x/y z), в) х (y z).
2. Проверить, можно ли с помощью операции суперпозиции получить из функций {0001,1101,0101} функцию (1011). Ответ обосновать.
В.14. 1. Найти замыкание системы функций и ее базис: {(1010) , (1100), (0111) }. Ответ обосновать.
2. Проверить полноту в P2 следующей системы функций:
{ х у , х у z, х у z , (х у) z }.
В.15. 1. Найти мощность множества функций Sn Тn1 .
2. Проверить, можно ли с помощью операции суперпозиции получить из функции {} функцию { }. Ответ обосновать.
В.16. 1. Проверить вхождение в класс S функций: а) x y z, б) х у х у, в) х (y z).
2. Проверить полноту в классе L системы функций {(1001),(10)}. Ответ обосновать
В.17. 1. Найти замыкание и базис множества функций {(0001), (10), (0101) }. Ответ обосновать.
2. Проверить, можно ли с помощью операции суперпозиции получить из функции {1110} функцию {0111}. Ответ обосновать.
В.18. 1. Проверить вхождение в класс L функций: а) х (y z), б) (00110011), в) ( х, y, z).
2. Найти замыкание системы функций {, , 1, 0 } и ее базис. Ответ обосновать.
В.19. 1. Доказать, что классы S и M не совпадают.
2. Проверить, можно ли с помощью операции суперпозиции получить из функций {0110,0001} функцию тождественный ноль 0. Ответ обосновать.
В.20. 1. Найти, используя теорему Поста, замыкание системы функций и ее базис: {(1011) , (1101), (0100), (0010)}. Ответ обосновать.
2. Существуют ли шефферовы функции, у которых вектор истинности заканчивается 1? Ответ обосновать.
В.21. 1. Найти число функций в множестве Sn \ Тn1 .
2. Проверить, можно ли с помощью операции суперпозиции получить из функции {} функцию { }. Ответ обосновать.
В.22. 1. Проверить вхождение в класс M функций: а) х (у1 у2 … уn)(n1), б) (00000011).
2. Дополнить систему функций {f} = {1011} до полной в P2 при помощи функций, не являющихся шефферовыми.
В.23. 1. Найти замыкание системы функций и указать в ней базис: {х у ,0 , х у , 1 }. Ответ обосновать.
2. Построить пример полной в P2 системы функций, содержащей эквивалентность { } и не включающей шефферовых функций.
В.24. 1. Доказать, что классы М и Т0 не совпадают.
2. Проверить, можно ли с помощью операции суперпозиции получить из функции {1000} функцию {1001}. Ответ обосновать.
В.25. 1. Найти число функций в множестве Тn0 Тn1 .
2. Проверить полноту в P2 системы функций {(0011), (0101), (0111)}. Ответ обосновать.
В.26. 1. Будет ли система функций { f } = {(0110), (10001000)} полна в P2 ? Ответ обосновать.
2. Проверить, можно ли с помощью операции суперпозиции получить из функции f = (11101110) функцию (1001)? Ответ обосновать.