Тема 2. Основы алгебры логики

 

Основы алгебры логики были заложены в середине XIX века трудами английского математика Дж. Буля, по имени которого она называется также булевой алгеброй. Понимание принципов, лежащих в ее основе, важно для овладения методами описания и проектирования цифровых устройств. Начало использованию алгебры логики для синтеза переключательных (релейных) схем было положено в 1938 г. работами американского ученого К. Шеннона.

Аксиомы алгебры логики. В алгебре логики рассматриваются переменные, которые могут принимать только два значения – 0 и 1. В дальнейшем переменные будем обозначать латинскими буквами (при необходимости с цифровыми индексами): x, y, B, А2 и т.п.

В алгебре логики определены отношение эквивалентности (=) и три операции: дизъюнкция (операция ИЛИ, логическое сложение), обозначаемая знаком Ú (например, х Ú Y); конъюнкция (операция И, логическое умножение), обозначаемая знаками Ù, & или точкой, которую можно опускать (например, х · А3 = х А3); и отрицание (операция НЕ, инверсия), обозначаемое чертой над переменными или над элементами 0 и 1 (например, , ).

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

x = х – рефлексивность;

если х = y, то y = x – симметричность;

если x = y и y = z, то x = z – транзитивность.

Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей х, вместо х можно подставить Y, и в результате будет получена эквивалентная формула.

Алгебра логики определяется следующей системой аксиом:

 

(2.1)

 

(2.2)

 

(2.3)

 

(2.4)

 

Аксиома (2.1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (2.2), (2.3) определяют свойства операций дизъюнкции и конъюнкции, а аксиома (2.4) – операции отрицания.

Законы, тождества и теоремы алгебры логики. С помощью аксиом алгебры логики можно доказать целый ряд тождеств и теорем. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных: если теорема истинна, то с учетом (2.2)…(2.4) уравнение, формулирующее утверждение теоремы, должно быть истинно при подстановке любых значений переменных в обе его части. Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1.

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

Операции логического сложения (дизъюнкции) и логического умножения (конъюнкции) для случая одной переменной x обладают следующими свойствами:

 

(2.5)

 

(2.6)

 

Для случая двух и более переменных справедливы следующие законы:

переместительные (коммутативные)

 

, (2.7)

 

сочетательные (ассоциативные):

 

, (2.8)

 

распределительные (дистрибутивные):

 

, (2.9)

 

двойственности (теоремы де Моргана):

 

, (2.10)

 

двойного отрицания:

 

, (2.11)

 

поглощения:

 

, (2.12)

 

операции склеивания:

 

, (2.13)

 

операции обобщенного склеивания:

 

, (2.14)

 

. (2.15)

 

Некоторые законы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в выражениях (2.5), (2.6), (2.11)…(2.15) правая часть выражения проще левой, поэтому проведя в логических выражениях соответствующие преобразования можно добиться существенного их упрощения. Наиболее часто для преобразования логических выражений с целью их упрощения используются тождества (2.12)…(2.15).

Операция сложения по модулю 2 (исключающее ИЛИ, логическая неравнозначность) обозначается символом Å и определяется соотношением:

 

.

 

Используя аксиомы алгебры логики, легко убедиться, что

 

0 Å 0 = 1 Å 1 = 0; 1 Å 0 = 0 Å 1 = 1. (2.16)

 

Из этих соотношений следует, что значение x Å y:

- совпадает со значением младшего разряда суммы двух одноразрядных двоичных чисел x и y;

- совпадает с результатом дизъюнкции переменных x и y, за исключением случая, когда две переменные равны 1

- равно 1 когда значения переменных не равны друг другу.

Перечисленные свойства операции x Å y и определяет ее названия. Операция суммирования по модулю 2 коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции:

 

. (2.17)

 

Для операции сложения по модулю два также справедливы следующие тождества:

 

. (2.18)

 

Логические функции. Любое логическое выражение, составленное из n переменных x_n,..., x ₁ с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию n переменных. В соответствии с аксиомами (2.1)…(2.4) функция может принимать в зависимости от значений переменных только два значения: 0 и 1. Такие функции являются весьма удобным инструментом для описания, анализа и синтеза логических схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким (1) и низким (0). В связи с этим логические функции называются переключательными.

Для функций n переменных x_n,..., x ₁ используется общее обозначение F (ν) = F (x_n,..., x ₁), где ν = (x_n,..., x ₁), т.е. совокупность переменных x_n,..., x ₁ можно рассматривать как n -мерный вектор. Так как каждая переменная x_p (р = 1, 2,..., n) может принимать только два значения (0 и 1), то число всех возможных комбинаций значений x_n,..., x ₁ конечно. В общем виде конкретное значение переменной x_p (0 или 1) будем обозначать через e_p.

Областью определения функции n переменных x_n,..., x ₁ является совокупность точек n -мерного пространства, причем каждая из точек задается определенной комбинацией значений этих переменных:

 

x_n = e_n ,..., x_p = e_p ,..., x ₁ = e ₁,

 

где e_р = 0 или 1 (р = 1, 2,..., n).

Обозначим точки, задающие область определения функции F (ν) через

 

ν_i = (e_n,..., e_p,... e ₁).

 

Если представить эту комбинацию значений переменных (e_n,..., e_p,... e ₁) как число, записанное в двоичном коде, то оказывается возможным пронумеровать все точки области определения логической функции с помощью n -разрядных двоичных чисел (e_n ... e_p... e ₁)₂ или с помощью эквивалентных им десятичных чисел i. Так как имеется 2 ⁿ различных n -разрядных двоичных чисел, то область определения функции n переменных будет содержать 2 ⁿ точек:

.

 

Для задания функции F (ν) следует указать ее значения во всех точках области определения, т.е. следует задать значения F (ν _i) = 0 или 1, где i = 0, 1,..., 2 ⁿ – 1. Каждой конкретной функции n переменных можно поставить в соответствие 2 ⁿ -разрядное число, составленное из значений F (ν _i) = 0 или 1, которые она принимает в 2 ⁿ точках области определения. Так как имеется всего различных 2 ⁿ -разрядных двоичных чисел, то и число различных функций n -переменных равно .

Функции n переменных могут зависеть не от всех переменных x_n,..., x ₁. Такие функции называются вырожденными. В частности, функция F ₀(ν), равная нулю, и функция F ₁(ν), равная единице во всех точках ν _i (i = 0, l,..., 2 ⁿ – 1) области определения, не зависят ни от одной переменной. Эти функции называются константой ноль и константой единица соответственно.

Функция n переменных F (ν) называется полностью определенной, если ее значения F (ν _i) = a_i = 0 или 1 заданы во всех 2 ⁿ точках ν _i области определения. Если же значение функции не задано хотя бы в одной точке ν _i, то она называется не полностью определенной. Не определенное в точке ν _i значение функции описывается символом с_i = * или Ф (Ф – совмещенные символы 0 и 1, что указывает на неопределенность значения функции), т.е., если в точке ν _i значение функции не задано, то F (ν _i) = с_i.

Не полностью определенные функции можно доопределять произвольным способом, полагая с_i = 0 или 1. Если значения функции не заданы в m точках, то функцию можно доопределить 2 ^m способами, так как имеется 2 ^m различных m -разрядных двоичных чисел, соответствующих различным способам доопределения функции в m точках. Таким образом, не определенной в m точках функции соответствует группа из 2 ^m полностью определенных функций.

Так как область определения любой функции n переменных конечна (2 ⁿ точек), она может быть задана таблицей значений F (ν _i) = a_i = 0 или 1 (или с_i), которые она принимает в точках ν _i, где i = 0, 1,..., 2 ⁿ – 1. Такие таблицы называются таблицами истинности.

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

Функции двух переменных F (x ₂, x ₁). Область определения таких функций состоит из 4 точек (2 ⁿ = 2² = 4): ν₀ = (0, 0), ν₁ = (0, 1), ν₂ = (1, 0), ν₃ = (1, 1). Общее количество функций двух переменных равно 16 ( . Значения всех возможных функций F (x ₂, x ₁) представлены в таблице 2.1, которая представляет собой совмещенную таблицу истинности функций F ₀… F ₁₅ двух переменных. В левой части таблицы перечислены все возможные сочетания значений переменных и , в правой части приведены значения функций F ₀… F ₁₅ при этих сочетаниях переменных.

 

 

Таблица 2.1 – Таблицы истинности функций двух переменных

 

i

x 2

x 1

F 0

F 1

F 2

F 3

F 4

F 5

F 6

F 7

F 8

F 9

F 10

F 11

F 12

F 13

F 14

F 15

 

Каждая функция F ₀… F ₁₅ обозначает одну из 16 возможных логических операций над двумя переменными x ₁ и x ₂, имеет собственное название и аналитическое описание:

F ₀ = 0 (F ₁₅ = 1) – константа ноль (единица);

– конъюнкция, логическое умножение, И;

( ) – запрет x ₁ (x ₂);

( ) – повторение x ₂ (x ₁);

– неэквивалентность, сложение по модулю 2, исключающее ИЛИ;

– дизъюнкция, логическое сложение, ИЛИ;

– функция Пирса, ИЛИ-НЕ;

– эквивалентность, исключающее ИЛИ-НЕ;

( ) – отрицание x ₁ (x ₂), инверсия x ₁ (x ₂), НЕ;

( ) – импликация x ₁ (x ₂);

– функция Шеффера, И-НЕ.

 

Функции двух переменных исключительно важны в силу того, что любая функция n переменных может быть получена из них методом суперпозиции – подстановкой этих функций вместо переменных в другие функции. Такая подстановка возможна на основании того, что области значений функций и переменных совпадают (0 и 1). Наибольшее применение получили следующие невырожденные функции двух переменных х ₂ и х ₁: F ₁ (конъюнкция, И), F ₆ (сумма по модулю два, исключающее ИЛИ), F ₇ (дизъюнкция, ИЛИ), F ₈ (ИЛИ-НЕ) и F ₁₄ (И-НЕ).

Принцип и закон двойственности. Алгебра логики обладает замечательным свойством, которое называется принципом двойственности: если имеет место тождество F (ν, 0, 1/ &, Ú) = G (ν, 0, 1/ &, Ú), где ν = (x_n,..., x ₁), то справедливо также тождество F (ν, 1, 0/ Ú, &) = G (ν, 1, 0/ Ú, &), т.е., если в каком-либо тождестве произвести взаимную замену символов 0 и 1 (если они имеются) и операций дизъюнкции и конъюнкции, то в результате также будет получено тождество. Два тождества, связанные между собой таким образом, называются двойственными. Истинность самого принципа двойственности не доказывается, так как данный принцип является внутренним свойством алгебры логики (заключен в ее аксиомах).

Законы двойственности (теоремы де Моргана (2.10)) определяют способ отыскания инверсных функций, представляющих собой дизъюнкцию и конъюнкцию двух переменных. К. Шеннон предложил обобщение этих теорем, позволяющее отыскивать инверсию любой функции F (ν). Закон двойственности имеет вид:

 

, (2.19)

 

где ν = (x_n,..., x ₁), , т.е. инверсию любой функции F (ν) можно получить взаимной заменой переменных x_p и их инверсий (р = 1, 2,..., n) и операций дизъюнкции и конъюнкции.

Теоремы разложения. В теории логических функций важное значение имеет теорема разложения: любую функцию F (ν) можно разложить по переменной x_p в форме

 

. (2.20)

 

Теорема легко доказывается методом перебора.

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

 

. (2.21)

 

С теоремами разложения связаны тождества:

 

, (2.22)

 

. (2.23)

 

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

 

, (2.24)

 

где e_р = 0 или 1. Данное символическое обозначение объединяет в одном символе оба первичных терма x_p и . Действительно, при подстановке в (2.24) значений e_р = 0 и 1 получаем:

 

 

Минимальным термом (минтермом, конституентой единицы) называется функция n переменных (конъюнкция первичных термов):

 

, (2.25)

 

где ν = (x_n,..., x ₁), e_р = 0 или 1, i = (e_n... e ₁)₂. Из данного определения следует, что имеется 2 ⁿ различных минтермов n переменных, так как имеется 2 ⁿ различных n -разрядных двоичных чисел i = 0, 1,…, 2 ⁿ– 1.

Минтермы обладают следующими свойствами:

 

(2.26)

 

; (2.27)

 

. (2.28)

 

Свойство (2.26) соответствует тому, что любой минтерм K_i (ν) равен 1 только в одной точке ν _i области определения.

Все минтермы двух переменных и :

 

;

;

;

.

 

Аналогично можно записать минтерм большего числа переменных. Например, пусть n = 4, i = 5 = (0101)₂, тогда

 

.

 

Максимальным термом (макстермом, конституентой ноля) называется функция n переменных (дизъюнкция инверсий первичных термов):

 

, (2.29)

 

где ν = (x_n,..., x ₁), e_р = 0 или 1, i = (e_n... e ₁)₂.

Макстермы обладают следующими свойствами:

 

(2.30)

 

; (2.31)

 

. (2.32)

 

Свойства макстермов могут быть получены из свойств минтермов на основании (2.29). Макстермы – функции, равные 0 только в одной точке ν _i области определения, состоящей из 2 ⁿ точек.

Все макстермы двух переменных и :

 

;

;

;

.

 

Запишем макстерм для n = 4:

 

.

 

Минтермы (макстермы) представляют собой функции, принимающие минимальное (максимальное) значение из значений своих первичных термов , т.е. если хотя бы один из первичных термов равен 0 (1), то и минтерм (макстерм) равен 0 (1).

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

СДНФ – совершенная дизъюнктивная нормальная форма. Теорему разложения (2.20) для функции n переменных можно использовать n раз, т.е. функцию можно разложить по всем n переменным x_p, где р = 1, 2,..., n. В качестве примера разложим функцию F (ν) = F (x ₂, x ₁) двух переменных x ₂ и x ₁. По теореме разложения получим

 

где ν _i = (e ₂, e ₁) – i -я точка области определения, i = (e ₂ e ₁)₂;

– минтерм двух переменных x ₂ и x ₁;

F (ν _i) = a_i = 0 или 1 – значение функции в i -й точке области определения.

Такая форма представления функции двух переменных и называется СДНФ. Разложение функции n переменных будет представлять собой дизъюнкцию 2 ⁿ членов вида :

 

, (2.33)

 

Выражение (2.33) представляет собой СДНФ функции n переменных.

Так как значения функции a_i = 0 или 1, то = 0, если a_i = 0, и , если a_i = 1. Поэтому СДНФ можно представить в виде

 

, (2.34)

 

где i 1 – номера точек области определения, в которых функция F (ν) равна 1.

СДНФ записи функции легко получить по ее таблице истинности. В качестве примера рассмотрим функцию трех переменных x ₃, x ₂ и x ₁, заданной таблицей истинности (таблица 2.2). Из нее следует, что а ₀ = а ₁= а ₄= а ₆= 0, а ₂ = а ₃= а ₅= а ₇= 1, поэтому

 

 

Таблица 2.2 – Таблица истинности функции трех переменных

i	x 3	x 2	x 1	F (ν)

 

СКНФ – совершенная конъюнктивная нормальная форма. Такую форму записи функции n переменных F (ν) можно получить на основании двойственной теоремы разложения (2.21). Однако СКНФ можно получить более простым способом – записав СДНФ инверсии функции . Инверсная функция в каждой точке ν _i области определения имеет инверсные значения по отношению к значениям a_i самой функции, т.е. если F (ν _i) = a_i, то .

Тогда на основании (2.33) СДНФ инверсной функции:

 

.

 

Отсюда на основании закона двойственности (2.19) следует

 

.

 

Используя определение макстермов (2.29) получаем СКНФ представления функции n переменных:

 

. (2.35)

 

Так как значения функции a_i = 0 или 1, то = 1, если a_i = 1, и , если a_i =. Поэтому СКНФ можно представить в виде

 

, (2.36)

 

где i 0 – номера точек области определения, в которых функция F (ν) равна 0.

Для примера рассмотрим функцию трех переменных x ₃, x ₂ и x ₁, заданной таблицей истинности (см. таблицу 2.2). Так как а ₀ = а ₁= а ₄= а ₆= 0, то на основании (2.36) СКНФ функции имеет вид:

 

 

Совершенные нормальные формы в базисах И-НЕ и ИЛИ-НЕ. Совокупность элементарных функций, с помощью которых можно записать любую функцию F (ν), называется функционально полной системой функций или базисом. Из выражений (2.34) и (2.36) следует, что для представления любой функции F (ν) в СДНФ и СКНФ достаточно использовать только операции (функции) И, ИЛИ и НЕ (опрерация НЕ нужна для получения первичных термов , входящих в минтермы и макстермы), т.е. совокупность этих операций является базисом.

Преобразуем СДНФ функции (2.33) с использованием закона двойного отрицания и закона двойственности:

 

, (2.37)

 

Данная форма представления функции называется совершенной нормальной формой (СНФ) в базисе И-НЕ, так как она требует использования только функций И-НЕ.

Преобразуем теперь СКНФ функции (2.35) с использованием закона двойного отрицания и закона двойственности:

 

. (2.38)

 

Данная форма представления функции называется совершенной нормальной формой в базисе ИЛИ-НЕ, так как она требует использования только функций ИЛИ-НЕ.

СНФ функции, рассматриваемой в качестве примера, в базисах И-НЕ и ИЛИ-НЕ будут запишутся в виде:

 

;

 

.

 

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