Свойства конъюнкции, дизъюнкции и отрицания

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

x₁&(x₂&x₃)= (x₁&x₂)&x₃,

x₁ (x₂ x₃)= (x₁ x₂) x₃,

переместительный

x₁ x₂= x₁ x₂,

x₁& x₂= x₁&x₂,

и распределительный законы. Кроме того, выполняется распределительный закон дизъюнкции относительно конъюнкции.

x₁ (x₂&x₃)= (x₁ x₂)& (x₁ x₃).

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

x 1	x 2	x 3	x2&x3	x1 (x2&x3)

x 1	x 2	x 3	x1 x2	x1 x3	(x1 x2)& (x1 x3)

Совпадение построенных таблиц доказывает наше утверждение.

Рассмотрим теперь ряд простых, но весьма важных соотношений

х х=х;

х&х=х.

х 1=1; х 0=х; х =1;

х&1=х. х&0=0. х& =0.

И как следствие получаем

х х … х=х,

х&х&…&х=х.

Как обобщение формул получаем следующие формулы, называемые формулами (законами) де Моргана

х₁ х₂ … х_n= ;

х₁&х₂&…&х_n= .

Свойства функций сложения по модулю 2, импликации, штриха Шеффера и стрелки Пирса (функции Вебба)

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

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

x₁ x₂= x₂ x₁;

x₁ (x₂ x₃)= (x₁ x₂) x₃;

x₁&(x₂ x₃)= (x₁&x₂) ( x₁&x₃).

Справедливы также очевидные соотношения

x x=0;

x 0=х;

x 1= ;

х =1.

Кроме того, выполняется формула х₁ х₂= x₁ x₂ x₁&x₂.

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

х®x=1;

x® = ;

x®1=1;

х®0= ;

0®х=1;

1®х=х;

х₁®х₂= ® ;

х₁®х₂® х₁= х₁.

Функции дизъюнкции и конъюнкции могут быть выражены через импликацию следующим образом:

х₁ х₂= ® х₂;

х₁&х₂= .

Для функции Шеффера и Вебба справедлив переместительный закон:

х₁ /х₂= х₂/х₁;

х₁¯х₂= х₂¯х₁.

Сочетательный закон для них не выполняется:

х₁/(х₂/х₃)¹(х₁/х₂)/х₃ ;

х₁¯( х₂¯х₃)¹ (х₁¯ х₂)¯ х₃.

Справедливы следующие очевидные соотношения, проверка которых аналогична приведенным выше примерам и осуществляется при помощи таблиц истинности:

х /х= , х¯ х= ;

х/ =1, х¯ =0;

х/1= , х¯1 =0;

х/0=1, х¯0= ;

х₁/х₂= = ;

х₁¯х₂= = & .

Функции Шеффера и Вебба связаны между собой соотношениями, аналогичными формулами де Моргана для функций конъюнкции и дизъюнкции:

х₁/х₂= ;

х₁¯х₂= .

ОСНОВНЫЕ КЛАССЫ ФАЛ

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

f (0, 0, …, 0)=0

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

Аналогично класс функций, сохраняющих константу единица, будет определен, как класс функций, для которых выполняется равенство

f (1, 1,…, 1)=1

Этот класс состоит также из функций.

Определение Функция f*(x₁ ,…,x_n) называется двойственной к функции f (x₁ ,…,x_n), если выполняется равенство

f*(x₁ ,…,x_n)= .

Определение Функция . f (x₁ ,…,x_n) самодвойственный, если она совпадает с двойственной себе функцией, т.е. справедливо равенство

f (x₁ ,…,x_n )= .

Определение ФАЛ f(x₁,…,x_n ) называется линейной, если она представима в следующем виде

f (x₁ ,…,x_n )=с₀ с₁х_{1 …} с_nх_n,

где коэффициент с_i {0, 1}.

Число членов этого класса .

Определение ФАЛ f(x₁,…,x_n ) называется монотонной, если для любых двух наборов Х₁ и Х₂ таких, что Х₁³ Х₂ выполняется равенство

f (X₁)³f (X₂)

X₁=< >

X₂=< >.

Определение ФАЛ f(x₁,…,x_n ) называется симметричной, если она не изменяется при произвольной перенумерации аргументов.

f(x₁,…,x_n )= f(y₁,…,y_n ),

где (y₁,…,y_n) – любая перестановка аргументов (x₁,…,x_n ).

АНАЛИТИЧЕСКАЯ ЗАПИСЬ ФАЛ

Пусть имеется двоичный набор < >. Сопоставим ему число i, определяемое

i= + +…+ ,

число i называют номером набора < >.

Рассмотрим функцию F(x₁,…,x_n), определяемую следующим соотношением

1, если номер набора i

(0) F_i=

0, в противном случае.

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

Теорема. Любая таблично заданная функция ФАЛ может быть задана в следующей аналитической форме

(1) f(x₁,…,x_n )= … = ,

где T_i – множество номеров наборов, на которых функция обращается в единицу.

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

1. Если на этом наборе функция равна единице, то в правой части соотношения (1) найдется , у которой i_j соответствует номеру рассматриваемого набора. Но тогда на основании (0) на данном наборе будет равно единице.

В силу хÚ1=1

х •1 = 1

х 0=х

х&0 =0

х =1

х • =0.

при этом вся правая часть (1) будет также равна единице. Если же на рассматриваемом наборе функция f(x₁,…,x_n )=0, то как следует из формулировки теоремы, среди характеристических функций не будет такой, у которой индекс совпадает с номером рассматриваемого набора аргументов. Все члены дизъюнкции будут равны 0 в правой части. Мы доказали, что левая и правая часть соотношения (1) совпадают на любом наборе.

2. В теореме (1) мы воспользовались дизъюнкцией характеристических функций. Выясним, нельзя ли вместо дизъюнкции использовать какую-либо другую ФАЛ. Для того, чтобы выполнялось соотношение, подобное (1), необходимо, чтобы при обращении любой из характеристических функций в «1» все выражение обращалось в «1», а при нулевых значениях (0) все выражение становилось равным 0.

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

Fi Fj	Fi Fj		Fi Fj	Fi Fj
0 0			1 0
0 1			1 1	(?)

Искомая функция может быть определена двумя различными способами. Если в ее определяющую таблицу вместо (?) дописать «1», то полученная функция будет дизъюнкцией. Этот случай рассматривается в теореме (1). Если же (?) заменить «0», то мы получим функцию сложения по модулю 2.

Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме

(2) f(x₁,…,x_n )= … = .

Представление функции в виде (1) будем называть дизъюнктивным, а представление в виде (2) – полиномиальным.

Для получения представлений другого типа рассмотрим функцию Ф_i(x₁, x₂,…,x_n).

0, если номер набора равен i

(3) Ф_i=

1, в противном случае

такие функции называют характеристическими функциями нуля. Из (1) и (3) следует

F_i(x₁,…,x_n)= (x₁,…,x_n).

Теорема.

Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме

(4) f(x₁,…,x_n )= … = ,

где T₀ – множество номеров наборов, на которых функция f обращается в нуль.

Представление функции в виде (4) называют конъюнктивным представлением.

Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей форме

f(x₁,…,x_n )= … , где i_j T₀ .

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

Условимся о ряде обозначений. Введем в рассмотрение «степень» аргумента х, которую будем обозначать .

Положим, что

х,

=

, .

Рассмотрим конъюнкцию

(5) .

Набор < > двоичный и существует равно 2ⁿ различных таких наборов. Таким образом, число различных конъюнкций также равно 2ⁿ.

Сопоставим каждой конъюнкции (5) номер, определяемый номером набора < >.

Тогда запись ( )_i , означает дизъюнкцию всех конъюнкций с номерами из множества δ.

Аналогично запись

( )_i , i δ

означает конъюнкцию всех дизъюнкций с номерами из множества δ.

Покажем, что =1 тогда и только тогда, когда выполняется равенство

x_i=α_i.

Это вытекает из рассмотрения следующих четырех возможных случаев:

1. = =1 2. =x_i=0

3. = =0 4. =x_i=1

Таким образом, конъюнкция , не обращается в 0 только в том случае, если одновременно выполняются следующие i равенств:

x₁=α₁

(6) x₂=α₂

……

x_i=α_i

Из (6) вытекает, что

F_i (x₁,…,x_n )= , при условии, что

i= + +…+ .

Тогда на основании теоремы (1) можно утверждать, что любая функция алгебры логики, кроме нуля, может быть представлена в следующей форме:

(7) f (x₁, x₂, …, x_n )= .

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

Представление ФАЛ в виде (7) называют совершенной дизъюнктивной нормальной формой этой функции (СДНФ).

Данная теорема позволяет сформулировать алгоритм перехода от табличного задания функции к записи этой функции в виде СДНФ. Этот алгоритм формулируется следующим образом:

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу.

2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент x_i входит в данный набор как «1», он вписывается в конъюнкцию, соответствующую данному набору, без изменения. Если же x_i входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.

3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.

Пример:пусть задана функция f(x₁, x₂, x₃) следующей таблицей:

x1	x2	x3	f(x1, x2, x3)

Требуется получить из нее совершенно дизъюнктивную нормальную форму.

Для нахождения ДСНФ выбираем из таблицы только те строки, в которых стоят наборы значений аргументов, обращающих функцию в единицу (это 4, 5, и 7 строки). Выписываем конъюнкции, соответствующие выбранным строкам:

& x₂&x₃, x₁& & , x₁& x₂& .

Соединяя эти конъюнкции знаками дизъюнкции, окончательно получаем

f(x₁, x₂, x₃)= x₂x₃ x₁ x₃ x₁x₂ .

Итак, можно отметить необходимые и достаточные условия совершенной нормальной дизъюнктивной формулы. СДНФ формулы f (x₁, x₂, …, x_n ), содержащие n различных переменных, обладают следующими свойствами:

А) в ней нет двух одинаковых слагаемых;

Б) ни одно слагаемое не содержит двух одинаковых множителей;

В) никакое слагаемое не содержит переменную вместе с ее отрицанием;

Г) в каждом слагаемом содержится в качестве множителя либо переменная х_i, либо ее отрицание , где i=1,2,…,n.

Д) число множителей равно числу n.

Если вместо (1) воспользоваться соотношением (2), получим полиномиальную совершенную нормальную функцию (ПСНФ).

Так для функции, рассмотренной в примере, ПСНФ имеет следующий вид:

f(x₁, x₂, x₃)= & x₂&x₃ x₁& & x₁& x₂& .

Кроме представления ФАЛ в СДНФ, возможно представление ее в некоторой другой форме, двойственной по отношению к СДНФ.

Теорема. Любая ФАЛ, кроме единицы, может быть представлена в следующей форме:

(8) f(x₁, x₂, x₃)= ( ).

Символ означает, что конъюнкция берется только по тем наборам, < >, для которых выполняется равенство:

f(x₁, x₂, x₃)=0.

Доказательство теоремы.

На основании предыдущей теоремы имеем

(x₁, x₂,…, x_n)=

или (x₁, x₂,…, x_n)= & ( ).

Как известно, равенство не нарушается, если от обеих его частей взять отрицание:

f (x₁, x₂, …, x_n )= .

Согласно закону де Моргана

f (x₁, x₂, …, x_n )= =&( ) f( ).

На тех наборах, для которых f( )=1 соответствующая дизъюнкция

f( )=1.

В силу х 1=1 такие наборы на значение конъюнкции не влияют и ими можно пренебречь:

f (x₁, x₂, …, x_n )= ( ).

Теорема доказана для всех n³1.

Представление ФАЛ в виде (8) носит название совершенной конъюнктивной нормальной формы(СКНФ).

Из теоремы вытекает алгоритм построения КСНФ:

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.

2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент x_i входит в данный набор как «0», он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же x_i входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.

3. Все полученные дизъюнкции соединяются между собой знаками конъюнкций.

Пример.

Написать СКНФ для функции, заданной следующей таблицей.

x1	x2	x3	f(x1, x2, x3)

f(x₁, x₂, x₃)= (x₁ x₂ x₃)&(x₁ )&( ).

Аналогично СДНФ, можно отметить необходимые и достаточные условия совершенной нормальной конъюнктивной формулы. СКНФ формулы f(x₁, x₂, …, x_n ), содержащие n различных переменных, обладают следующими свойствами:

А) в ней нет двух одинаковых множителей;

Б) ни один множитель не содержит двух одинаковых слагаемых;

В) ни один множитель не содержит какой-нибудь переменной вместе с ее отрицанием;

Г) каждый множитель содержит в качестве слагаемого или х_i, или ее отрицание , где i=1,2,…,n.

Д) число слагаемых равно числу n.

Как следует из алгоритмов построения СДНФ и СКНФ выбор той или иной формы аналитической записи определяется видом таблицы заданной функции. Если большинство значений нулевое, то выгодно записывать в СДНФ, в противном случае более экономичную запись дает СКНФ.

Итак, если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

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

Если какой-либо член φ дизъюнктивной (конъюнктивной) функции не содержит переменной x_i , то она вводится тождественным преобразованием

для получения СДНФ φ = φ&( x_i )= φ x_i ,

и для СКНФ соответственно φ =( φ x_i)( φ ).

В силу тождеств φ φ= φ и φ φ= φ одинаковые члены, если они появляются, заменяются одним таким членом.

Приведем соотношения эквивалентных преобразований, полезных при упрощении формул:

Законы склеивания

1) ;

2) ;

3) ;

4) .

Законы поглощения

1) ;

2) ;

3) .

Правила:

1. Если слагаемое некоторой суммы входит в другое слагаемое, то это второе слагаемое можно из суммы удалить.

2. Если множитель некоторого произведения входит слагаемым в другой множитель, то второй множитель можно удалить.

3. В каждом слагаемом можно удалить множитель, который равносилен отрицанию другого слагаемого.

4. В каждом множителе можно удалить слагаемое, которое равносильно отрицанию другого множителя.

Пример.

1. Заданную функцию f(x,y,z)=x z x привести к СДНФ:

x z x = x z x (y )= x z xy x ;

2. Задана функция f(x,y,z)= (x z). Необходимо привести к СКНФ.

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

Добавить к каждому члену соответственно y , x , z

= • • = .

Полная система функций.

Определение. Система ФАЛ (f₁, f₁,…, f_m) называется полной, если любая функция может быть представлена суперпозицией функций f₁, f₁,…, f_m.

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

Примеры полных систем функций: x₁x₂; x₁ x₂ ; x₁ x₂ ; x₁x₂= .

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f₁ , образующей этот базис, превращает систему функций (f₁, f₁,…, f_m) в неполную.

Любая функция, как было показано ранее, может быть представлена в виде СДНФ или СКНФ:

(x₁, x₂,…, x_n)=

(x₁, x₂,…, x_n)= .

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

Минимизация функций алгебры логики

Любая ФАЛ может быть записана в виде СДНФ или СКНФ. Покажем на примере, что такая запись в ряде случаев является неэкономной.

Пример. Пусть задана ФАЛ в СДНФ.

f(x₁, x₂, x₃)= & x₂&x₃ x₁& x₂& x₁& & x₃ x₁& & & x₂& x₃.

Добавим к функции один конъюнктивный член & x₂&x₃. Это добавление не меняет данной функции так как x x=x:

f(x₁, x₂, x₃)= x₂x₃ x₁ x₂ x₁ x₃ x₁ x₂x₃ x₂x₃.

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

f(x₁, x₂, x₃)= x₂ (x₃ ) x₁ ( x₃ ) x₂ x₃ (x₁ ).

Исполь