114

1. преобразуем выражение (x(y z) yz) ;

x(y Ú z)Ú yz = (x(y Ú z))× yz = (x Ú (y Ú z))× (y Ú z) = (x Ú y × z)(y Ú z) = = (x y Ú x z Ú y y z Ú y z) = (x y Ú xz Ú y z);

2. подставим полученное выражение в исходное и продолжим преобразования:

xy Ú (xy Ú xxz)(x y Ú xz Ú yz) = xy Ú xy(x y Ú xz Ú yz) = xy Ú xy y Ú xyz Ú xyz = = xy Ú xyz = y(x Ú xz) = y(x Ú xz Ú xz) = yx Ú yz.

Приведение булевых выражений к СДНФ.

Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные ( xy = xyz Ú xy`z ) , например:

xy Ú ` x y`z = xyz Ú xy`z Ú ` x y`z .

2.3.1. БУЛЕВА АЛГЕБРА ФУНКЦИЙ И ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ В НЕЙ

Все эквивалентные преобразования в булевой алгебре проводятся с помощью основных эквивалентных соотношений (законов):

·ассоциативность;

·коммутативность;

·дистрибутивность

а) относительно дизъюнкции; б) относительно конъюнкции; идемпотентность x × x = x; x Ú x = x;

∙ закон двойного отрицания x = x ;

· свойства констант 0 и 1 :

115

а) x × 1 = x ; б) x Ú 1 = 1 ; в) `0 = 1 ;

г) x × 0 = 0 ; д) x Ú 0 = x ; е) `1 = 0 ;

· правила де Моргана

а) x1 x2 = x1 Ú x2 ; б) x1 Ú x2 = x1 × x2 ;

Данные эквивалентные соотношения отличаются тем, что:

а) они не выводимы друг из друга – убедиться в их справедливости можно, используя стандартный метод доказательства эквивалентности формул, т.е. построение таблиц истинности;

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

Упрощение формул

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

116

x xy = x y .

Правила приведения к ДНФ

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

Примеры ДНФ

Все процедуры приведения к ДНФ основаны на законах булевой алгебры и сводятся к следующему:

1)Все отрицания «спустить» до переменных;

2)Раскрыть скобки с помощью основных эквивалентных преобразований;

3)Удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью;

4)Удалить константы с помощью.

Процедура приведения к КНФ

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

КНФ называется конъюнкция элементарных дизъюнкций.

Пример булевой функции, заданной в КНФ :

( x `y ) (`x z ) (`x y `z ) .

Процедура приведения булевой функции от ДНФ к КНФ:

1) Применить к формуле правило двойного отрицания:

F = K1 K2 Km и привести K1 K2 Km к ДНФ

118

При записи конкретной функции коэффициенты a0, a1, …, an выпадают, так как члены, при которых ai = 0, можно опустить, а коэффициенты, равные 1 – не писать.

Доказательство. Пусть задана произвольная переключательная функция f(x1, x2, …, xn), равная «1» на некоторых наборах с номерами m1, m2, …, mp. Очевидно, что f(x1, x2, …, xn) можно записать:

где Kmi – конституента «1».

Так для набора с номером mi получаем

Km1 + Km2 + + Kmi + + Kmp = 0 + 0 + + 1+ + 0 = 1.

Пример. Представить в виде полинома Жегалкина функцию f14(x, y).