Логические основы ЭВМ

Логические основы ЭВМ базируются на так называемой алгебре логики, в основном разработанной английским математиком Джорджем Булем.

Алгебра логики

В алгебре логики совершают операции только с переменными, имеющими двоичную природу. Другими словами, рассматриваемые переменные принимают из двух возможных только одно значение и любое высказывание, несмотря на его содержание, рассматривают только на предмет истинности, т. е. верно или неверно, истинно или ложно. Нужно отметить, что для алгебры логики объектом может быть только утвердительное высказывание, например: сегодня — четверг; солнце — звезда; Волга впадает в Каспийское морс и т. д. В этих высказываниях говорится только об одном факте (истинном или ложном), и поэтому их называют простыми. При связывании двух или более простых высказываний получают сложные высказывания. Для определения истинности сложного высказывания применяют три основных действий алгебры логики: отрицание, сложение, умножение.

В дальнейшем при рассмотрении отдельных простых высказываний будем обозначать их прописными буквами. Если рассматриваемое высказывание ложно, то присвоим ему значение 0, если истинно, — значение 1. Тогда, например:

А — воробей является птицей, т. е. А = 1;

В — столицей Канады является г. Лондон, т. е. В = 0.

Рассмотрим первое действие — отрицание.

Отрицание осуществимо для одного высказывания. Отрицание высказывания получают при применении выражения «неверно, что» или применяя частицу НЕ. Например: декабрь летний месяц года -А; декабрь НЕ летний месяц года — А

или неверно, что декабрь летний месяц года — А.

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

Действие логического отрицания определяет следующая таблица:

Следуя этой таблице можно сказать, что отрицая истинное высказывание, мы говорим ложь (не истину), а отрицая ложное высказывание, мы говорим истину. Отрицание 1 равно 0 и 0 = 1.

Если над А написать две черты, то получим двойное отрицание А — А_у или словами: неверно, что декабрь НЕ летний месяц года. Выражение А = А в логике известно как закон двойного отрицания.

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

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

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

При смене мест В и А получится такая же таблица истинности. Таким образом, АВ = ВА, а также А • А = А; А • 1 = А; А 0 = 0.

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

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

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

Таблица истинности для логической суммы имеет вид:

Таблица истинности не изменится, если поменять местами А и В, т. е. А + В = В + А. Кроме того, А + А = А; >4 + 1 = 1; А + 0 = А.

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

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

Существуют сложные высказывания, имеющие различный вид при одинаковых таблицах истинности и при этом имеющие одни и те же значения входящих в них простых высказываний. Такие сложные высказывания принято называть эквивалентными. Также существуют сложные высказывания, истинность которых является постоянной и не зависит от того, истинны ли входящие в них простые высказывания. Такие высказывания принято называть тождественными. Таковым является высказывание х = АА, для которого значение всегда равно 0 (никогда не истинно). Например: неверно, что лампа светит И лампа не светит. В логике этот закон называют законом противоречия.

Высказывание х = А + А является также тождественным и его значение равно 1 (всегда истинно). Например: линия прямая ИЛИ линия не прямая. Это известно в логике как закон исключенного третьего.

Логическая сумма обладает следующим свойством:

Логические произведения подчиняются равенствам:

Справедливы и следующие выражения:

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

заменив в левой части равенства знаки, получим:

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

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

Применяя свойства сложения высказываний можно выполнить преобразование этих высказываний в более простые.

Пусть высказывание имеет вид х = А + АВ. Выполним его преобразование:

Поскольку 1 +? = 1, следовательно, х = Л1 = Л. Тогда АлАВ = А.

При выполнении этой операции происходит исчезновение простого высказывания В. Такая операция называется поглощением. На основании закона двойственности можно записать А (АлВ) = А.

Рассмотрим еще одну операцию, применяемую для упрощения логических формул. Эту операцию называют слиянием:

Такое преобразование является слиянием по В. Здесь также возможно применение закона двойственности: (А + В) • (А + В) = А.

В специальной литературе приведены зависимости Булевой алгебры. Рассмотрим эти зависимости.

В качестве постулатов:

• 0−0 = 0; 0 + 0 = 0; 0 = 1;
• 0−1 = 0; 0 + 1 = 1; 1 = 0.
• 1−0 = 0; 1 + 0 = 1;

М = 1; 1 + 1 = 1;

В качестве теорем:

А 0 = 0; А, А = 0; Ал-А = А;

0Л = 0; А + 0 = А; Л + Л = 1;

АЛ = А; О + А = А; А = А.

А = А; А +1 = 1;

А-А = А; 1 + А = 1;

В качестве законов:

• • идентичности А = А; А = А;
• • коммутативности АВ = BA; А + В = В + А;
• • ассоциативности А (ВС) = ABC; А + (В + С) = А +В + С;
• • идемпотентности АА = А; А + А = А;
• • дистрибутивности А (В + С)= АВ + АС;

А + ВС = (А + В)(А + С);

• • поглощения А + АВ = А; А (А + В) = А;
• • слияния АВ + АВ = А; (А + В)^А + Z?) = А;
• • дс Моргана АВ = А + В; А + В = А В.

Некоторых тождеств:

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

2^я

переменных, можно составить 2″ функций. Например, при п = 2 число функций для двух двоичных переменных равно 2² = 2⁴ = 16. Для этих функций значения истинности даны в табл. 3.3. Под таблицей приведено их описание. Английские названия самых распространенных функций приведены в скобках.

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