02Глава21-22 (Полезная книги), страница 3

f₉(AB)= m₀+m₃= m₀ m₃=

.

На базе функции 1, /\ и строится алгебра Жегалкина, но по своим свойствам она более близка к обычной алгебре и отличается от последней лишь тем, что логическое сложение заменено сложением по mod 2.

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

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

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

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

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

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

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)=1 x y;

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

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

L₁: f₀(x)=0, f₁(x)=x, f₂(x)=1 x, 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_n0 b_n1 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₄)= 1 y₁ 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₂ 1 y₁ y₂ y₃ y₄=1 y₁.

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

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

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

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

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.

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

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

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

f(111…1)=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₂ … >, а затем увеличим этот набор. При этом значение любой монотонной функции φ_i1y₂… > уменьшиться не может, отсюда следует, что набор аргументов функции f₁ не уменьшится с увеличением набора функции f₂, а, следовательно, и значение функции f₂ не уменьшится. Аналогично будет при подстановке аргументов.

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

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

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

Пример. 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).

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

Поскольку функции φ_i самодвойственные, то из соотношения

находим

Таблица 15

x 0 0 1 1

y 0 1 0 1 L K₀ K₁ M U Примечание

f₀ 0 0 0 0 x x x

f₁ 0 0 0 1 x x x

f₂ 0 0 1 0 x

f₃ 0 0 1 1 x x x x x

f₄ 0 1 0 0 x

f₅ 0 1 0 1 x x x x x

f₆ 0 1 1 0 x x

f₇ 0 1 1 1 x x x

f₈ 1 0 0 0 f₈ не принадлежит ни к

f₉ 1 0 0 1 x x одному из указанных

f₁₀ 1 0 1 0 x x классов функций

f₁₁ 1 0 1 1 x

f₁₂ 1 1 0 0 x x

f₁₃ 1 1 0 1 x

f₁₄ 1 1 1 0 f₁₄ не принадлежит ни к

f₁₅ 1 1 1 1 x x x одному из указанных

классов функций

Так как f₁ самодвойственная функция, то

Сравнивая последнее выражение с выражением f₂ , окончательно получаем

,

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

Свойства функций двух переменных представлены в табл.15.

§8. Полные системы булевых функций.

Определение. Система булевых функций {f₁, f₂, …,f_n} называется полной, если любая переключательная функция может быть представлена суперпозицией функций данной системы.

Теорема Поста-Яблонского. Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала:

• хотя бы одну функцию, не сохраняющую константу нуль;

• хотя бы одну функцию, не сохраняющую константу единица;

• хотя бы одну функцию, не являющуюся линейной;

• хотя бы одну функцию, не являющуюся монотонной;

• хотя бы одну функцию, не являющуюся самодвойственной.

Это критерий полноты системы.

Система функций {f₁, f₂, …,f_n}, являющаяся полной, называется базисом.

Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций f_i , образующих тот базис, превращает систему функций {f₁, f₂, …,f_n } в неполную.

Будем рассматривать функции, зависящие от n аргументов. Число различных функций равно .

Тривиальная полная система состоит из всех функций.

Функции инверсии, дизъюнкции и конъюнкции образуют полную систему. Это вытекает из основной теоремы, утверждающей, что любая булева функция может быть записана в виде дизъюнкции минтермов (или конъюнкции макстермов).

Базис { /\,\/,¯ } не минимален, так как может быть уменьшен за счет выбрасывания из него /\ или \/. Это следует из формул де Моргана:

Базисы {/\,¯} и {\/,¯} являются минимальными.

Другие базисы:

а) { ,/\,1}- функционально полная система (это следует из теоремы Жегалкина);

б) функция импликации и константа 1: {x→y,1};

в) функция импликации и инверсии : {x→y,¯}.

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

f₁₄(xy)=x | y= .

Доказательство. Выразим ¯ и /\ через функцию Шеффера:

Так как {¯,/\} – полная система, утверждение доказано.

Пример. Выразим функцию, используя только функцию Шеффера:

.

Пример. Доказать, что А↓В образует функционально полную систему

Так как инверсия и дизъюнкция выражаются только через функцию «стрелка Пирса», а {¯,\/} – функционально полная система, то А↓В является функционально полной системой.