Минимизация булевых функций

Автор работы: Пользователь скрыл имя, 05 Апреля 2012 в 22:12, лекция

Описание

Элементарные конъюнкции(дизъюнкции) называются конституентами единицы(нуля), если он содержат все переменные функции.
В геометрическом смысле каждому набору переменных соответствует вершина n- мерного куба с координатами(например х1х2 х3). Элемент х1х2 х3 принято называть 0- кубом. Множество 0- кубов, на которых функция принимает единичные значения, называется кубическим комплексом К0 .

Работа состоит из  1 файл

Минимизация булевых функций.doc

— 121.50 Кб (Скачать документ)


Минимизация булевых функций

Основные понятия

Элементарные конъюнкции(дизъюнкции) называются конституентами единицы(нуля), если он содержат все переменные функции.

В геометрическом смысле каждому набору переменных соответствует вершина n- мерного куба с координатами(например х1х2 х3). Элемент х1х2 х3 принято называть 0- кубом. Множество 0- кубов, на которых функция принимает единичные значения, называется кубическим комплексом К0 .

Например,  для f=xyz

К0 будет иметь следующий вид 000

              011

              110

              010

Если рассматривать ребро куба, то увидим что задействуется два К0 куба и образуется К1 куб. Причем на месте где есть различие между кубами ставится Х. Например 100 и 101 различаются по третьей координате и следовательно запись для К1 имеет вид 100 и 10Х(т. е. рассматривается ребро куба).

Например, для К0     011

              100

              101

              110

              111

К1 будет иметь следующий вид    Х11

              10Х

              1Х0

              1Х1

              11Х

т.е. каждый 0- куб последовательно сравнивается друг с другом.

В кубе для набора из 3 переменных – 4 вершины образуют грань.

 

Карты Карно – специальные таблицы, позволяющие упрощать процесс поиска минимальной формы булева выражения(булевой функции).

Карта Карно для функций двух переменных

            х

00

10

01

11

y                         
 

Карта Карно для функций трех переменных

 

 

Изменение yz

00                            01                              11                            10

Изменение x    0

                         1                        

000

001

011

010

100

101

111(xyz)

110

 

Карта Карно для функций четырех переменных

 

 

Изменение x1x2

              00              01              11              10

                             00

Изменение          01

x3 x4                                11

                                           10

0000

0100

1100

1000

0001

0101

1101

1001

0011

0111

1111

1011

0010

0110

1110

1010

 

Примеры карт Карно булевых выражений

Пример№1. Упростить булево выражение    xyz

Карта Карно для функций трех переменных

 

 

Изменение yz

 

Изменение x

z

x

xz

 

xyz

Проставим 1 в ячейки, где конъюнкции в выражении и таблицы совпадает

 

 

Изменение yz

 

Изменение x

1

z

1

x

1

 

1

1

 

Запишем таблицу в другом виде

 

 

xy

y

 

 

x

 

z

1

1

 

 

 

1

1

1

 

 

В первом прямоугольнике получим   xy y=y, результат y.

          Пример№2.               Пусть f=xyy   yz     xyz

 

 

q

zq

z

 

 

 

 

y

1

 

 

1

xy

1

 

 

1

x

 

 

 

 

Информация о работе Минимизация булевых функций