Основы синтеза и диагностирования автоматов. Воронин В.В. - 117 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

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

Рубрика: 

113
Класс Р
о
– это класс функций, сохраняющих нуль, т.е. равных
нулю на нулевом наборе
f(0,0,….,0)=0.
Класс
Р
1
– это класс функций, сохраняющих единицу, т.е. рав-
ных единице на единичном наборе
f(1,1,….,1)=1. Число функций в
классе
Р
о
и
Р
1
определяется выражением
n
2
2
-1
.
Класс L – это класс линейных функций. Функция & и
⊕
соот-
ветствуют обычным алгебраическим операциям умножения и сложе-
ния; если учесть, что
⎯х=х
⊕
1,
1)]1()1[()1()1( ⊕⊕⋅⊕=⊕⋅⊕=∧=∨ yxyxyxyx ,
то всякая функция алгебры логики может быть представлена ариф-
метическим полиномом (по модулю
2). Например,
х
∧
у=х
⋅
у;
х
∨
у=(х
⊕
1)
⋅
(у
⊕
1)
⊕
1=х
⋅
у
⊕
х
⊕
у
⊕
1
⊕
1=х
⋅
у
⊕
х
⊕
у;
х
→
у =
⎯
х
∨
у=(х
⊕
1)
⋅
у
⊕
(х
⊕
1)
⊕
у=х
⋅
у
⊕
у
⊕
х
⊕
1
⊕
у=
=х
⋅
у
⊕
х+1 (т.к. у
⊕
у=0);
х
∼
у= yx ⊕ =х
⊕
у
⊕
1.
Если логическая функция может быть представлена в виде
х
i1
⊕
х
i2
⊕
….
⊕
х
ik
⊕
a ,
где а константа (0 или 1), то она называется линейной.
Функции
⎯х, х
∼
у являются линейными, а функции х
∧
у, х
∨
у, х
→
у
–
не линейными.
Класс
М - это класс монотонных функций. Упорядочим множе-
ство {0,1}, полагая, что 0
<
1. Далее введем частичное упорядочение
двоичных наборов одинаковой длины. Пусть
α
=(
α
1
,
α
2
,…,
α
n
) и
β
=(
β
1
,
β
2
,…,
β
n
) - двоичные наборы. Будем считать, что
α<β
(младше,
предшествует), если
α
i
≤β
i
для всех i, причем, по крайней мере для
одного
i имеет место строгое неравенство. Например, 001
<
011. Надо

Страницы