Специальная математика. Соловьев А.Е. - 28 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

X X
1
1
1 1
1
1
Z Z Z
2.1.8. Функциональная полнота
Совокупность логических операций функциолнально полна, когда какие-либо из операпций
совокупности обладают нижеперечисленными свойствами:
1. Несохранение 0 ( f(0, 0, ..., 0) = 1)
2. Несохранение 1 ( а(1, 1, ..., 1) = 0)
3. Не самодвойственность.
f(X
1
,X
2
,...,X
n
) f(X
1
,X
2
,...,X
n
)
4. Немонотонность.
1

2
...
n

1

2
...
n
f(
1
,
2
,...,
n
)<f(
1
,
2
,...,
n
)
5. Нелинейность.
Функция называется нелинейной, если она не может быть представлена в виде :
a
0
a
1
x
1
a
2
x
2
...,
где a
i
= 1 или 0
Примеры линейных функций:
1 X = X
a
0
= 1
a
1
= 1
a
2..
= 0
X Y - неравнозначность.
a
0
= 0
a
1
= 1
a
2
= 1
a
3..
= 0
Функционально полные наборы создают, например:
и &; и ; и . Операции штрих Шеффера и стрелка Пира каждая в отдельности
образуют функционально полный набор.
2.2. Логика предикатов
Предикат - логическая функция, аргументы которой могут принимать значения из
некоторой предметной функции, а сама функция может принимать значение истина либо
ложь.
Если переменная одна, то предикат одноместный, две - двухместный и т.д.
— 28 —
Y
Y
_
Y
     X               X

1Y       1       1       1   Y

                             _
1                        1   Y


Z            Z           Z

                                 2.1.8. Функциональная полнота

Совокупность логических операций функциолнально полна, когда какие-либо из операпций
совокупности обладают нижеперечисленными свойствами:

1. Несохранение 0 ( f(0, 0, ..., 0) = 1)
2. Несохранение 1 ( а(1, 1, ..., 1) = 0)
3. Не самодвойственность.

   f(X1,X2,...,Xn)  f(X1,X2,...,Xn)
4. Немонотонность.
   12...n 12...n
   f(1,2,...,n)

Страницы