Упражнение. Найдите число всех различных n-местных булевых функций, принимающих одинаковые значения на одних и тех же наборах значений переменных

Найдите число всех различных n -местных булевых функций, принимающих одинаковые значения на одних и тех же наборах значений переменных. Замкнут ли класс таких функций?

Класс монотонных булевых функций

Введем на множестве всех n- местных двоичных векторов частичный порядок: вектор a = < а ₁ ,…,а_n > предшествует вектору b = < b ₁, …,b_n > тогда и только тогда, когда a ₁£ b ₁, …,a_n £ b_n. Записываем это так: a µ b.

Булева функция называется монотонной, если из того, что a предшествует b следует, что f (a) £ f (b),где f (a) = f (a ₁, …, a_n). Множество всех монотонных булевых функций обозначим через М. Легко видеть, функции отрицание, сумма по модулю два, эквиваленция и импликация немонотонны, а тождественная функция, конъюнкция и дизъюнкция монотонны.

ТЕОРЕМА. Класс М замкнут.

Доказательство. Пусть f ₁(х ₁, …, х_n) Î М, f ₂(у ₁, …, у_m) Î M,

a ₁ £ b ₁, …, a_{n + m – 1}£ b_{n+m –1}Þ f ₂(a_n,.., a_{n+m –1})£ f ₂(b_n, …, b_{n+m –1}).

Рассмотрим функцию f = f ₁(x ₁, …, x_{n –1}, f ₂(y ₁, …, y_m)).Для нее

f (a ₁, …, a_{n+m –1}) = f ₁(a _{1, …,} a_{n –1}, f ₂(a_n, …, a_{n+m –1})) £ f ₁(b ₁, …, b_{n –1},

f ₂(b_n,…, b_{n+m –1})) = f (b ₁, …, b_{n+m –1}) Þ f Î M.

Повторением этого рассуждения можно доказать, что любая суперпозиция функций из М вновь принадлежит М, а это значит, что класс М замкнут. ■

Упражнение

Докажите, что функции Шеффера и Пирса немонотонные, а функция h (x, y, z) = xy Ú xz Ú yz монотонная.