МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное

учреждение высшего образования

«Юго-Западный государственный университет»

Лабораторная работа №4

По дисциплине «Математическая логика и теория алгоритмов»

Вариант №5

Выполнил: Бунина А.В.

студент группы ИБ-01б

Проверил: Добрица В.П.

профессор

Курск, 2021

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

⇒, | , ¬

Первый набор ⇒, |, ¬:

	Р0	P1	L	S	M
	-	+	-	-	-
|	-	-	-	-	-
¬	+	+	-	-	+

X

→

Y

1. Принадлежность классу T₀.

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

X

Y

X

→

Y

0

0

1

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

   X

   Y

   X

   →

   Y

   1

   1

   1

3. Принадлежность классу самодвойственных функций S.

Если функция на противоположных наборах принимает противоположные значения, то она принадлежит классу самодвойственных функций S. (0,0) = 1 и (1,1) = 1 (Запись не верна. Это же функция на этих наборах принимает значение 1.) - значения совпадают. Значит функция не принадлежит классу самодвойственных функций S.

X	Y	X→Y
0	0	1
0	1	1
1	0	0
1	1	1

Функция принадлежит классу самодвойственных функций (S), если на противоположных наборах она принимает противоположные значения. Проверяем:

Проверим значения на наборах {0, 0} и {1, 1}: 1 и 1 совпадают.

Поэтому функция не принадлежит классу S.

(А что такое двойственная функция?)

Определение. Булева функция f^*(x₁, …, x_n) называется двойственной булевой функции f(x₁, …, x_n), если она получена из f(x₁, …, x_n) инверсией всех аргументов и самой функции, то есть

f^*(x₁, …, x_n) = (  ₁, …,   _n).

4. Принадлежность классу линейных функций L.

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

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

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.

(Чем различаются понятия «алгебра Жегалкина» и «полиномы Жегалкина»?)

Ответ: Алгебра Жегалкина - множество булевых функций, рассматриваемое вместе с операциями конъюнкции и сложения (по модулю два).

А полиномы Жегалкина играю роль совершенных нормальных форм булевой алгебры в алгебре Жегалкина.

5. Принадлежность классу монотонных функций M.

Функция принадлежит классу монотонных функций M, если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β).

(А как определяется порядок на последовательностях из 0 и 1?)

Две последовательности из 0 и 1 α₁, …, α_n и (β₁, …, β_n) назовем соседними, если существует единственная координата i, что α_i < β_i и для всех j ≠ i выполняются равенства α_j = β_j .

(0,0) = 1 и (0,1) = 1 - монотонность не нарушена. (0,0) = 1 и (1,0) = 0 - монотонность нарушена. Значит функция не принадлежит классу монотонных функций M. (См. замечание в 3.)

Функция принадлежит классу монотонных функций (M), если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β).

Сравниваем соседние наборы по 1-й переменной:

Сравним значения {1} и {1}: условие монотонности выполнено.

Сравним значения {0} и {1}: условие монотонности выполнено.

Сравниваем соседние наборы по 2-й переменной:

Сравним значения {1,1} и {0,1}: условие монотонности нарушено.

Таким образом функция не принадлежит классу M.

X

|

Y

1. Принадлежность классу t0.

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

X

Y

X

|

Y

0

0

1

2. Принадлежность классу t1.

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

X

Y

X

|

Y

1

1

0

3. Принадлежность классу самодвойственных функций S.

Если функция на противоположных наборах принимает противоположные значения, то она принадлежит классу самодвойственных функций S.

(0,0) = 1 и (1,1) = 0 - значения противоположны.

(0,1) = 1 и (1,0) = 1 - значения совпадают. Значит функция не принадлежит классу самодвойственных функций S. (См. замечание в 3.)

X	Y	X|Y
0	0	1
0	1	1
1	0	1
1	1	0

Функция принадлежит классу самодвойственных функций (S), если на противоположных наборах она принимает противоположные значения. Проверяем:

Проверим значения на наборах {0, 0} и {1, 1}: 1 и 0 противоположны

Проверим значения на наборах {0, 1} и {1, 0}: 1 и 1 совпадают.

Поэтому функция не принадлежит классу S

4. Принадлежность классу линейных функций L.

Функция принадлежит классу линейных функций L, если её полином Жегалкина не содержит коньюнкций. Найдем полином Жегалкина.

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.

5. Принадлежность классу монотонных функций M.

Функция принадлежит классу монотонных функций M, если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β).

(0,0) = 1 и (0,1) = 1 - монотонность не нарушена.

(0,0) = 1 и (1,0) = 1 - монотонность не нарушена.

(0,1) = 1 и (1,1) = 0 - монотонность нарушена. Значит функция не принадлежит классу монотонных функций M.

¬X

1. Принадлежность классу t0.

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

X	¬X
0	1