Дискретная математика. Прокушев Л.А. - 18 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

16
Более удобный аналитический способ задания булевых функций
основан на использовании булевой алгебры функций с операцией
суперпозиции. Суперпозицией функций f
1
, f
2
, …, f
m
называется функ-
ция f, полученная с помощью подстановок этих функций друг в друга и
переименования переменных, а формулой называется выражение, опи-
сывающее эту суперпозицию, например, (
ху⊕
)
→
ху ху∨
. Формулу
можно вычислить, если уже вычислены значения всех ее подформул.
Пример. Вычислить формулу
32 1 1 2
(
)(&(
))
хх х xx
∨⊕ ⊕
на наборе
123
1, 1,
0.
хх х===
Используя табл. 2, получим:
32
1;
хх∨=
1121
&( ) 0
0;
хxxх
⊕=⋅=
32 1 1 2
(
)(&( ))10
1.
хх х xx
∨⊕ ⊕ =⊕=
О формуле, задающей функцию, говорят, что она реализует или пред-
ставляет функцию. В отличие от табличного задания представление
данной функции формулой не единственно. Например, используя мно-
жество функций {f
1
, f
7
, f
12
} (И, ИЛИ, НЕ), функцию f
8
(стрелка Пирса)
можно представить формулами:
Окончание таблицы 2
яицкнуФеинавзаН
-ечанзобО
еин
яинечанЗ x:
1100
яинечанЗ y:
1010
еынвиткиФалумроФ
f
9
-тнелавивкЭ
ьтсон
x ≡ y 1001
f
01
еинациртО у
ЕН( у)
0101x
f
11
яантарбО
яицакилпми
x ← y 1101
f
21
еинациртО х
ЕН( х)
0011y
f
31
яицакилпмИ x → y 1011
f
41
хиртШ
ареффеШ
xy 0111
f
51
-ацинидЕ
атнатснок
11111y,x1
y
v xy xy
y
v xy
v xy
v xy

Страницы