Некоторые свойства элементарных функций

1. Функции конъюнкция, дизъюнкция, сумма по модулю 2 обладают свойством ассоциативности, что позволяет опускать скобки и использовать следующие обозначения:

_{n n}

٨x_i = x₁ x₂ ... x_n , ٧x_i = x₁ ٧x₂ ٧...٧x_n ,

^{i=1 i=1}

2. х₁х₂=х₁ ٧х₂, х₁ ٧ х₂=х₁х₂– закон де Моргана,

– закон двойного отрицания.

3. х х = х, х ٧ х = х, хх = 0, х٧х = 1,

х 0 = 0, х 1 = х, х ٧0 = х, х٧1 = 1.

Свойства можно проверить по таблице булевых функций (табл. 3.5).

3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формы

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

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

_{=(1,...,1)}

f (x₁,x₂...,x_n) = ٧f (₁,₂...,_n) х₁^1 х₂^2 ... х_n^n , (4)

^{=(0,...,0)}

где _i  {0, 1}, x_i⁰ =x_i, x_i¹ = х_i ,  = (₁,...,_n) и дизъюнкция берётся по всем n-мерным наборам из нулей и единиц.

Доказательство. Покажем, что левая и правая части соотношения (4) совпадают. Произвольный набор  = (₁, ₂,..., _n), где каждое _i  {0,1}, подставим в соотношение (4). В левой части получим f (₁,₂,..,_n), а в правой части

_{=(1,...,1)}

٧f(₁,₂,...,_n)₁^1₂^2..._n^n = f(₁,₂,...,_n)₁^1₂^2..._n^n=

^{=(0,...,0)}

=f (₁,₂,...,_n) .

Равенства в правой части вытекают из свойств конъюнкции, дизъюнкции и из того, что х^ = 1  x = .

Если f (x₁, x₂,...,x_n) ≢ 0, то соотношение (4) можно переписать в форме

f (x₁, x₂...,x_n) = ٧ х₁^1 х₂^2х_n^n (5)

по всем 

f ()=1

Эта форма называется совершенной дизъюнктивной нормальной формой (совершенной ДНФ) функции f (x₁,x₂,...,x_n).

Построение совершенной ДНФ из табличного задания функции производится следующим образом. Для каждого набора  = (₁,...,_n) такого, что f (₁,...,_n) = 1, составляется выражение х₁^1х_n^n и затем все такие конъюнкции соединяются знаком дизъюнкции. Например, для функции сложения по модулю два совершенная ДНФ имеет вид

х₁  х₂ =х₁х₂ ٧х₁x₂ .

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

_{=(1,...,1)}

f (x₁,x₂,...,x_n) = ٨(f (₁,₂...,_n) ٧ х₁^1 ٧ х₂^1 ٧...٧х_n^n) , (6)

^{=(0,...,0)}

где _i = {0,1}, x_i⁰ = x_i, x_i¹ = х_i,  = (₁,...,_n) и конъюнкция берётся по всем n-мерным наборам из нулей и единиц.

Доказательство. Из свойства булевой функции (закон двойного отрицания) имеем f (x₁,...,x_n) = (x₁,...,x_n).

Для функцииf (x₁,...,x_n) по теореме 1 существует представление в виде

_{=(1,...,1)}

f (x₁,x₂,...,x_n) = ٧f (₁,₂,...,_n) х₁^1х₂^2...х_n^n , тогда

^{=(0,...,0)}

_{= (1,...,1)}

f (x₁,x₂,...,x_n) = ٧f (₁,₂,...,_n) х₁^1х₂^2...х_n^n =

^{=(0,...,0)}

_{=(1,...,1)}

= ٨ (f (₁,₂,...,_n) ٧x₁^1 ٧ x₂^2 ٧...٧x_n^n), что следует из закона

^{=(0,...,0)}

де Моргана. Заметим также, что x_i^i = x_i^i. Следовательно,

_{=(1,...,1)}

f(x₁,х₂,...,x_n) = ٨(f (₁,₂,...,_n) ٧х₁^1 ٧ х₂^2 ٧...٧х_n^n)

^{=(0,...,0)}

Если f (x₁,x₂,...,x_n) ≢ 1, то соотношение (6) можно переписать в форме

f(x₁,x₂,...,x_n) = ٨ (х₁^1 ٧х₂^2 ٧...٧х_n^n ). (7)

по всем ,

f()=0

Эта форма называется совершенной конъюнктивной нормальной формой (совершенной КНФ) функции f (x₁,x₂,...,x_n).

Построим совершенную КНФ функции х₁  х₂ (табл. 3.5):

х₁  х₂ = (х₁ ٧х₂) (х₁ ٧х₂).

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