Ответы к контрольной работе: Графы, Булевы Функции, СДНФ, СКНФ
Описание
Оглавление
5.Дать определение ориентированной сети.6
6.Дать определение порядковой функции сети.6
7.Сформулируйте и докажите теорему о высота бинарного дерева с заданным числом листьев.7
9.Сформулировать и доказать лемму о свойствах k-й степени матрицы меток дуг.9
10.Сформулировать теорему о матрице стоимостей размеченного над полукольцом.10
11.Что такое язык в алфавите V?. 11
12.Как определяется операция объединения языков?. 11
13.Как определяется операция соединения языков?. 11
14.Что называют итерацией языка L?. 11
15.Что называется дополнением языка L?. 11
16.Как определяется регулярный язык в алфавите V?. 12
17.Что такое конечный автомат как граф, взвешенный над полукольцом регулярных языков?. 12
18.Что такое язык, допускаемый конечным автоматом?. 13
19.Какой конечный автомат называется детерминированным?. 13
20.Сформулируйте этапы детерминизации конечного автомата.13
22.В чем заключается метод вытягивания построения детерминированного автомата.15
23.Как построить конечный автомат для объединения языков?. 15
24.Как построить конечный автомат для соединения языков?. 16
25.Как построить конечный автомат для итерации языка?. 17
26.Как построить конечный автомат для дополнения конечного языка.18
27.Сформулируйте теорему Клини.19
28.Сформулируйте теорему о детерминизации. 22
29.Сформулируйте теорему о разрастании.23
30.Что такое булева функция.24
31.Как определяется булев порядок. 24
33.Как задать булеву функцию с помощью таблицы?. 25
34.Что называют фиктивной переменной булевой функции?. 26
35.Как найти фиктивную переменную по таблице?. 26
36.Какие булевы функции называют равными?. 26
37.Как определяется суперпозиция булевых функций?. 26
38.Определите понятие формулы над заданным множеством F булевых функций.27
39.Как определяется функция, представляемая формулой.27
40.Что такое дизъюнктивная нормальная форма (ДНФ)?. 28
41.Что такое коньюктивная нормальная форма (КНФ)?. 28
42.Что такое совершенная дизъюнктивная нормальная форма (СДНФ)?. 28
43.Что такое совершенная коньюктивная нормальная форма (СКНФ)?. 28
44.Какая ДНФ называется сокращенной?. 28
45.Какая ДНФ называется тупиковой?. 28
46.Какая ДНФ называется кратчайшей?. 29
47.Какая ДНФ называется минимальной?. 29
48.В чем состоит задача минимизации булевых функций в классе ДНФ?. 29
49.Назовите основные этапы алгоритма Квайна—Мак-Клоски.29
50.В чем заключается тождество склейки?. 30
51.В чем заключается тождество поглощения?. 30
52.Как тождества склейки и поглощения используются для получения сокращенной ДНФ из СДНФ?. 30
53.Как применимость тождества склейки можно увидеть на карте Карно.30
54.Какое множество булевых функций называется полным?. 30
55.Какое множество булевых функций называют базисом Жегалкина?. 31
56.Что такое полином Жегалкина?. 31
58.Какая булева функция называется линейной?. 32
59.Как установить линейность булевой функции?. 32
60.Какая булева функция называется монотонной?. 32
61.Как установить монотонность булевой функции по таблице?. 33
62.Какая булева функция называется самодвойственной?. 33
63.Как установить самодвойственность булевой функции по таблице.34
64.Перечислите классы Поста.34
65.Что означает утверждение о том, что каждый класс Поста замкнут?. 35
66.Как с использованием несамодвойственной функции и отрицания реализовать константу?. 36
67.Как с использованием немонотонной функции и отрицания реализовать константу?. 36
68.Как с использованием нелинейной функции, констант и отрицания реализовать конъюнкцию?. 37
69.Сформулируйте утверждение о свойствах классов Поста (о замкнутости).37
70.Сформулируйте утверждение о несамодвойственной функции.38
71.Сформулируйте утверждение о немонотонной функции.38
72.Сформулируйте утверждение о нелинейной функции.38
73.Сформулируйте теорему Поста.38
МГТУ им. Н.Э.Баумана
lisalimonova
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
