Найдем значение функции f2 на противоположных наборах аргументов

Класс самодвойственных функций (U).

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

Класс функций, сохраняющих единицу (К1).

Класс функций, сохраняющих нуль (К0).

Класс линейных функций от n аргументов (Ln).

Основные классы функций алгебры логики.

Рассмотрим пять классов булевых функций, которые называются замечательными классами, так как функции, принадлежащие к этим классам, обладают следующими свойствами: любая булева функция, полученная с помощью операций суперпозиции и подстановки из функций одного класса, обязательно будет принадлежать к тому же классу.

Напомним, что подстановкой называется замена одних аргументов функции другими или изменение порядка записи аргументов; суперпозицией называется подстановка в функцию вместо ее аргументов других функций.

В соответствии с теоремой Жегалкина любая булева функция представлена в виде полинома.

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

f(x₁ x₂ … x_n)= α₀α₁ x₁α₂ x₂ … α_n x_n,

где α₀, α₁, … , α_n – коэффициенты, равные 0 или 1.

Число различных линейных функций n переменных равно числу различных наборов вида <α₀ α₁ … α_n > и равно 2ⁿ⁺¹.

Пример. n=2. Класс L₂состоит из 8 функций:

f₀(xy)=0; f₃(xy)=x; f₅(xy)=y;

f₆(xy)= ; f₉(xy)=1xy;

f₁₀(xy)=1y; f₁₂(xy)=1x; f₁₅(xy)=1.

Отметим, что переключательные функции одного аргумента все линейны:

L₁: f₀(x)=0, f₁(x)=x, f₂(x)=1x, f₃(x)=1.

Теорема. При суперпозиции линейных функций и при подстановке в эти функции других переменных получаются линейные переключательные функции и только они.

Дано f₁(x₁ x₂ … x_n)= α₀α₁ x₁ … α_n x_n;

φ₁(y₁ y₂ … )= b₁₀ b₁₁ y₁ … ;

φ₂(y₁ y₂ … )= b₂₀ b₂₁ y₁ … ;

. . . . . . . . . . . . . . . . . . . .

φ_n(y₁ y₂ … )= b_n₀ b_n₁ y₁ … ,

Подставим φ_i вместо x_i функции f₁ , получим выражение f₂, в котором постоянные коэффициенты умножаются на линейные функции. Приведя подобные члены, получим представление функции f₂ в виде линейного полинома.

Пример. f₁(x₁ x₂ x₃)=1 x₁ x₂ x₃;

x₁=φ₁(y₁ y₂ y₃ y₄)= y₁ y₃y₄;

x₂=φ₂(y₁ y₂)= 1 y₁y₂;

x₃=φ₃(y₁ y₂ y₃ y₄)= 1y₁ y₂y₃y₄;

f₂(y₁ y₂ y₃ y₄)= 1 φ₁(y₁ y₂ y₃ y₄) φ₂(y₁ y₂) φ₃(y₁ y₂ y₃ y₄)=

=1 y₁y₃y₄1 y₁y₂1y₁y₂y₃y₄=1 y₁.

При любых подстановках x_i функция остается линейной.

Из линейных функций нельзя получить нелинейную, а наоборот можно.

Если функция на нулевом наборе аргументов <00…0> равна нулю, то говорят, что функция сохраняет нуль:

f(000…0)=0.

При фиксированном n число таких функций составляет половину всех булевых функций n аргументов, т.е. .

Пример. n=2. В класс К₀входят следующие функции:

f₀(xy), f₁(xy) , f₂(xy) , f₃(xy) , f₄(xy) , f₅(xy) , f₆(xy) , f₇(xy).

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

Пусть имеем

f₁(x₁ x₂ … x_n), φ₁(y₁ y₂ … ), …, φ_n(y₁ y₂ … ).

Все эти функции сохраняют нуль на нулевом наборе. Подставив вместо x_i функции φ_i, получим новую функцию

f₂(y₁ y₂ … )= f₁(φ₁,φ₂, …,φ_n).

Найдем значение f₂ на нулевом наборе:

f₂ (00 …0)= f₁ (000 …0)=0.

Так как на нулевом наборе все аргументы равны нулю, то любая подстановка этих аргументов не изменит значение функции.

Если булева функция на единичном наборе <111…1> аргументов равна единице, то говорят, что эта функция сохраняет единицу:

f(111…1)=1.

Так как на одном наборе <11..1> значение функции зафиксировано, то остается 2ⁿ-1 независимых наборов, т.е. число функций, сохраняющих единицу, равно половине от всех функций n переменных, т.е. .

Пример. n=2. Класс К₁содержит:

f₁(xy), f₃(xy) , f₅(xy) , f₇(xy) , f₉(xy) , f₁₁(xy) , f₁₃(xy) , f₁₅(xy).

Теорема. При суперпозиции переключательных функций, сохраняющих 1, и при подстановке в эти функции других переменных получаются функции, сохраняющие 1, и только они.

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

Число функций класса М оценивается асимптотически:

≤ φ_n ≤,

где φ_n – число монотонных функций от n аргументов; А– некоторая константа.

Пример. n=2. Класс М содержит

f₀(xy), f₁(xy) , f₃(xy) , f₅(xy) , f₇(xy) , f₁₅(xy).

При суперпозиции монотонных булевых функций и при подстановке в эти функции переменных получаются монотонные функции и только они. Имеем монотонные функции:

f₁(x₁ x₂ … x_n);

φ₁(y₁ y₂ … );

. . . . . . .

φ_n(y₁ y₂ …).

Пусть f₂(y₁ y₂ …)= f₁(φ₁,φ₂, …,φ_n).

Зафиксируем значение функции f₂ на некотором наборе < y₁ y₂ … >, а затем увеличим этот набор. При этом значение любой монотонной функции φ_i<y₁y₂… > уменьшиться не может, отсюда следует, что набор аргументов функции f₁ не уменьшится с увеличением набора функции f₂, а, следовательно, и значение функции f₂ не уменьшится. Аналогично будет при подстановке аргументов.

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

или, что то же самое,

Пример. n=2. Класс U содержит

f₃(xy) , f₅(xy) , f₁₀(xy) , f₁₂(xy).

При суперпозиции самодвойственных переключательных функций и при подстановке в эти функции переменных получаются самодвойственные функции и только они.

Имеем самодвойственные функции

f₁(x₁ x₂ … x_n);

φ₁(y₁ y₂ …);

. . . . . . .

φ_n(y₁ y₂ …).

Подставляя функции φ_i вместо аргументов x_i, получаем

f₂(y₁ y₂ … )= f₁(φ₁φ₂ …φ_n).