Дискретная математика

vk.com/club152685050 | vk.com/id446425943

а) дизъюнкции относительно конъюнкции

ab c a c b c ,

б) конъюнкции относительно дизъюнкции

a b c ac bc.

11.Свойство импликации a b a b.

12.Свойства эквиваленции

a b a b b a .

13.Свойства сложения по модулю 2

1 a a , a b a b a b.

§ 6. Дизъюнктивные нормальные формы представления булевых функций

Пусть имеются переменные x1, x2 ,..., xn .

Конъюнкцию переменных или их отрицаний называют элементарной конъюнкцией или конъюнктом.

Например, конъюнктами будут

K1 x1x3 ,

K2 x2 x5 xn , K3 x7 .

51

где каждый конъюнкт Ki представляет конъюнкцию взятых с отрицаниями или

без них переменных функции, называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Представление булевой функции в ДНФ не единственно. Например, функция

f x1, x2 x1 x2 x1 x1x2 x1 x2

представлена в двух разных ДНФ.

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

Если представление (1) обладает следующими свойствами:

1.Каждый конъюнкт содержит все переменные или их отрицания;

2.Все конъюнкты различны;

3.Ни один конъюнкт не содержит одну и ту же переменную дважды;

4.Ни один конъюнкт не содержит одновременно переменную и её отрицание,

то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ)

функции f x1, x2 ,..., xn

Без доказательства приведем теорему.

Теорема. Любая булева функция f x1, x2 ,..., xn , не тождествннно равная 0, может быть единственным образом представлена в СДНФ.

Из доказательства этой теоремы следует Алгоритм построения СДНФ булевой функции, заданной таблично:

Пример. Функция f x1, x2 , x3 задана таблично (табл. 4). Найти её СДНФ.

52

vk.com/club152685050 | vk.com/id446425943

В последнем столбце в соответствии с алгоритмом записаны конъюнкции переменных для тех наборов, на которых заданная функция принимает значение 1. Составляем их дизъюнкцию и получаем СДНФ:

fx1, x2 , x3 = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .

§7. Конъюнктивные нормальные формы представления булевых функций

Пусть имеются переменные x1, x2 ,..., xn .

Дизъюнкцию переменных или их отрицаний называют элементарной дизъюнкцией или дизъюнктом.

Например, дизъюнктами будут

D1 x1 x2 ,

D2 x3 x5 xn , D3 x7.

где каждый дизъюнкт Di представляет дизъюнкцию взятых с отрицаниями

или без них переменных функции, называется конъюнктивной нормальной формой (КНФ) этой функции.

Представление булевой функции в КНФ не единственно. Например, функция

53

vk.com/club152685050 | vk.com/id446425943

f x1, x2 x1 x1 x2 x1 x2

представлена в двух разных КНФ.

Введем понятие совершенной конъюнктивной нормальной формы

булевой функции.

Если представление (2) обладает следующими свойствами:

1.Каждый дизъюнкт содержит все переменные или их отрицания;

2.Все дизъюнкты различны;

3.Ни один дизъюнкт не содержит одну и ту же переменную дважды;

4.Ни один дизъюнкт не содержит одновременно переменную и её

отрицание, то КНФ называется совершенной конъюнктивной нормальной формой (СКНФ) функции f x1, x2 ,..., xn .

Без доказательства приведем теорему.

vk.com/club152685050 | vk.com/id446425943

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

значение 0. Составляем их конъюнкцию и получаем СКНФ

f x1, x2 , x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .

§ 8. Аналитическое преобразование булевой функции в нормальные формы

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

1. Устраняем операции , , , ,| , используя свойства:

a b a b ,

a b a b b a ,

a b a b , a b a b , a | b a b .

2. Используя законы де Моргана, операцию отрицания переносим непосредственно на переменные и убираем двойные отрицания:

a b a b , a b a b ,

a a .

3. Используя закон дистрибутивности конъюнкции относительно дизъюнкции a b c ac bc , преобразуем формулу так, чтобы все

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

ДНФ, только вместо п. 3 применяется п. 3 .

3 . Используя закон дистрибутивности дизъюнкции относительно конъюнкции ab c a c b c , преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции, и получаем КНФ.

Пример 1. Привести к ДНФ функцию f x, y.z x y y z .

fx, y.z x y y z x y y z

x y y z x y y z x y y z

55

vk.com/club152685050 | vk.com/id446425943

x y y z x y x yz .

Получили ДНФ заданной функции. Можно упростить её и получить другую ДНФ: x y x yz x y 1 z x y .

Отметим, что функция, заданная в виде f x, y.z x y , может

рассматриваться и как ДНФ, состоящая из одного логического слагаемого, и как КНФ, состоящая из двух логических сомножителей.

Пример 2.

Привести к КНФ функцию

f x, y, z x y y z x .

fx, y, z x y y z x

x y y z x x y y z x

x y y x z x .

Получили КНФ заданной функции. Используя свойства дистрибутивности и поглощения, можно получить другую КНФ: f x, y, z x .

Функция в виде f x, y, z x может рассматриваться и как КНФ,

состоящая из одного логического сомножителя, и как ДНФ, состоящая из одного логического слагаемого.

§9. Аналитическое приведение булевой функции к СДНФ

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

1. Если в конъюнкт K входит некоторая переменная вместе со своим отрицанием, то удаляем этот конъюнкт из ДНФ, т. к.

Kx1 ... xk xk ... xn 0 .

2.Если одна и та же переменная xk входит в конъюнкт несколько раз, то

удаляем все xk , кроме одной, т. к.

xk xk xk .

3. Если в некоторый конъюнкт K не входит переменная xk , то этот конъюнкт заменяем на

56

vk.com/club152685050 | vk.com/id446425943

KK xk xk K xk K xk .

4.Если в полученной ДНФ имеется несколько одинаковых конъюнктов,

то оставляем один из них, т. к.

K K K .

В результате получаем СДНФ.

Пример. Найти СДНФ для ДНФ функции f x, y, z x x x y z y .

fx, y, z x x x y z y x y z

x y y yz x x xy x y xyz xyz

xy z z x y z z xyz xyz

xyz xy z x yz x y z xyz xyz

xyz xy z x yz x y z xyz

§10. Аналитическое приведение булевой функции к СКНФ

Для нахождения СКНФ данную булеву функцию приводим к любой КНФ,

азатем преобразуем её дизъюнкты с помощью следующих действий:

1.Если в дизъюнкт D входит некоторая переменная вместе со своим отрицанием, то удаляем этот дизъюнкт из КНФ, т. к.

D x1 ... xk xk ... xn 1.

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

xk xk xk .

3. Если в некоторый конъюнкт D не входит переменная xk , то этот дизъюнкт заменяем на

DD xk xk D xk D xk .

4.Если в полученной КНФ имеется несколько одинаковых дизъюнктов, то оставляем один из них, т. к.

D D D .

В результате получаем СКНФ.

Пример. Найти СКНФ для КНФ функции

f x, y, z x z z x x y y z .

57

vk.com/club152685050 | vk.com/id446425943

fx, y, z x z z x x y y z x y y z

x y z z xx y z

x y z x y z x y z x y z

x y z x y z x y z .

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

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

2.Для любой булевой функции можно найти её СДНФ и СКНФ двумя способами:

-с помощью таблицы, задающей функцию;

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

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

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

определенная следующим образом:

f x1, x2 ,..., xn f x1, x2 ,..., xn ,

называется двойственной к функции f .

vk.com/club152685050 | vk.com/id446425943

f1 x1, x2 f1 x1, x2 x1 x2 x1 x2 x1 x2 f7 x1, x2

Таким образом, для конъюнкции двойственной является дизъюнкция. 2. Найти функцию, двойственную к функции стрелка Пирса

f8 x1, x2 x1 x2 x1 x2 .

f8 x1, x2 x1 x2 x1 x2 x1 | x2 f14 x1, x2 .

Таким образом, штрих Шеффера есть функция, двойственная к функции стрелка Пирса.

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

Примером самодвойственных функций могут являться функции

f f1 x1,..., xn ,..., fn x1,..., xn

f f1 x1,..., xn ,..., fn x1,..., xn .

59

vk.com/club152685050 | vk.com/id446425943

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

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

Пример. Найти функцию, двойственную к

f x, y, z xy x z x y z .

f x, y, z x y x z x y z .

§12. Минимизация булевых функций

Одну и ту же булеву функцию можно представить различными формулами. Если какая-то техническая схема реализует булеву функцию, то выбор более простой формулы, задающей функцию, ведет к более простой схеме, т. е. к экономии материала, объёма, веса, электропотребления и т.д.

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

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

Пример. ДНФ xy xy не является минимальной. Она содержит 4 вхождения переменных. Преобразуем данную ДНФ к равносильной

xy xy x x y y

Полученная ДНФ имеет одно вхождение переменной.

Одним из методов минимизации ДНФ является метод Квайна. Чтобы рассмотреть его, введём несколько определений.