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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
78
Пример 1. Для функции
(
)
00110111
=
f построить несколько ДНФ .
Указать кратчайшую и минимальную среди них.
Решение. Предварительно построив таблицу истинности для
f
и
применяя преобразования, получим следующие ДНФ :
.;
;;
;;
;;
;;
3
6
7
11
15
5
4
3
2
1
5
4
3
2
1
=∨=
=∨=
=∨=
=∨=
=
=
D
D
D
D
D
zxyD
yxzxyxD
yxzyxyxD
zyxzyxzyxyxD
zyxzyxzyxzyxzyxD
ρ
ρ
ρ
ρ
ρ
Кратчайшей ДНФ является
5
D . У нее число логических слагаемых,
т.е. длина
2
=
S
наименьшее.
Минимальной ДНФ является
5
D , т .к.
3
51
=
=
≤≤
i
D
i
D
min
ρ
ρ
.
Определение 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
ρ
;
Шаг 4. Сравнить таблицы истинности для функции
f
и для ДНФ ,
двигаясь по упорядоченному множеству , полученному на 3-ем шаге .
Первая ДНФ , у которой таблица истинности будет такой, как у
функции
f
, является минимальной.
Определение 4. Импликантом функции
f
называется элементар-
ная конъюнкция
ρ
ρ
σ
σσ
iii
x&...&x&xK
2
2
1
1
= ,
{
}
10 ,
k
σ
,
{
}
n...,,,i
k
21
для
всех ρ,k 1 = такая, что
f
f
=
.
Импликант
K
функции
f
называется простым импликантом, если
после отбрасывания любой буквы
k
k
i
x
σ
из
получается элементарная
конъюнкция, не являющаяся уже импликантом функции
f
.