contents
Булева алгебра

Аналитические представления функций


expand

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

Способ представления функции в виде математического выражения (формулы) называется аналитическим. В этой главе узнаем, какие бывают виды формул и для чего нужно это разнообразие.

Пусть задана булева функция F(a,b,c) , которая принимает единичное значение только на одном наборе переменных, как показано в таблице истинности. Такие функции называются минтермами (минимальными термами, конституентами единицы).

Это набор № 3, где a=0, b=1, c=1.
F(a,b,c) = ᖰaᖳbc

Минтермом n переменных называется конъюнкция, в которую каждая переменная входит один раз в прямой или инверсной форме. Минтермы обозначаются буквой m с десятичным номером, который соответствует номеру набора, на котором функция принимает значение единицы. Всего минтермов может быть столько, сколько строк в таблице. То есть 2кол-во переменных

F(a,b,c) = m3 или F(a,b,c) = (3)

Пусть функция F(a,b,c) принимает единичное значение на нескольких наборах, как показано в таблице истинности. Чтобы представить эту функцию аналитически, запишем дизъюнкцию минтермов, составляющих ее.

F(a,b,c) = (3,6) = m6+m7= ᖰaᖳbc ∨ abᖰcᖳ

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

Пусть задана булева функция от трех переменных F(a,b,c) , которая принимает единичное значение на всех наборах, кроме одного. Такие функции называют макстермами или конституентами нуля.

F(a,b,c) = ¬m5= ¬( aᖰbᖳc ) = ᖰaᖳ ∨ b ∨ ᖰcᖳ ( по теореме де Моргана )

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

Пусть функция F(a,b,c,d) принимает значение 1 на всех наборах, кроме трех (5, 12, 13). Чтобы представить эту функцию аналитически в СДНФ нужно перечислить все минтермы, составляющие ее.

F(a,b,c,d) = ᖰaᖳ ᖰbᖳ ᖰcᖳ ᖰdᖳ ∨ ᖰaᖳ ᖰbᖳ ᖰcᖳ d ∨ ᖰaᖳ ᖰbᖳ c ᖰdᖳ ∨ ᖰaᖳ ᖰbᖳ c d ∨ ᖰaᖳ bᖰcᖳ ᖰdᖳ ∨ ᖰaᖳ b c ᖰdᖳ ∨ ᖰaᖳ b c d ∨ a ᖰbᖳ ᖰcᖳ ᖰdᖳ ∨ a ᖰbᖳ ᖰcᖳ d ∨ a ᖰbᖳ c ᖰdᖳ ∨ a ᖰbᖳ c d ∨ a b c ᖰdᖳ ∨ a b c d

Запишем функцию в виде конъюнкции макстермов. Такую форму называют совершенной конъюнктивно нормальной (СКНФ):

F(a,b,c,d) = (a ∨ ᖰbᖳ ∨ c ∨ ᖰdᖳ ) ( ᖰaᖳ ∨ ᖰbᖳ ∨ c ∨ d) ( ᖰaᖳ ∨ ᖰbᖳ ∨ c ∨ ᖰdᖳ)

Формула, записанная в СКНФ получилась лаконичней, чем в СДНФ. КНФ лучше использовать тогда, когда на большинстве наборов функция принимает единичное значение. Тогда гораздо легче указать наборы, при которых функция не равна единице, чем перечислять все минтермы. Определение через отрицание возможно благодаря тому, что переменная в алгебре логики имеет только два возможных значения и кол-во наборов ограничено. Если сказано, что функция принимает значение 0 только на наборах 5,12,13, значит на всех остальных наборах функция принимает значение 1.

Если бы переменная была из бесконечного множества чисел, то мы бы не смогли определить ее значение через отрицание. Например, можно сказать, что x ≠ 3, x ≠ 5, x ≠ 14, и т.д… Однако из этого не следует чему же равен x.

Пусть функция F(a,b,c) задана в ДНФ следующим образом: F1 = a ᖰbᖳ ᖰcᖳ ∨ a ᖰbᖳ c
Каким образом можно получить ее КНФ без построения таблицы истинности? Для этого используем двойное инвертирование и затем теорему Де Моргана:
F1 = ¬¬F1 = ¬¬( a ᖰbᖳ ᖰсᖳ ∨ a ᖰbᖳ c ) = ¬[¬( a ᖰbᖳ ᖰсᖳ) ∧ ¬(a ᖰbᖳ c )] =¬[( ᖰaᖳ ∨ b ∨ с) ∧ ( ᖰaᖳ ∨ b ∨ ᖰcᖳ )] =¬(( ᖰaᖳ ∨ b ∨ с ) ( ᖰaᖳ ∨ b ∨ ᖰcᖳ ))

Если нужно получить ДНФ из КНФ, то выполняем аналогичную последовательность действий: F2 = ( a ∨ с ) ( ᖰaᖳ ∨ b )
F2 = ¬¬F2 = ¬¬(( a ∨ с ) ( ᖰaᖳ ∨ b )) = ¬(¬( a ∨ с )∨ ¬( ᖰaᖳ ∨ b )) = ¬( ᖰaᖳ ᖰcᖳ ∨ a ᖰbᖳ )

Пусть дана булева функция F(a,b,c) = ab ∨ ᖰbᖳc. Формула записана в виде дизъюнкции конъюнкций (ДНФ). Она не является совершенной, т.к. не во всех «слагаемых» присутствует каждая переменная в прямой или инверсной форме. Для того, чтобы получить из нее СДНФ необходимо для каждого аргумента применить теорему разложения:

Всякую булеву функцию можно представить в следующем виде: F(A1, A2,…, An) = A1F(1, A2,…,An) ∨ ᖰAᖳ1 F(0, A2,…,An)

F(a,b,c) = ab ∨ ᖰbᖳc
Разложим по аргументу а:
F(a,b,c) = a( 1b ∨ ᖰbᖳc ) ∨ ᖰaᖳ( 0b ∨ ᖰbᖳc ) = ab ∨ aᖰbᖳc ∨ ᖰaᖳ ᖰbᖳ c
В первом «слагаемом» все еще отсутствует переменная c, поэтому разложим по c:
F(a,b,c) = ab ∨ aᖰbᖳc ∨ ᖰaᖳ ᖰbᖳ c = c(ab ∨ aᖰbᖳ1∨ ᖰaᖳ ᖰbᖳ1) ∨ ᖰсᖳ(ab ∨ aᖰbᖳ0 ∨ ᖰaᖳ ᖰbᖳ0) = abc ∨ aᖰbᖳc ∨ ᖰaᖳ ᖰbᖳ c ∨ abᖰсᖳ
Если таблицы истинности для исходной формулы и получившейся СДНФ совпадают, значит разложение выполнено верно.

Рассмотрим еще одну функцию от трех аргументов. Запишем ее СДНФ:

F(a,b,c) = aᖰbᖳ ᖰcᖳ ∨ aᖰbᖳc ∨ abᖰcᖳ ∨ abc

Если внимательно посмотреть на таблицу, то можно заметить, что функция принимает значение 1 на тех же наборах, на которых a = 1. Переменные b и с являются фиктивными, от них не зависит результат.

F(a,b,c) = a

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

Если формула записана в виде дизъюнкции конъюнкций ( «произведения сумм», ДНФ ) или конъюнкции дизъюнкций («суммы произведений», КНФ), то говорят, что функция представлена в нормальной форме . Кроме нормальных форм, выделяют формы высших порядков, например:

F(a,b,c) = ( a ∨ c ) ( a ∨ bc )

Хотя формула содержит "произведение сумм", но второй сомножитель представлен дизъюнкцией аргумента a и конъюнкцией аргументов b и c, поэтому такая форма не называется нормальной. Порядок функции характеризуется разнообразием использования операций, например:
F = a ( нулевой порядок )
F = a + ᖰbᖳ +с ( первый порядок )
F = a + ᖰaᖳ ᖰbᖳ ( второй порядок )
F = a + ᖰaᖳ (a ∨ с)( третий порядок )
F = a + ᖰaᖳ (a ∨ bс)( четвертый порядок ) и т.д...

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