1. Краткие теоретические сведения.

3.1.1. Основные понятия алгебры логики. Логические функции, способы их представления.

Для структурно-функционального описания логических схем, составляющих основу любого дискретного вычислительного устройства, ЭВМ или ВС в целом, используется аппарат булевой алгебры, ­созданной в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами. Впервые практическое применение булевой алгебры было сделано К. Шенноном в 1938 г. для анализа и разработки релейных переключательных сетей, результатом чего явилась разработка метода представления любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принципов их преобразования на основе правил булевой алгебры. Ввиду наличия аналогий между релейными и современными электронными схемами аппарат булевой алгебры нашел широкое применение для анализа, описания и проектирования последних. Использование булевой алгебры позволяет не только более удобно оперировать с булевыми выражениями (описывающими те или иные электронные узлы), чем со схемами или логическими диаграммами, но и на формальном уровне путем эквивалентных преобразований и базовых теорем упрощать их, давая возможность создавать экономически и технически более совершенные электронные устройства любого назначения. Наряду с этим одним из применений ЭВМ и микропроцессоров является замена аппаратной логики на программную, поэтому операции булевой алгебры часто встречаются и в ПО микро-ЭВМ. Утилитарная значимость аппарата булевой алгебры и описываемых им логических схем заключается также и в наличии ряда методик автоматизированного обнаружения структурных ошибок ПО на основе конечно-автоматного подхода, базирующегося на указанном аппарате. Являясь основным средством анализа, разработки и описания структурно-функциональной архитектуры современной ВТ, булева алгебра является обязательной составной частью целого ряда разделов вычислительных наук.

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

Во всех случаях, как правило, в тех или иных точках логических схем появляются сигналы двух различных уровней. ­Следовательно, сигналы могут представляться бинарными символами {0, 1} или логическими значениями {Истина (True), Ложь (False)}.

Поэтому, ­множество элементов B={0, 1} булевой алгебры выбирается бинарным; такая ­алгебра ­называется бинарной или переключательной. Ее элементы называются константами, или логическими 0 и 1; в ряде случаев логическим 0 и 1 соответствуют бинарные цифры, в других случаях им соответствуют логические значения соответственно Ложь (False) и Истина (True).

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

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

Под высказыванием будем понимать всякое предложение, принимающее два значения - истинно или ложно. Значение истинности будем обозначать как TRUE или цифрой «1», ложное значение соответственно FALSE или цифрой «0». Высказывание - «Москва - столица России» является истинным, а высказывание - «Енисей - река в Европе» - ложным. Высказывание бывают простыми и сложными. Исходные (простейшие) высказывания будем называть простыми, а образованные из них другие высказывания - сложными.

Будем обозначать высказывания переменными х_1,х₂,...;у_1,у₂,... Сложные высказывания образуются из простых высказываний путем объединения их связками «И», «ИЛИ», «Если ... ,ТО», «НЕ» и др. Данным связкам в математической логике присвоено название логических операций.

Существует несколько булевых операций, из которых только три: И (AND), ИЛИ (OR) и НЕ (NOT) — полагаются базовыми, остальные можно получать на их основе. Операция И называется логическим умножением или конъюнкцией, операция ИЛИ называется логическим сложением или дизъюнкцией, операция НЕ называется логическим отрицанием или инверсией (дополнением) .

Обозначаются логические операции знаками:

«И» - &, Ù;

«ИЛИ» - Ú, +;

«НЕ» - ù, - ;

«Если ..., ТО» - ®.

Одним из способов представления комбинационной схемы является задание ее логической F-функции посредством булева выражения, состоящего из булевых констант и переменных, соединенных знаками операций И, ИЛИ, НЕ и, возможно, скобками. Для уменьшения количества используемых скобок предполагается, что логическая И - операция имеет приоритет выше, чем ИЛИ - операция.

Приведем в качестве примера одно из сложных высказываний: «Если ЭВМ будет исправна и выделено время на решение задачи, то будет получен результат».

Обозначим переменными следующие высказывания:

х₁ - ЭВМ будет исправна;

х_{2 -} выделено время на решение задачи;

у - будет получен результат.

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

( х₁ Ù х₂ ) ® у.

Вопрос: как можно прочитать следующее сложное высказывание применительно к предыдущему примеру.

Рассмотрим сложное высказывание, известное из электротехники. Оно образовано из двух простых высказываний: «Ток в цепи нагрузки появляется при замкнутых контактах 1 и 2».

+° °-

1 2 R

Обозначим: х₁ - замкнут контакт 1; х₂ - замкнут контакт 2; у - наличие тока в цепи.

Рассмотрим все варианты и составим таблицу.

Таблица 3.1.

х1	х2	у
0 0 1 1	0 1 0 1	0 0 0 1

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

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

ФАЛ может обозначаться у, f, F.

У = х₁ & х₂.

Логическая связка, соответствующая союзу «И», называется конъюнкцией.

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

Таблица 3.2.

Переменные		Функция
х1	х2	F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 1 1	0 1 0 1	0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

В алгебре логики наиболее часто распространены следующие логические функции:

конъюнкция - F₁ = х₁ & х₂; _____

отрицание конъюнкции - F₁₄ = х₁ & х₂;

дизъюнкция - F₇ = х₁ Ú х₂; _____

отрицание дизъюнкции (стрелка Пирса)- F₈ = х₁ Ú х₂;

инверсия Х₁ - F₁₁ = х_1;

инверсия Х₂ - F₁₀ = х₂;

равнозначность - F₉ = х_{1 } х₂;

отрицание равнозначности - F₆ = х₁  х₂ (сложение по модулю 2);

импликация - F₁₃ = х₁ ® х₂.