Электроника:Цифровая электроника/Карты Карно/Булевы соотношения на диаграммах Венна

Содержание

Теория

Практика

Проверка знаний

Рецепты

Эксперименты

Резерв

Резерв

Резерв

Резерв

Перевод: Макаров В. (valemak)

Проверка/Оформление/Редактирование: Мякишев Е.А.

Булевы соотношения на диаграммах Венна

Итак, в прошлой лекции нас особо заинтересовал четвёртый пример, где A частично пересекается с B. Тем не менее, сначала рассмотрим всю заштрихованную область (рисунок 1 ниже, правая диаграмма) и только затем перекрывающуюся область (рисунок 1 ниже, левая диаграмма). Давайте назначим некоторые логические выражения для вышеперечисленных областей, как показано ниже.

Итак, на левой диаграмме Венна слева видим красную горизонтально заштрихованную область для множества A. Множеству B соответствует синяя вертикально заштрихованная область.

Рис. 1. Диаграмма Венна, где множества A и B частично перекрываются.

Если брать совокупную площадь обоих множеств, независимо от стиля/цвета штриховки, то получаем то, что изображено справа на рисунке 1 выше, соответствует функции ИЛИ для выражений А и В. Если обозначить булевыми терминами, то это A + B.

Эта общая область отмечена штриховкой, с наклоном 45°. Всё, что находится за пределами заштрихованной области, соответствует НЕ-(A + B), как показано в правой части рисунка 1 выше. Перейдём к следующей части четвёртого примера.

Другой взгляд на диаграмму Венна с перекрывающимися кругами – посмотреть только на часть, общую и для A и для B, это область с двойной штриховкой в левой части рисунка 2 ниже. Логическим выражением именно для этой общей области, соответствующей функции И, является A × B или просто AB, как показано в правой части рисунка 2 ниже. Обратите внимание, что всё, кроме AB, отмеченного двойной штриховкой, является НЕ-AB, также обозначаемое как (AB)'.

Рис. 2. Диаграмма Венна, на которой выделено пересечение двух множеств (область с двойной штриховкой).

Обратите внимание, что некоторые из элементов A на рисунке 2 выше, являются элементами (AB)'. Некоторые из элементов B являются элементами (AB)'. При этом ни один из элементов (AB)' не находится внутри области AB с двойной штриховкой.

Рис. 3. Диаграммы Венна с двумя множествами, где одно множество является подмножеством другого. Так как подмножество по сути является пересечением обеих множеств, оно помечено двойной штриховкой.

Мы повторили второй случай (левая часть рисунка 3 выше) из прошлой лекции. Тот самый упомянутый пятый пример (правая часть рисунка 3 выше) приведена для сравнения (когда не множество A является подмножеством множества B, а наоборот – множество B является подмножеством множества A). Позже мы найдём случайный элемент или группу элементов, полностью содержащихся в другой группе на карте Карно.

Ну а сейчас, на рисунке 4 ниже, мы покажем, как составлять диаграммы Венна на основе логических выражений, включающих дополнения переменных.

Рис. 4. Составление диаграммы Венна для логического выражения, содержащего дополнение переменной.

Пример 1: Составим диаграмму Венна для A'B (НЕ-A И B).

Решение: Начнём с верхней левой части рисунка 4 выше, где изображена красная горизонтально заштрихованная область A' (НЕ-А). В правой верхней части синяя вертикально заштрихованная область – это множество B. Затем, в нижней левой части рисунка сформирована функция A'B (НЕ-А И B) – это пересечение обеих предыдущих областей (отмечено двойной красно-синей штриховкой). Большинство людей использовали бы эту часть (нижнюю левую) рисунка как ответ на приведённый пример.

Однако для лучшего понимания покажем только область A'B с двойной штриховкой. Выражение A'B – это область пересечения как A', так и B. Чистая область за пределами A'B это (A'B)' (НЕ-(НЕ-A И B)), которая не была частью поставленного примера.

Давайте попробуем нечто подобное с логической функцией ИЛИ.

Пример 2: Составим диаграмму Венна для B' + A (НЕ-B ИЛИ A).

Рис. 5. Составление диаграммы Венна для логического выражения, содержащего функцию ИЛИ.

Решение: В левой части рисунка 5 выше изображено множество B (круг с синей штриховкой). В средней части рисунка 5 выше изображено дополнение к B, т.е. B' (область с синей штриховкой за пределами круга). Наконец, в правой части рисунка 5 выше мы накладываем A (круг с синей штриховкой) поверх B' (область с красной штриховкой за пределами красного круга). Поскольку нам нужна функция ИЛИ, будем искать всю заштрихованную область независимо от стиля штриховки. Таким образом, A + B' – это всё, что заштриховано в правой части рисунка 5 выше. Для лучшего понимания этот ответ показан в виде единой заштрихованной области в левой части рисунка 6 ниже.

Рис. 6. Составление диаграммы Венна для логического выражения, содержащего дополнения.

Пример 3: Составим диаграмму Венна для (A + B')' (НЕ-(A ИЛИ НЕ-B)).

Решение: Зелёная заштрихованная под углом 45° область A + B' – результат предыдущего примера. Переходя к (A + B')', текущему примеру, найдём в левой части рисунка 6 выше дополнение к A + B' – это будет белая чистая область, соответствующая (A + B')'.

Обратите внимание, что мы повторили, в правой части рисунка 6 выше, результат с двойной штриховкой A'B из предыдущего примера 1 для сравнения с нашим результатом примера 3. Области, соответствующие как (A + B')' из примера 3 так и AB' из примера 1 (как левая так и правая часть рисунка 6 выше), соответственно, идентичны. Это можно доказать с помощью закона де Моргана и двойного отрицания.

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

Пример 4: Составим диаграмму Венна для A' + B'.

Рис. 7. Составление диаграммы Венна для логического выражения, содержащего сумму дополнений.

Решение: Итак, в левой верхней части рисунка 7 выше показано A' (красная горизонтально заштрихованная область за пределами красного круга). В правой верхней части рисунка 7 выше показано B' (синяя горизонтально заштрихованная область за пределами синего круга). На нижней части рисунка показано наложение обеих диаграмм. Мы всё ещё можем наблюдать красную горизонтальную штриховку A', наложенную на другую (синюю вертикальную) штриховку B'. Мы видим, что в эту область вошла внутренняя часть круга B, но только та, что не является общей с внутренней частью круга A.

Если только смотреть на синюю вертикальную штриховку B', то заметим, что эта область содержит именно ту внутреннюю часть круга А, что не имеет пересечения с внутренней частью круга B. Любая область с любой штриховкой, независимо от типа, соответствует A' + B'. То есть к этому выражению относится всё, кроме чистой белой области в самом центре.

Пример 5: Составим диаграмму Венна для (A'+ B')'.

Решение: Оно уже есть: на рисунке 7 выше, нижняя часть. Белая незаштрихованнная область в центре, это всё, что не входит в предыдущее решение A'+ B', а это и есть (A'+ B')'.

Пример 6: Покажем с помощью диаграммы Венна, что (A'+ B')' = AB.

Решение: Взглянем на левую часть рисунка 8 ниже:

Рис. 8. Диаграмма Венна, содержащая пересечение двух множеств.

Ранее мы показали на диаграмме с нижней части рисунка 7 выше, что белая незаштрихованная область – это (A' + B')'. В предыдущем примере мы показали дважды заштрихованную область на пересечении (наложении) AB. На рисунке 8 средняя часть – это, фактически повторение фигуры, которая присутствует в левой части.

Сравнивая две диаграммы Венна, видим, что эта незаштрихованная область (A '+ B')' совпадает с дважды заштрихованной областью AB (A И B). Мы также можем доказать, что (A'+ B')' = AB с помощью закона де Моргана и двойного отрицания, как уже это делали выше.

Рис. 9. Диаграмма Венна с тремя переменными.

На рисунке 9 выше показана диаграмма Венна с тремя переменными – области A (красная горизонтальная штриховка), B (синяя вертикальная штриховка) и C (зелёная штриховка под углом 45°). Обратите внимание в самый центр диаграммы – там, где перекрываются все три области, представляя логическую функцию И от трёх переменных ABC (A И B И C).

Есть также более крупная область в форме лепестка, где перекрываются A и B, что соответствует логическому выражению AB. Аналогичным образом перекрываются A и C, создавая логическое выражение AC. А там, где перекрываются B и C, создаётся логическое выражение BC.

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

• A, одна переменная – это большая круглая область (в данном случае красного цвета).
• AB, две переменные – это меньшая область в форме лепестка (и с красной и с синей штриховкой).
• ABC, три переменные – наименьшая область (одновременно с красной, с синей и с зелёной штриховкой).
• Чем больше переменных в выражении И, тем меньше общая область пересечения.