Элементы математической логики. 3 страница
Теорема. Любая таблично заданная функция ФАЛ может быть задана в следующей аналитической форме
(1) f(x1,…,xn )= 
… 
= 
,
где Ti – множество номеров наборов, на которых функция обращается в единицу.
Справедливость этой теоремы вытекает из следующего. Возьмем произвольный набор аргументов из таблицы, задающей функцию. Возможны два случая:
1. Если на этом наборе функция равна единице, то в правой части соотношения (1) найдется 
, у которой ij соответствует номеру рассматриваемого набора. Но тогда на основании (0) на данном наборе будет равно единице.
В силу хÚ1=1
х •1 = 1
х 
0=х
х&0 =0
х 
=1
х • 
=0.
при этом вся правая часть (1) будет также равна единице. Если же на рассматриваемом наборе функция f(x1,…,xn )=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(x1,…,xn )= 
… 
= 
.
Представление функции в виде (1) будем называть дизъюнктивным, а представление в виде (2) – полиномиальным.
Для получения представлений другого типа рассмотрим функцию Фi(x1, x2,…,xn).
0, если номер набора равен i
(3) Фi=
1, в противном случае
такие функции называют характеристическими функциями нуля. Из (1) и (3) следует
Fi(x1,…,xn)= 
(x1,…,xn).
Теорема.
Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме
(4) f(x1,…,xn )= 
… 
= 
,
где T0 – множество номеров наборов, на которых функция f обращается в нуль.
Представление функции в виде (4) называют конъюнктивным представлением.
Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей форме
f(x1,…,xn )= 
… 
, где ij 
T0 .
Перейдем теперь к аналитическому выражению самих характеристических функций.
Условимся о ряде обозначений. Введем в рассмотрение «степень» аргумента х, которую будем обозначать 
.
Положим, что
х, 
=
, 
.
Рассмотрим конъюнкцию
(5) 
.
Набор < 
> двоичный и существует равно 2n различных таких наборов. Таким образом, число различных конъюнкций также равно 2n.
Сопоставим каждой конъюнкции (5) номер, определяемый номером набора < >.
Тогда запись 
( )i , означает дизъюнкцию всех конъюнкций с номерами из множества δ.
Аналогично запись
( 
)i , i δ
означает конъюнкцию всех дизъюнкций с номерами из множества δ.
Покажем, что 
=1 тогда и только тогда, когда выполняется равенство
xi=αi.
Это вытекает из рассмотрения следующих четырех возможных случаев:
1. 
= 
=1 2. 
=xi=0
3. 
= =0 4. 
=xi=1
Таким образом, конъюнкция 
, не обращается в 0 только в том случае, если одновременно выполняются следующие i равенств:
x1=α1
(6) x2=α2
……
xi=αi
Из (6) вытекает, что
Fi (x1,…,xn )= 
, при условии, что
i= 
+ 
+…+ 
.
Тогда на основании теоремы (1) можно утверждать, что любая функция алгебры логики, кроме нуля, может быть представлена в следующей форме:
(7) f (x1, x2, …, xn )= 
.
При этом дизъюнкция в правой части берется только по тем номерам наборов аргументов, по которым функция, заданная таблично, обращается в единицу.
Представление ФАЛ в виде (7) называют совершенной дизъюнктивной нормальной формой этой функции (СДНФ).
Данная теорема позволяет сформулировать алгоритм перехода от табличного задания функции к записи этой функции в виде СДНФ. Этот алгоритм формулируется следующим образом:
1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу.
2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент xi входит в данный набор как «1», он вписывается в конъюнкцию, соответствующую данному набору, без изменения. Если же xi входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.
3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.
Пример:пусть задана функция f(x1, x2, x3) следующей таблицей:
| x1 | x2 | x3 | f(x1, x2, x3) |
Требуется получить из нее совершенно дизъюнктивную нормальную форму.
Для нахождения ДСНФ выбираем из таблицы только те строки, в которых стоят наборы значений аргументов, обращающих функцию в единицу (это 4, 5, и 7 строки). Выписываем конъюнкции, соответствующие выбранным строкам:
& x2&x3, x1& 
& 
, x1& x2& 
.
Соединяя эти конъюнкции знаками дизъюнкции, окончательно получаем
f(x1, x2, x3)= x2x3 x1 x3 x1x2 .
Итак, можно отметить необходимые и достаточные условия совершенной нормальной дизъюнктивной формулы. СДНФ формулы f (x1, x2, …, xn ), содержащие n различных переменных, обладают следующими свойствами:
А) в ней нет двух одинаковых слагаемых;
Б) ни одно слагаемое не содержит двух одинаковых множителей;
В) никакое слагаемое не содержит переменную вместе с ее отрицанием;
Г) в каждом слагаемом содержится в качестве множителя либо переменная хi, либо ее отрицание 
, где i=1,2,…,n.
Д) число множителей равно числу n.
Если вместо (1) воспользоваться соотношением (2), получим полиномиальную совершенную нормальную функцию (ПСНФ).
Так для функции, рассмотренной в примере, ПСНФ имеет следующий вид:
f(x1, x2, x3)= & x2&x3 
x1& & x1& x2& .
Кроме представления ФАЛ в СДНФ, возможно представление ее в некоторой другой форме, двойственной по отношению к СДНФ.
Теорема. Любая ФАЛ, кроме единицы, может быть представлена в следующей форме:
(8) f(x1, x2, x3)= 
( 
).
Символ означает, что конъюнкция берется только по тем наборам, < >, для которых выполняется равенство:
f(x1, x2, x3)=0.
Доказательство теоремы.
На основании предыдущей теоремы имеем
(x1, x2,…, xn)= 
или (x1, x2,…, xn)= & ( ).
Как известно, равенство не нарушается, если от обеих его частей взять отрицание:
f (x1, x2, …, xn )= 
.
Согласно закону де Моргана
f (x1, x2, …, xn )= 
=&( 
) f( 
).
На тех наборах, для которых f( )=1 соответствующая дизъюнкция
f( )=1.
В силу х 1=1 такие наборы на значение конъюнкции не влияют и ими можно пренебречь:
f (x1, x2, …, xn )= 
( ).
Теорема доказана для всех n³1.
Представление ФАЛ в виде (8) носит название совершенной конъюнктивной нормальной формы(СКНФ).
Из теоремы вытекает алгоритм построения КСНФ:
1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.
2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент xi входит в данный набор как «0», он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же xi входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.
3. Все полученные дизъюнкции соединяются между собой знаками конъюнкций.
Пример.
Написать СКНФ для функции, заданной следующей таблицей.
| x1 | x2 | x3 | f(x1, x2, x3) |
f(x1, x2, x3)= (x1 x2 x3)&(x1 )&( ).
Аналогично СДНФ, можно отметить необходимые и достаточные условия совершенной нормальной конъюнктивной формулы. СКНФ формулы f(x1, x2, …, xn ), содержащие n различных переменных, обладают следующими свойствами:
А) в ней нет двух одинаковых множителей;
Б) ни один множитель не содержит двух одинаковых слагаемых;
В) ни один множитель не содержит какой-нибудь переменной вместе с ее отрицанием;
Г) каждый множитель содержит в качестве слагаемого или хi, или ее отрицание , где i=1,2,…,n.
Д) число слагаемых равно числу n.
Как следует из алгоритмов построения СДНФ и СКНФ выбор той или иной формы аналитической записи определяется видом таблицы заданной функции. Если большинство значений нулевое, то выгодно записывать в СДНФ, в противном случае более экономичную запись дает СКНФ.
Итак, если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.
Можно показать, что любая булева функция, не являющаяся тождественным нулем (единицей) имеет одну и только одну совершенную дизъюнктивную (конъюнктивную) нормальную форму.
Если какой-либо член φ дизъюнктивной (конъюнктивной) функции не содержит переменной xi , то она вводится тождественным преобразованием
для получения СДНФ φ = φ&( xi 
)= φ xi 
,
и для СКНФ соответственно φ 
=( φ xi)( φ ).
В силу тождеств φ φ= φ и φ φ= φ одинаковые члены, если они появляются, заменяются одним таким членом.
Приведем соотношения эквивалентных преобразований, полезных при упрощении формул:
Законы склеивания
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 
= 
• 
• 
= 
.
Полная система функций.
Определение. Система ФАЛ (f1, f1,…, fm) называется полной, если любая функция может быть представлена суперпозицией функций f1, f1,…, fm.
Система функций { f1, f1,…, fm }, являющаяся полной, называется базисом.
Примеры полных систем функций: x1x2; x1 x2 ; x1 
x2 ; x1x2= 
.
Дата добавления: 2017-11-04; просмотров: 368;