- •Понятие множества. Способы задания множеств.
- •Операции над множествами. Диаграммы Эйлера-Венна.
- •Алгебра множеств.
- •Кортеж. График. Свойства графиков.
- •Соответствия. Свойства соответствий.
- •Отношения. Свойства отношений. Примеры.
- •Высказывания. Операции над высказываниями.
- •Формы представления высказываний. Примеры.
- •Преобразования высказываний. Примеры.
- •Минимизация высказываний методом Квайна. Пример.
- •Минимизация высказываний с помощью карт Карно. Пример.
- •Понятие графа. Способы задания графа. Пример.
- •Виды графов: эйлеров, полный, планарный, деревья. Примеры.
- •Определение путей в графе. Пример.
- •Приведение графа к ярусно-параллельной форме. Пример.
- •Внутренняя и внешняя устойчивость графа. Ядро графа. Пример.
- •4.9. Множество внешней устойчивости. Ядро графа
- •Поиск минимального остова в графе.
- •Понятие автомата. Виды автоматов.
- •Минимизация автоматов.
- •Переход от автомата Милли к автомату Мура и наоборот.
-
Минимизация высказываний методом Квайна. Пример.
Высказывание называется минимальным, если оно содержит наименьшее количество элементарных конъюнкций (дизъюнкций).
-
Выражение из произвольной формы приводится к СДНФ.
Элементарные конъюнкции в СДНФ называются конституентами единицы.
2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные поглощения мы получим Сокращенную ДНФ (СкДНФ), в которую входят все конъюнкции, не участвовавшие в склеивании. Конъюнкции в СкДНФ называются импликантами.
Примечание: Склеивание: XY XY ≡ X
Неполное склеивание: XY XY ≡ X XY XY
-
На основании СкДНФ и СДНФ строим импликантную матрицу: по столбцам располагаем конституенты единицы, по строкам – импликанты.
-
Находим минимальное покрытие импликантной матрицы, т.е. такой набор строк, который охватывает плюсами все столбцы. Получаем минимальную дизъюнктивную нормальную форму (МДНФ).
Пример 1:
f = XYZ XYZ XYZ XYZ XYZ
1 2 3 4 5
1-2 : XY (6)
1-3 : YZ (7)
1-5 : XZ (8 )
3-4 : XZ (9)
4-5 : YZ (10)
7-10 : Z
8-9 : Z
Импликантная матрица.
|
_ _ _ XYZ |
_ _ XYZ |
_ _ XYZ |
_ XYZ |
_ _ XYZ |
_ _ XY |
+ |
+ |
|
|
|
_ Z |
+ |
|
+ |
+ |
+ |
СкДНФ(f) = XY Z = МДНФ.
-
Минимизация высказываний с помощью карт Карно. Пример.
Одним из способов задания функций алгебры логики являются карты Карно.
Y X 0 1 0 1 0 1 1 1
f
= XY
f = XY XY XY
X |
Y |
f |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
Y Z X |
0 0 |
0 1 |
1 1 |
1
f
= YZ
XZ |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
c d a b |
0 0 |
0 1 |
1 1 |
1 0 |
0 0 |
1 |
1 |
1 |
1
f
= b
d |
0 1 |
1 |
0 |
0 |
1 |
1 1 |
1 |
0 |
0 |
1 |
1 0 |
1 |
1 |
1 |
1 |
При использовании карт Карно производится покрытие с помощью правильной конфигурации, содержащей единицы.
Правильными конфигурациями являются все прямоугольники, имеющие площадь 2n (1, 2, 4, 8, 16, …).
При покрытии руководствуются следующими правилами:
-
Число покрытий должно быть минимальным, а площадь, покрываемая каждой правильной конфигурацией, максимальна.
-
Конфигурации могут перекрываться и накладываться друг на друга.
-
Можно объединять клетки, стоящие на противоположных сторонах таблицы. Угловые элементы объединяются в одну конфигурацию.
В МДНФ выписываем конъюнкции, состоящие из элементов, не меняющих своего значения в пределах одной конфигурации. Причем, если переменная сохраняет значение «1», то она записывается без отрицания, а если значение «0», то с отрицанием.