Свойства элементарных функций алгебры логики

 

Рассмотрим основные законы, аксиомы и теоремы алгебры логики

Некоторые законы обычной алгебры применимы и к алгебре логики. Например:

Закон коммутативности:

для умножения

АВ = ВА;

для сложения

A + B = B + A.

 

Закон ассоциативности:

для умножения

A(BC) = (AB)С,

для сложения

A + (B + С) = (A + B) + С.

 

Закон дистрибутивности умножения по отношению к сложению:

 

A(B + С) = AB + AC.

 

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

 

A +BС = (A + B)(A + С)

 

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

 

а) б)

1) A = 1, если A 0; A = 0, если A 1;

2) Если A = 0, тоA = 1 Если A = 1, тоA = 0

3) 0 + 0 = 0; 0 0 = 0;

4) 0 + 1 = 1 1 0 = 0;

5) 1 + 1 = 1 1 1 = 1;

6)0 = 1 1 = 0;

7) A + 0 = A A 1 = A;

8) A + 1 = 1 A 0 = 0;

9) A + A = A A A = A;

10) A = A;

11) A +A = 1 AA= 0;

12) A + B + C =ABC ABC =A + B + C

(теорема де Моргана);

13) A(A + B) = A A + AB = A

(закон поглощения).

14) A +AB = A + B A(A + B) = AB

 

В алгебре логики широко используется также специфический закон склеивания:

 

15) AB +AB = B(A +A) = B (A + B)(A +B) = A

 

Аксиомы и теоремы, записанные слева, называются двойственными аксиомам и теоремам, записанным справа.

Двойственность определяется как изменение всех знаков операции И на знаки операции ИЛИ, всех знаков операции ИЛИ на знаки операции И, всех нулей на единицы и всех единиц на нули.

Двойственность является одним из основных свойств алгебры логики и означает, что если f(A, B, C) и f(A, B, C) - двойственные функции, то

 

f(A, B, C) = f(A,B,C).

 

Законы де Моргана являются одной из иллюстраций свойства двойс-твенности и, как уже отмечалось, могут быть сформулированы в виде:

 

ABC =A +B +C

 

A + B + C =ABC,

 

Из законов де Моргана вытекают следствия:

 

ABC = A +B +C

 

A + B + C = ABC.

 

Следовательно, появляется возможность выражать конъюнкцию через дизъюнкцию и отрицание, или дизъюнкцию - через конъюнкцию и отрицание. Законы де Моргана и следствия из них справедливы для любого количества переменных.

Функция сложения по модулю 2 представляется следующим образом:

 

A B = AB +AB = (A + B)(A +B)

 

Для этой функции справедливы следующие аксиомы:

 

A A = 0; A A A = A; A A = 1; A 1 =A; A 0 = A

 

На основании рассмотренных аксиом и свойств элементарных логических функций можно, например, вывести правила представления функций И, ИЛИ, НЕ через функцию сложения по модулЮ 2 и наоборот:

 

F = A 1;

A + B = A B AB

F D = (A B) (A + B)

 

Для функции Шеффера, которая может быть выражена соотношением

x1/x2 = x1x2

Характерны аксиомы:

x/x =x+ x/x = 1+ x/0 = 1+

x/1 =x+ x/0 = 1+ x/1 = x.

 

Функции И, ИЛИ, НЕ через функцию Шеффера выражаются так:

 

x1x2 = x1/x2 = x1/x2/x1/x2; x = x/x;

x1 + x2 = x1x2 =x1/x2 = x1/x1/x2/x2.

 

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

 

x1 x2 = x1 + x2 =x1x2

 

Для этой функции справедливы аксиомы:

 

x x =x; x 0 =x; x x = 0; x 1 = 0.

 

Функции И, ИЛИ, НЕ выражаются через функцию Пирса (Вебба) следующим образом:

 

x1x2 = (x1 x1) (x2 x2); x1 + x2 = (x1 x2) (x1 x2); x = x x.

 

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

 

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

 

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

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

Табличный способ. Для представления логической функции можно использовать, так называемый, табличный способ когда функция представляется своей таблицей истинности. Приведем пример такой таблицы для некоторой логической функции трех аргументов f(x1, x2, x3):

 

 

Т а б л и ц а 7.3.

 

№ Набор Значение

набора x1 x2 x3 функции

0 0 0 0 1

1 0 0 1 0

2 0 1 0 0

3 0 1 1 1

4 1 0 0 1

5 1 0 1 0

6 1 1 0 1

7 1 1 1 0

 

Обычно в таблице истинности столбец с номером набора не приводится.

Теперь рассмотрим пример простой таблицы истинности элементарных функций AND - f1(A,B), OR - f7(A,B), XOR - f6(A,B) (из Таблицы 7.2):

 

Т а б л и ц а 7.4.

A B f1(A,B) f7(F=D) f6(F=D)

0 0 0 0 0

0 1 0 1 1

1 0 0 1 1

1 1 1 1 0

 

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

Переменные и их инверсии часто называют литералами.

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

Дизъюнктивный терм (макстерм) - это логическая функция, связывающая все переменные в прямой или инверсной форме, т.е. литералы, знаком дизъюнкции.

Например:

H1 = A +B + C +D; H2 = A B.

 

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

Конъюнктивный терм (минтерм) - это логическая функция, связывающая переменные в прямой или инверсной форме, т.е. литералы, знаком конъюнкци.

Например:

F1 =A & B &C & D; F2 = A B C.

 

Минтерм называют также конституентой единицы, т.к. эта функция равна 1 только тогда, когда все ее аргументы одновременно равны единице.

Ранг терма - r, определяется количеством литерал, входящих в данный терм.

Например, для минтерма F =ABCDE r = 5, а для макстерма H ==A + B + C r = 3.

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

 

f(x1, x2,..., xn) = F1 F2... Fn = Fi = Fi, (7.1)

 

где i - номера наборов, на которых функция равна 1, - знак дизъюнкции, объединяющий все минтермы Fi.

Пример: записать в аналитическом виде функцию, заданную таблично:

 

x1 x2 x3 f(x1, x2, x3) x1 x2 x3 f(x1, x2, x3)

0 0 0 1 1 0 0 1

0 0 1 0 1 0 1 0

0 1 0 0 1 1 0 0

0 1 1 1 1 1 1 0

 

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

Р е ш е н и е: Согласно (7.1)

 

f(x1, x2, x3) = F1(0, 0, 0) + F2(0, 1, 1) + F3(1, 0, 0) =x1x2x3 +x1x2x3 + x1x2x3.

 

Ответ:f(x1, x2, x3) =x1x2x3 +x1x2x3 + x1x2x3.

F1 F2 F3

 

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

Например, в случае предыдущей функции имеем:

 

f(x1, x2, x3) = f1(0, 0, 1) + f2(0, 1, 0) + f3(1, 0, 1) + f4(1, 1, 0) + f5(1, 1, 1).

 

Любая таблично заданная ФАЛ может быть задана аналитически в виде конъюнкции конечного числа макстермов, на каждом из которых функция равна нулю:

 

f(x1, x2,..., xn) = H1 H2 \\\ Hn = Hi = Hi.

 

Например, используя правила двойственности, результат предыдущего решения можно представить в следующем виде:

 

f(x1, x2, x3) = (x1 + x2 +x3)&(x1 +x2 + x3)&(x1 + x2 +x3)&(x1 +x2 + x3) &(x1 +x2 +x3).

H1 H2 H3 H4 H5

 

Нормальная дизъюнктивная форма (НДФ) это дизъюнктивное объединение минтермов различных рангов, включая ранг равный единице.

Например: f(x1,x2,x3) = x3 +x1x2 + x2x3 +x1x2x3.

Нормальная конъюнктивная форма (НКФ) это конъюнктивное объединение макстермов, включающее в себя макстермы различных рангов.

Например: f(x1,x2,x3) = (x1 +x2)(x2 + x3)(x1 +x2 + x3).

Каждая логическая функция в общем случае может иметь несколько НДФ или НКФ.

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

xy xy z yx содержит семь букв или литерал, но три переменные: x, y, z.

Минимальная форма представления ФАЛ это такая форма, которая содержит минимальное количество термов, которые имеют минимальные ранги.

Ранее мы рассмотрели процедуру формирования аналитической формы ФАЛ по ее таблице истинности. Теперь рассмотрим обратную процедуру: построение таблицы истинности по логическому выражению.

Если в логическом выражении n аргументов, то для них в таблице предусматривается n колонок и одна колонка для значений функции. Для 2nнаборов аргументов выделяется такое же количество строк. После этого, начиная с нулевого набора, каждый набор вписывается в таблицу и для него вычисляется значение функции, которое также заносится в таблицу.