Вопросы MOD 4

Модуль 4 «Булевы функции»Дискретная математика, ИУ5, 2 курс, 3 семестр.Вопросы для подготовки к защите домашнего задания №3Лектор Ткачев С.Б.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.Что такое булева функция.Как определяется булев порядокЧто такое булев кубКак задать булеву функцию с помощью таблицы?Что называют фиктивной переменной булевой функции?Как найти фиктивную переменную по таблице?Какие булевы функции называют равными?Как определяется суперпозиция булевых функций?Определите понятие формулы над заданным множеством F булевых функций.Как определяется функция, представляемая формулой.Что такое дизъюнктивная нормальная форма (ДНФ)?Что такое коньюктивная нормальная форма (КНФ)?Что такое совершенная дизъюнктивная нормальная форма (СДНФ)?Что такое совершенная коньюктивная нормальная форма (СКНФ)?Какая ДНФ называется сокращенной?Какая ДНФ называется тупиковой?Какая ДНФ называется кратчайшей?Какая ДНФ называется минимальной?В чем состоит задача минимизации булевых функций в классе ДНФ?Назовите основные этапы алгоритма Квайна—Мак-Клоски.В чем заключается тождество склейки?В чем заключается тождество поглощения?Как тождества склейки и поглощения используются для получения сокращеннойДНФ из СДНФ?Как применимость тождества склейки можно увидеть на карте Карно.Какое множество булевых функций называется полным?Какое множество булевых функций называют базисом Жегалкина?Что такое полином Жегалкина?В чем заключается метод неопределенных коэффициентов построения полиномаЖегалкина по таблице булевой функции?Какая булева функция называется линейной?Как установить линейность булевой функции?Какая булева функция называется монотонной?Как установить монотонность булевой функции по таблице?Какая булева функция называется самодвойственной?Как установить самодвойственность булевой функции по таблице.Перечислите классы Поста.Что означает утверждение о том, что каждый класс Поста замкнут?Как с использованием несамодвойственной функции и отрицания реализоватьконстанту?Как с использованием немонотонной функции и отрицания реализовать константу?Как с использованием нелинейной функции, констант и отрицания реализоватьконъюнкцию?Сформулируйте утверждение о свойствах классов Поста (о замкнутости).Сформулируйте утверждение о несамодвойственной функции.Сформулируйте утверждение о немонотонной функции.Сформулируйте утверждение о нелинейной функции.Сформулируйте теорему Поста.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.Что такое язык в алфавите V?Как определяется операция объединения языков?Как определяется операция соединения языков?Что называют итерацией языка L?Что называется дополнением языка L?Как определяется регулярный язык в алфавите V?Что такое конечный автомат как граф, взвешенный над полукольцом регулярныхязыков?Что такое язык, допускаемый конечным автоматом?Какой конечный автомат называется детерминированным?Сформулируйте этапы детерминизации конечного автомата.Опишите основные приемы построения конечного автомата, эквивалентногоисходному автомату, и не содержащего λ переходов.В чем заключается метод вытягивания построения детерминированного автомата.Как построить конечный автомат для объединения языков?Как построить конечный автомат для соединения языков?Как построить конечный автомат для итерации языка?Как построить конечный автомат для дополнения конечного языка.Сформулируйте теорему Клини.Сформулируйте теорему о детерминизацииСформулируйте теорему о разрастании..