Конспект лекций по дискретной математике

Приложение Булевой алгебры к синтезу комбинационных схем

Двоичная система логики:

1. Элементы Булевой алгебры:

а) числа

b) переменные

с) операции

d) выражения

e) функции

f) законы

А) Числа:

Два числа: логический ноль и логическая единица в Булевой алгебре

отождествляются с понятиями “истина” и ”ложь”.

В) Переменные:

Булевы (логические, двоичные) переменные называются переменными,

принимающими значение из множества - ноль и единица.

С) Операции:

1. Отрицание (инверсия).

2. Конъюнкция (логическое умножение).

3. Дизъюнкция (логическое сложение).

Унарной является операция отрицания.

Обозначения:

1. Отрицание [pic], ( x

2. Конъюнкция a&b, a(b, ab, a(b

3. Дизъюнкция a(b

D) Выражения:

Переменные, знакооперации, соединенные вместе при возможном наличии

скобок для задания порядка выполнения операций.

Приоритет задается порядком операции.

Е) Функции:

Булевой (логической) функцией называется такая функция, аргументами

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

множества ноль и единица.

Областью определения Булевой функции является совокупность 2n

двоичных наборов ее аргументов. Набор аргументов можно рассматривать как n-

компонентный двоичный вектор.

Формы задания Булевой функции:

1. Аналитическая (в виде логического выражения)

2. Табличная (в виде таблицы истинности)

3. Графическая

4. Таблично-графическая (в виде карты Карно)

5. Числовая

6. Символическая форма

1) Аналитическая:

_ _

y=(x1 ( x2) x3

_ _ _ _ _ _

y=x1 x2 x3 ( x1 x2 x3 ( x1 x2 x3

2) Табличная:

| | | |_ | |

|x1 |x2 |x3 |x1 ( x2|y |

|0 |0 |0 |1 |1 |

|0 |0 |1 |1 |0 |

|0 |1 |0 |1 |1 |

|0 |1 |1 |1 |0 |

|1 |0 |0 |0 |0 |

|1 |0 |1 |0 |0 |

|1 |1 |0 |1 |1 |

|1 |1 |1 |1 |0 |

Переход от аналитической к табличной однозначен! Обратный переход не

является однозначным.

Основные законы (тождества)

1) ab=ba

a(b=b(a

2) Ассоциативный:

a(bc)=(ab)c

a((b(c)= (a(b) (c

3) Дистрибутивный:

a(b(c)=ab(ac

a((bc)=(a(b)(a(c)

4) Закон двойного отрицания:

a=a

5) Тавтологии:

aa=a

a(a=a

6) Законы нулевого элемента:

a0=0

a(0=a

7) Законы единичного элемента:

а1=а

а(1=1

8) Законы дополнительного элемента:

В Булевой алгебре дополнительным элементом к а является а.

_ _

а(а=1; аа=0

9) Двойственности (деМоргана):

__ _ _

ab=a(b

___ _ _

a(b=a b

Cледствия: ab=a(b; a(b=a b

10) Поглощения:

a(ab=a

a(a(b)=a

11) Сокращения:

а(аb=a(b

a(a(b)=ab _ _ _ _

Cледствия: a(ab=a(b; a(a(b)=ab

12) Склеивания:

_ _

ab(ab=a; (a(b)(a(b)=a

Комментарии:

1) Для доказательства законов можно использовать:

а) Метод совершенной индукции.

б) Использование одних законов для доказательства других законов.

Метод совершенной индукции состоит в доказательстве эквивалентности левой и

правой части на всем множестве наборов аргументов. Для этого составляется

таблица истинности.

2) Большинство законов задается парой соотношений, при этом одно

соотношение можно получить из другого заменив операции конъюнкции на

дизъюнкцию или дизъюнкцию на конъюнкцию (метод не применим в законах, в

которых участвуют константы). С константами же константы заменяются на

противоположные значения. (Дуальность законов Булевой алгебры)

3) Некоторые законы можно распространять на произвольное число элементов.

4) В любом законе можно заменить любую букву на произвольное логическое

выражение.

5) Законы применяются для упрощения Булевых функций.

Разнообразие Булевых функций.

1. Булева функция от одной переменной.

|Обозначение |Значения аргумента и функции |Наименование |

|аргумента и | |функции |

|функции | | |

|x |0 |1 | |

|[pic] |0 |0 |Логический ноль |

|[pic] |0 |1 |Повторение x |

|[pic] |1 |0 |Инверсия x |

|[pic] |1 |1 |Логическая единица|

2. Возможные функции от двух переменных.

|[pic] |0 |0 |0 |0 |“0” |Логический ноль |+ |- |

|[pic] |0 |0 |0 |1 |x1&x2 |Конъюнкция |- |x1 x2 |

|[pic] |0 |0 |1 |0 |x1(x2 |Запрет x1 по x2 |- |x1 [pic]2 |

|[pic] |0 |0 |1 |1 |x1 |Повторение x1 |+ |- |

|[pic] |0 |1 |0 |0 |x2(x1 |Запрет x2 по x1 |- |x2[pic]1 |

|[pic] |0 |1 |0 |1 |x2 |Повторение x2 |+ |- |

|[pic] |0 |1 |1 |0 |x1(x2 |Сумма по модулю 2 неравнозначная |- |[pic]1 x2 ( |

|[pic] |0 |1 |1 |1 |x1(x2 |Дизъюнкция |- |x1 ( x2 |

|[pic] |1 |0 |0 |0 |x1(x2 |Функция Вебба |- |x1(x2 |

|[pic] |1 |0 |0 |1 |x1(x2 |Равнозначность |- |[pic]1[pic]2 |

| | | | | | | | |( x1 x2 |

|[pic] |1 |0 |1 |0 |[pic]2 |Отрицание x2 |+ |- |

|[pic] |1 |0 |1 |1 |x2(x1 |Импликация от x2 к x1 |- |[pic]2 ( x1 |

|[pic] |1 |1 |0 |0 |[pic]1 |Отрицание x1 |+ |- |

|[pic] |1 |1 |0 |1 |x1(x2 |Импликация x1 к x2 |- |[pic]1 ( x2 |

|[pic] |1 |1 |1 |0 |x1 | x2 |Штрих Шеффера |- |[pic] |

|[pic] |1 |1 |1 |1 |“1” |Логическая единица |+ |- |

Определение: Булева функция от n аргументов fn(x) называется вырожденной по

аргументу xi, если ее значение не зависит от этого аргумента, то есть для

всех наборов аргументов имеет место равенство:

f(x1, x2, ... , xi-1, 0, xi+1, ... , xn) = f(x1, x2, xi-1, 1, xi+1,

... , xn).

Функция запрета x1(x2 принимает значение, равное нулю при равенстве

запрещающей переменной (x2) единице и повторяет значение аргумента x1 при

равенстве запрещающей переменной нулю.

Понятие импликации в Булевой алгебре отождествляется с выражением

следования (если ... то ... ).

Пример: Имеют место два простых высказывания.

А. На небе тучи.

В. Идет дождь. В(А

|А |В |В(А |

|f |f |t |

|f |t |f |

|t |f |t |

|t |t |t |

Из истины не может следовать ложь!

Некоторые функции от трех переменных.

|Значение аргументов|Значение функций |

| |2 |ИЛИ |мажоритарности |

|x1 |x2 |x3 |x1(x2(x3 |XOR (x1,x2,x3)|x1#x2#x3 |

|0 |0 |0 |0 |0 |0 |

|0 |0 |1 |1 |1 |0 |

|0 |1 |0 |1 |1 |0 |

|0 |1 |1 |0 |0 |1 |

|1 |0 |0 |1 |1 |0 |

|1 |0 |1 |0 |0 |1 |

|1 |1 |0 |0 |0 |1 |

|1 |1 |1 |1 |0 |1 |

Функция - сумма по модулю 2 и исключающее ИЛИ являются эквивалентными

только для двух аргументов.

Общее разнообразие функций от n аргументов равно 22

В самом компактном виде любую Булеву функцию можно представить

символически: [pic], где n-количество аргументов, а N-десятичный эквивалент

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

Пример:

f3(x)=x1(x2(x3=[pic]

Невырожденные функции от двух переменных с добавлением функции

отрицания принято называть функциями Булевой алгебры. С учетом обращаемости

некоторых базовых функций к некоторым аргументам, их общее количество равно

девяти.

Нормальные формы Булевых функций

Нормальные формы - это особый класс аналитических выражений,

используемых при решении задачи минимизации Булевых функций и для перехода

от табличной формы задания к аналитической. Нормальные формы строятся на

основании операций конъюнкции, дизъюнкции и отрицания, причем отрицание

только единственной переменной.

Определение: Элементарной конъюнкцией (дизъюнкцией) называется

конъюнкция (дизъюнкция) конечного числа попарно различимых переменных или

их отрицаний.

Элементарную конъюнкцию (дизъюнкцию) принято называть конъюнктивным

(дизъюнктивным) термом.

В частном случае терм, как конъюнктивный так и дизъюнктивный может

состоять из единственной буквы (литерала). Под буквой будем понимать

аргумент Булевой функции и его отрицания.

Примеры конъюнктивных термов:

_ _

x1, x2, x1x3, x2x4x5 (терм)

___ _

x1x2, x1x2x3 (не терм)

Рангом терма называется количество букв входящих в него.

Дизъюнктивной (конъюнктивной) нормальной формой Булевой функции называется

дизъюнкция (конъюнкция) конечного числа попарно различимых конъюнктивных

(дизъюнктивных) термов.

Каноническая нормальная форма.

Конституентой единицы (нуля) называется конъюнктивный (дизъюнктивный)

терм максимального ранга. Т.е. для Булевой функции от n переменных

конституента включает в себя n букв.

Свойство конституенты: Конституента единицы (нуля) принимает значение

единицы (нуля) на одном и только одном наборе аргументов.

Пример: _ _

n=4 x1x2x3x4 (1010)=1

_ _ _

x1(x2(x3(x4=0

Определение: Дизъюнктивная (конъюнктивная) нормальная форма

называется канонической, если все ее дизъюнктивные (конъюнктивные) термы

представляют собой конституенты единицы (нуля). Иногда канонические формы

называют совершенными.

Пример получения канонических форм:

y=x1(x2

|x1 |x2 |y |Конституен|Конституен|

|0 |0 |0 |- |x1(x2 |

|0 |1 |1 |[pic]1x2 |- |

|1 |0 |1 |x1[pic]2 |- |

|1 |1 |0 |- |[pic]1([pi|

| | | | |c]2 |

КДНФ - каноническая дизъюнктивная нормальная форма:

_ _

y=x1x2(x1x2

ККНФ - каноническая конъюнктивная нормальная форма:

_ _

y=(x1(x2)(x1(x2)

1) С помощью канонических форм наиболее просто осуществляется переход от

табличной формы задания Булевой функции к аналитической.

2) С помощью канонических форм можно осуществить преобразование любой

функции в Булев базис.

3) Любая Булева функция за исключением логического нуля и логической

единицы имеет единственные КДНФ и ККНФ. Логическую единицу можно

представить в виде КДНФ и логический ноль в виде ККНФ.

4) Правило перехода от табличной формы задания Булевой функции к

аналитической:

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

функция равна единице (нулю).

б) для каждого из этих наборов составляют конституенты единицы

(нуля).

в) объединением конституенты единицы (нуля) знаками дизъюнкции

(конъюнкции) получается аналитическая форма в виде КДНФ (ККНФ).

Пояснение: при составлении конституент единицы (нуля) используют следующее

правило:

Если некоторый аргумент принимает на наборе значение равное нулю, то в

конституенту единицы он входит с отрицанием, а в конституенту нуля без

него.

5) КДНФ и ККНФ представляют собой две различные, но эквивалентные

аналитические формы булевой функции. Это означает, что из одной формы можно

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

_ _ _ _ _ _ _ _

_ _

y=(x1(x2)(x1(x2)=x1x1(x1x2(x2x1(x2x2=x1x2(x2x1=x1x2(x1x2 (КДНФ)

6) Принципиально существует другой способ получения ККНФ:

а) составляется КДНФ, но не для самой, а для ее отрицания.

б) берется отрицание над полученной КДНФ, которое снимается с

применением закона двойственности.

_ _ _ = ------------ ----- ---- _

y=x1x2(x1x2, y=y=x1x2(x1x2=x1x2 x1x2=( x1(x2)(x1(x2)

Разнообразие двоичных алгебр

В связи с тем, что любую сколь угодно сложную Булеву функцию можно

представить в канонических формах, то есть записать ее с помощью операций

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

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

Естественно предположить, что система Булевых операций является не

единственной, с помощью которой можно образовать некоторый базис.

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

соответствующей операцией и на основе совокупности этих операций построить

двоичные алгебры, отличные от Булевой. К наиболее распространенным двоичным

алгебрам относятся: алгебра Жигалкина ((, &); алгебра Вебба (Пирса) (();

алгебра Шеффера ( | ). В каждой из этих алгебр действуют собственные

законы. Естественно существуют взаимно однозначные переходы от операций

одного базиса к операциям другого.

Числовое представление Булевых функций

Для любой Булевой функции можно предложить две числовые формы,

основанные на перечислении десятичных эквивалентов наборов аргументов на

которых функция принимает значение единицы (нуля).

f3(x)=[pic](0,2,6,7) - от этой числовой формы легко перейти к КДНФ путем

замены каждого из наборов в перечислении конституенты единицы.

_ _ _ _ _ _ _ _ _

_ _

y=x1x2x3(x1x2x3(x1x2x3(x1x2x3=x1x3(x2(x2)(x1x2(x3(x3)=x1x3(x1x2 (ДНФ)

f3(x)=[pic]&(1,3,4,5)

_ _ _ _ _ _

y=(x1(x2(x3) (x1(x2(x3) (x1(x2(x3) (x1(x2(x3) (*)

Преобразование произвольной аналитической формы Булевой функции в

нормальную

В Булевой алгебре в виде теоремы доказывается следующее утверждение:

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

аналитическое выражение Булевой алгебры в произвольной форме к нормальной

форме.

Пример:

_ _ _ _

_ _

y=f4(x)=(x1x2(x2x3)(x1|x4)=(x1x2(x2x3)(x1x4)=(x1x2(x2x3)(x1(x4)=

_ _ _ _ _ _ _

_ _ _

=x1x2(x1x2x4(x1x2x3(x2x3x4=x1x2(x1x2x3(x2x3x4=x1(x2(x2x3)(x2x3x4=

_ _ _ _

=x1(x2(x3) (x2x3x4=x1x2(x1x3(x2x3x4

(КДНФ)

Замечания:

1) В общем случае любая Булева функция может иметь несколько КДНФ,

отличающихся либо количеством термов, либо количеством букв в этих термах.

2) При построении комбинационной схемы, реализующей данную функцию по

ее нормальной форме предпочтительней та, которая обладает наименьшим числом

термов и наименьшим количеством букв в этих термах.

3) По сравнению со схемой, построенной по ДНФ, схема, построенная по

скобочной форме (*), является более предпочтительной т.к. при одном и том

же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9

вместо 10).

Задача преобразования нормальной формы Булевой функции в

скобочной форме называют задачей фактеризации.

4) Сущность конструктивного подхода при получении ДНФ состоит в

следуюшем:

а) преобразование операций не-Булевого базиса к операциям

Булевого базиса (см. последние строки таблицы)

б) снятие отрицаний над выражениями с применением законов

двойственности

в) раскрытие скобок с применением дистрибутивного закона

г) упрощения выражения с применением закона поглощения

Приведение произвольных нормальных форм Булевой функции к каноническим

Для приведения произвольной ДНФ к КНФ необходимо использовать правило

дизъюнктивного развертывания применительно к каждому из неполных

конъюнктивных термов.

_ _

P=P(xi(xi)=Pxi(Pxi, где P-неполный конъюнктивный терм (ранг этого терма

меньше n), а xi - недостающий в терме

аргумент.

Пример:

_ _ _ _ _ _

_ _ _ _

y=x1(x2x3(ДНФ)=x1(x2(x2)(x3(x3) (x2x3(x1(x1)=x1x2x3( x1x2x3(

_ _ _ _ _ _ _ _ _

(x1x2x3(x1x2x3( x1x2x3( x1x2x3 (КДНФ)

Замечание:

После раскрытия скобок могут получиться одинаковые термы, из которых

нужно оставить только один.

y=[pic] (0,1,2,3,5)=f3

Преобразование КНФ к ККНФ реализуется путем применения правила

конъюнктивного развертывания к каждому неполному дизъюнктивному терму.

_ _

P=P(xixi=(P(xi)(P(xi)

_ _ _ _ _ _ _ _ _

y=x1(x2x3(ДНФ)=(x1(x2)(x1(x3)(КНФ)=(x1(x2(x3x3)(x1(x3(x2x2)=

_ _ _ _ _ _ _ _

=(x1(x2(x3)(x1(x2(x3)(x1(x2(x3)(x1(x2(x3)(ККНФ)

y=[pic](4,6,7)

Минимизация булевых функций на картах Карно(см. Практику).

Метод Квайна-МакКласски базируется на кубическом представлении

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

Кубическое представление булевых функций.

Страницы: 1, 2, 3

МЕНЮ

Конспект лекций по дискретной математике

Конспект лекций по дискретной математике

ИНТЕРЕСНОЕ