86371 (Булевы функции), страница 5
Описание файла
Документ из архива "Булевы функции", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. .
Онлайн просмотр документа "86371"
Текст 5 страницы из документа "86371"
=
О паре единиц в правой части диаграммы можно сказать то же самое: = .
Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.
Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение . Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:
m=n-log2M,
где n- число переменных,
M - число склеиваемых наборов.
Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».
Минимизация булевой функции заключается в нахождении минимального покрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкает к ее правому краю, а верхний край диаграммы примыкает к нижнему ее краю. Для удобства можно предположить, что диаграмма сворачивается в цилиндр как по горизонтали, так и по вертикали. После получения минимального покрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.
В диаграмме Вейча необходимо и достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.
Новую склейку можно образовывать в том случае, если есть хотя бы одна единичная клетка, не участвовавшая до этого в склейке.
Вся диаграмма должна быть покрыта наименьшим количеством склеек. В склейку может входить 2n соседних клеток (2, 4, 8, 16. и т.д.).
Рассмотрим несколько примеров.
Таблица 19 Таблица 20
X4 X3
|
|
|
|
| |||||||||||
х 1 |
| х1 | 1 | 1 |
| ||||||||||
х 1 | 1 | 1 | х3 | х1 | 1 | 1 | 1 | 1 | х3 | ||||||
| 1 | 1 | х3 |
| 1 | 1 | 1 | 1 | х3 | ||||||
| 1 | 1 |
|
| 1 | 1 |
| ||||||||
| х4 | х4 |
|
| х4 | х4 |
| ||||||||
f1= v f2= X4 v X3
-
7.4 Карты Карно
Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примеры карт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды - коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.
х2х3 х1 | 00 | 01 | 11 | 10 | х3х4 х1х2 | 00 | 01 | 11 | 10 | ||
0 | 000 | 001 | 011 | 010 | 00 | 0000 | 0001 | 0011 | 0010 | ||
1 | 100 | 101 | 111 | 110 | 01 | 0100 | 0101 | 0111 | 0110 | ||
11 | 1100 | 1101 | 1111 | 1110 | |||||||
10 | 1000 | 1001 | 1011 | 1010 | |||||||
а) | б) |
Рисунок 2- Карты Карно:
а) функции 3-х переменных;
б) функции 4-х переменных.
-
8.Особенности минимизации булевых функций большим числом переменных
Рассмотрим некоторые особенности работы с картами Карно для большого числа переменных. При числе переменных, равном или больше пяти, отобразить графически функцию в виде единой плоской карты невозможно. В таких случаях строят комбинированную карту, состоящую из совокупности более простых базовых карт, например карт для функции 4-х переменных. Процедура минимизации в этом случае состоит в том, что сначала находят минимальные формы внутри базовых карт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия для совокупности карт. Соседними клетками являются клетки, совпадающие при наложении базовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменных представлены на рис. 3 и 4. соответственно.
Р исунок 3-Карта Карно для булевой функции 5-ти переменных
х 3х4 х1х2 | 00 | 01 | 11 | 10 | 00 | 01 | 11 | 10 | |||||||||
00 | |||||||||||||||||
01 | |||||||||||||||||
11 | |||||||||||||||||
10 | |||||||||||||||||
х5=0 | х5=1 |
Рисунок 4- Карта Карно для булевой функции шести переменных
х3х4 х1х2 | 00 | 01 | 11 | 10 | 00 | 01 | 11 | 10 | 00 | 01 | 11 | 10 | 00 | 01 | 11 | 10 | |
00 | |||||||||||||||||
01 | |||||||||||||||||
1 1 | |||||||||||||||||
10 | (1) | (2) | (3) | (4) | |||||||||||||
х 5х6 | 00 | 01 | 11 | 10 |
По рисунку 4 можно сделать вывод, что соседними являются для 1-й базовой карты - 2-я и 4-я; для 2-й - 1-я и 3-я; для 3-й 2-я и 4-я; для 4-й - 1-я и 3-я.
При увеличении количества переменных на одну, площадь карты увеличивается в два раза - к ней пририсовывается еще такая же карта. При этом новая переменная равняется 1 на новой карте, и 0 на той, которая была ранее.
-
9.Минимизация конъюнктивных нормальных форм
Минимизация КНФ производится аналогично рассмотренным методам минимизации ДНФ булевых функций, поэтому остановимся лишь на основных положениях.
Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля X1 v v v X4
Определение. Имплицентой g булевой функции f называется функция, принимающая значение 0 на подмножестве нулевых наборов функции f.
Определение. Простой имплицентой функции f называется элементарная дизъюнкция, являющаяся имплицентой функции f, причем никакая ее собственная часть имплицентой функции f не является.
Задачей, минимизации КНФ является определение минимальной КНФ. Эта задача также решается в два этапа— поиск сокращенной КНФ (конъюнкция всех простых имплицент) и затем нахождение минимальной КНФ. Второй этап минимизации выполняется с помощью таблицы Квайна точно так же, как при поиске минимальной ДНФ, так как возможны только два варианта: либо данная простая имплицента поглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения: (A v x)A=A