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

6 7 8 9 10 11 12

Класс самодвойственных функций (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).