Лабораторная работа Функции алгебры логики (булевы функции). Лабораторная работа Функции алгебры логики (булевы функции) Разложение по переменным

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

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

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"

Подобные документы

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

реферат , добавлен 06.12.2010


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

учебное пособие , добавлен 29.04.2009


Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.

курсовая работа , добавлен 12.05.2009


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

контрольная работа , добавлен 26.04.2011


Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.

контрольная работа , добавлен 20.01.2011


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

контрольная работа , добавлен 29.11.2010


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

курсовая работа , добавлен 16.01.2012

Пусть s принимает значения 0 или 1, т.е. s {0, 1}.

Введем обозначение:

x s = Øx , если s = 0, x s = x , если s = 1.

Т.е. x 0 = Øx , x 1 = x .

Очевидно, что x s = 1, если x = s и x s = 0, если x s .

Теорема 4.5 (о разложении булевой функции по переменным).

Каждая булева функция f (x 1 , x 2 , ... , x n ) может быть представлена в виде:

f (x 1 , x 2 , ... , x n ) = f (x 1 , x 2 , ... , x m , x m +1 , ... , x n ) =

V x 1 s 1 &x 2 s 2 &...&x m sm & f (s 1 , s 2 , ... s m , x m +1 , ... , x n ), (4.1)

m n , где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s m ) (их 2 m ).

Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2 m = 2 2 =4) конъюнкции и имеет вид:

f (x 1 , x 2 , x 3 , x 4) = x &x &f (0, 0, x 3 , x 4) V x &x &f (0, 1, x 3 , x 4) V x & x &f (1, 0, x 3 , x 4) V x & x &f (1, 1, x 3 , x 4) = Øx 1 &Øx 2 &f (0, 0, x 3 , x 4) V Øx 1 &x 2 &f (0, 1, x 3 , x 4) V x 1 &Øx 2 &f (1, 0, x 3 , x 4) V x 1 &x 2 &f (1, 1, x 3 , x 4).

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

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y 1, y 2 , ... , y m , y m +1 , ... , y n ) .

Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).

В левой части получим f (y 1, y 2 , ... , y n ) .

Т. к. y s = 1 только, когда y = s , то среди 2 m конъюнкций y 1 s 1 &y 2 s 2 &...&y m sm в правой части (4.1) только одна обратится в 1 – та, в которой y 1 = s 1 ,…, y m = s m . Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y 1 y 1 &y 2 y 2 &...&y m ym &f (y 1, y 2 , ... , y m , y m +1 , ... , y n ) = f (y 1, y 2 , ... , y n ) .

Теорема 4.5 доказана.

Теорема 4.6 (о представлении булевой функции формулой в СДНФ),

Всякая булева функция f (x 1 , x 2 , ... , x n ),не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

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

При m = n получим важное следствие теоремы 4.5:

f (x 1 , x 2 , ... , x n ) = V x 1 s 1 &x 2 s 2 &...&x n sn , (4.2)

f (s 1 , s 2 , ... , s n ) = 1

где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s n ), на которых f = 1.

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

Очевидно также, что для булевой функции f (x 1 , x 2 , ... , x n ), тождественно равной 0, разложение (2) не существует.

В силу изложенного для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СДНФ можно воспользоваться следующим алгоритмом.

Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).

Шаг 1. s 1 , s 2 , ... , s n , для которых значение f равно 1, т. е. f (s 1 , s 2 , ... , s n ) = 1.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x 1 s 1 &x 2 s 2 &...&x n sn , где x i si = x i , если s i = 1 и x i si =Øx i , если s i = 0, i = 1, 2, ... ,n .

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Пример 4.15.

Найдем формулу в СДНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

f (x 1 , x 2 , x 3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.

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

x 1 0 &x 2 1 &x 3 1 = Øx 1 &x 2 &x 3 .

x 1 1 &x 2 0 &x 3 0 = x 1 &Øx 2 &Øx 3 .

x 1 1 &x 2 0 &x 3 1 = x 1 &Øx 2 &x 3 .

x 1 1 &x 2 1 &x 3 1 = x 1 &x 2 &x 3 .

3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:

f (x 1 , x 2 , x 3) = Øx 1 &x 2 &x 3 V x 1 &Øx 2 &Øx 3 V x 1 &Øx 2 &x 3 V x 1 &x 2 &x 3 .

Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.

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

Теорема 4.7 (о представлении булевой функции формулой в СКНФ),

Всякая булева функция f (x 1 , x 2 , ... , x n ),не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

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

Рассмотрим функцию Øf (x 1 , x 2 , ... , x n ). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F 1 . Очевидно, условие, что функция Øf (x 1 , x 2 , ... , x n ) не равна тождественно 0, равносильно условию, что функция f (x 1 , x 2 , ... , x n ) не равна тождественно 1. Кроме того, по закону де Моргана формула F 2 º ØF 1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания

F 2 º ØF 1 º ØØf (x 1 , x 2 , ... , x n ) º f (x 1 , x 2 , ... , x n ),

что и доказывает теорему.

Для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)

Шаг 1. Выбираем в таблице все наборы переменных s 1 , s 2 , ... , s n , для которых значение f (s 1 , s 2 , ... , s n ) = 0.

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию

x 1 Ø s 1 Vx 2 Ø s 2 V...Vx n Ø sn , где x i Ø si = x i , если s i = 0 и x i Ø si = Øx i , если s i = 1, i = 1, 2, ... , n .

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.

Пример 4.16.

Найдем формулу в СКНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f (x 1 , x 2 , x 3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.

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

x 1 1 Vx 2 1 Vx 3 1 = x 1 Vx 2 Vx 3 .

x 1 1 Vx 2 1 Vx 3 0 = x 1 Vx 2 VØx 3 .

x 1 1 Vx 2 0 Vx 3 1 = x 1 VØx 2 Vx 3 .

x 1 0 Vx 2 0 Vx 3 1 = Øx 1 VØx 2 V x 3 .

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

f (x 1 , x 2 , x 3) = (x 1 Vx 2 Vx 3)&(x 1 Vx 2 VØx 3)&(x 1 VØx 2 Vx 3)&(Øx 1 VØx 2 Vx 3).

Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.

Замечание. Т. к. всего строк в таблице функции 2 n , то, если число дизъюнктивных членов в СДНФ равно p , а число конъюнктивных членов в СКНФ равно q , то p +q =2 n .

Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2 3 .

Разложение Шеннона Рассмотрим разложение булевой функции f (x 1, x 2, . . . , xn) по переменной xi. Разложение Шеннона: f (x 1, x 2, . . . , xn)= xi f(x 1, . . . , xi 1, 1, xi+1, . . . , xn) xi f(x 1, . . . , xi 1, 0, xi+1, . . . , xn). Доказательство (не умоляя общности, для i =1). Если x 1 = 0, то f(0, x 2, . . . , xn) = 0 f (1, x 2, . . . , xn) 1 f(0, x 2, . . . , xn) = f (0, x 2, . . . , xn). Если x 1 = 1, то f(1, x 2, . . . , xn) = 1 f(1, x 2, . . . , xn) 0 f(1, x 2, . . . , xn) = f(0, x 2, . . . , xn). ЧТД Пример. Булеву функцию f (x, y, z) = x y / y z , разложим по переменной z: f (x, y, z) = z(x y / y 1) z (x y / y 0)= [по свойствам 0 и 1] = z z (x y / y). Сомножитель f (x 1, . . . , xi -1, 1, xi+1, . . . , xn) в формуле Шеннона называется коэффициентом разложения функции f (x 1, x 2, . . . , xn) по переменной xi при xi, а сомножитель f (x 1, . . . , xi -1, 0, xi+1, . . . , xn) - коэффициентом разложения функции f (x 1, x 2, . . . , xn) по xi при xi. Пример. f (x, y, z) = x y / y = y (x 1 / 0) y (x 0 / 1). x 1 / 0 - коэффициент разложения функции f (x, y, z) по y при y ; x 0 / 1 - коэффициент разложения функции f (x, y, z) по y при y.

Разложение функции по k переменным Доказательство. Подставим в левую и правую части равенства произвольный набор a 1 a 2. . . an: Упростим правую часть, рассуждая следующим образом. Нетрудно проверить, что 1, если и только если ai = 0 = 1, 11 = 1, но 0 1 = 0 и 10 = 0), ci (в самом деле: 0 поэтому конъюнкция равна единице лишь в единственном случае, когда наборы a 1 a 2. . . ak и с1 с2. . . сk совпадают. А это значит, что она не обращает в ноль лишь одно слагаемое правой части - то, для которого a 1 a 2. . . ak = с1 с2. . . сk и в котором сама обращается в единицу. Подставив в ставшееся слагаемое a 1 a 2. . . ak вместо с1 с2. . . сk , получим

Совершенная дизъюнктивная нормальная форма (Сов. ДНФ) Применив формулу разложения булевой функции f (x 1, x 2, . . . , xn) по k переменным при k = n, получим: Поскольку коэффициентами разложения f (c 1, c 2, . . . , cn) в этой формуле являются значения функции f (x 1, x 2, . . . , xn) на всевозможных наборах c 1 c 2. . . cn, то возможны два случая: если набор c 1 c 2. . . cn M 0 (f), то f (c 1, c 2, . . . , cn) = 0 и поэтому обращается в 0 соответствующее слагаемое правой части; если набор c 1 c 2. . . cn M 1 (f), то f(c 1, c 2, . . . , cn)=1 и слагаемое упрощается. В результате имеем: Совершенная дизъюнктивная нормальная форма булевой функции, или Сов. ДНФ, - это формула вида:

Утверждение о единственности Сов. ДНФ Любая булева функция, кроме константы 0, представима cовершенной дизъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. ДНФ (по таблице истинности) вытекает из определения Сов. ДНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередная 1 и по набору значений аргументов этой строки формируется конъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в конъюнкцию в степени 0 (с инверсией), иначе в степени 1 (без инверсии); полученная конъюнкция добавляется в формулу как очередное слагаемое. Пример. Обратим внимание на тот факт, что нам впервые удалось от табличного способа задания функции перейти к формульному!

Утверждение о единственности Сов. КНФ Любая булева функция, кроме константы 1, представима cовершенной конъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. КНФ по таблице истинности вытекает из определения Сов. КНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередной 0 и по набору значений аргументов этой строки формируется дизъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в дизъюнкцию в степени 1 (без инверсии), иначе в степени 0 (с инверсией); полученная дизъюнкция добавляется в Сов. КНФ как очередной сомножитель. Пример.

Элементарная конъюнкция и ДНФ Рассмотрим множество переменных x 1, x 2, . . . , xn. Элементарной конъюнкцией назовем конъюнкцию, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии). Примеры. x 1 x 2 x 3 x 4, x 1 x 2 x 4 , x 3 - элементарные конъюнкции, x 1 x 2 x 4, x 1 x 3 - неэлементарные. В частности, 1 - это элементарная конъюнкция, не содержащая ни одной переменной. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом. Пример. Ранг элементарной конъюнкции x 1 x 2 x 4 равен трем. Полной конъюнкцией назовем элементарную конъюнкцию, состоящую из всех переменных, т. е. конъюнкцию ранга n. Пример. При n = 4 конъюнкция x 1 x 2 x 3 x 4 - полная. Дизъюнктивной нормальной формой (ДНФ) назовем дизъюнкцию различных элементарных конъюнкций. Пример. x 1 x 2 x 4 x 1 x 2 x 3 x 4 x 3 - ДНФ. Очевидно, что совершенная ДНФ является частным случаем ДНФ. Длиной ДНФ назовем число конъюнкций в данной ДНФ. Рангом ДНФ назовем сумму рангов ее конъюнкций. Пример. Длина ДНФ из предыдущего примера равна трем, а ранг - восьми.

Выделим переменную x 1 и рассмотрим функцию f относительно нее.

Все множество наборов таблицы истинности разбивается на два подмножества, в каждом из которых по четыре набора <0, a 2 , a 3 > и <1, a 2 , a 3 >.

Тогда функцию f(x 1 ,x 2 ,x 3) можно представить в виде дизъюнкции двух функций от двух переменных и эта формула будет иметь вид:

Рассмотрим следующие формулы:

Левая часть первой формулы эквивалентна правой, поскольку для x 1 =0 и в соответствии с операцией конъюнкции. Аналогично можно показать справедливость второй формулы. Таким образом, поставив эти формулы в предыдущую дизъюнкцию, получим:

Это выражение называется разложением функции f(x 1 ,x 2 ,x 3) по переменной x 1 .

Теперь аналогично можно разложить функции f(0,x 2 ,x 3) и f(1,x 2 ,x 3) по переменной x 2 . Получим

Подставляя эти формулы в предыдущие получим

Внесем в соответствии с дистрибутивностью операции & переменную x 1 и ее инверсию в скобки, получим

В общем виде для функции f(x 1 ,x 2 ,..,x n) от n переменных разложение по m переменным (m£n) имеет вид

где дизъюнкция берется по всем 2 m наборам переменных x 1 ,x 2 ,..,x m .

Рассмотрим разложение (*4) при крайнем случае, когда m=n. (см. пример (*3)).

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

Проделаем все это для примера (*3).

После удаления из (*3) конъюнкций с нулевыми значениями функции f на заданных наборах, получим:

Так как в соответствии с таблицей истинности

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

то из конъюнкций уберем сомножители функций, после чего получим:

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

Лемма. Любая булева функция (кроме константы "0") имеет СДНФ, при том только одну.

Аналогично можно ввести конъюнктивную форму,

Построение СДНФ для функции, заданной таблицей

Данное следствие носит конструктивный характер, т.к. оно по таблице функции позволяет построить формулу, являющуюся СДНФ (если ).
СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f ; каждому “единичному” набору (d 1 ,…,d n), т.е. набору, на котором значение функции равно 1, соответствует конъюнкция всех переменных, в которой x i взято с отрицанием, если d i=0 , и без отрицания, если d i =1 .

Рассмотрим вопрос представления n -местной булевой функции f (x 1 ,x 2 ,…,x n ) какой-нибудь формулой алгебры высказываний.

Введем обозначение, где - параметр, равный 0 или 1.

Очевидно, что

Теорема 1.1. Каждую функцию алгебры логики f (x 1 , x 2 ,…, x n ) при любом m (1 £ m £ n ) можно представить в следующей форме:

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

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

т.к. , если только , если же , то и соответствующее логическое слагаемое можно отбросить.

Замечание . Указанное в теореме представление функции называется разложением функции по m переменным .

Следствие 1 (разложение по одной переменной).

В этом случае функции и называются компонентами разложения .

Следствие 2 (разложение по всем переменным).

Очевидно, что если , то

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

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

1. Каждое логическое слагаемое содержит все переменные, входящие в формулу f (x 1 ,x 2 ,…,x n ).

2. Ни одно логическое слагаемое не содержит одновременно переменную и ее отрицание.

3. Все логические слагаемые в формуле различны.

4. Ни одно логическое слагаемое не содержит одну и ту же переменную дважды.

Эти четыре свойства называются свойствами совершенства (или свойствами С).

Если f (x 1 ,x 2 ,…,x n ) задана таблицей истинности, то соответствующая формула алгебры логики восстанавливается довольно просто. Для всех значений аргументов x 1 ,x 2 ,…,x n , при которых f принимает значение 1, нужно записать конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции x i , если x i =1, и , если x i =0. Дизъюнкция всех записанных конъюнкций и будет необходимой формулой. О значениях f 0 можно не беспокоиться, т.к. соответствующее слагаемое в формуле будет равно 0 и его можно отбросить в силу равносильности f Ú 0 ≡ f .

Например, пусть функция f (x , y , z ) имеет следующую таблицу истинности:

x	y	z	f (x , y , z )