Элементы алгебры логики

Логические основы построения вычислительной машины

В вычислительных машинах коды нуля и единицы представляются электрически­ми сигналами, имеющими два различных состояния:

q импульс или его отсутствие;

q высокий или низкий потенциал;

q высокий потенциал или его отсутствие.

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

При импульсном способе отображения код единицы идентифицируется наличи­ем электрического импульса, код нуля – отсутствием его (впрочем, может быть и наоборот). Импульс характеризуется амплитудой и длительностью, причем дли­тельность должна быть меньше временного такта машины.

При потенциальном способе отображения код единицы – это высокий уровень напряжения, а код нуля – отсутствие сигнала или низкий его уровень. Уровень напряжения не меняется в течение всего такта работы машины. Форма и амплиту­да сигнала при этом во внимание не принимаются, а фиксируется лишь сам факт наличия или отсутствия сигнала.

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

Алгебра логики – это раздел математической логики, значение всех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.

Высказывание – это любое предложение, в отношении которого имеет смысл ут­верждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, то есть каждое высказывание или истинно, или ложно и не может быть одновременно и истинным и ложным. Высказывания:

q «Сейчас идет снег» – это утверждение может быть истинным или ложным;

q «Москва – столица России» – истинное утверждение;

q «Частное от деления 10 на 2 равно 3» – ложное утверждение.

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

Простейшими операциями в алгебре логики являются операции логического сложе­ния (операция дизъюнкции, ИЛИ)и логического умножения (операция конъюнкции, И). Для обозначения операции логического сложе­ния используют символы + или , а логического умножения – символы · или . Пра­вила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий. В частности, для алгебры логики выполняются следующие законы.

1. Сочетательный:

(а + b) + с = а + (b + с),

(a ·b) ·c = a· (b·c).

2. Переместительный:

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

(a · b) = (a ·b).

3. Распределительный:

a · (b + c)= a·b +а·c,

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

Справедливы соотношения, в частности:

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

Наименьшим элементом алгебры логики является 0, наибольшим элементом – 1. В алгебре логики также вводится еще одна операция – отрицания (операция НЕ, инверсия), обозначаемая чертой над элементом.

По определению:

Справедливы, например, такие соотношения:

Функция в алгебре логики – алгебраическое выражение, содержащее элементы алгеб­ры логики а, b, с, связанные между собой операциями, определенными в этой алгебре.

Примеры логических функций:

Согласно теоремам разложения функций на конституанты (составляющие), лю­бая функция может быть разложена на конституанты:

(3)

и т. д. Эти соотношения используются для синтеза логических функций и вычис­лительных схем.