Опр. 1. Любую булеву функцию можно представить многочленом Жегалкина однозначно с точностью до перестановки слагаемых

Любую булеву функцию можно представить многочленом Жегалкина однозначно с точностью до перестановки слагаемых.

Т.е. любую функцию можно выразить через полную систему многочлена {+, , 1}. Она полная, т.к. она может быть выражена через { , }. Х = Х+1

Тождества:

1. X+Y=Y+X 1^` XY=YX

2. (X+Y)+Z = X+(Y+Z) 2^` (XY)Z = X(YZ)

3. X+X = 0 3^` XX = X

4. X(Y+Z) = XY+XZ

5. 0+X = X

6. 0X = 0

7. 1X = X

Данные тождества доказываются с помощью таблицы истинности или по аналогии с основными равносильностями.

Доказательство теоремы основывается на полноте системы {+, , 1} и на всех вышеуказанных тождествах кроме 3 и 3^`.

Поиск по сайту: