Основы дискретной математики. Щипцов В.В - 34 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

34
булева функция, невелико. Ввиду громоздкости вычислений, ограничимся
случаем трех переменных.
Изложим вкратце идею метода неопределенных коэффициентов.
Исходную логическую функцию f(x,y,z) записывают в виде логической суммы
конъюнктивных членов с неопределенными коэффициентами, которые могут
быть равны либо 0, либо 1. Эти конъюнктивные члены представляют собой
возможные комбинации, составленные из переменных x,y,z и их отрицаний.
Неопределенные коэффициенты, фигурирующие в конъюнктивных членах,
принято снабжать двумя наборами индексов - нижним и верхним. Нижний
набор указывает на то, из каких переменных составлена конъюнкция, а верхний
говорит о том, взята переменная или ее отрицание. Например, коэффициент К
2
1
стоит при конъюнктивном члене, состоящем из одной переменной y (нижний
индекс 2), а единица указывает на то, что взята сама переменная, а не ее
отрицание; коэффициент К
13
01
говорит о том, что в соответствующей
конъюнкции взяты переменные x и z (нижние индексы 1 и 3), верхний индекс 0
говорит о том, что берется отрицание х, т.е. рассматриваемая конъюнкция
имеет вид x
⋅z. Аналогичным образом, например, коэффициент К
123
101
указывает,
что соответствующая ему конъюнкция имеет вид xyz.
Полученное таким образом соотношение для булевой функции f(x,y,z) с
неопределенными коэффициентами вычисляют на всех двоичных наборах
(x,y,z) (число которых равно восьми). Это приводит к системе восьми линейных
уравнений относительно неопределенных коэффициентов.
1
1
2
1
3
1
12
11
13
11
23
11
123
111
1
1
2
1
3
0
12
11
13
10
23
10
123
110
1
1
2
0
3
1
12
10
13
11
23
01
123
101
1
1
2
0
3
0
12
10
13
10
23
00
123
100
1
0
2
1
3
1
12
01
13
01
23
11
123
011
1
0
2
1
3
0
12
01
13
00
23
10
123
010
KKKK K K K
KKKK K K K
KKKK K K K
KKKK K K K
KKKK K K K
KKKK K K K
f (1,1,1)
f (1,1,0)
f (1,0,1)
f (1,0,0)
f (0,1,1)
+++ + + + =
++++++ =
+++ + + + =
+++ + + + =
++++++ =
++++++ =
+++ + + + =
++++++ =
f (0,1,0)
f (0,0,1)
f (1,0,0)
KKKK K K K
KKKKKKK
1
0
2
0
3
1
12
00
13
01
23
01
123
001
1
0
2
0
3
0
12
00
13
00
23
00
123
000
(18)
При минимизации конкретной булевой функции в правые части
написанных уравнений подставляют значения этой функции и среди решений
полученной системы отбирают те их них, которые содержат минимальное
количество переменных.
В качестве примера рассмотрим булеву функцию (13), которая была
минимизирована ранее по методу Кванта-Петрика. Для нее правые части
уравнений системы (18) имеют соответственно значения: 1, 1, 1, 0, 0, 1, 0, 1.

Страницы