ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5725
Скачиваний: 13
16
Решение. Если бы не знак инверсии (черта) над правой ча-
стью первой функции, то эта функция была бы представленной
в СДНФ, поскольку функция зависит от двух аргументов A и B и
оба эти аргумента входят в обе конъюнкции, которые являются
минтермами. Но знак отрицания, поставленный над конъюнкци-
ей или дизъюнкцией, всегда приводит к выражению, которое не
относится к нормальным формам. Следовательно, первая функ-
ция к СДНФ не относится.
Вторая и шестая функции заданы одиночными минтермами,
следовательно, обе эти функции являются представленными в
СДНФ.
Третья функция не относится к СДНФ по той же причине,
что и первая, т.е. из-за знака инверсии, поставленного над вто-
рой конъюнкцией.
Четвертая функция не является дизъюнкцией минтермов,
следовательно, она представлена не в СДНФ.
В пятой функции не указаны аргументы, от которых она за-
висит, поэтому с уверенностью нельзя утверждать, что функция
представлена в СДНФ.
Седьмая функция не относится к СДНФ из-за знака инвер-
сии, поставленного над конъюнкцией
.
AB
Ответ: 2, 6. (В компьютер вводим 26.)
Пример 4. Укажите номера всех функций, представленных
в СДНФ.
1)
( , )
;
f A B
AB
AB
AB
=
+
+
2)
( )
;
f C
C
=
3)
( , , )
(
)(
)(
);
f A B C
A
B
CD A
BC
C A
B
C
=
+ +
+
+
+ +
4)
( , , , )
;
f A B C D
A
B
C
D
= + + +
5)
;
f
ABC
BCD
ACD
ABD
=
+
+
+
6)
( , , )
;
f A B C
ABC
ABC
ABC
=
+
+
7)
( , , , )
;
f A B C D
ABCD
=
8)
( , , , )
;
f A B C D
A
B
C
D
= + + +
9)
( , , , )
.
f A B C D
ABD
=
Ответ: 1, 2, 6, 7. (В компьютер вводим 1267.)
17
2.2 Тесты по теме № 3: «ДНФ булевых функций»
Функция называется представленной в ДНФ, если она запи-
сана в виде дизъюнкции конъюнкций, но в отличие от СДНФ
конъюнкции могут содержать любое число аргументов. Отсюда
следует, что всякая совершенная дизъюнктивная нормальная
форма одновременно является и представленной в ДНФ. Пояс-
ним это примерами тестов.
Пример 1. Укажите номера всех функций, представленных
в ДНФ.
1)
( , , )
;
f B C D
BCD
BCD
=
+
2)
( , , , )
(
)
;
f A B C D
AB
C D
AC
=
+
+
3)
( , , , )
(
);
f A B C D
ABC C
D
=
+
4)
( , , )
;
f A B C
A
B
C
= + +
5)
( , , , )
(
)(
);
f A B C D
B
C
D D
A
=
+ +
+
6)
( , , , )
;
f A B C D
A
=
7)
( , , , )
(
);
f A B C D
A
D C
D
= +
+
8)
( , , , )
.
f A B C D
A
DC
D
= +
+
Решение. Из всех восьми перечисленных функций в
ДНФ представлены три функции: 1, 4 и 6. Вторая, седьмая
и восьмая функции относятся к формам высшего порядка.
Третья и пятая функции представлены в КНФ.
Ответ: 1, 4, 6. (В компьютер вводим 146.)
Пример 2. Укажите номера всех функций, представленных
в ДНФ.
1)
( , , , )
;
f A B C D
AC
=
2)
( , , , )
;
f A B C D
AB
CD
AD
=
+
+
3)
( , , )
;
f A B D
A
=
4)
( , , , )
(
);
f A B C D
ABCD
ABCD
ABCD
AB C
D
=
+
+
+
+
5)
( , , )
;
f A B E
ABE
ABE
=
+
6)
( , , )
;
f A B C
ABC
AC
BC
AC
=
+
+
+
7)
( , , , )
(
)
.
f A B C D
A
B
C
D ABCD
=
+ + +
18
Решение. В ДНФ представлены функции 1, 2, 3, 5 и 6. Чет-
вертая функция относится к формам высшего порядка, а седьмая
представлена в КНФ.
Ответ: 1, 2, 3, 5, 6. (В компьютер вводим 12356.)
Пример 3. Укажите номера всех функций, представленных
в ДНФ.
1)
( , )
;
f A B
AB
AB
=
+
2)
( , , , )
;
f A B C D
A
BC
BCD
ACD
= +
+
+
3)
( , , , )
;
f A B C D
A
B
C
D
= + + +
4)
( , , , )
;
f A B C D
CD
AB
=
+
5)
( , , , )
(
);
f A B C D
ABC C
D
=
+
6)
( , , , )
;
f A B C D
ABC
ABC
ABC
=
+
+
7)
( , , , )
;
f A B C D
ABCD
=
8)
( , , , )
.
f A B C D
ABCD
=
Решение. Функции 1 и 8 представлены со знаком ин-
версии над конъюнкцией, а функция 4 — над дизъюнкци-
ей. Поэтому они не относятся к ДНФ. Функция 5 записана
в КНФ. Все остальные функции представлены в ДНФ.
Ответ: 2, 3, 6, 7.
(В компьютер вводим 2367.)
Пример 4. Укажите номера всех функций, представленных
в ДНФ.
1)
( , , , , )
;
f A B C D E
AC
BCDE
ACDE
ABD
=
+
+
+
2)
( , , , )
(
)(
)(
);
f A B C D
A
B
C A
B
C A
B
C
=
+ +
+ +
+ +
3)
( , , , )
;
f A B C D
AB
=
;
)
,
,
,
(
4)
D
D
C
B
A
f
=
5)
( , , , )
;
f A B C D
A
B
C
D
= + + +
6)
( , , , )
;
f A B C D
ABCD
ABCD
=
+
7)
( , , , )
;
f A B C D
ABCD
ABC D
=
+
8)
( , , , )
(
)(
)(
).
f A B C D
A
B
C
D B
C
D A C
D
=
+ + +
+ +
+ +
Ответ: 1, 3, 4, 6.
(В компьютер вводим 1346.)
19
2.3 Тесты по теме № 4: «КНФ булевых функций»
Функция называется представленной в КНФ, если она запи-
сана в виде конъюнкции дизъюнкций, при этом отдельная
дизъюнкция, а также отдельная конъюнкция также относятся к
КНФ. Поясним это примерами тестов.
Пример 1. Укажите номера всех функций, представленных
в КНФ.
1)
( , , , )
;
f A B C D
C
BCD
ACD
ABD
= +
+
+
2)
( , , , )
(
)
;
f A B C D
ABCD
C D
AC
=
+
+
3)
( , , , )
(
);
f A B C D
ABC C
D
=
+
4)
( , , )
(
);
f A B C
A BC
ABC
=
+
5)
( , , , )
(
)(
)(
);
f A B C D
A
D B
C
D D
AC
=
+
+ +
+
6)
( , , , )
;
f A B C D
CD
=
7)
( , , , )
(
).
f A B C D
C
BCD C
D
= +
+
Решение. Выражения 2, 4, 5 и 7 — это формы высших по-
рядков. Выражение 1 — ДНФ. К конъюнктивным нормальным
формам относятся только выражения 3 и 6.
Ответ: 3, 6.
Пример 2. Укажите номера всех функций, представленных
в КНФ.
1)
( , , , )
;
f A B C D
A
B
C
D
= + + +
2)
( , , , )
;
f A B C D
A CD
AD
= +
+
3)
( , , )
;
f A B D
ABD
=
4)
( , , , )
;
f A B C D
ABCD
=
5)
( , , )
;
f A B E
ABE
=
6)
( , , , )
(
);
f A B C D
ABC B
D
=
+
7)
( , , , )
(
)
.
f A B C D
A
B
C
D ABCD
=
+ + +
Решение. Не являются КНФ выражения: 2 — так как это
ДНФ, 4 и 5 — из-за знака инверсии над конъюнкцией. Осталь-
ные выражения представлены в КНФ.
Ответ: 1, 3, 6, 7.
20
Пример 3. Укажите номера всех функций, представленных
в КНФ.
1)
( , )
;
f A B
A
B
= +
2)
( , , , )
;
f A B C D
ABC
=
3)
( , , , )
;
f A B C D
A
B
C
D
= + + +
4)
( , , , )
;
f A B C D
A
B
C
D
= + + +
5)
( , , , )
(
)(
);
f A B C D
A B
C C
D
=
+
+
6)
( , , , )
;
f A B C D
ABC
ABC
ABC
=
+
+
7)
( , , , )
;
f A B C D
ABCD
=
8)
( , , , )
;
f A B C D
ABCD
=
9)
( , , , )
(
)(
).
f A B C D
AB
C
D A
D
=
+ +
+
Решение. Выражение 3 не является КНФ из-за знака инвер-
сии над дизъюнкцией. Выражение 6 — ДНФ. В восьмой функ-
ции содержится инверсия над конъюнкцией, поэтому она к КНФ
не относится. Выражение 9 не является КНФ из-за конъюнкции
AB, находящейся в первой скобочной дизъюнкции.
Ответ: 1, 2, 4, 5, 7.
Пример 4. Укажите номера всех функций, представленных
в КНФ.
1)
( , , , , )
;
f A B C D E
ABCE
=
2)
( , , , )
(
)(
)(
);
f A B C D
A
B
C A
B
C A
B
C
=
+ +
+ +
+ +
3)
( , , , )
;
f A B C D
AB
=
4)
( , , , )
;
f A B C D
AB
C
D
A
=
+ + +
5)
( , , , )
(
) ;
f A B C D
A
B
C D
=
+ +
6)
( , , , )
;
f A B C D
A
B
C
D
ABCD
= + + + +
7)
( , , , )
(
)(
);
f A B C D
CD B
C
D A C
D
=
+ +
+ +
8)
( , , , )
(
)(
);
f A B C D
CD B
C
D A C
D
=
+ +
+ +
9)
( , , , )
.
f A B C D
A
B
C
D
= + + +
Ответ: 1, 2, 3, 5, 7, 9.