43

УДК 519

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

––––––––––––––

МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

––––––––––––––––––––––

Кафедра “Персональные компьютеры и сети”

БУЛЕВА АЛГЕБРА

Учебное пособие

по курсу

дискретная математика

Москва

2003

СОДЕРЖАНИЕ

Введение 3

Аксиомы и законы булевой алгебры 4

Аксиомы булевой алгебры 4

Законы булевой алгебры 5

Приоритеты логических операций 8

Функции алгебры логики 9

Формы задания функций алгебры логики 9

Полином Жегалкина 17

Классы логических функций 18

Теорема о функциональной полноте 21

Минимизация функций алгебры логики 24

Правила склеивания 27

Правило поглощения 28

Правило развертывания 28

Этапы минимизации ФАЛ 30

Расчетный метод 30

Табличный метод 33

Литература 42

Введение

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

Логика - это наука о законах и формах мышления, математическая же логика занимается применением формальных математических методов для решения логических задач.

В цифровых устройствах чрезвычайно широко используется простейший раздел математической логики - исчисление высказываний или алгебра логики. Алгебру логики часто называют булевой алгеброй в честь английского математика Джоржа Буля, который в 1847 году опубликовал краткую брошюру “Математический анализ логики, сопровождаемый наброском исчисления дедуктивных рассуждений”, а в 1854 году вышел его основной труд “Исследование законов мысли, на которых основаны математические теории логики и вероятностей”.

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

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

Аксиомы и законы булевой алгебры

Булеву алгебру как математическую структуру представляют совокупностью следующих объектов:

БА=(0, 1, x_i, И, ИЛИ, НЕ, =), (1)

где 0 - символ, обозначающий абсолютную ложь (константа”0”),

1 - символ, обозначающий абсолютную истину (константа “1”).

Примечание: здесь 0 и 1 не цифры!

x_i - i-я логическая переменная, от которой зависит какая-либо логическая функция.

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

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

НЕ - одноместная логическая операция, определяемая как логическое отрицание (другое название - инверсия).

= - отношение эквивалентности.

Аксиомы булевой алгебры

Объекты (1) булевой алгебры определяются следующими аксиомами:

1. x= 0, если x не равно 1.

x = 1, если x не равно 0.

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

2. а) 0^.0 = 0, б) 1+1 = 1,

0^.1 =1^.0 = 0, 1+0 = 0+1 = 1,

1^.1 = 1. 0+0 = 0.

Аксиомы 2,а определяют логическую операцию И. В качестве знака операции И кроме точки используются знаки: отсутствие знака, &, ^ .

Аксиомы 2,б определяют логическую операцию ИЛИ. В качестве знака операции ИЛИ кроме + используются знаки V.

3.

Аксиома 3 определяет операцию логического отрицания.

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

1) рефлексивности: x = x;

2) симметричности: если x₁ = x₂, то x₂ = x₁;

3) транзитивности: если x₁ = x₂ и x₂ = x₃, то x₁ = x₃.

Из свойств отношения эквивалентности следует принцип подстановки: если x₁ = x₂, то в любом логическом выражении, содержащем x₁, вместо x₁ можно подставить x₂ и в результате будет получено эквивалентное выражение.

Законы булевой алгебры

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

Основные законы алгебры логики принято разбивать на три группы.

1. Законы одинарных элементов:

а) законы универсального множества:

x^.1 = x, x+1 = 1.

б) законы нулевого множества:

x^.0 = 0, x+0 = x.

2. Законы отрицания:

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

б) законы дополнительности:

^. = 0, x+ = 1.

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

,

3. Комбинационные законы:

а) Законы тавтологии (идемпотентности):

xxx...x = x, x+x+...+x = x.

Отсюда следует, что булева алгебра является алгеброй без степеней и коэффициентов.

б) Переместительные законы (коммутативные):

x₁x₂ = x₂x_1, x₁+x₂ = x₂+x₁.

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

x₁x₂x₃ = (x₁x₂) x₃ =(x₁x₃) x₂ = (x₂x₃) x₁,

x₁+x₂+x₃ = (x₁+x₂)+x₃ = (x₁+x₃)+x₂ = (x₂+x₃)+x₁.

г) Распределительные законы (дистрибутивные):

Первого рода - умножение относительно сложения:

x₁(x₂+x₃) = x₁x₂+x₁x₃.

Второго рода - сложение относительно умножения:

x₁+x₂x₃ = (x₁+x₂)(x₁+x₃).

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

Обратите внимание, что аксиомы 2 записаны с учетом закона двойственности. Если в любой строке одного из столбцов произвести взаимную замену 0 и 1 и операций И и ИЛИ, то получим аксиому в этой же строке другого столбца.

Совокупность конкретных значений логических переменных, от которых зависит булева функция, называется набором логических переменных. Если булева функция зависит, например, от трех переменных x₂,x₁ и x₀, тогда x₂ = 0, x₁ = 1, x₀ = 1 является набором. Наборы могут быть представлены различными способами. Указанный выше набор можно представить как ,x₁,x₀, где знак инверсии говорит о том, что x₂ = 0, а отсутствие знака инверсии - x₁ = x₀ = 1. Тот же набор можно представить как 0,1,1 или просто 011. Рассматривая последнее представление как двоичное число, можно записать его в виде десятичного эквивалента 3 = 0^.2²+1^.2¹+1^.2⁰. Отсюда видно, что логическим переменным, как и разрядам двоичного числа, можно условно присвоить “веса”: для x₀ вес будет 2⁰ = 1, для x₁ - 2¹ = 2, для x₂ - 2² = 4 и т.д. Именно поэтому логические переменные удобно обозначать индексированными буквами, начиная с индекса 0 для младшей переменной, 1 для следующей переменной и т.д. до индекса п-1, если функция зависит от n переменных. При таком обозначении индекс переменной совпадает с показателем степени основания двоичной системы счисления, т.е. характеризует вес переменной. Так для переменной x₅ вес будет равен 2⁵ = 32.

Если функция алгебры логики зависит от n переменных, то всего для них существует 2ⁿ наборов, так как добавление одной переменной увеличивает число наборов в два раза. Одна переменная имеет два набора: 0 и 1, две переменные - четыре: 0 = 00, 1= 01, 2 =10, 3 = 11 и т.д. Десятичный эквивалент набора логических переменных называется номером набора.

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

Вес набора удобно изображать римскими цифрами, так для n = 3 имеем: набор 000 с весом 0; наборы 001, 010, 100 с весом I; наборы 011, 101, 110 с весом II и набор 111 с весом III.

Если наборы рассматривать как их десятичные эквиваленты, то для любых двух наборов можно ввести естественную или лексикографическую упорядоченность или отношение порядка (<).

Аксиомы отношения порядка:

рефлексивность: Хi < Хj;

антисимметричность: если Хi< Хj и Хj < Хi, то Хi = Хj;

транзитивность: если Хi < Хj, а Хj < Хk, то Хi < Хk.

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

Рассмотрим два набора переменных Х' = ( '_n-1,..., '_i,..., '₀) и Х'' = ( ''_n-1,..., ''_i,..., ''₀), где '_i и ''_i это одна и та же переменная _i, входящая соответственно в наборы Х' и Х'', таких, что удовлетворяется неравенство для всех i, т.е. x'₀ x''₀; x'₁ x''₁; x'₂ x''₂ и т.д.

Тогда говорят, что для наборов выполнено отношение предшествования Х' Х''. Например, для n = 3 010 110.

Не все пары наборов находятся в отношении предшествования, например, 010 и 101, наборы одного веса 001 и 100 и др. Поэтому наборы в отношении предшествования являются лишь частично упорядоченными. Те, для которых отношение предшествования не выполняется, называются несравнимыми.

Логическое произведение (конъюнкция) любого числа переменных из конечного набора n переменных называется элементарным (элементарной), когда сомножителями в нем являются либо переменные, либо их отрицания. Например, является элементарным произведением, а ( ₃+x₂) ₀ и не являются элементарными.