Булевы функции от одной и двух переменных

Булевы функции от одной переменной – это отображения множества {0,1} в себя. Булевы функции от одной переменной можно рассматривать как унарные операции на множестве {0,1}. В следующей таблице приведены все четыре булевы функции от одной переменной.

x g₀(x) g₁(x) g₂(x) g₃(x)

--------------------------------

0 0 0 1 1

1 0 1 0 1

Имеем:

g₀(x)=0 – функция, тождественно равная 0 (тождественный ноль);

g₁(x)=x – тождественная функция;

g₂(x)=1–x – эта функция соответствует отрицанию и носит то же название; в теории булевых функций отрицание принято обозначать через x’, поэтому мы будем писать g₂(x)=x’;

g₃(x)=1 – функция, тождественно равная 1 (тождественная единица).

Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве {0,1}. В следующей таблице приведены все шестнадцать булевых функции от двух переменных (значения аргументов и функций выписаны в строках, функции перечисляются в столбце). Для некоторых функций указаны используемые обозначения и названия.

x₁ 0 0 1 1

x₂ 0 1 0 1

-------------------------------

f₀ 0 0 0 0 0 – тождественный ноль

f₁ 0 0 0 1 ⋅ умножение, конъюнкция

f₂ 0 0 1 0

f₃ 0 0 1 1 x₁

f₄ 0 1 0 0

f₅ 0 1 0 11 x₂

f₆ 0 1 1 0 ⊕ – сложение по модулю 2

f₇ 0 1 1 1 ∨ – дизъюнкция

f₈ 1 0 0 0 ↓ – стрелка Пирса

f₉ 1 0 0 1 ↔ – эквивалентность

f₁₀ 1 0 1 0

f₁₁ 1 0 1 1 ← – обратная импликация

f₁₂ 1 1 0 0

f₁₃ 1 1 0 1 → – импликация

f₁₄ 1 1 1 0 | – штрих Шеффера

f₁₅ 1 1 1 1 1 – тождественная единица

Комбинируя перечисленные функции (с помощью суперпозиций), можно строить более сложные булевы функции, в том числе и большего числа переменных, например, xy→zt и т.п. Булевы отрицание, конъюнкция (умножение), дизъюнкция, импликация обладают свойствами, подобными тем, которыми обладают соответствующие логические операции (с естественной заменой равносильности формул на равенство функций). Например, законы де Моргана принимают следующий вид (знак умножения, как это часто делается, опущен):

(xy)’=x’∨y’; (x∨y)’=x’y’.

Кроме того, имеем:

1’=0; 0’=1;

x∨x’=1; xx’=0;

0x=0; 1x=x; 0∨x=x; 1∨x=x.

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

x’ = x→0 = x|x = x↓x = 1⊕x;

xy = (x’∨y’)’ = x’↓y’ = (x↓x)↓(y↓y);

x∨y = (x’y’)’ = x’→y = =(x→y)→y = x’|y’ = (x|x)|(y|y);

x→y = x’∨y;

x↔y = (x→y) (y→x) = xy∨x’y’;

Все эти равенства легко проверяются с помощью таблиц.

Принцип двойственности естественным образом переносится на булевы функции. Приведем необходимые формулировки. Двойственной к булевой функции f(x,y,…,z) называется функция

f^*(x,y,…,z)=f’(x’,y’,…,z’).

Если f(x,y,…,z) представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой формуле конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции. x⊕y = xy’∨x’y.

ДНФ и КНФ

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

x y z f(x,y,z)

--------------------------------

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

Тогда

f(x,y,z) = x’y’z’∨xy’z’∨xyz.

Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция принимает значение 1. Каждое слагаемое содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 0 в соответствующем наборе. Так, набору (0,0,0) соответствует слагаемое x’y’z’, набору (1,0,0) – слагаемое xy’z’, набору (1,1,1) – слагаемое xyz. Каждый из дизъюнктивных членов принимает значение 1 на своем наборе значений переменных и значение 0 – на всех остальных. Дизъюнкция этих трех слагаемых принимает значение 1 лишь тогда, когда значение 1 принимает хотя бы одно из слагаемых. Таким образом, функция в правой части записанного равенства принимает значение 1 на тех же трех наборах значений аргументов, что и функция f (на остальных наборах обе эти функции принимают значение 0). Тем самым справедливость равенства установлена.

Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Получаемые при этом формулы называются совершенными дизъюнктивными нормальными формами, сокращенно СДНФ. Считается, что СДНФ тождественного нуля – это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого.

Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме, сокращенно СКНФ. СКНФ рассмотренной ранее функции имеет следующий вид:

f(x,y,z) = (x∨y∨z’)(x∨y’∨z)(x∨y’∨z’)(x’∨y∨z’)(x’∨y’∨z).

Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0. Каждый множитель содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 1 в соответствующем наборе. Так, набору (0,0,1) соответствует множитель xyz’, набору (0,1,0) – множитель xy’z, и т. д. Каждый из конъюнктивных членов принимает значение 0 на своем наборе значений переменных и значение 1 – на всех остальных. Конъюнкция этих трех множителей принимает значение 0 лишь тогда, когда значение 0 принимает хотя бы один из множителей. Таким образом, функция в правой части записанного равенства принимает значение 0 на тех же трех наборах значений аргументов, что и функция f.

Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.

Теорема. Пусть f(x₁,x₂,…,x_n) – произвольная булева функция. Тогда

f(x₁,x₂,…,x_n) = x₁⋅f(1,x₂,…,x_n) ∨ x₁’⋅f(0,x₂,…,x_n);

f(x₁,x₂,…,x_n) = (x₁∨f(0,x₂,…,x_n))(x₁’∨⋅f(1,x₂,…,x_n)).

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

f(x,y) = x⋅f(1,y) ∨ x’⋅f(0,y).

При любом y подстановка в правую часть x=1 и x=0 дает соответственно

1⋅f(1,y) ∨ 1’⋅f(0,y) = f(1,y) ∨ 0⋅f(0,y) = f(1,y) ∨ 0⋅= f(1,y);

0⋅f(1,y) ∨ 0’⋅f(0,y) = 0 ∨ 1⋅f(0,y) = 1⋅f(0,y) = f(0,y).

Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции слева и справа от знака равенства равны. На общий случай доказательство распространяется практически без изменений. Достаточно считать, что y обозначает не одну переменную, а набор переменных. Второе равенство из формулировки теоремы доказывается аналогично (впрочем, его справедливость следует из принципа двойственности).􀀀

Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции. Например,

f(x,y) = x⋅f(1,y) ∨ x’⋅f(0,y) =

= x⋅(y⋅f(1,1) ∨ y’⋅f(1,0)) ∨ x’⋅(y⋅f(1,1) ∨ y’⋅f(1,0)) =

= x⋅y⋅f(1,1) ∨ x⋅y’⋅f(1,0) ∨ x’⋅y⋅f(1,1)∨ x’⋅y’⋅f(1,0).

Функция f(x,y) представлена в виде дизъюнкции четырех дизъюнктивных членов. Те из них, для которых коэффициент f(α,β) равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции f(x,y)=x⊕y имеем f(0,0)=f(1,1)=0 и f(0,1)=f(1,0)=1, поэтому

x⊕y=x⋅y’ ∨ x’⋅y.

Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.

Например, x’yz, x’y – конъюнкты. Пустой конъюнкт (в который не входит ни одна переменная) считается равным 1. Дизъюнктивной нормальной формой (сокращенно ДНФ) называется дизъюнкция конечного числа конъюнктов. Ясно, что любая СДНФ является ДНФ. Характеристический признак СДНФ – в каждый из ее конъюнктов входят все переменные. Например, x’yz∨y’ – это ДНФ, не являющаяся совершенной. Представление булевой функции в виде СДНФ с точностью до порядка конъюнктов однозначно. При отказе от совершенности формы однозначность представления пропадает. Вообще говоря, одну и ту же булеву функцию можно представить разными способами в виде ДНФ.

Двойственным образом определяются конъюнктивные нормальные формы (КНФ). Элементарной дизъюнкцией (дизъюнктом) называют дизъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза. Пустой дизъюнкт считается равным 0. Конъюнктивной нормальной формой называется конъюнкция конечного числа дизъюнктов.

Не нашли, что искали? Воспользуйтесь поиском: