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

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

Алгебра логики оперирует с логическими высказываниями.

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

Высказывания:

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

· «Вашингтон — столица США» — истинное утверждение;

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

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

Простейшими операциями в алгебре логики являются операции логического сложения (иначе: операция ИЛИ, операция дизъюнкции) и логического умножения (иначе: операция И, операция конъюнкции).

Для обозначения операции логического сложения используют символы + или V. а логического умножения — символы • или /\. Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий. В частности, для алгебры логики выполняются следующие законы.

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

(а+b)+c = а +^:(b+с),

(а•b)•c = а•^:(b•с).

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

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

(а • b) = (b•а),

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

a•(b + c) = a•b + a•c,

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

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

а + а = а а + b=b, если а<=b,

а•а = а а•b=а, если а <= b,

a + a•b = a a•b = b, если а >= b,

а + b= а,если а>=b.

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

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

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

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

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

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

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

37 Логический синтез вычислительных схем

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

Таблица 3.3. Логический синтез (создание) вычислительных схем

a	b	F1(a,b)=S	F2(a,b)=P

В этой таблице f1(a, b) = S — значение цифры суммы в данном разряде; f2(а, b) = Р — цифра переноса в следующий (старший) разряд. Т.О. можно записать:

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

b b

a ab

&

b (ab=ab=s)

ab

a a

a

b (ab=p)

Рис. 1 Логическая блок-схема сумматора

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

Для логических схем «ИЛИ», «И» и «НЕ» существуют типовые технические схемы, реализующие их на реле, электронных лампах, дискретных полупроводниковых элементах.

Для построения современных компьютеров обычно применяются системы интегральных элементов, у которых с целью большей унификации в качестве базовой логической схемы используется всего одна из схем: «И — НЕ» (штрих Шеффера), «ИЛИ — НЕ» (стрелка Пирса) или «И — ИЛИ - НЕ».

a a+b

Схема «ИЛИ» реализующая операцию логического сложения

b

&

A a•b

Схема «И» реализующая операцию логического умножения

B

A a

Схема «НЕ» реализующая операцию инверсии

Рис. Международное обозначение логических блоков

Выполнение логических операций в компьютере

В перечень машинных команд, которые используются при программировании, обязательно входят и некоторые логические операции. Чаще всего это операции OR (ИЛИ), AND (И), NOT (HE) и XOR (исключающее ИЛИ).