Понятие об алгебре логики

Для дальнейшего рассмотрения вопросов обработки информации большое значение имеет знакомство с алгеброй логики – одной из основных частей математической логики, основанной на применении алгебраических методов к логике. (Математическая логика – это наука, изучающая предмет формальной или “обычной” логики методом формализованных языков.)

Алгебра логики является одним из основных инструментов в теории релейных схем, в теории ЭВМ и дискретных автоматов, в прикладной информатике и кибернетике. Она представляет собой, прежде всего, алгебру высказываний. В алгебре логики под высказыванием понимают всякое предложение, которое либо истинно (имеет значение Т-true), либо ложно (имеет значение F-false). Отдельные высказывания обозначаются буквами какого-либо алфавита, например: A,B,C,D... Истинность или ложность высказываний называется их значениями истинности. Истинность высказывания отождествляют с числом 1, а ложность – с числом 0. Запись А=1, С=0 означает, что высказывание А истинно (например, А=Екатеринбург – крупный промышленный центр Урала), а С–ложно (например, С=снег черный).

Предметом изучения алгебры логики являются двоичные функции, то есть функции, которые в результате выполнения принимают только два значения 1 – истинно и 0 – ложно.

Из одного или нескольких высказываний, принимаемых за простые, можно составлять сложные высказывания, которые будут являться двоичными функциями простых высказываний. Объединение простых высказываний в сложные производится без учета внутреннего содержания (смысла) этих высказываний, а только по признаку истинности. К числу основных логических операций для получения сложных высказываний относятся операции отрицания, конъюнкции, дизъюнкции, эквивалентности и импликации. Если под переменными A, B, C, и т.д. понимать не только высказывания, а вообще любую систему элементов, для которой определены действия логического умножения, сложения и отрицания и которая удовлетворяет основным законам алгебры логики, то получим абстрактную алгебру, называемую алгеброй Буля. В частности, высказывания и основные логические операции представляют собой частный случай алгебры Буля. Поэтому в теории алгоритмов и ЭВМ, в теории релейных схем, в теории двоичных переключательных схем и автоматов и т.д. чаще говорят не "алгебра логики", а "алгебра Буля" и не "двоичная логическая функция", а "булева функция" или "переключательная функция".

Поскольку аргументы переключательной функции могут принимать (как и она сама) только два значения 0 и 1, то область определения любой переключательной функции всегда конечна. Совокупность значений истинности аргументов называется набором. Если имеется n переменных (аргументов функции – простых высказываний), то существует различных наборов значений их истинности. Так как переключательная функция (сложное высказывание) определена на этих наборах и сама может принимать значения 0 или 1, то число различных булевых функций M от n переменных равно . Например, пусть имеем функции от одного аргумента, то есть n = 1, тогда Z = 2ⁿ = 2¹ = 2 набора истинности аргумента – 1 и 0 и количество сингулярных функций (функций от одного аргумента) будет равно М=2^Z=2²=4.

Основные логические операции. Рассмотрим кратко основные логические операции и получаемые с их помощью логические функции.

1. Отрицание, или инверсия, является функцией одной переменной, то есть отрицание, одна из четырех сингулярных функций, может иметь также два значения: если X=1, то f(X)==0 и, если X=0, то f(X)==1. Читается “не X”. Это высказывание противоположное по значению исходному. Обозначается операция чертой над аргументом. Аргументом отрицания может быть и сложное высказывание, то есть другая булева функция. Это мы увидим чуть дальше по тексту. Три других сингулярных функций – это сама величина Х, то есть f(X)=X, и две константы, не зависящие от значения Х: f(X)=1 и f(X)=0.

При n=2 имеем четыре набора значений их истинности. Следовательно, булевых функций от двух аргументов (бинарных) существует 16. Бинарные переключательные функции получаются с помощью следующих логических операций.

2. Конъюнкция, или логическое умножение, обозначается значками , & или точкой и читается как “и”. Получаемая функция f(,X)=XX= XX (читается “Xи X”) имеет значение истинности (1) только тогда, когда аргументы Xи X истинны, то есть при X₁=1 и X₂=1 функция f(X₁,X₂)=1. Во всех других случаях она имеет значение ложности (0). Аргументами конъюнкции могут быть другие переключательные функции. Сама конъюнкция также может быть аргументом другой логической функции. Например, если функция Y=X1X₂, то, применив отрицание, получим f(Y)==.

3. Дизъюнкция, или логическое сложение, обозначается значком  или + и читается как “или”. Это неразделительный союз “или” (при звоне будильника Дима или Коля проснутся - не разделяется кто: или тот, или другой, или оба вместе). Есть еще исключающее “или” (выбирай: он или я). Этот союз не может быть дизъюнкцией, хотя другой логической операцией может и быть. Получаемая функция f(,)= =+ читается “ или ” и имеет значение ложности только тогда, когда и ложны, то есть при =0 и =0 функция f(,)=0. Во всех остальных случаях она истинна. Аргументами дизъюнкции могут быть другие переключательные функции. Например, если Y=, a Z=, то f(Y,Z)= Y Z= ( ) . Сама дизъюнкция также может быть аргументом другой логической функции.

4. Эквивалентность. С помощью этой логической операции может быть получена функция, имеющая значение истинности тогда, когда значения истинности ее аргументов одинаковы, и значение ложности – во всех остальных случаях. Эта логическая операция обозначается значками ~ или и читается “ эквивалентно”. Если ==1 или ==0, то функция f(,)=1; при =1 и =0 или =0 и =1 функция f(,)=0. Для эквивалентности справедливы выражения: А~1=A и A~0=.

5. Импликация. С помощью этой логической операции может быть получена булева функция, имеющая ложное значение в том и только в том случае, когда аргументы – истинно, а – ложно. При =1 и =0 функция f(,)==0. Во всех остальных случаях ее значение истинно. Обозначается эта функция значком  и читается как “если , то ”. Смысл импликации можно передать словами “ ложно или истинно”. Здесь союз “или” – не исключающее.

Рассмотрим еще три важнейшие переключательные функции, получаемые путем применения отрицания к рассмотренным выше операциям.

6. Применив операцию отрицания к функции эквивалентности, получим новую функцию f(,)=. Нетрудно видеть, что она имеет смысл исключающего “или” (для проверки подставьте значения истинности). Эта логическая операция имеет важнейшее значение в теории и практике ЭВМ, так как она представляет собой сложение двоичных чисел по модулю два (без переносов из разряда в соседний разряд) и обозначается значком , то есть f(,)==.

7. Применив операцию отрицания к функции, полученной путем конъюнкции f(,)=, получим новую булеву функцию – штрих Шеффера f()==или X_{1 } X₂. Эта логическая операция имеет важнейшее значение в теории и практике ЭВМ и логических схем, так как через нее может быть выражена любая функция Буля. Электронная схема, реализующая ее, является функциональным универсальным элементом, при помощи которого в принципе могут быть построены любые функциональные схемы автоматов.

8. Применив операцию отрицания к функции, полученной путем дизъюнкции f, получим новую логическую функцию, которая обозначается так: f(,)== и называется стрелка Пирса. Остальные бинарные функции рассматривать не будем, так как они не имеют большого практического применения по сравнению с рассмотренными выше.

Преобразование логических функций. Из рассмотренного выше возникает вопрос: возможен ли минимальный набор простых булевых функций, с помощью которых можно представить все функции алгебры Буля или сколь угодно сложную булеву функцию? Этот вопрос связан с одним из основных понятий булевой алгебры – понятием функциональной полноты системы булевых функций.

Оказывается, можно привести несколько систем булевых функций, обладающих функциональной полнотой. Одной из таких систем является система, состоящая из операций конъюнкции, дизъюнкции и отрицания. Из нее можно получить еще две системы, исключая поочередно функции конъюнкцию и дизъюнкцию. Наконец, можно привести несколько систем, состоящих всего лишь из одной функции, которые будут обладать также функциональной полнотой. Это функции штрих Шеффера и стрелка Пирса. Недостающие функции конъюнкции, дизъюнкции и отрицания для этих систем можно получить на основе известных правил алгебры логики.

Правила приводятся без доказательств в качестве справочных данных, но легко можно убедиться в их справедливости, подставив в правые и левые части равенств значения переменных, равные 0 и 1. Эти правила используются для преобразования сложных логических выражений к более удобному или простому виду.

1. =; 2. ; 3.;

4.;5.; 6. 

; 7. ;

8. = ; 9. 10.

11.; 12. 13. 14.

15. 16.; 17.

Соотношения 2,3,4,5 показывают, что для операций конъюнкции и дизъюнкции справедливы переместительные (2,4) и сочетательные (3,5) законы, в силу чего многочисленные конъюнкции и дизъюнкции, например, можно писать без скобок. Такое выражение часто называют произведением, а члены его - множителями. Выражение вида называют суммой, а члены его - слагаемыми. Соотношение 6 показывает, что в алгебре логики, как и в арифметике, справедлив распределительный закон умножения относительно сложения – закон дистрибутивности. В отличие от арифметики, в алгебре логики есть еще распределительный закон сложения относительно умножения, выражаемый соотношением 7. Соотношения 8 и 9 называются законами де Моргана (или законами инверсии). Они вместе с соотношением 1 позволяют преобразовывать логические выражения в такой вид, что операции отрицания будут относиться только к простым высказываниям (аргументам булевых функций). Соотношения 10 и 11 – законы тождества для сложения и умножения. Соотношение 14 – закон исключенного третьего, а 15 – закон противоречия.

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

18. 19.

20. 21.

22. 23.

24.

25.

26. 27.

28. 29. ;

30.; 31.

32. 33.

34. 35. 36.

Использование соотношений 26 и 36 позволяют любые выражения, содержащие знаки эквивалентности, импликации и штрих Шеффера, приводить к выражениям, содержащим только знаки конъюнкции, дизъюнкции и инверсии.

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

Простейшие электронные схемы (интегральные схемы - ИС), реализующие элементарные булевы функции, называются логическими элементами и являются элементной базой дискретных устройств. При описании цифровых устройств на уровне функциональных схем и описании цифровых интегральных схем логический элемент обозначается прямоугольником, внутри которого указывается символ выполняемой функции. Инверсия по входу (выходу) функционального элемента обозначается кружком на входе (выходе) прямоугольника. При этом логическая операция отрицания применительно к преобразованию сигналов означает, что сигнал на выходе элемента НЕ будет тогда, когда не будет сигналов на его входах, и наоборот. Для логической операции конъюнкции функциональный элемент обозначается знаком & в верхнем левом углу прямоугольника. Сигнал на выходе элемента И будет только тогда, когда сигналы будут одновременно на всех его входах. Если хотя бы одного входного сигнала не будет, то на выходе сигнала тоже не будет. Для логической операции дизъюнкции функциональный элемент обозначается цифрой 1 в верхнем левом углу прямоугольника. Сигнал на выходе элемента ИЛИ не будет, если не будет ни одного входного сигнала. Если будет хотя бы один из всех входных сигналов, будет сигнал и на выходе элемента.

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

Задача анализа схем состоит в том, что, имея какую-либо готовую схему, требуется описать ее работу логическим выражением, задающим некоторую функцию алгебры логики. Затем, путем преобразования ее, исследовать вопрос: нельзя ли получить более простую схему, содержащую меньшее количество элементов, которая бы реализовала данную функцию алгебры логики? Это очень важный вопрос. Чем меньше элементов содержит схема, тем она надежнее работает, потребляет меньше энергии, более компактна конструктивно, более проста в изготовлении и т.д., то есть менее затратна.

Рассмотрим пример. Пусть имеем фрагмент некоторой логической схемы, изображенный на рис.9 (а).

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

Применяя приведенные ранее соотношения 6, 14, 12 к первым двум скобкам, получим: Подставив полученное значение в исходное выражение, и применяя снова соотношения 7, 14, 12, получим: Таким образом, упростив выходное логическое выражение, видим, что приведенный на рис. 9 (а) фрагмент схемы может быть представлен в виде одного простейшего логического элемента ИЛИ, изображенного на рис. 9 (б).

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

Методы алгебры логики также находят широкое применение в теории множеств и при составлении логических схем программ. Конъюнкция часто используется для конкатенации – слияния двух выражений (обычно строковых), чтобы образовать одно более длинное выражение. Часто ее используют для выделения определенной части двоичного кода с помощью специально подобранных кодов из нулей и единиц, чтобы проверить какое-либо условие. Например: по выражению если X AND 8=1 то проверяется третий разряд переменной Х на равенство 1 и выполняется какое-то условие. Здесь слово AND является логическим умножением.

Дизъюнкция используется для формирования двоичного кода из двух имеющихся кодов (чаще всего выделенных с помощью логического умножения).

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

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

Лекция 13