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

Теория.

 

Общие понятия.

Логическая функция f (x1,x2,...,x_n) - это функция, принимающая значения 0 и 1, аргументы которой (x1,x2,...,x_n) также принимают значения 0 и 1. Здесь 0 и 1 - не арифметические величины, а истинностные значения.

0 - "нет" - ЛОЖЬ;

1 - "да" - ИСТИНА.

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

Первоначально логические функции использовались для описания схем на основе переключательных (двухстабильных) элементов, которые назывались переключательные схемы (switching circuits).

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

Рассмотрим область определения и область значений булевой функции. Аргументы булевой функции n переменных можно рассматривать как выборку из n элементов (выборку размерности n), каждый из которых принимает два значения { 0, 1 }. Область определения такой булевой функции (всевозможные наборы аргументов) можно рассматривать как множество перестановок с повторениями в выборке размерности n из двух элементов { 0, 1 }. Таким образом, количество входных наборов m булевой функции n переменных вычисляется по формуле

m = 2ⁿ.

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

K = 2m, или K = 2 .

(1)

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

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

Словесный - при этом способе словесное описание однозначно определяет все случаи, при которых функция принимает значения 0 или 1. Например, многовходовая функция ИЛИ может иметь такое словесное описание: функция принимает значение 1, если хотя бы один из аргументов принимает значение 1, иначе - 0.

Числовой - функция задается в виде десятичных (или восьмеричных, или шестнадцатиричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Условие, что функция f (x1, x2, x3) = 1 на наборах 1,3,5,6,7 записывается f (1, 3, 5, 6, 7) = 1. Аналогичным образом булева функция может быть задана по нулевым значениям. При нумерации наборов переменным x1, x2, x3 ставится в соответствие веса 2², 2¹, 2⁰, т.е. 6 набору соответствует двоичный эквивалент 110, а 1 набору - 001.

Табличный - Функция задается в виде таблицы истинности (соответствия), которая содержит 2n строк (по числу наборов аргументов), n столбцов по числу переменных и один столбец значений функции. В такой таблице каждому набору аргументов соответствует значение функции. n = 3, число строк 23 = 8, число возможных функций трех переменных 2 = 28 = 256.

Аналитический - Функция задается в виде алгебраического выражения, получаемого путем применения каких-либо логических операций к перемененным алгебры логики. применяя операции конъюнкции и дизъюнкции можно задать функцию выражением f (x1, x2, x3) = x1x2 v x3. Способ получения такого аналитического описания булевой функции будет рассмотрен в последующих разделах.

Координатный - при этом способе задания таблица истинности функции представляется в виде координатной карты состояний, которая часто называется картой Карно. Такая карта содержит 2ⁿ клеток по числу наборов всевозможных значений n переменных функции. Переменные функции разбиваются на две группы так, что одна группа определяет координаты столбца, а другая - координаты строки. При такoм способе построения клетка определяется координатами переменных, соответствующих определенному двоичному набору. Внутри клетки карты Карно ставится значение функции на данном наборе. Переменные в строках и столбцах располагаются так, чтобы соседние клетки карты Карно различались только в одном разряде переменных, т.е были соседними. Такой способ представления очень удобен для наглядности при минимизации булевых функций.

Диаграмный - является способом представления функционирования схемы, реализующей булеву функцию, во времени. Изображается в виде системы графиков, у которых ось Х соответствует автоматному времени (моментам времени), а ось Y соответствует напряжению дискретных уровней сигналов "логический 0" (0,4 в) и "логическая 1" (2,4 в).

 

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

 

Как любая алгебраическая система булева алгебра базируется на совокупности некоторых предположений, которые принято называть аксиомами, т.е предположениями не требующими доказательств. Аксиомы определяются для двух логических значений 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).

 

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

Так как в булевой алгебре функции принимают только два значения 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; Полученную таким образом инверсную функцию называют обратной ДНФ.