Тема 5. Логические функции

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

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

Высказывание — некоторое предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами. Впервые практическое применение булевой алгебры было сделано К. Шенноном в 1938 г. для анализа и разработки релейных переключательных сетей, результатом чего явилась разработка метода представления любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принципов их преобразования на основе правил булевой алгебры. Ввиду наличия аналогий между релейными и современными электронными схемами аппарат булевой алгебры нашёл широкое применение для их структурнофункционального описания, анализа и проектирования. Использование булевой алгебры позволяет не только более удобно оперировать с булевыми выражениями (описывающими те или иные электронные узлы), чем со схемами или логическими диаграммами, но и на формальном уровне путём эквивалентных преобразований и базовых теорем упрощать их, давая возможность создавать экономически и технически более совершенные электронные устройства любого назначения. Операции булевой алгебры часто встречаются и в программном обеспечении вычислительных устройств, где они используются для замены аппаратной логики на программную.

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

Элементы. Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие. Первые производят обработку информации, представленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться бинарными символами { } или логическими значениями {Истина (True), Ложь (False)}. Поэтому множество элементов булевой алгебры выбирается бинарным { }, а сама алгебра называется бинарной, или переключательной. Её элементы называются константами, или логическими 0 и 1, которым в ряде случаев соответствуют бинарные цифры, в других случаях — логические значения, соответственно ложь (False) и истина (True). В дальнейшем для обозначения булевых переменных будем использовать буквы латинского алфавита — , , , …. Набор переменных , , , … может рассматриваться как -разрядный двоичный код, разрядами которого являются эти переменные.

Операции. Основными, или базовыми, операциями булевой алгебры служат: И (AND), ИЛИ (OR) и НЕ (NOT). Операция И называется логическим умножением или конъюнкцией и обозначается знаком «&». Операция ИЛИ называется логическим сложением или дизъюнкцией и обозначается знаком «˅». Операция НЕ называется логическим отрицанием или инверсией (дополнением) и обозначается знаком «‾».