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

Лабораторная работа №6.

Схемотехническая реализация логических элементов. Построение логических схем.

Теоретическая часть.

Законы булевой алгебры. Основные аксиомы, теоремы и тождества

 

Как любая алгебраическая система булева алгебра базируется на совокупности некоторых предположений, которые принято называть аксиомами, т.е предположениями не требующими доказательств. Аксиомы определяются для двух логических значений 1 ("ИСТИНА") и 0 ("ЛОЖЬ") и операций логического умножения (конъюнкции), которая обозначается " & ", " · " или не обозначается вовсе, логического сложения (дизъюнкции), которая обозначатся " v ", "+", и отрицания (инверсии), которая обозначается горизонтальной чертой (" - ") над переменной или выражением, например, . Булевой переменной, обозначаемой обычно x_i, называется переменная принимающая два логических значения { 0, 1 }.

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

1. Аксиомы конъюнкции 0· 0 = 0; 1· 1 = 1; 0· 1 = 1· 0 = 0;

2. Аксиомы дизъюнкции 0 v 0 = 0; 1 v 1 = 1; 0 v 1 = 1 v 0 = 1;

3. Аксиомы отрицания Если x = 0, то = 1;

Если x = 1, то = 0;

Следующие 5 правил обычно называют теоремами булевой алгебры. Особенностью теорем булевой алгебры является то, что для их доказательства пользуются простой подстановкой значений булевых переменных. Это обусловлено тем, что переменные могут принимать только 2 значения - 0 и 1.

4. Операции с константами:

5. Идемпотентность (тавтология, повторение):

Для n переменных:

6. Противоречие:

 

7. Правило "исключенного третьего":

8. Двойное отрицание (инволюция):

 

Следующие 4 правила обычно называют законами или тождествами булевой алгебры.

9. Ассоциативность (ассоциативный закон):

10. Коммутативность (коммутативный закон):

11. Дистрибутивность (дистрибутивный закон):

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

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

12. Законы де Моргана (законы инверсии или отрицания):

Расширенный закон де-Моргана:

 

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

13. Поглощение (элиминация):

14. Закон Блейка-Порецкого:

15. Склеивание (объединение):

 

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

 

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

 

Дизъюнктивная и конъюнктивная нормальные формы

 

В данном подразделе более подробно рассматривается аналитическое представление булевых функций в виде уравнений (булевых уравнений) с использованием операций дизъюнкции (ИЛИ), которую принято обозначать " v ", конъюнкции (И), которую принято обозначать " & ", " · " или не обозначать вовсе, и отрицания (инверсии), которую обозначают горизонтальной чертой (" - ") над выражением, например, . Рассмотрим основные понятия и определения, используемые при аналитическом представлении булевых функций.

Элементарное произведение - произведение (конъюнкция) любого числа букв (переменных) булевой функции, взятых с отрицанием или без. Например, x1x2x3, 1x3.

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

f = x1x2x3 v 1x3.

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

Элементарная сумма - логическая сумма (дизъюнкция) любого числа букв (переменных) булевой функции, взятых с отрицанием или без. Например, (x1 v x2 v x3), ( 1 v x3).

Конъюнктивная нормальная форма (КНФ) - конъюнкция элементарных сумм. Термин "нормальная" озачает, что в данном выражении отсутствуют групповые инверсии, т.е инверсия над несколькими переменными сразу. Пример КНФ f = (x1 v x2 v x3)· ( 1 v x3).

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

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

Скобочные формы

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

Например, для функции четырех переменных f (11, 13, 14, 15) = 1, ДНФ имеет вид f = x1x2x3 v x1x2x4 v x1x3x4. Если в первых двух элементарных произведенниях вынести за скобки x1x2, то получим скобочную форму f = x1x2 (x3 v x4) v x1x3x4, которая содержит на две буквы меньше, чем исходная ДНФ.

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

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

Для получения СДНФ на основе таблицы истинности необходимо:

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

2) Полученные элементарные конъюнкции объединяются знаками дизъюнкции.

Для получения СКНФ на основе таблицы истинности необходимо:

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

2) Полученные элементарные дизъюнкции объединяются знаками конъюнкции.

В качестве примера рассмотрим булеву функцию трех переменных, f (1,3,5,6,7)=1. Ниже приведены таблица истинности и полученные на ее основе СДНФ и СКНФ.

x1 x2 x3 f (x1, x2, x3) 0 0 0   0 0 1   0 1 0   0 1 1   1 0 0   1 0 1   1 1 0   1 1 1

СДНФ f = 1 2x3 v 1x2x3 v x1 2x3 v x1x2 3 v x1x2x3; СКНФ f = (x1 v x2 v x3)· (x1 v 2 v x3)· ( 1 v x2 v x3).

 

Минимальные ДНФ и КНФ этой функции будут иметь вид:

ДНФ f = x1x2 v x3;

КНФ f = (x1 v x3)· (x2 v x3).

Инверсные функции

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

На основании закона Де-Моргана можно сформулировать правило получения инверсной функции.

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

Например, для ДНФ f = x1x2 v x3, = ( 1 v 2)· 3; Полученную таким образом инверсную функцию называют обратной КНФ.

Для КНФ f = (x1 v x3)· (x2 v x3), = 1 3 v 2 3; Полученную таким образом инверсную функцию называют обратной ДНФ.

 

Минимизация логических функций.

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

Минимизация производится с помощью применения законов склеивания и поглощения.

 

Пример.

Найти минимальную ДНФ функции Y=f (x1, x2, x3); f (0,2,3,4,5,7)=1.

Решение.

Построим таблицу истинности функции Y.

 

x1 x2 x3	f (x1, x2, x3)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

 

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

 

Y= 1 2 3 v 1x2 3 v 1x2x3 v x1 2 3 v x1 2x3 v x1x2x3

 

Применим склеивание следующим образом: Fx v F = F

Получим:

Y= 1x2 v x2x3 v x1x3 v x1 2 v 2 3 v 1 3

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

 

Y1= 1x2 v x1x3 v 2x3;

Y2= 1x2 v x2x3 v x1 2 v 1 3;

Y3= 1x2 v x1x3 v x1 2 v 1 3;

Y4= 1 3 v x2x3 v x1 2;

Y5= 1 3 v 1x2 v x1x3 v x1 2.

 

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

 

 

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Элемент НЕ

A

При подаче на вход схемы сигнала низкого уровня (0) транзистор будет заперт, т.е. ток через него проходить не будет, и на выходе будет сигнал высокого уровня (1). Если же на вход схемы подать сигнал высокого уровня (1), то транзистор “откроется”, начнет пропускать электрический ток. На выходе за счет падения напряжения установится напряжение низкого уровня. Таким образом, схема преобразует сигналы одного уровня в другой, выполняя логическую функцию.

Элемент ИЛИ

А	В	С

Функция “ИЛИ” - логическое сложение (дизъюнкция), ее результат равен 1, если хотя бы 1 из аргументов равен 1.
Здесь транзисторы включены параллельно друг другу. Если оба закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический “0”). Достаточно подать сигнал высокого уровня (“1”) на один из транзисторов, как схема начнет пропускать ток, и на сопротивлении нагрузки установится также сигнал высокого уровня (логическая “1”).

 

Элемент И

A	B	C

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R_н близко к нулю.
Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня.
И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

Таким образом, каждой базовой логической функции – «И», «ИЛИ», «НЕ» - соответствует особым образом сконструированная схема, называемая логическим элементом. Комбинируя сигналы, обозначающие логические переменные, и выходы, соответствующие логическим функциям, с помощью логических элементов, пользуясь таблицей истинности или представлением логической функции в виде КНФ и ДНФ, можно составить структурную или функциональную схему (см. примеры ниже), являющуюся основой для аппаратной реализации схемы.

Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет.
Не менее важной формой описания логических устройств является структурная формула. Покажем на примере как выписывают формулу по заданной функциональной схеме (1 схема).
Ясно, что элемент “И” осуществляет логическое умножение значений и В.
Над результатом в элементе “НЕ” осуществляется операция отрицания, т.е. вычисляется значение выражения:
Формула и есть структурная формула логического устройства.

Итак, основные логические функции обозначаются

Инверсия
Конъюнкция
Дизъюнкция

Пример: дана логическая схема:

A E I Y

Она построена на основании булева выражения - Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E

Практическая часть.

Задание 1. Для каждой из функциональных схем выписать соответствующую структурную формулу.

 

2) Для КНФ и ДНФ из заданий приведенных ниже построить функциональные схемы.

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

Варианты:

1) f (1,2,3,4) = 1; f (2,4,5,6,7) = 1; f (1,2,3,8,13,14,15) = 1;

2) f (1,2,4,5) = 1; f (3,4,5,6,7) = 1; f (1,2,4,8,12,14,15) = 1;

3) f (1,2,5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;

4) f (1,2,6,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,9,11,12,15) = 1;

5) f (0,2,4,6) = 1; f (1,2,4,5,7) = 1; f (0,3,5,10,12,13,14) = 1;

6) f (0,3,5,6) = 1; f (0,1,2,6,7) = 1; f (1,2,3,5,7,10,14) = 1;

7) f (1,2,5,7) = 1; f (0,3,4,5,7) = 1; f (1,2,4,5,8,12,13) = 1;

8) f (0,4,5,7) = 1; f (1,2,3,6,7) = 1; f (4,5,6,8,9,11,12) = 1;

9) f (0,1,2,3) = 1; f (3,4,5,6,7) = 1; f (8,9,11,12,13,14,15) = 1;

10) f (2,3,4,5) = 1; f (0,1,3,6,7) = 1; f (7,10,11,12,13,14,15) = 1;

11) f (3,4,5,6) = 1; f (0,1,2,5,7) = 1; f (0,4,8,12,13,14,15) = 1;

12) f (1,2,3,5) = 1; f (0,3,4,6,7) = 1; f (2,4,7,8,9,12,15) = 1;

13) f (1,2,3,6) = 1; f (0,2,4,5,7) = 1; f (3,6,9,12,13,14,15) = 1;

14) f (1,2,3,7) = 1; f (0,1,4,6,7) = 1; f (2,4,6,8,11,13,15) = 1;

15) f (1,2,4,6) = 1; f (0,1,4,5,7) = 1; f (0,5,7,10,11,12,13) = 1;

16) f (1,2,4,7) = 1; f (0,2,4,6,7) = 1; f (1,6,9,10,11,12,14) = 1;

17) f (0,1,3,6) = 1; f (1,2,4,5,6) = 1; f (0,2,4,9,11,12,13) = 1;

18) f (0,1,4,5) = 1; f (1,2,3,4,6) = 1; f (0,1,4,5,8,9,12) = 1;

19) f (0,1,3,5) = 1; f (1,2,4,6,7) = 1; f (1,2,4,15,9,10,12) = 1;

20) f (1,3,5,6,7) = 1; f (0,1,2,3,4) = 1; f (6,7,9,11,12,13,15) = 1;

21) f (1,2, 4, 5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7, 11,13,14,15) = 1;

22) f (1,2,5,6,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,7, 9,11,12,15) = 1;

23) f (1,2, 3,5,6) = 1; f (0,1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;

24) f (1,2,6,7) = 1; f (1,3,4,6,7, 9) = 1; f (1,2,4, 5, 9,11,12,15) = 1;

25) f (1,2,5,6) = 1; f (0, 1,6,7) = 1; f (1,2,5,6,7,13,14,15) = 1;

26) f (1,2,6,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,9, 10,11,12,15) = 1;

27) f (0,1,2,5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;

28) f (0,1,2) = 1; f (1,3,4,6,7) = 1; f (1,2,4,9,11,12,13) = 1;

29) f (1,2,5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;

30) f (1,2,3,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,5,8,9,11,) = 1;