Булева алгебра — это… Что такое Булева алгебра?

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

Булевой алгеброй^[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

В нотации · + ¯  

Первые три аксиомы означают, что (A, , ) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

Некоторые свойства

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a

любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

См. также Алгебра логики

Примеры

• Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:

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

• Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.

• Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.

• Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
  A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R },
  тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.

Принцип двойственности

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

Представления булевых алгебр

Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.

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

Аксиоматизация

В 1933 г. американский математик Хантингтон предложил следующую аксиоматизацию для булевых алгебр:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности : (x + y) + z = x + (y + z).
3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
3. Уравнение Роббинса: n(n(x + y’) + n(x + n(y))) = x.

Этот вопрос оставался открытым с 30-х годов и был любимым вопросом Тарского и его учеников.

В 1996 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

Примечания

Литература

Булева алгебра (структура) — Вікіпедія

Матеріал з Вікіпедії — вільної енциклопедії.

Булева алгебра утворена

підмножинами множини {x,y,z}

Бу́лева а́лгебра — це алгебраїчна структура, що є доповненою дистрибутивною ґраткою, та частина математики яка вивчає подібні структури.

Алгебра логіки — застосування алгебраїчних методів і символіки для вивчення логічних відношень і розв’язання логічних задач.

Формальне визначення[ред. | ред. код]

Булева алгебра — алгебраїчна структура з двома бінарними операціями:

• ∧{\displaystyle \land } («meet», «булеве множення») — узагальнення кон’юнкції,
• ∨{\displaystyle \lor } («join», «булеве додавання») — узагальнення диз’юнкції,

та унарною операцією:

• ¬a{\displaystyle \lnot a} чи  a¯{\displaystyle \ {\bar {a}}\;}(«булеве доповнення») — узагальнення заперечення;

що задовільняють такі аксіоми:

a∨b=b∨a,{\displaystyle a\lor b=b\lor a,}	a∧b=b∧a{\displaystyle a\land b=b\land a}	(комутативність)
a∨(b∨c)=(a∨b)∨c,{\displaystyle a\lor (b\lor c)=(a\lor b)\lor c,}	a∧(b∧c)=(a∧b)∧c{\displaystyle a\land (b\land c)=(a\land b)\land c}	(асоціативність)
(a∨b)∧b=b,{\displaystyle (a\lor b)\land b=b,}	(a∧b)∨b=b{\displaystyle (a\land b)\lor b=b}	(закон поглинання)
a∨(b∧c)=(a∨b)∧(a∨c),{\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c),}	a∧(b∨c)=(a∧b)∨(a∧c){\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}	(дистрибутивність)
(a∨a¯)∧b=b,{\displaystyle (a\lor {\bar {a}})\land b=b,}	(a∧a¯)∨b=b{\displaystyle (a\land {\bar {a}})\lor b=b}	(доповнення)

Аксіоми 1,2,3 визначають ґратку.

Аксіоми 1,2,3,4 визначають дистрибутивну ґратку.

Аксіоми 1,2,3,5 визначають доповнену ґратку.

З аксіом випливають такі теореми:

a∨a=a,{\displaystyle a\lor a=a,}	a∧a=a{\displaystyle a\land a=a}	(ідемпотентність)
a∨a¯=b∨b¯,{\displaystyle a\lor {\bar {a}}=b\lor {\bar {b}},}	a∧a¯=b∧b¯{\displaystyle a\land {\bar {a}}=b\land {\bar {b}}}

Тобто вирази a∨a¯{\displaystyle a\lor {\bar {a}}} та a∧a¯{\displaystyle a\land {\bar {a}}} не залежать від вибору елемента.

Елемент a∨a¯{\displaystyle a\lor {\bar {a}}} називається булевою одиницею 1, елемент a∧a¯{\displaystyle a\land {\bar {a}}} називається булевим нулем 0.

Над множиною A також визначене бінарне відношення ≤, яке має назву відношення нестрогого порядку та відповідає умовам:

1. x≤x (рефлективність)
2. якщо x≤y та y≤x, то x=y (антисиметричність)
3. якщо x≤y та y≤z, то x≤z (транзитивність)

Замість x≤y можна писати у≥x. Множина з таким відношенням має назву впорядкованої.

Нехай S — підмножина елементів впорядкованої множини A. Елемент a’ має назву верхньої (нижньої) границі S, якщо для будь-якого а з S справедливе a ≤ a’ (a ≥ a’). Якщо множина усіх верхніх (нижніх_ границь множини S містить найменший (найбільший) елемент, то він має назву точної верхньої (точної нижньої) границі і позначається sup S(inf S). Якщо для будь-яких a, b з множини A існують inf (a, b) та sup (a, b), то така множина називається структурою або решіткою. Точна верхня границя такої множини є a∧b{\displaystyle a\land b}, точна нижня границя є a∨b{\displaystyle a\lor b}.

Зв’язок з булевим кільцем[ред. | ред. код]

Кожна булева алгебра еквівалентна булевому кільцю і навпаки:

Операції булевого кільця:

a+b=(a∧¬b)∨(b∧¬a){\displaystyle a+b=(a\land {\neg }b)\lor (b\land {\neg }a)}

ab=a∧b{\displaystyle ab=a\land b}

Кожна скінченна булева алгебра ізоморфна алгебрі всіх підмножин скінченної множини (полю множин). Тому число елементів булевої алгебри завжди є ступенем 2.

В 1933 американський математик Едвард Хантінгтон запропонував наступну аксіоматизацію для булевих алгебр:

• комутативність: a∨b=b∨a{\displaystyle a\lor b=b\lor a}
• асоціативність: a∨(b∨c)=(a∨b)∨c{\displaystyle a\lor \left(b\lor c\right)=\left(a\lor b\right)\lor c}
• аксіома Хантінгтона: ¬(¬a∨b)∨¬(¬a∨¬b)=a.{\displaystyle \neg \left(\neg a\lor b\right)\lor \neg \left(\neg a\lor \neg b\right)=a.}

Герберт Робінс задав питання: чи можна скоротити третю аксіому так, як подано нижче

• аксіома Робінса: ¬(¬(a∨b)∨¬(a∨¬b))=a.{\displaystyle \neg \left(\neg \left(a\lor b\right)\lor \neg \left(a\lor \neg b\right)\right)=a.}

Алгебра логіки та алгебра множин є загально-відомими прикладами булевої алгебри.

Алгебра логіки (двійкова алгебра)[ред. | ред. код]

Найважливішим прикладом булевої алгебри є булева алгебра з двома елементами — одиничний елемент 1 та нульовий елемент 0. Ця алгебра є фундаментом функціонування цифрових дискретних систем. Операція ∨{\displaystyle \lor } в такій алгебрі має назву «логічного АБО» (logical OR), операція ∧{\displaystyle \land } — «логічного І» (logical AND), а елементам 1 та 0 ставляться у відповідність твердження «істина» (true) та «неправда» (false). Результати цих двох операцій можуть бути зведені в такі таблиці:

∨{\displaystyle \lor } 0 1 0 0 1 1 1 1

∧{\displaystyle \land } 0 1 0 0 0 1 0 1

Така двійкова алгебра відіграє ключову роль в описі цифрових схем (насамперед це стосується цифрових схем без зворотних зв’язків).

алгебра буля — это… Что такое алгебра буля?

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

Буль представляет логику как алгебру классов (будем обозначать их символами А, В, С,…). Основными операциями в А. Б. являются: сложение классов AE.B; умножение классов АCВ; дополнение класса А\’. Свойства этих операций описываются следующими аксиомами:

la. AE(BEC)=(AEB) EC — ассоциативность сложения;

16. AC(BCC)= (ACВ) EC — ассоциативность умножения;

2a.AEB= BEA — коммуникативность сложения;

2б.АCВ =ВCА — коммуникативность умножения;

3a.AE(ВCС)= =(AEB) C(AEC) — дистрибутивность сложения относительно умножения;

36.AC(BEC)==(ACB) E(ACC) — дистрибутивность умножения относительно сложения.

В А. Б. существуют два элемента 0 и 1, операции с которыми

подчиняются следующим соотношениям:

AE0=A;

AC1=A;

AEA\’=1;

ACA\’=0.

Характерная особенность А.Б. заключается в том, что в ней отсутствуют коэффициенты и показатели степеней. Сумма двух А

равна А: АEА=А, а не 2А, как в обычной алгебре. Точно так же и произведение двух A равно A: АCА=А, а не A2.

Важным законом А. Б. является принцип двойственности, согласно которому если в некотором справедливом равенстве мы заменим все вхождения E на C и C на E, 1 на 0 и 0 на 1, то получим равенство, двойственное первому и также справедливое. Примерами двойственных равенств являются приведенные выше аксиомы.

А.Б. широко применяется при проектировании и проверке электрических схем, в которых используются реле, работающие по принципу «да — нет», при программировании и проектировании ЭВМ, в операциях с переключателями, сигналами, схемами. В современной математической логике этот раздел значительно усовершенствован и разрабатывается как теория булевых алгебр, в том числе как алгебра множеств, алгебра высказываний и т. п. В области традиционной логики соотношения А. Б. часто используются для иллюстрации и прояснения отношений между объемами понятий.

Словарь по логике. — М.: Туманит, изд. центр ВЛАДОС. А.А.Ивин, А.Л.Никифоров. 1997.

Алгебра Буля Википедия

a∨(b∨c)=(a∨b)∨c{\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}	a∧(b∧c)=(a∧b)∧c{\displaystyle a\land (b\land c)=(a\land b)\land c}	ассоциативность
a∨b=b∨a{\displaystyle a\lor b=b\lor a}	a∧b=b∧a{\displaystyle a\land b=b\land a}	коммутативность
a∨(a∧b)=a{\displaystyle a\lor (a\land b)=a}	a∧(a∨b)=a{\displaystyle a\land (a\lor b)=a}	законы поглощения
a∨(b∧c)=(a∨b)∧(a∨c){\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}	a∧(b∨c)=(a∧b)∨(a∧c){\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}	дистрибутивность
a∨¬a=1{\displaystyle a\lor \lnot a=1}	a∧¬a=0{\displaystyle a\land \lnot a=0}

Алгебра Буля Википедия

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

Булевой алгеброй^[1][2][3] называется непустое множество A с двумя бинарными операциями ∧{\displaystyle \land } (аналог конъюнкции), ∨{\displaystyle \lor } (аналог дизъюнкции), одной унарной операцией ¬{\displaystyle \lnot } (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:

В нотации · + ¯

a+(b+c)=(a+b)+ca(bc)=(ab)ca+b=b+aab=baa+ab=aa(a+b)=aa+bc=(a+b)(a+c)a(b+c)=ab+aca+a¯=1aa¯=0{\displaystyle {\begin{aligned}&a+(b+c)=(a+b)+c&a(bc)=(ab)c\\&a+b=b+a&ab=ba\\&a+ab=a&a(a+b)=a\\&a+bc=(a+b)(a+c)&a(b+c)=ab+ac\\&a+{\bar {a}}=1&a{\bar {a}}=0\end{aligned}}}

Первые три аксиомы означают, что (A, ∧{\displaystyle \land }, ∨{\displaystyle \lor }) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля.

Некоторые свойства

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

Примеры

• Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:

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

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

Представления булевых алгебр

Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.

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

Аксиоматизация

В 1933 году американский математик Хантингтон^[en] предложил следующую аксиоматизацию для булевых алгебр:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
3. Уравнение Роббинса: n(n(x + y) + n(x + n(y))) = x.

Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.

В 1996 году Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

Примечания

Литература

2.8.1. Законы алгебры Буля

СДНФ = a b c + a b c + a b c +a b c ;

СКНФ = (a + b + c) (a + b + c) ( a + b + c) ( a + b + c) .

2.8.Минимизация булевых функций. Метод Квайна – МакКласки

В математической логике определяется специальная алгебра, алгебра Буля, содержащая операции логического умножения, логического сложения и отрицания { ,+, — }, которые позволяет производить тождественные преобразования логических выражений. К этим законам относятся

Закон идемпотентности (одинаковости):

a + a = a,	a a = a.
Закон коммутативности:
a + b = b + a,	a b = b a.

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

a + (b + c) = (a + b) + c, a (b c) = (a b) c.

Законы дистрибутивности:

-дистрибутивность конъюнкции относительно дизъюнкции:

а(b + c) = a b + a c.

-дистрибутивность дизъюнкции относительно конъюнкции:

а + b c = (a + b) (a + c).

Закон двойного отрицания:

a = a .

Законы де Моргана:

a + b = a b , a b = a + b .

Законы поглощения:

a + a b = a, a (a + b) = a.

Законы, определяющие действия с логическими константами 0 и 1:

67

a + 0 = a	a + 1 = 1
a 0 = 0	a 1 = a
0 = 1					+ a =1
		a
1 = 0
		a a = 0

Правомерность всех рассмотренных выше законов может быть легко доказана, например, с использованием таблиц истинности.

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

Закон склеивания:

1)a b + a b = b .

Доказательство этого тождества проводится с использованием первого закона дистрибутивности:

a b+ a b =b (a+a) = b 1 = b .

2)(a + b) ( a + b) = b .

Доказательство этого тождества проводится с использованием второго закона дистрибутивности:

(a + b) ( a + b) = a a + b = b .

Закон Блейка–Порецкого:

a + a b = a + b , a + a b = a + b .

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

a+ a b = a 1 + a b = a (b + b) + a b =

= a b + a b + a b = a b + a b + a b + a b = a+b.

Закон свертки логического выражения:

a b+a c+ b c = a b+ a c .

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

a b+ a c + b c =

= a b (c + c) + a c (b + b) + b c (a + a) =

=a b c + a b c + a b c + a b c + a b c + a b c =

=(a b c + a b c )+( a b c + a b с) + (a b с+ a b c) =

=a b + a c + a c = a b + a c.

2.8.2. Упрощение логических функций

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

Задача 2.11. Упростить СДНФ функции (a b) c.

Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c + a b c + a b c + a b c = b c + b c +a b c =

= c +a b c = c +a b.

Задача 2.12. Упростить СДНФ функции (a↓ b) ↓ c.

Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c + a b c = b c + a c .

Задача 2.13. Упростить СДНФ функции (a b) c .

Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c .

Дальнейшее упрощение невозможно.

Задача 2.14. Упростить СДНФ функции (a →b) →c .

Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c + a b c + a b c + a b c + a b c =

= a c + a = a +c.

Задача 2.15. Упростить СДНФ функции a b + a b .

Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c + a b c +a b c = a b + a b .

2.8.3. Метод Квайна – МакКласки

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

1.Представить наборы (конституенты), на которых функция истинна, в виде двоичных эквивалентов;

2.Упорядочить двоичные эквиваленты по ярусам (по числу единиц двоечных эквивалентов) и провести склейку (применить правило склеивания к соответствующим конституентам) наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; пометить каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001-

и101-, и т.д.

3.Построить таблицу Квайна, столбцы которой соответствуют двоичным наборам истинности функции, а строки – максимальным интервалам. Если i-й набор покрывается j-м интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего;

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

Рассмотрим функцию F1, которая истинна на наборах {1, 3, 5, 7, 11, 13, 15}. Совершенная дизъюнктивная нормальная форма данной функции равна:

СДНФ = x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4 + +x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4 .

Двоичные эквиваленты истинных наборов:

1	0001
3	0011
5	0101
7	0111
11	1011
13	1101
15	1111

Упорядочим двоичные наборы по ярусам и проведем склейки, до тех пор, пока это возможно (табл. 2.7).

Таблица 2.7

		Склеивание элементов
0001	√ √		00-1 √		0—1
0011	√ √		0-01 √		—11
0101	√ √		-011 √		-1-1
0111	√ √ √		0-11 √ √
1101	√ √		-101 √
1011	√ √	01-1		√ √
1111	√ √ √	11-1		√
		-111		√ √
		1-11		√

Затем строим таблицу Квайна (табл. 2.8), в которой наборы 0001, 1101 и 1011 покрываются единственно возможным образом, следовательно, покрывающие их минимальные интервалы называются обязательными и образуют ядро покрытия, так как должны входить в любое покрытие.

В табл. 2.8 соответствующие единицы подчеркнуты, интервалы {0- -1,- -11, -1-1} образуют не только ядро покрытие, но и покрывают всю таблицу Квайна.

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

МДНФ = {0 — — 1, — — 1 1, -1-1} = x1 x4 + x3 x4 + x2 x4.

Таблица 2.8

			Таблица Квайна
	0001
		0011	0101	0111		1011	1101	1111
0—1	1	1	1	1
—11		1		1		1		1
-1-1			1	1			1	1

Задача 2.16. Найти МДНФ функции

f1 = ( x1 x2 ) (x1 x3 ) x4 .

Решение. Построим таблицу истинности для f1.

x x x x			4	(	x		x	) (x	x	) x	4
1	2	3		1		2		1	3
0 0 0 0				0
0 0 0 1				1
0 0 1 0				1
0 0 1 1				1
0 1 0 0				1
0 1 0 1				0
0 1 1 0				0
0 1 1 1				1
1 0 0 0				0
1 0 0 1				1
1 0 1 0				1
1 0 1 1				1
1 1 0 0				0
1 1 0 1				1
1 1 1 0				0
1 1 1 1				1

Совершенная ДНФ исследуемой функции имеет вид:

СДНФ = x1 x2 x3 x4 + x1 x2 x3 x 4 + x1 x2 x3 x4 + +x1 x2 x3 x4 + x1 x 2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4 +

+x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4 .

Упорядочим двоичные наборы по ярусам и проведем склейку

(табл. 2.9).

Таблица 2.9

	Склейка для задачи 2.16
0001	√√	00-1 √		-0-1
0010	√√	-001 √		-01-
0100		001- √		—11
0011	√√√√	-010 √		1—1
1010	√√	0-11 √
1001 √√√		-011 √√√
0111 √√		101- √
1011	√√√√	10-1 √√
1101	√√	1-01	√
1111 √√√		-111	√
		1-11 √√
		11-1	√

В первом столбике присутствует набор, который не участвовал ни в одной склейке – он сам является максимальным интервалом 0100. В третьем столбике к нему добавляется еще четыре макси-

мальных интервала: {-0-1, -01-, —11, 1—1}.

Строим таблицу Квайна (табл. 2.10).

Таблица 2.10

Таблица Квайна для задачи 2.16

	0001	0010	0100	0011	1010	1001	0111	1011	1101	1111
0100			1
-0-1	1					1		1	1
-01-		1		1	1			1
—11				1			1	1		1
1—1						1		1	1	1

Определим ядро покрытия, в которое войдут обязательные интервалы: {0100, -0-1, -01-, —11}. В данном случае, ядро покрытия покрывает и всю таблицу в целом.

Минимальная дизъюнктивная нормальная форма f1 имеет вид:

МДНФ = x1 x2 x3 x4 + x2 x4 + x2 x3 + x3 x4.

Задача 2.17. Найти МДНФ функции f2(x1 x2 x3), которая принимает единичные значения на наборах 0,2,3,6 и 7.

Решение. Построим таблицу истинности для f2.

						x1 x2 x3							f2
						0 0 0						1
						0 0 1						0
						0 1 0						1
						0 1 1						1
						1 0 0						0
						1 0 1						0
						1 1 0						1
						1 1 1						1
СДНФ =						+		x2		+			x2 x3 + x1 x2			+ x1 x2 x3 .
	x1		x2		x3		x1		x3			x1			x3

Упорядочим двоичные наборы по ярусам и проведем склейку

(табл. 2.11).

Таблица 2.11

Склейка для задачи 2.17

000	√√	0-0 √		—0
010	√√	-00	√
100	√√	-10	√
110	√√√	1-0	√
111	√	11-

В результате склейки у нас получилось всего два максимальных интервала: {11-, —0}. Без построения таблицы Квайна очевидно, что они образуют минимальное покрытие, так как удаление любого из этих интервалов приведет к потери наборов, на которых функция f2(x1 x2 x3) истинна. МДНФ = x1 x2 + x3.

2.9.Функционально полные системы логических функций

Рассмотрим понятия полноты, или функциональной полноты, для системы логических функций.

Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций.

	Адрес этой страницы (вложенность) в справочнике dpva.ru:  главная страница  / / Техническая информация / / Математический справочник / / Математическая логика. Булева алгебра = алгебра логики.  / / Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций. Поделиться:    Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций. *Бабичева, Болдовская, Справочник по математике. СибАДИ, 2010. (классная книга) Законы Булевой алгебры. Законы Булевой алгебры. Поглощение A + (A*B) = A A*(A + B) = A Аннулирование A + 1 = 1 A*0 = 0 Ассоциативность (объединение) (A + B) + C = A + (B + C) (A*B)*C=A*(B*C) Коммутативность (перестановка) A + B = B + A A*B=B*A Дополнение A + ¬A = 1 A*¬A = 0 Правило Де Моргана ¬(A + B) = ¬A*¬B ¬(A*B) = ¬A + ¬B Дистрибутивность A*(B + C) = (A*B) + (A*C) A + (B*C) = (A + B)*(A + C) Двойное отрицание ¬¬A=A Тождественность A + 0 = A A*1 = A Тавтология A*A = A A + A = A Поиск в инженерном справочнике DPVA. Введите свой запрос: