1 Называется полиномом Жегалкина.

X

→

Y

Найдем полином Жегалкина.

P(X, Y) = C0 ⊕ C2Y ⊕ C1X ⊕ C12XY 

P(0, 0) = C0 = 1

P(0, 1) = C0 ⊕ C2 = 1   =>   1 ⊕ C2 = 1   =>   C2 = 0

P(1, 0) = C0 ⊕ C1 = 0   =>   1 ⊕ C1 = 0   =>   C1 = 1

P(1, 1) = C0 ⊕ C2 ⊕ C1 ⊕ C12 = 1   =>   1 ⊕ 0 ⊕ 1 ⊕ C12 = 1   =>   0 ⊕ C12 = 1   =>   C12 = 1

Получаем полином Жегалкина:

P(X, Y) = 1 ⊕ X ⊕ XY

Полином Жегалкина содержит конъюнкции, поэтому функция не принадлежит классу линейных функций L.

X

|

Y

Найдем полином Жегалкина.

P(X, Y) = C0 ⊕ C2Y ⊕ C1X ⊕ C12XY 

P(0, 0) = C0 = 1

P(0, 1) = C0 ⊕ C2 = 1   =>   1 ⊕ C2 = 1   =>   C2 = 0

P(1, 0) = C0 ⊕ C1 = 1   =>   1 ⊕ C1 = 1   =>   C1 = 0

P(1, 1) = C0 ⊕ C2 ⊕ C1 ⊕ C12 = 0   =>   1 ⊕ 0 ⊕ 0 ⊕ C12 = 0   =>   1 ⊕ C12 = 0   =>   C12 = 1

Получаем полином Жегалкина:

P(X, Y) = 1 ⊕ XY

Полином Жегалкина содержит конъюнкции, поэтому функция не принадлежит классу линейных функций L.

¬X

- линейный многочлен, значит, функция принадлежит этому классу.

Г) Класс булевых ф-й, сохраняющих 0:

Среди данных ф-й подобных нет. (Обоснуйте.)

Функция  не принадлежит классу T₀, т.к. на нулевом наборе она не принимает значение 0.

X	Y	X → Y
0	0	1

Функция  не принадлежит классу T₀, т.к. на нулевом наборе она не принимает значение 0.

X	Y	X | Y
0	0	1

Функция  не принадлежит классу T₀, т.к. на нулевом наборе она не принимает значение 0.

X	¬X
0	1

Д) Класс булевых ф-й, сохраняющих 1:

Из данных ф-й к данному классу относится (Обоснуйте.)

1. Функция принадлежит классу t1, т.К. На единичном наборе она принимает значение 1.

X	Y	X → Y
1	1	1

Функция не принадлежит классу T₁, т.к. на единичном наборе она не принимает значение 1.

X	Y	X | Y
1	1	0

Функция не принадлежит классу T₁, т.к. на единичном наборе она не принимает значение 1.

X	¬X
1	0

Задача 2. Для указанной формулы найти эквивалентный полином Жегалкина.

(Вы перепутали обозначение операции.)

Выразим штрих Шеффера и стрелку Пирса с помощью элементарных логических операций:

Задача 3. Для указанного полинома Жегалкина указать эквивалентную булеву формулу.

xy yz x

1. 

2. 

3. (Почему заменили на ? Ведь это разные операции.)

x y = x ⊕ y ⊕ xy. Если xy  0 , то x  y  x  y .В данном случае

, поэтому данные операции можно считать эквивалентными.

Задача 4. Придумать примеры функций: а) немонотонную, б) не самодвойственную, в) нелинейную, г) не сохраняющую 0, д) не сохраняющую 1. Привести обоснование.

а) Немонотонная ф-я

X	Y	Y	XY
0	0	1	1
0	1	0	0
1	0	1	1
1	1	0	1

XY. Данная функция принадлежит к классу немонотонных функций, так как не удовлетворяет условию монотонности (00 меньше 01, но 1 не меньше или равно 0).

б) Не самодвойственная ф-я

X	Y	X	XY
0	0	1	0
0	1	1	1
1	0	0	0
1	1	0	0

XY. Данная функция не принадлежит к классу самодвойственных функций, так как не удовлетворяет условию самодвойственности (при 00 и 11, 0 равен 0). (Зачем это, если далее написано правильно?) Забыла убрать эту запись, когда исправляла.

XY. Данная функция не принадлежит к классу самодвойственных функций, так как не удовлетворяет условию самодвойственности (при a=00 и b=11 значения функции должны быть противоположны, в нашем случае f(a)=0 и f(b)=0).

в) Нелинейная ф-я

XY ⊕ X

XY)X  XYX

XY)X  XYX

X Y

X YДанная функция принадлежит к классу нелинейных функций, так как не удовлетворяет условию линейности (XY – конъюнкция длиной более 1).

г) Не сохраняющая 0

X	Y	XY	XY)
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

XY). Данная функция принадлежит к классу не сохраняющих 0 функций, так как не удовлетворяет условию (при 00 функция равна 1).

д) Не сохраняющая 1

X	Y	XY	XY)
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

XY). Данная функция принадлежит к классу не сохраняющих 1 функций, так как не удовлетворяет условию (при 11 функция равна 0).

Задача 5. Является ли данный набор булевых функций функционально полным?

Система F булевых функций называется функционально полной, если любая булева функция может быть представлена формулой над F, т.е. является суперпозицией булевых функций из F.

Критерий Поста: Система F булевых функций является полной тогда и только тогда, когда F целиком не содержится ни в одном из классов Поста.

Предполным классом К называется неполный класс, при добавлении любой функции f(x), которая не принадлежит ему, получается класс полный.

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0;

2. Хотя бы одна функция, не сохраняющая 1;

3. Хотя бы одна нелинейная функция;

4. Хотя бы одна немонотонная функция;

5. Хотя бы одна не самодвойственная функция.

Рассмотрим наши ф-и

x	y	x y
0	0	1
0	1	1
1	0	0
1	1	1

x y

СДНФ: (xy) (xy) (xy)

xy⊕ xy⊕ xy (Почему заменили на ⊕ ?)

x y = x ⊕ y ⊕ xy. Если xy  0 , то x  y  x  y . Поэтому, когда исходная формула – СДНФ, мы можем выполнить эквивалентное преобразование, заменив дизъюнкцию сложением по модулю 2.

(x⊕1)y⊕1)⊕ x⊕1)y⊕ xy

xy ⊕ x ⊕ y ⊕ 1 ⊕ xy ⊕ y⊕ xy

xy ⊕ x ⊕ 1– полином Жегалкина

Функция x y: а) не сохраняющая 0 (так как при a = 00, f(a) = 1); б) сохраняющая 1 (так как при a = 11, f(a) = 1); в) не линейная (так как полином Жегалкина содержит конъюнкцию); г) не монотонная (так как при a=01, b=10, f(a)=1 не меньше или равно f(b)=0); д) не самодвойственная (так как при a=00, b=11, f(a)=1 и f(b)=1).

x	y
0	0	0
0	1	0
1	0	0
1	1	1

СДНФ:

хy – полином Жегалкина

Функция : а) сохраняющая 0(так как при a = 00, f(a) = 0); б) сохраняющая 1(так как при a = 11, f(a) = 1); в) не линейная(так как полином Жегалкина содержит конъюнкцию);г) ) не монотонная (так как при a=01, b=10, f(a)=1 не меньше или равно f(b)=0);д)не самодвойственная (так как при a=00, b=11, f(a)=0 и f(b)=1)

Таким образом, набор функционально полный

2)

x	x
0	1
1	0

СДНФ: x

x ⊕ 1– полином Жегалкина.

Функция x: а) не сохраняющая 0, б) не сохраняющая 1, в) линейная, г) немонотонная, д) самодвойственная.

Функция x самодвойственная, так как на при противоположных значениях переменной, функция имеет противоположные значения (при a=0, f(a)=1, при a=1, f(a)=0).

Таким образом, набор  функционально полный (Вы уверены? Внимательно проверьте по критерию.)

Данный набор не является функционально полным, поскольку по теореме Поста не соблюдаются критерии 3 и 5.

1. Хотя бы одна функция, не сохраняющая 0;

2. Хотя бы одна функция, не сохраняющая 1;

3. Хотя бы одна нелинейная функция;

4. Хотя бы одна немонотонная функция;

5. Хотя бы одна не самодвойственная функция.