Элементарные функции алгебры логики

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

Теорема 2. Число всех функций алгебры логики, существенно зависящих от п аргументов, определяется следующим рекуррентным соотношением:

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

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

Рассмотрение множества элементарных функций алгебры логики начнем со случая п = 0. В силу теоремы 1 в этом случае имеются только две функции, совпадающие с константами 0 и 1: f₁ = 0, f₁ = 1. Обе эти функции мы будем считать элементарными.

Для п = 1, согласно теореме 1, имеем 2 2 = 4 различные функции, представленные в таблице 4.6.

В этом случае только функции f₃ и f₄ существенно зависят от х₁, а для функций f₁ и f₂ этот единственный аргумент является фиктивным. Эти две функции определяются таблицей 4.7.

Таблица 4.6 – Логические функции
одного аргумента

x1

f1

f2

f3

f4

Таблица 4.7 – Логические функции
повторения и отрицания

x1

f3

f4

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

f₄ = (читается “не x”).

Найдем число функций алгебры логики, существенно зависящих от двух и трех переменных. Из примера (таблица 4.6) вытекает, что А= 2 и А₁ = 2. Применяя теорему 2, имеем:

,

.

В случае п = 2 в силу теоремы 2 имеем десять различных функций, существенно зависящих от аргументов х₁ и х₂. Из этих десяти функций к элементарным функциям будем относить следующие семь функций, представленных в таблице 4.8.

Таблица 4.8 – Элементарные логические функции двух переменных

x1

x2

f5

f6

f7

f8

f9

f10

f11

Функция f₅, определяемая этой таблицей, носит название дизъюнкции х₁ и х₂ или логического сложения х₁ и х₂. Для ее обозначения применяются следующие символы:

Мы на протяжении всего дальнейшего изложения будем называть функцию f₅дизъюнкцией и обозначать дизъюнкцию х₁ и х₂ при помощи символа "+".

Функция f₆ носит название конъюнкции или логического умножения х₁ и х₂. Для ее обозначения применяется символ "&":

Вместо этого символа часто применяют точку или вообще опускают всякий знак между х₁ и х₂, т. е.

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

Функция f₇ носит название функции эквивалентности или функции равнозначности. Для ее обозначения применяется следующая запись:

В дальнейшем будем называть эту функцию эквивалентностью х₁ и х₂. Для ее обозначения будем употреблять первый из двух вышеприведенных символов.

Функция f₈ носит название импликации х₁ в х₂. Она обозначается следующим образом:

Функция f₉ носит название функции Вебба и обозначается следующим образом:

Функция f₁₀ называется функцией Шеффера и обозначается следующим образом:

Функция f₁₁ обычно называется функцией сложения по модулю два (реже ее называют функцией разноименности). Для ее обозначения употребляются символы:

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

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

– распределительный закон конъюнкции относительно дизъюнкции:

Кроме того, имеет место распределительный закон дизъюнкции относительно конъюнкции:

который не имеет места в обычной алгебре, так как если бы он существовал, то он бы имел следующий вид:

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

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

Таблица 4.9 – Сравнение логических функций

x1

x2

x3

x2 & x3

x1 + (x2 & x3)

x1

x2

x3

x1 + x2

x1 + x3

(x1 + x2) & (x1 + x3)

Рассмотрим теперь ряд простых, но весьма важных соотношений:

	(4.10)
	(4.11)
	(4.12)
	(4.13)

Из (4.10) как следствие получаем:

Как обобщение вышеприведенных формул получаем следующие формулы, обычно называемые формулами де Моргана:

	(4.14)
	(4.15)

Рассмотренные 11 функций позволяют строить новые функции алгебры логики двумя основными путями:

1) путем перенумерации аргументов;

2) путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f₁, f₂, …, f_k и путем применения (возможно многократного) этих двух правил, будем называть суперпозицией функций f₁, f₂, …, f_k._.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10638 – | 8011 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

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

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

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

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

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

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

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;

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

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

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

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) – двойственные функции, то

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

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

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

Функция сложения по модулю 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 и наоборот:

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

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 функции

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

Теперь рассмотрим пример простой таблицы истинности элементарных функций 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)

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

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

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

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

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.

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

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

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).

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

Например: 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наборов аргументов выделяется такое же количество строк. После этого, начиная с нулевого набора, каждый набор вписывается в таблицу и для него вычисляется значение функции, которое также заносится в таблицу.

Последнее изменение этой страницы: 2016-06-23; Нарушение авторского права страницы

Существует несколько синонимов по отношению к функциям алгебры логики:

• 1. функции алгебры логики (ФАЛ);
• 2. переключательные функции;
• 3. булевские функции;
• 4. двоичные функции.

По мере необходимости будем пользоваться всеми этими синонимами.

Рассмотрим некоторый набор аргументов:

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

Чему равно число различных наборов?

Поставим каждому набору в соответствие некоторое двоичное число:

• 0, 0. 0 нулевой набор
• 0, 0. 1 первый набор
• 0, 0. 1,0 второй набор
• 1, 1. 1 (2 n -1)-ый набор

Очевидно, что количество различных X₁,X₂. X_n n-разрядных чисел в позиционной двоичной системе есть 2 n .

Допустим, что некоторая функция F(X₁,X₂. X_n) задана на этих наборах и на каждом из них она принимает либо ‘0’-ое, либо ‘1’-ое значение.

Такую функцию называют функцией алгебры логики или переключательной функцией.

Чему равно число различных переключательных функций ‘n’ аргументов?

Т.к. функция на каждом наборе может принять значение ‘0’ или ‘1’, а всего различных наборов 2 n , то общее число различных функций ‘n’ аргументов есть: 2 2n .

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