Упражнение

Найдите число всех различных 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 монотонная.