ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6748
Скачиваний: 28
76
Теперь мы можем составить таблицу, отражающую принад-
лежность каждой из функций двух переменных к рассмотренным
классам функций
(табл. 3.6).
Таблица 3.6 – Свойства функций двух переменных
Свойства функции
Обозначе-
ние функ-
ции
Наименование
функции
Сохра-
няю-
щая 0
Сохра-
няю-
щая 1
Самодвой-
ственность
Моно-
тонность
Линей-
ность
f
1
= 0
Нулевая функция
+ -
-
+ +
f
2
= x
1
x
2
Конъюнкция +
+ - + -
f
3
= x
1
→ x
2
Запрет x
1
f
4
= x
1
Повторение x
1
f
5
= x
2
→ x
1
Запрет x
2
f
6
= x
2
Повторение x
2
f
7
= x
1
⊕ x
2
Сложение по |2|
f
8
= x
1
٧ x
2
Дизъюнкция
f
9
= x
1
↓ x
2
Стрелка Пирса
f
10
= x
1
∼ x
2
Эквивалентность
f
11
=
⎯x
2
Отрицание x
2
f
12
= x
2
→
x
1
Импликация x
2
в
x
1
f
13
=
⎯x
1
Отрицание x
1
f
14
= x
1
→
x
2
Импликация x
1
в
x
2
f
15
= x
1
| x
2
Штрих Шеффера
f
16
= 1
Единичная
функция
77
Эта таблица весьма
полезна при выявлении полных систем бу-
левых функций. В ней заполнены только две первых строки. Остав-
шуюся часть таблицы заполните самостоятельно.
3.5
Минимизация
дизъюнктивных
нормальных
форм
3.5.1
Основные
определения
Теорема о полноте даёт ответ на вопрос, из какой системы
функций можно получить в виде суперпозиции любую функцию. Но
в практических задачах нужна не столько возможность, сколько
правила, пользуясь которыми можно получить представление, оп-
тимальное в некотором смысле. Каждое представление функции в
виде суперпозиции можно охарактеризовать некоторым числом,
которое называется сложностью данного представления (напри-
мер, число применений операции суперпозиции) и зависит от кон-
кретной задачи. Тогда можно поставить задачу об отыскании пред-
ставления булевой функции наименьшей сложности. В принципе,
такую задачу всегда можно решить последовательным перебором
различных суперпозиций функций системы. Рассмотрим теперь су-
перпозиции над системой функций, содержащей лишь конъюнкцию,
дизъюнкцию и отрицание. Именно для этих суперпозиций методы
минимизации разработаны достаточно хорошо. Чтобы дать точную
формулировку задачи, приведем некоторые определения.
Элементарной конъюнкцией U
i
называется выражение
U
i
=
r
r
i
i
x
x
σ
σ
...
1
1
, где все
j
i
x
(j = 1,…,r) – различны, а r –
ранг конъюнкции. Единица считается конъюнкцией нулевого ран-
га.
Дизъюнктивной нормальной формой (ДНФ) называется
дизъюнкция N = U
1
٧ U
2
٧…٧
U
k
элементарных конъюнкций
U
1
, U
2
,..., U
k
. Совершенная ДНФ – частный случай ДНФ.
Минимальной ДНФ функции f (x
1
,...,x
n
) называется ДНФ
N = U
1
٧ U
2
٧…٧
U
k,
представляющая функцию f (x
1
,...,x
n
) и содер-
жащая наименьшее количество букв по сравнению с другими ДНФ,
78
то есть число букв в N равно min
r
i
i
k
=
∑
1
, где r
i
- ранг конъюнкции U
i
,
а минимизация проводится
по всем ДНФ функции f (x
1
,...,x
n
).
Тогда задача об отыскании представления булевой функции
наименьшей сложности формулируется так: для всякой функции
найти представление в виде минимальной ДНФ.
Прежде чем описать метод решения задачи дадим ещё несколь-
ко определений.
Импликантом функции f (x
1
,...,x
n
) называется элементарная
конъюнкция U
i
=
x
i
1
1
σ
...
x
i
r
r
σ
, если выполнено соотношение
U
i
→ f (x
1
,...,x
n
)
≡
1. Это означает, что если на некотором наборе
импликант U
i
обращается в единицу, то функция f(x
1
,...,x
n
) на этом
наборе тоже обращается в единицу. Любая элементарная конъюнк-
ция произвольной совершенной ДНФ является импликантом данной
функции.
Простым импликантом функции f (x
1
,...,x
n
) называется им-
пликант функции f (x
1
,...,x
n
) , если элементарная конъюнкция, полу-
чающаяся из него удалением любой буквы, не является импликан-
том функции.
Сокращенной ДНФ функции f (x
1
,...,x
n
) называется дизъюнк-
ция всех простых импликантов функции f (x
1
,...,x
n
).
Теорема 5 (без доказательства). Сокращённая ДНФ представ-
ляет функцию f (x
1
,...,x
n
).
Теорема 6 (без доказательства). Минимальная ДНФ функции
f (x
1
,...,x
n
) получается из ее сокращённой ДНФ удалением некото-
рых элементарных конъюнкций.
3.5.2
Этапы
минимизации
ДНФ
В силу теоремы 6 получение минимальной ДНФ можно разбить
на два этапа.
1.
Нахождение сокращенной ДНФ.
2.
Нахождение тупиковых ДНФ (таких, из которых нельзя уда-
лить ни одного простого импликанта) путём удаления подмно-
жества элементарных конъюнкций из сокращённой ДНФ. Вы-
бор минимальной из полученных тупиковых ДНФ.
79
Рассмотрим первый этап получения минимальной ДНФ. Ме-
тод получения сокращённой ДНФ функции f(x
1
,...,x
n
) из ее совер-
шенной ДНФ состоит в последовательном применении двух равно-
сильных преобразований:
1) операции полного склеивания, которая состоит в замене
выражения Ax ٧ A
⎯x на A, так как
Ax ٧ A
⎯x
≡
A (x ٧
⎯x)
≡
A·1
≡
A;
2) операции неполного склеивания, которая состоит в заме-
не Ax ٧ A
⎯x на Ax ٧ A⎯x ٧ A, так как
Ax ٧ A
⎯x ٧
A
≡
A (x ٧
⎯x) ٧ A
≡
A ٧ A = A ;
3) операции поглощения, которая состоит в замене
AB ٧ A на A, так как AB ٧ A
≡
A (B ٧ 1)
≡
A.
Здесь A и B – произвольные элементарные конъюнкции.
Теорема 7 (без доказательства). Сокращённую ДНФ функ-
ции f (x
1
,...,x
n
) можно получить из ее совершенной ДНФ, применяя
все возможные операции неполного склеивания, а затем операции
поглощения.
Пример 1. Построить сокращённую ДНФ функции
f (x
1
, x
2
) = x
1
→ x
2
. Имеем
f (x
1
, x
2
) =
⎯x
1
⎯x
2
٧
⎯x
1
x
2
٧
x
1
x
2
=
⎯x
1
⎯x
2
٧
⎯x
1
x
2
٧
⎯x
1
٧ x
1
x
2
=
⎯= x
1
⎯x
2
٧
⎯x
1
x
2
٧
⎯x
1
٧ x
1
x
2
٧ x
2
=
⎯x
1
٧ x
2
.
Теперь перейдем ко второму этапу получения минимальной
ДНФ.
Пусть дана сокращённая ДНФ функции f (x
1
,...,x
n
):
N = U
1
٧ U
2
٧
…
٧ U
k
. Простой импликант называется ядерным
(входящим в ядро функции f (x
1
,...,x
n
) ), если
k
U
i
→
٧
U
j
/≡
1.
j = 1
i
≠ j
Эта запись означает, что простой импликант U
i
является ядер-
ным импликантом функции f (x
1
,...,x
n
), если существует набор
α = (α
1
,...,
α
n
), на котором импликант U
i
обращается в 1, а все ос-
тальные импликанты сокращённой ДНФ
− в ноль.
Пример 2. Найти ядерные импликанты функции f (x
1
,x
2
,x
3
,x
4
),
заданной своей сокращённой ДНФ
⎯x
2
⎯x
4
٧
x
1
⎯x
4
٧
x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
.
80
Простой импликант x
2
⎯x
4
является ядерным, так как на наборе
(0,0,0,0)
⎯x
2
⎯x
4
= 1, а дизъюнкция оставшихся импликантов
x
1
⎯x
4
٧
x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
= 0.
Простой импликант x
1
⎯x
4
− неядерный, так как он равен еди-
нице на наборах {1,0,0,0}, {1,0,1,0}, {1,1,0,0}, {1,1,1,0}, но на этих
же наборах
⎯x
2
⎯x
4
٧
x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
= 1,
следовательно
x
1
⎯x
4
→⎯x
2
⎯x
4
٧ x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
≡
1.
Простой импликант x
1
x
2
− ядерный, так как на наборе {1,1,0,1}
x
1
x
2
= 1, а
⎯x
2
⎯x
4
٧
x
1
⎯x
4
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
= 0.
Простой импликант x
2
x
3
x
4
− неядерный, так как на наборах
{0,1,1,1}, {1,1,1,1}
⎯x
2
⎯x
4
٧
x
1
⎯x
4
٧
x
1
x
2
٧
⎯x
1
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
= 1.
Простой импликант
⎯x
1
x
3
x
4
− неядерный, так как на наборах
{0,0,1,1}, {0,1,1,1}
⎯x
2
⎯x
4
٧
x
1
⎯x
4
٧
x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
⎯x
2
x
3
= 1;
Простой импликант
⎯x
1
⎯x
2
x
3
− неядерный, так как на наборах
{0,0,1,0}, {0,0,1,1}
⎯x
2
⎯x
4
٧
x
1
⎯x
4
٧
x
1
x
2
٧
x
2
x
3
x
4
٧
⎯x
1
x
3
x
4
= 1.
Теорема 8 (без доказательства). Простой импликант U
i
входит
во все тупиковые ДНФ тогда и только тогда, когда U
i
входит в
ядро функции f (x
1
,...,x
n
), то есть тогда и только тогда, когда он явля-
ется ядерным.
Следствие. Пусть ядро f (x
1
,...,x
n
) состоит из импликантов
U
ℓ
1
, ... ,U
ℓ
m
, тогда импликант U
ℓ
, для которого выполнено со-
отношение
m
U
ℓ
→
٧
U
ℓ
j
≡
1
j = 1
(импликант U
ℓ
обращается в единицу на тех же наборах, что и
дизъюнкция ядерных импликантов), не входит ни в одну из тупико-
вых ДНФ функции f (x
1
,...,x
n
).
Возвращаясь к примеру 2, отметим, что импликант x
1
⎯x
4
удов-
летворяет следствию из теоремы 8: x
1
⎯x
4
→⎯x
2
⎯x
4
٧
x
1
x
2
≡
1 и по-
этому не входит ни в одну тупиковую форму.
Импликант x
2
x
3
x
4
, для которого