ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16652
Скачиваний: 202
186
Получилось выражение Жегалкина, в котором нет конъюнкций, следова-
тельно, заданная функция является линейной.
Линейные функции образуют функционально замкнутый класс, т. е. су-
перпозиция линейных функций всегда есть только линейная функция.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Укажите номера функций, являющихся линейными:
1) f = 0; 2) f = A+B; 3) f = 1+A; 4) f = AB; 5) f = 1+0·BC.
2. Какие функции являются линейными? Укажите их номера.
1) f = 0·AB+C; 2) f = A⊕B; 3) f = 1⊕AB; 4) f = AB;
5) f =
.
C
A
C
A
+
3. Какие функции являются нелинейными? Укажите их номе-
ра.
1) f = AB+1; 2) f = 1·0·A+B; 3) f = 1⊕ C
A
; 4) f = C
A
;
5) f =
.
C
A +
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
9.4 Самодвойственные функции
Булева функция называется самодвойственной, если
1
2
1
2
( ,
,...,
)
( ,
,...,
).
n
n
f A А
А
f A А
А
=
Согласно этому определению самодвойственная функция на противопо-
ложных наборах принимает противоположные значения. Два n-значных набора
называются противоположными (взаимно инверсными), если их арифметиче-
ская сумма в десятичном представлении есть число
.
1
2 −
n
Чтобы по заданному
набору найти ему противоположный, достаточно в нём нули заменить едини-
цами, а единицы – нулями. Например, если 01100 – заданный набор, то проти-
воположный ему – 10011.
Очевидно, что исследовать на самодвойственность необходимо только
такие функции, в которых число минтермов равно
,
2
1
−
n
т. е. на половине набо-
ров значений аргументов функция равна единице, и на половине – нулевое, так
как только среди них содержатся самодвойственные функции. Если число мин-
термов не равно
,
2
1
−
n
то функция является несамодвойственной.
187
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 9.3
· · · · · · · · · · · · · · · · · · · · · · ·
Определить, является ли самодвойственной функция
( , , , ) (4, 6, 7,10,11,12,13,14,15).
f A B C D =
Данная функция зависит от четырёх переменных и содержит девять мин-
термов. Это признак несамодвойственности, так как если бы она была самод-
войственной, то число её минтермов равнялось бы восьми. Таким образом, за-
данная функция в класс самодвойственных функций не входит.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 9.4
· · · · · · · · · · · · · · · · · · · · · · ·
Выяснить, является ли самодвойственной функция вида
.
)
,
,
,
(
D
B
A
D
C
A
D
B
A
ABD
D
C
B
A
f
+
+
+
=
Представим её в СДНФ, например при помощи карты Вейча:
( , , , ) (1, 2, 3, 6, 8,10,13,15).
f A B C D =
Функция содержит восемь минтермов, т. е. равна единице точно на поло-
вине наборов значений аргументов. Чтобы определить, является ли она самод-
войственной, все возможные минтермы четырёх переменных запишем в два ря-
да: в первом из них номера возрастают слева направо до номера 7, а во втором
убывают. Минтермы, входящие в заданную функцию, подчеркнём:
0 1 2 3 4 5 6 7
15 14 13 12 11 10 9 8
При таком расположении минтермов наборы в колонках, представленные
десятичными числами, являются противоположными. В каждой колонке нахо-
дится точно один подчёркнутый минтерм. Это говорит о том, что функция на
противоположных наборах принимает противоположные значения. Следова-
тельно, рассмотренная функция является самодвойственной.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 9.5
· · · · · · · · · · · · · · · · · · · · · · ·
Определить, является ли самодвойственной функция вида
.
)
,
,
,
(
D
B
A
D
C
A
D
B
A
BD
A
D
C
B
A
f
+
+
+
=
Её СДНФ имеет вид:
188
( , , , ) (1, 2, 3, 5, 6, 7,12,14).
f A B C D =
Данная функция, как и в предыдущем примере, содержит также восемь
минтермов. Проверим её на самодвойственность:
0 1 2 3 4 5 6 7
15 14 13 12 11 10 9 8
Из этой записи видно, что имеются противоположные наборы, на кото-
рых функция не меняется: 0 и 15 (оба минтерма не подчёркнуты), 1 и 14 (оба
подчёркнуты) и др. Следовательно, функция является несамодвойственной.
Класс самодвойственных функций функционально замкнут. Это значит, в
результате применения операции суперпозиции к самодвойственным функциям
всегда будут получаться только самодвойственные функции.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Укажите номера самодвойственных функций.
1) f = A ;
2) f = 1·A+B; 3) f =
;
C
A +
4) f =
D
ABC +
;
5) f = AB AB
+
.
2. Укажите номера несамодвойственных функций.
1) ( , , ) (0, 2, 4, 6, 8,10,12,14);
f A B C =
2) ( , , ) (0,1, 2, 4, 6);
f A B C =
3) ( , , , ) (0,1, 2, 5, 8, 9,11,12);
f A B C D =
4) ( , , ) (0,1, 2, 5);
f A B C =
5) ( , , , ) (0,1, 7, 8,10,11,12,13);
f A B C D =
6) ( , , ) (0,1, 4, 6).
f A B C =
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
9.5 Функции, сохраняющие единицу
Булева функция сохраняет единицу, если на единичном наборе значений
аргументов она принимает единичное значение. Например:
.
D
C
A
BCD
C
AB
f
+
+
=
Эта функция сохраняет единицу, так как на наборе 1111 она равна едини-
це. Функция
D
C
A
D
BC
BC
A
f
+
+
=
не сохраняет единицу, так как она равна нулю при
1.
A
B
C
D
= = =
=
189
Пусть функция представлена в СДНФ. Она сохраняет единицу, если в неё
входит минтерм с максимальным номером. Например:
( , , ) (1, 2, 3, 5, 6, 7).
f A B C =
Для трёх переменных максимальный номер равен 7. Минтерм с этим но-
мером входит в функцию, следовательно, она сохраняет единицу.
Функция, представленная в КНФ, сохраняет единицу, если в каждом ско-
бочном выражении, где записаны дизъюнкции, находится хотя бы одна неин-
версная переменная. Например:
.
)
)(
)(
(
E
D
C
A
D
C
B
C
B
A
f
+
+
+
+
+
+
=
В данной КНФ четыре скобочных выражения (отдельную букву E можно
рассматривать как частный случай скобочной дизъюнкции, содержащей только
одну букву). В каждом из них содержится неинверсная переменная. При замене
их единицами все скобочные дизъюнкции будут равны единице, вследствие че-
го функция примет единичное значение. Это признак того, что функция сохра-
няет единицу.
Функции, сохраняющие единицу, образуют функционально замкнутый
класс, т. е. если в этом классе применять операцию суперпозиции, то всегда бу-
дут получаться только функции, сохраняющие единицу.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Укажите номера функций, сохраняющих единицу.
1) f =
CD
A +
;
3) f =
;
BD
C
A
+
+
5) f =
;
B
A
B
A
+
2) f = (A + B)(C + D); 4) f =
D
BC
A
+
;
6) f =
.
E
D
BC
A
+
+
2. Укажите номера функций, не сохраняющих единицу.
1) ( , , ) (0, 2, 4, 6, 7);
f A B C =
2) ( , , ) (0,1, 2, 4, 6);
f A B C =
3) ( , , , ) (0,1, 2, 5, 8, 9,11,15);
f A B C D =
4) ( , , ) (0,1, 5);
f A B C =
5) ( , , , ) (0,1, 7, 8,11,12,13,15);
f A B C D =
6) ( , , ) (0, 2, 5, 6).
f A B C =
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
190
9.6 Функции, сохраняющие нуль
Булева функция сохраняет нуль, если на нулевом наборе она принимает
нулевое значение. Например, функция
CD
A
C
B
B
A
f
+
+
=
сохраняет нуль, так как она равна нулю на наборе 0000. Функция
D
C
A
C
A
AB
f
+
+
=
не сохраняет нуль, поскольку на нулевом наборе она равна единице.
По виду булевой функции легко определить, сохраняет ли она нуль:
а) функция, представленная в ДНФ, сохраняет нуль, если в каждой её
конъюнкции содержится хотя бы одна неинверсная переменная. Если же в за-
писи функции хотя бы одна конъюнкция состоит только из инверсных букв, то
эта функция нуль не сохраняет;
б) функция, представленная в КНФ, сохраняет нуль, если в неё входит не
менее одной дизъюнкции, где нет инверсных переменных. Например, функция
)
)(
)(
(
D
C
B
D
C
A
B
A
f
+
+
+
+
+
=
содержит дизъюнкцию A + B с неинверсными переменными. На наборе 0000
она равна нулю, следовательно, функция сохраняет нуль;
в) функция, заданная в СДНФ, не сохраняет нуль, если она содержит ну-
левой минтерм m
0
. Если же в ней нет минтерма m
0
, то функция нуль сохраняет.
Функции, сохраняющие нуль, образуют функционально замкнутый класс,
т. е. в результате применения операции суперпозиции к функциям, сохраняю-
щим нуль, всегда будут получаться только сохраняющие нуль функции.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Укажите номера функций, сохраняющих нуль.
1) f =
CD
A +
;
3) f =
;
BD
C
A
+
+
5) f =
;
B
A
B
A
+
2) f = A + B(C + D); 4) f =
D
ABC +
;
6) f =
.
E
D
BC
A
+
+
2. Укажите номера функций, не сохраняющих нуль:
1) ( , , ) (0, 2, 4, 6, 7);
f A B C =
2) ( , , ) (1, 2, 4, 6);
f A B C =
3) ( , , , ) (0,1, 2, 5, 8, 9,11,15);
f A B C D =
4) ( , , ) (0,1, 5);
f A B C =
5) ( , , , ) (1, 7, 8,11,12,13,15);
f A B C D =
6) ( , , ) (0, 2, 5, 6).
f A B C =
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·