Оглавление
Оглавление 1
Постановка задачи 2
Часть 1. Способы перечисления 3
Часть 2. Минимизация с помощью метода Квайна и Мак-Класски 7
Часть 3. Минимизация с помощью карт Карно 10
Часть 4. Минимизация на гиперкубе 14
Выводы 20
Постановка задачи
|
Получить минимальную форму заданной функции численной процедурой минимизации |
|
|
Вариант № 4 |
T={0,1,2,3,4,6,9,11,13,14,16,17,18,19,20,22,25,27,28,31} |
Требуется построить минимальную форму функции алгебры логики, заданной с помощью множества истинности T (множество наборов на которых функция истинна).
Минимальная форма функции – форма содержащая не большее число символов, чем любая другая ее форма. Любая функция имеет хотя бы одну минимальную форму, но в то же время одна функция может иметь несколько минимальных форм.
Часть 1.
Способы перечисления.
Теоретической базой при проектировании современных цифровых устройств, предназначенных для целей числовых вычислений, решения логических задач и задач управления, является булева алгебра или алгебра логики.
Существует несколько способов задания функций:
-
С помощью множеств – задаются множества наборов значений аргументов функции, на которых она принимает единичное, нулевое значения и значения, на которых она не определен.
По условию, нам задана функция алгебры логики множеством истинности:
T={0,1,2,3,4,6,9,11,13,14,16,17,18,19,20,22,25,27,28,31}
-
Аналитический – функция задается счетным множеством формул.
СДНФ
F(x) =
-
С помощью таблиц – таблиц истинности или «карт Карно» .
|
|
|
X1X2X3X4X5 |
F(x)5 |
|
0 |
|
0 0 0 0 0 |
1 |
|
1 |
|
1 0 0 0 0 |
1 |
|
2 |
|
0 1 0 0 0 |
1 |
|
3 |
|
1 1 0 0 0 |
1 |
|
4 |
|
0 0 1 0 0 |
1 |
|
5 |
|
1 0 1 0 0 |
0 |
|
6 |
|
0 1 1 0 0 |
1 |
|
7 |
|
1 1 1 0 0 |
0 |
|
8 |
|
0 0 0 1 0 |
0 |
|
9 |
|
1 0 0 1 0 |
1 |
|
10 |
|
0 1 0 1 0 |
0 |
|
11 |
|
1 1 0 1 0 |
1 |
|
12 |
|
0 0 1 1 0 |
0 |
|
13 |
|
1 0 1 1 0 |
1 |
|
14 |
|
0 1 1 1 0 |
1 |
|
15 |
|
1 1 1 1 0 |
0 |
|
16 |
|
0 0 0 0 1 |
1 |
|
17 |
|
1 0 0 0 1 |
1 |
|
18 |
|
0 1 0 0 1 |
1 |
|
19 |
|
1 1 0 0 1 |
1 |
|
20 |
|
0 0 1 0 1 |
1 |
|
21 |
|
1 0 1 0 1 |
0 |
|
22 |
|
0 1 1 0 1 |
1 |
|
23 |
|
1 1 1 0 1 |
0 |
|
24 |
|
0 0 0 1 1 |
0 |
|
25 |
|
1 0 0 1 1 |
1 |
|
26 |
|
0 1 0 1 1 |
0 |
|
27 |
|
1 1 0 1 1 |
1 |
|
28 |
|
0 0 1 1 1 |
1 |
|
29 |
|
1 0 1 1 1 |
0 |
|
30 |
|
0 1 1 1 1 |
0 |
|
31 |
|
1 1 1 1 1 |
1 |
Карты Карно
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
0 0 0 0 0 |
1 |
1 0 0 0 0 |
1 |
1 1 0 0 0 |
1 |
0 1 0 0 0 |
1 |
0 1 1 0 0 |
1 |
1 1 1 0 0 |
0 |
10 1 0 0 |
0 |
0 0 1 0 0 |
1 |
|||||||
|
|
0 0 0 1 0 |
0 |
1 0 0 1 0 |
1 |
1 1 0 1 0 |
1 |
0 1 0 1 0 |
0 |
0 1 1 1 0 |
1 |
1 1 1 1 0 |
0 |
1 0 1 1 0 |
1 |
0 0 1 1 0 |
0 |
|||||||
|
|
0 0 0 1 1 |
0 |
1 0 0 1 1 |
1 |
1 1 0 1 1 |
1 |
0 1 0 1 1 |
0 |
0 1 1 1 1 |
0 |
1 1 1 1 1 |
1 |
1 0 1 1 1 |
0 |
0 0 1 1 1 |
1 |
|||||||
|
|
0 0 0 0 1 |
1 |
1 0 0 0 1 |
1 |
1 1 0 0 1 |
1 |
0 1 0 0 1 |
1 |
0 1 1 0 1 |
1 |
1 1 1 0 1 |
0 |
1 0 1 0 1 |
0 |
0 0 1 0 1 |
1 |
|||||||
-
Графический – с помощью графического представления функции гиперкубом.
Совершенно нормальные формы однозначно представляют функции алгебры логики, но могут быть очень громоздкими. Реализация этих форм программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации.
Какого-либо правила группировки, гарантированно приводящего любую ДНФ к её минимальной форме, не существует. Приходится пробовать различные варианты и сравнивать результаты. Процедуру поиска заметно облегчают специально разработанные методы минимизации.
Наиболее очевидным способом минимизации СДНФ (совершенной дизъюнктивной нормальной формы логической функции: "дизъюнктивной" как сумма произведений; "совершенной", так как в каждое произведение входят все переменные; "нормальной", поскольку в любом произведении каждая переменная встречается лишь однажды) является выполнение преобразований, аналогичных преобразованиям обычной алгебры. Это возможно, поскольку для операций И и ИЛИ справедливы законы ассоциативности (сочетательный) и дистрибутивности (распределительный). Другими словами, аргументы можно группировать, а общие аргументы - выносить за скобки. Речь идёт о том, чтобы перейти от СДНФ к ДНФ с минимумом слагаемых, при этом количество множителей в каждом слагаемом должно быть также минимальным (избавиться от "совершенства"), то есть максимально уменьшить количество переменных и операций в СДНФ. При большом количестве переменных и операций часто трудно прийти сразу же к "минимальной" ДНФ, поэтому используют другие способы минимизации функций.