ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ

Введение

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

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

При написании конспекта лекций использовалась следующая литература: для раздела 1.1 – [1, 2]; для раздела 1.2 – [3]; для раздела 1.3 – [4, 5]; для раздела 2.1 – [2]; для раздела 2.2 – [6, 7]; для разделов 3.1, 3.2 – [2, 8].

Г л а в а 1

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ

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

1.1. Аксиоматика и свойства алгебры логики

Алгебру логики можно представить как множество логических переменных (т.е. таких переменных, каждая из которых может принимать значения из множества – в дальнейшем слово «логические» будем опускать) и двух констант 0 («ложь») и 1 («истина»), для всех элементов которого определено отношение эквивалентности (другие термины: равнозначность, тождественность), обозначаемое символом «=» (другие символы: «», «», «») и три основные операции: сложение («ИЛИ», объединение, дизъюнкция), обозначаемое символом «+» («»), умножение («И», пересечение, конъюнкция), обозначаемое символом «×» («», «&», отсутствие символа), отрицание («НЕ», инверсия), обозначаемое символом «–» («ù», «!»).

Данное определение не является базисом алгебры логики – ниже будет показано, что операции сложение и умножения могут быть выражены через две другие операции, а отношение эквивалентности – через сложение, умножение и отрицание. Однако подобное описание позволяет сразу ввести некоторые наиболее употребительные в алгебре логики понятия.

Для всех переменных отношение эквивалентности удовлетворяет следующим свойствам:

если то (симметричность);

если и , то (транзитивность).

Определения операций сложения и умножения приведены в табл. 1.1, определение операции отрицания – в табл. 1.2.

Таблица 1.1 Таблица 1.2

		+	×

Из табл. 1.1 видно, что сумма переменных равна 1, когда значение хотя бы одной переменной равно 1, а произведение равно 1, когда значения всех переменных равны 1.

Непосредственно из данных определений следуют все перечисленные свойства:

(нулевые константы);

(единичные константы);

(отрицание);

(двойное отрицание);

(идемпотентность);

(коммутативность);

(ассоциативность);

(дистрибутивность).

Докажем второе свойство дистрибутивности:

= [по первому свойству дистрибутивности] = == [по второму свойству идемпотентности] = = [по первому свойству дистрибутивности и свойствам единичных констант] = = [аналогично] = =.

При доказательстве этого свойства дважды использовалось следующее тождество:

(поглощение).

Из первого свойства дистрибутивности и первого свойства отрицания следует

(склеивание).

Возможность перехода между операциями сложения и умножения определяется следующими законами:

(правила де Моргана).

Благодаря ассоциативности можно обобщить свойства идемпотентности на произвольное количество переменных:

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

Реализуя свойство склеивания для двух первых слагаемых, из данного выражения получаем:

Последовательно используя свойства поглощения и идемпотентности, можно записать:

Подставляя в наше выражение, получаем:

Попарно склеивая второе слагаемое с четвертым, а третье с пятым, окончательно получаем:

Докажем часто используемое в алгебре логики тождество:

Применяя свойства склеивания и идемпотентности, можно записать:

В результате получаем:

Заменяя везде в доказанном тождестве на , получаем:

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

Таблица 1.3

Название операции	Обозначение	Представление через операции «И», «ИЛИ», «НЕ»	Смысл
сумма по модулю 2 (исключающее “ИЛИ”			или , но не и одновременно
штрих Шеффера (антиконъюнкция)			не , или не
стрелка Пирса (антидизъюнкция)			ни , ни
следование (импликация)			или не , или и одновременно
эквивалентность (двойная импликация)			или не и не одновременно, или и одновременно
разность (запрет)			, но не

Рассмотрим некоторые свойства дополнительных операций.

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

Операции штрих Шеффера и стрелка Пирса являются универсальными, так как с их помощью можно выразить операции «И», «ИЛИ», «НЕ»:

1.2. Формы представления булевых функций

Булевой функцией (БФ) называется функция , у которой аргументы пробегают множество и которая на любом наборе значений аргументов принимает значение из того же множества . Например, функция вида где , является БФ.

Для удобства описания переключательных схем БФ обычно представляют в одной из стандартных форм: дизъюнктивной нормальной форме (ДНФ) или совершенной дизъюнктивной нормальной форме (СДНФ); конъюнктивной нормальной форме (КНФ) или совершенной конъюнктивной нормальной форме (СКНФ).

Представим произвольную БФ в СДНФ.

Введем следующие обозначения: Общее обозначение: Из вторых свойств идемпотентности и отрицания соответственно следует

Обобщая два последних тождества, получаем

Воспользовавшись первым свойством отрицания, можно осуществить следующий переход:

В результате обобщения получаем разложение Шеннона по :

Последовательно раскладывая по получаем:

Последнее соотношение является представлением БФ в СДНФ. Иначе говоря, БФ в СДНФпредставляется в виде суммы произведений переменных или их отрицаний, причем ни в какое произведение не входит дважды одна и та же переменная. Если произведения не обязательно содержат все переменные – БФ представлена в виде ДНФ. Например, представление БФ

является СДНФ, а полученное в результате применения свойства склеивания выражение

является ДНФ.

Представим произвольную БФ в СКНФ.

Разложим инвертированную БФ в СДНФ:

Выполним отрицание обеих частей и применим правило де Моргана:

Так как то можно записать:

Очевидно, если то В результате имеем:

Последнее соотношение является представлением БФ в СКНФ. Иначе говоря, БФ в СКНФпредставляется в виде произведения сумм переменных или их отрицаний, причем ни в какую сумму не входит дважды одна и та же переменная. Если суммы не обязательно содержат все переменные – БФ представлена в виде КНФ. Например, представление БФ

является СКНФ, а полученное в результате перемножения содержимого двух первых скобок выражение

является КНФ.

Для перехода от СДНФ к СКНФ необходимо последовательно выполнить следующие действия: суммировать все произведения, не входящие в СДНФ; заменить все знаки умножения знаками произведения и наоборот; проинвертировать все переменные. В нашем примере БФ зависит от трех переменных, поэтому ее полная СДНФ будет равна

В результате исключения всех имеющихся в СДНФ произведений получаем

Заменяем знаки:

В результате инвертирования всех переменных получаем СКНФ:

Оказалось, что рассмотренные примеры СДНФ и СКНФ являются различными представлениями одной и той же БФ. Для перехода от СКНФ к СДНФ необходимо выполнить все перечисленные действия в обратной последовательности.

1.3. Таблицы истинности и таблицы решений

Табличный способ представления БФ является одним из самых удобных.

Таблицей истинности (ТИ) называется таблица, в левой части которой расположены наборы значений аргументов в порядке возрастания их номеров (наборы таких значений соответствуют числам записанных в двоичной системе счисления – таким образом, последующий набор значений аргументов ТИ можно получить добавлением единицы к младшему разряду предыдущего набора), а в правой части указаны значения БФ для каждого из наборов. Например, табл. 1.4 является ТИ для БФ вида Очевидно, что табл. 1.1, 1.2 также являются ТИ для БФ вида

Таблица 1.4

С помощью ТИ очень просто представить БФ в СДНФ или СКНФ.

Для получения СДНФиз ТИ отбираются все входные наборы, для которых . Далее, для каждого из таких наборов составляются произведения, которые затем суммируются. Для получения СКНФ из ТИ отбираются все входные наборы, для которых . Далее, для каждого из таких наборов составляются суммы инверсий переменных, которые затем перемножаются.

СДНФ и СКНФ для БФ, заданной табл. 1.4, соответствуют СДНФ и СКНФ, рассмотренным в разделе 1.2.

Рассмотрим пример. Для формульно заданной БФ следующего вида

табл. 1.5. является ТИ.

Рассматривая строки табл. 1.5 с номерами 2, 10, 13-16, получаем СДНФ:

Рассматривая строки табл. 1.5 с номерами 1, 3-9, 11-12, получаем СКНФ:

Таблица 1.5

Таблицей решений (ТР) называется таблица, в которой некоторым наборам значений аргументов из множества сопоставлены значения функции из множества . Таким образом, принципиальным отличием ТР от ТИ является то, что количество наборов значений аргументов в общем случае не равно . В силу этого, наборы значений аргументов могут располагаться в ТР в произвольном порядке. Когда значение переменной для данного набора аргументов не влияет на значение функции, в соответствующем месте ТР ставится символ «–» . Табл. 1.6 является ТР.

Таблица 1.6

№ строки
		–
	–
			–

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

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

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

Проанализируем табл. 1.6. Каждая из первых трех строк ТР из-за безразличных значений переменных , и соответственно может быть записана в виде двух строк (табл. 1.7).

Таблица 1.7

№ строки

Из табл. 1.7 видно, что четвертая строка «покрывается» первой, ее можно без последствий исключить. Частично перекрывают друг друга также вторая и третья строки (комбинация 111), поэтому в силу того, что эти строки еще содержат уникальные комбинации 011 и 110, данную избыточность можно устранить, заменив вторую и третью строки входными наборами 011, 110 и 111. Из табл. 1.7 также можно заключить, что исходная ТР непротиворечива (противоречивой ТР была бы в случае, например, в четвертой строке). Из табл. 1.7 также видно, что данная ТР не является полностью определенной – значения БФ не определены для входных наборов 001, 100, 101. Рассмотрим различные способы доопределения ТР.

Может быть принято решение о том, что на незаданных наборах входных переменных . В данном случае происходит доопределение нулями. В результате подобного доопределения табл. 1.6 преобразуется в табл. 1.8.

В соответствии с правилом построения СДНФ по ТИ получаем:

Таблица 1.8 Таблица 1.9


	–		–



Иначе		Иначе

Может быть принято решение о том, что на незаданных наборах входных переменных . В данном случае происходит доопределение единицами. В результате подобного доопределения табл. 1.6 преобразуется в табл. 1.9.

В соответствии с правилом построения СКНФ по ТИ получаем:

Может быть принято решение о том, что на незаданных наборах входных переменных значения безразличны. В данном случае происходит безразличное доопределение. Так как в этом случае появляется возможность выбрать значения функции таким образом, чтобы получившаяся БФ была как можно более простой (минимальной), то правило «Иначе» в этом случае применять нецелесообразно и незаданные входные наборы следует записать в таблицу в явном виде (табл. 1.10). Безразличные значения БФ будем обозначать символом d.

Таблица 1.10


	–



			d
			d
			d

В следующей главе будет показано, как использовать данную информацию для минимизации БФ с помощью карт Карно.

Упражнения

1. На основе свойств алгебры логики упростить представления булевых функций:

а) ;

б) ;

в) ;

г)

2. Для булевых функций из упр. 1 построить таблицы истинности и составить СДНФ и СКНФ.

3. Проанализировать и доопределить всеми известными способами таблицы решений:

а)			б)
			–

–		–
	–

в)					г)
		–
–			–
	–			–
				–

Г л а в а 2

Одной из важнейших задач, возникающих при синтезе переключательных схем,… Представление БФназывается минимальным, если оно включает минимальное количество вхождений букв (обозначений…

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

2.2. Метод неопределенных коэффициентов

Теоретически решение задачи минимизации представления БФ может быть получено путем полного перебора всех возможных эквивалентных представлений. При этом максимально возможное число букв в представлении БФ от переменных будет равно .

Метод неопределенных коэффициентов позволяет более эффективно упрощать логические функции. Сначала для заданной БФ от переменных составляют полную ДНФ, куда каждая из конъюнкций входит с двоичным коэффициентом Эта ДНФ запишется так:

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

При значениях аргументов данная ДНФ примет следующий вид:

Последовательно перебирая все наборы входных переменных и подставляя их в ДНФ, получаем систему из уравнений:

Минимальная форма БФ определяется путем выбора простейшего набора двоичных коэффициентов, удовлетворяющих данной системе уравнений.

На основании изложенного подхода составим формальный алгоритм минимизации представления БФ и продемонстрируем его функционирование на примере минимизации представления функции

1. Для заданной в произвольной форме БФ заполняется таблица истинности (для нашей функции – табл. 2.1).

Таблица 2.1

2. Составляется система уравнений, аналогичная рассмотренной выше. В правую часть уравнений подставляются конкретные значения из таблицы истинности. Для нашей функции получаем:

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

4. Все нулевые коэффициенты подставляем в оставшиеся уравнения с единицей в правой части. Для нашей функции будут упрощены четвертое, шестое, седьмое и восьмое уравнения:

5. Полученная на предыдущем шаге система уравнений допускает дальнейшее упрощение. Для этого нужно в каждом уравнении оставить коэффициенты, соответствующие наименьшим конъюнкциям. Из первого уравнения следует: , из второго – , из третьего – . Так как нам уже известно, что , из четвертого уравнения следует: .

Итак, оптимальным решением системы уравнений является: . Следовательно, минимальная ДНФ заданной БФ запишется так: .

Упражнения

1. Упростить исходные представления булевых функций, приведенные в упр. 1 к первой главе:

а) с помощью карт Карно;

б) с помощью метода неопределенных коэффициентов.

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

Г л а в а 3

СТРУКТУРНАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

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

3.1. Контактные схемы

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

Таблица 3.1

Схема	Логическая операция

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

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

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

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

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

а)	б)

в)

Рис. 3.1. Схемные представления свойств коммутативности, ассоциативности и

дистрибутивности

Простой пример контактной схемы, реализующей операцию сумма по модулю 2, показан на рис. 3.2.

Рис. 3.2. Реализация операции сложения по модулю 2 контактной схемой

На основе стандартных методов минимизации представлений БФ осуществляют переход к простейшим контактным схемам, содержащим минимальное количество элементов. Пусть имеется БФ, представленная в СДНФ:

На рис. 3.3 изображена реализующая ее схема, содержащая 12 контактов. Используя, например, карты Карно, в результате упрощения представления функции получаем:

Реализующая ее схема (рис. 3.4) содержит всего 5 контактов.


Рис. 3.3. Исходная контактная схема	Рис. 3.4. Упрощенная контактная схема

3.2. Бесконтактные схемы

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

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

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

2. В качестве значений входов логических элементов могут быть константы 0 и 1.

3. Никакие два выхода логических элементов нельзя соединять вместе.

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

Таблица 3.2

Логический элемент	Логическая операция
Дизъюнктор
Конъюнктор
Инвертор

Упражнения

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

а) контактных схем;

б) бесконтактных схем.

2. Дополнительные логические операции из табл. 1.3 реализовать в виде:

а) контактных схем;

б) бесконтактных схем.

Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986.

2. Миллер Р. Теория переключательных схем. т. I. – М.: Наука, 1971.

3. Блох А.Ш. Граф-схемы и их применение. – Минск: Высшая школа, 1975.

4. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. – М.: Наука, 1986.

5. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. – СПб.: Наука, 1998.

6. Кобринский Н.Е., Трахтенберг Б.А. Введение в теорию конечных автоматов. – М.: Физматгиз, 1962.

7. Скурихин Н.А., Яхонтов Ю.К. Методы анализа и синтеза дискретных автоматов: конспект лекций. – Л.: ЛТА, 1983.

8. Яглом И.М. Булева структура и ее модели. – М.: Советское радио, 1980.

ОГЛАВЛЕНИЕ

Введение....................................................................................................... 3

Г л а в а 1. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ..................... 3

1.1. Аксиоматика и свойства алгебры логики......................................... 3

1.2. Формы представления булевых функций......................................... 7

1.3. Таблицы истинности и таблицы решений....................................... 10

Упражнения............................................................................................. 14

Г л а в а 2. МИНИМИЗАЦИЯ ПРЕДСТАВЛЕНИЙ БУЛЕВЫХ

ФУНКЦИЙ................................................................................................. 15

2.1. Карты Карно.................................................................................... 15

2.2. Метод неопределенных коэффициентов......................................... 22

Упражнения............................................................................................. 24

Г л а в а 3. СТРУКТУРНАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ.. 25

3.1. Контактные схемы........................................................................... 25

3.2. Бесконтактные схемы....................................................................... 28

Упражнения............................................................................................. 29

Литература................................................................................................. 29