Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 27 стр.

UptoLike

Составители: 

27
Пример 1. Для функции
(
)
00110111
=
f построить несколько ДНФ.
Указать кратчайшую и минимальную среди них.
Решение. Предварительно построив таблицу истинности для
f
и
применяя преобразования, получим следующие ДНФ:
1
2
3
4
5
1D
2D
3D
4D
5D
D=xyzЪ xyzЪ xyzЪ xyzЪ xyz;
ρ =15;
D=xyЪxyzЪ xyzЪ xyz; ρ =11;
D=xyЪxyzЪ xy; ρ =7;
D=xyЪxzЪ xy; ρ =6;
D=yЪxz; ρ =3.
Кратчайшей ДНФ является
5
D . У нее число логических слагаемых,
т.е. длина
2
=
S
наименьшее.
Минимальной ДНФ является
5
D , т.к.
15
i

min3
i
DD

rr
Определение 3. ДНФ функции
f
называется тупиковой, если от-
брасывание любого ее слагаемого или буквы приводит к неэквивалентной
ДНФ.
Тупиковая ДНФ функции
f
определяется неоднозначно. Среди ту-
пиковых ДНФ функции
f
всегда содержится и минимальная.
Приведем алгоритм построения минимальной ДНФ для функции
(
)
n
x...,,x,xf
21
.
Шаг 1. Построить всевозможные э.к. из переменных ,x,...,x,x,
n21
1
,x,...,x
n1
.x...xx...,,xx...,,xx
nji 2121
;
Шаг 2. Из построенных э.к. построить всевозможные ДНФ;
Шаг 3. Упорядочить множество всех полученных ДНФ на 2-м шаге в
направлении возрастания величин
i
D
r
;
Шаг 4. Сравнить таблицы истинности для функции
f
и для ДНФ,
двигаясь по упорядоченному множеству, полученному на 3-м шаге.
Первая ДНФ, у которой таблица истинности будет такой, как у
функции
f
, является минимальной.
Определение 4. Импликантом функции
f
называется элементар-
ная конъюнкция
r
r
s
ss
iii
x&...&x&xK
2
2
1
1
= ,
{
}
10,
k
Î
s
,
{
}
n...,,,i
k
21
Î
для
всех
r
,k 1= такая, что
f
f
K
=
Ú
.
Импликант
K
функции
f
называется простым импликантом, если
после отбрасывания любой буквы
k
k
i
x
s
из
K
получается элементарная
конъюнкция, не являющаяся уже импликантом функции
f
.