UML_4822 дм практикум

результате получим x y z x y . Дополним член конъюнкции, не

содержащий переменной z, конъюнкцией zz и применим закон дистрибу-

тивности дизъюнкции относительно конъюнкции:

x y z x y zz x y z x y z x y z .

Из одинаковых членов полученной конъюнкции оставим один, удалив остальные: x y z x y z .

Задача 210. Приведите следующие формулы к ДНФ, а затем и к СДНФ с помощью равносильных преобразований:

Задача 211. Приведите следующие формулы к КНФ, а затем и к СКНФ с помощью равносильных преобразований:

Задача 212. Приведите к СДНФ и СКНФ функции:

1)x1x3x4 | x1x3 | x3x4 ;

2)x1x2 x3 x4 ;

3)x1 x2 x3 x4 x1x2 x4 ;

4)x1 x2 x3 x4 .

91

Для нашего примера СКНФ имеет вид:

x y z x y z x y z x y z x y z .

Задача 213. Составьте СДНФ и СКНФ для формул f1, f2, f3, f4, соответствующих данной таблице истинности (табл.3.12).

Таблица 3.12 Таблица истинности формул f1, f2, f3, f4

Задача 214. Составьте формулы f1, f2, f3, f4, f5 по приведенной ниже таблице истинности (выберите рациональный способ). Упростите полученную формулу.

Таблица 3.13 Таблица истинности формул f1, f2, f3, f4, f5

93

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

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

Теорема. Для того, чтобы формула алгебры логики была тождественно истинна (ложна), необходимо и достаточно, чтобы любая элементарная дизъюнкция, (конъюнкция), входящая в КНФ А (ДНФ А), содержала переменную и ее отрицание.

Пример 215. Будет ли формула x y xy y тождественно ис-

тинной, тождественно ложной или выполнимой?

Решение. Приведем формулу к какой-либо нормальной форме:

x y xy y x y xy y x y xy y xy xy y .

Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима.

Преобразуем данную формулу к КНФ:

x y xy y xy xy y xy y xy y xy y x y yy x.

Это выражение не является тождественно истинным, так как элементарная сумма y x не тождественно истинна. Таким образом, исходная

формула не тождественно истинна и не тождественно ложна, следовательно, она выполнима.

Задача 216. Используя критерий тождественной истинности и тождественной ложности формулы, установите, будет ли данная формула тождественно истинной, тождественно ложной или выполнимой?

1)xy x xy ;

2)x y xy xy ;

3)xy x y ;

4)x y x y ;

5)x z y z x y ;

6)x y x y x ;

7)x & z x & z y & z x & y & z ;

8)x & y & z x & y z x ;

Ответ. 1) ТИФ; 2) ТЛФ; 3)-5) – выполнимые.

94

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

1)x & x y ;

2)xy x xy y ;

3)x y y x ;

4)x z yz ;

5)x y xz x x yz ;

6)ab bc a b c b ;

7)a c b c ;

8)a b bc ac ;

9)x y y zx & x y z ;

10)x & y z x & y y & x z z y x & z ;

11)xy xyz & x xy y xz y xyz xy ;

12)x & z x xz xy z y x yz .

Ответ.

1)СДНФ = xy, CКНФ = (x y)(x y)(x y) ;

2)СДНФ = xy, CКНФ = (x y)(x y)(x y) ;

3)СДНФ = xy xy x y , СКНФ = (x y) ;

4)СДНФ = xyz xyz x yz ;

СКНФ = (x y z)(x y z )(x y z)(x y z)(x y z) ;

5)СДНФ = xyz xy z xyz xyz xyz x y z x yz ,

СКНФ (x y z ) ;

6)СДНФ = abc abc abc abc abc abc abc ,

СКНФ = (a b c ) ;

7)СДНФ = abc abc abc abc ,

СКНФ = (a b c )(a b c )(a b c)(a b c ) ;

8) СДНФ = abc abc abc abc abc abc abc abc , СКНФ=1.

Задача 218. Найдите СДНФ для всякой тождественно истинной формулы, содержащей:

1)одну переменную;

2)две переменных;

3)три переменных.

Ответ.

95

1)x x ;

2)xy xy xy x y ;

3)xyz xyz xyz xy z xy z xyz x y z .

Задача 219. Найдите СКНФ для всякой тождественно ложной формулы, содержащей:

1)одну переменную;

2)две переменных;

3)три переменных.

Ответ.

1)xx ;

2)(x y)(x y)(x y)(x y) ;

3)(x y z )(x y z)(x y z )(x y z) & & (x y z )(x y z)(x y z )(x y z).

Задача 220. Докажите равносильность формул xy y x и x y x y сравнением их совершенных нормальных форм (конъюнк-

тивных или дизъюнктивных).

Задача 221. Найдите более простой вид формул, имеющих следующие СДНФ и СКНФ:

1)xy xy xy ;

2)x y x y x y ;

3)xyz xyz xyz ;

4)x y z x y z x y z .

Ответ. 1) x y ; 2) x & y ; 3) z(x y) ; 4) x( y z) z ( y x) .

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

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

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

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

Формула, представленная в ДНФ, упрощается многократным при-

96

(a b)(a b ) a; a(a b) a ; a(a b) ab ). В результате приходим к такому аналитическому выражению, для которого дальнейшие преобразования оказываются невозможными, то есть получают тупиковую форму.

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

Определение. Конъюнкция вида P(x1, x2,...xn ) 1 называется элемен-

тарной конъюнкцией нулевого ранга.

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

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

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

Определение. Длиной ДНФ называют число элементарных конъюнкций, образующих эту ДНФ.

Например, длина x1x3 x2x4 x1x5 x1x3 равна 4.

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

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

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

Например, x1 x1x2x3 x1 x2x3 – кратчайшая минимальная форма

функции.

Рассмотрим использование следующих практических методов минимизации: метода неопределенных коэффициентов, метода, основанного на применении диаграмм Вейча (карт Карно), и алгебраического метода, известного как метод Мак-Класски.

3.5.1. Метод неопределенных коэффициентов

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

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

97

де k {0,1} - коэффициенты. Метод заключается в подборе коэффициентов таким образом, чтобы получаемая ДНФ была минимальной.

Если теперь задать всевозможные значения переменных от 000 до 111, то получим 2n (23 =8) уравнений для определения коэффициентов k:

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

Пример 222. Минимизировать заданную функцию

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

f 1,1,1 1. На основании возможно составление системы уравнений неопределенных коэффициентов:

98

После вычеркивания нулевых коэффициентов получим:

k2300 k123000 =1;

k11 k1210 k1310 k2300 k123100 =1; k11 k1210 k1311 k123101=1;

k11 k1211 k1310 k123110 =1; k11 k1211 k1311 k123111 =1.

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

Ответ. Вид минимизированной функции f x1, x2 , x3 x1 x2x3 .

Следует отметить, что метод неопределенных коэффициентов эффективен, когда число переменных невелико и не превышает 5-6.

Задача 223. Минимизируйте методом неопределенных коэффициентов булеву функцию:

1)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

2)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

3)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

4)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

5)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

6)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

7)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

8)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

9)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

10)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

3.5.2. Минимизация при помощи диаграмм Вейча (карт Карно)

Основная идея заключается в том, что исходная булева функция, задаваемая в виде СДНФ, представляется в форме специальной таблицы. Столбцы и строки таблицы соответствуют всевозможным наборам значений не более 2-х переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому соседние клетки табли-

99

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

Карта Карно для функции двух переменных имеет вид:

Карта Карно для функции трех переменных имеет вид:

Здесь крайний правый и крайний левый столбцы считаются соседними.

Карта Карно для функции четырех переменных имеет вид:

x2 x2

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

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

На таблице определено понятие правильной конфигурации. Правильной конфигурацией ранга i булевой функции f x1,..., xn называют

прямоугольники, имеющие площадь 2n-i клеток. Ранг покрытия равен сумме рангов всех правильных конфигураций.

100