Храбров Е. А. 2 page

Логическая функция может быть задана четырьмя способами:

1) словесно (описанием ситуации);

2) алгебраическим выражением;

3) таблицей истинности;

4) электрической схемой, состоящей из контактов переключателей.

Например:

1. Лифт можно вызвать, если закрыты двери лифта на первом этаже и на втором этаже и на третьем этаже.

2. Если закрытые двери на первом этаже обозначить как А = 1, на втором как В = 1, на третьем как С = 1, возможность вызвать лифт обозначить как F = 1, а логическую функцию И обозначить знаком умножения "×", то алгебраическое выражение будет иметь вид:

F = A×B×C

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

А В С F

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

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

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

4.1. ФУНКЦИИ булева базиса И, ИЛИ, НЕ

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

Возможные виды алгебраической записи функции И:

F = A & B; F = A ^ B; F = A x B; F = A × B; F = AB.

Контактная схема для функции И для двух переменных A и B:

Таблица истинности функции 2И:

А В F

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

0 0 0

0 1 0

1 0 0

1 1 1

Условное графическое обозначение (УГО) в отечественных схемах логического элемента, реализующего функцию И:

В зарубежных схемах логический элемент И (AND – gate) обозначают следующим образом:

– старое обозначение:
– новое американское обозначение:
– новое европейское обозначение:

Наиболее часто встречаются следующие названия и буквенные обозначения функции ИЛИ: логическое сложение, дизъюнкция, OR, ИЛИ.

Алгебраическая запись функции ИЛИ: F = A v B; F = A + B.

Контактная схема для функции 2ИЛИ:

Таблица истинности функции 2ИЛИ: А В F

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

0 0 0

0 1 1

1 0 1

1 1 1

Условное графическое обозначение логического элемента, реализующего функцию ИЛИ в отечественных схемах:

В зарубежных схемах логический элемент ИЛИ (OR – gate) обозначают следующим образом:

– старое обозначение:
– новое американское обозначение:
– новое европейское обозначение:

Наиболее часто встречаются следующие названия и буквенные обозначения функции НЕ: логическое отрицание, инверсия, дополнение, NOT, НЕ.

Возможные виды алгебраической записи функции НЕ:

F = ù A; F = A¢, F =`A.

Контактная схема для функции НЕ:

Таблица истинности функции НЕ:

А F

–––––––

0 1

1 0

Условное графическое обозначение (УГО) логического элемента, реализующего функцию НЕ в отечественных схемах:

В зарубежных схемах логический элемент НЕ (NOT) обозначают следующим образом:

– старое обозначение:
– новое американское обозначение:
– новое европейское обозначение:

4.2. Инвертирующие базисы, ОТРИЦАТЕЛЬНАЯ ЛОГИКА.

Три вышеописанные логические функции И, ИЛИ, НЕ, с помощью которых можно получить все остальные логические функции, называют булевым базисом.

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

Элемент И–НЕ называют также: штрих Шеффера (Sheffer stroke), NAND (сокращение от NOT AND).

Алгебраическая запись функции И–НЕ: F = A ½ B; F = A B.

Контактная схема для функции И–НЕ для двух переменных A и B:

Таблица истинности функции 2И–НЕ:

А В F

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

0 0 1

0 1 1

1 0 1

1 1 0

Условное графическое обозначение (УГО) логического элемента, реализующего функцию И–НЕ в отечественных схемах:

В зарубежных схемах логический элемент И–НЕ обозначают следующим образом:

– старое обозначение:
– новое американское обозначение:
– новое европейское обозначение:

Элемент ИЛИ–НЕ называют также: стрелка Пирса (Pierce arrow), NOR (сокращение от NOT OR).

Алгебраическая запись функции ИЛИ–НЕ:

F = A ¯ B; F = A + B.

Контактная схема для функции 2ИЛИ–НЕ:

Таблица истинности функции 2ИЛИ–НЕ:

А В F

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

0 0 1

0 1 0

1 0 0

1 1 0

Условное графическое обозначение (УГО) логического элемента, реализующего функцию ИЛИ–НЕ в отечественных схемах:

В зарубежных схемах логический элемент ИЛИ–НЕ обозначают следующим образом:

– старое обозначение:
– новое американское обозначение:
– новое европейское обозначение:

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

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

Это можно проиллюстрировать следующим образом:

– в положительной логике: в комнате зимой Т епло, если батареи отопления В ключены И окна З акрыты (Т = ВЗ);

– в отрицательной логике: в комнате зимой НЕ Т епло, если батареи отопления НЕ В ключены ИЛИ окна НЕ З акрыты (` Т = ` В + ` З).

Здесь И переходит в ИЛИ когда входные аргументы и вывод отрицаются, при этом смысл выражения практически не меняется.

Благодаря этому переходу от И к ИЛИ и удается с помощью однотипных элементов инвертирующего базиса получать все остальные логические функции. Об этом говорят два постулата де 'Моргана:

АВ = `А + `В; А + В = `А`В.

Если логический элемент в положительной логике реализует функцию И, то в отрицательной логике этот же элемент реализует функцию ИЛИ, и наоборот, логический элемент ИЛИ положительной логики реализует функцию И в отрицательной логике.

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

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

НЕ
И:
ИЛИ:

Приведенные на этих рисунках построения логических функций НЕ, И, ИЛИ выполнены с помощью только логических элементов 2И–НЕ.

4.3. СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ (СДНФ и СКНФ) ЗАПИСИ БУЛЕВЫХ ВЫРАЖЕНИЙ.

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

F = `A`В`С + `А В`С + А В`С + А В С.

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

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

F = (`А + В +`С) (`А + В + С) (А +`В + С) (А + В + С).

Так же, как и СДНФ, СКНФ является явно избыточной.

4.4. ПРЕОБРАЗОВАНИЕ ТАБЛИЦЫ ИСТИННОСТИ В БУЛЕВО ВЫРАЖЕНИЕ

Допустим, имеется логическая функция F для трех переменных А, В и С, заданная в виде следующей таблицы истинности:

№ А В С F Примечания

0 0 0 0 1 Р₀ = `А`В`С

1 0 0 1 0

2 0 1 0 1 Р₂ = `А В`С

3 0 1 1 1 Р₃ = `А В С

4 1 0 0 0

5 1 0 1 0

6 1 1 0 0

7 1 1 1 1 Р₇ = А В С

Из всех возможных восьми комбинаций входных переменных А, В и С данная функция F равна единице только для тех четырех комбинаций, которые записаны в виде логических произведений P₀, P₂, P₃ и P₇ в правой части таблицы, в разделе примечания. При остальных наборах входных переменных функция F равна нулю. Смысл каждого булева выражения в том, чтобы показать при каких сочетаниях входных переменных или их инверсий заданная функция F равна единице. Поскольку функция будет иметь такое значение при любом из наборов Р₀, Р₂, Р₃, Р₇ независимо друг от друга, то их можно соединить между собой знаком ИЛИ, логическим сложением:

F = Р₀ + Р₂ + Р₃ + Р₇.

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

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

Р₀ = `А`В`С; Р<sub>2</sub> = `А В`С; Р<sub>3</sub> = `А В С; Р₇ = А В С.

Исходя из этого, получаем результирующее выражение:

F = `А`В`С + `А В`С +`А В С + А В С.

Как можно заметить, это выражение записано в СДНФ.

4.5. ОСНОВНЫЕ ЗАКОНЫ БУЛЕВОЙ АЛГЕБРЫ И ПРАВИЛА ПРЕОБРАЗОВАНИЙ.

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

А + В = В + А АВ = ВА

(А + В) + С = (А + С) + В (АВ)С = (АС)В

А(В + С) = АВ + АС А + (ВС) = (А + В)(А +С)

А + В = `А ×`ВА × В = `А +`В

А + А = АА А = А

А = АА +`АВ = А + В

А + АВ = АА×(А + В) = А

А +`А = 1А ×`А = 0

А + 0 = А А × 0 = 0

А + 1 = 1 А × 1 = А

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

4.6. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ АЛГЕБРАИЧЕСКИМ СПОСОБОМ И ПО КАРТАМ КАРНО

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

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

А + А +...= А; АВС + АВС +...=АВС;

А А А... = А; АВС АВС... = АВС.

2. Умножение членов уравнения на сумму А +`А = 1, или сложение их с А ×`А = 0.

3. Использование выражений, которые в предыдущем разделе подчеркнуты.

Пример минимизации логической функции алгебраическим способом:

F = `А В С + А`В С + А В`С + А В С =

= `А В С + А`В С + А В`С + А В С + А В С + А В С =

добавили

= `А В С + А В С + А`В С + А В С + А В`С + А В С =

= (А +`А) В С + (В +`В) А С + (С +`С) А В =

= А В + В С + А С.

Для минимизации логических функций очень удобно пользоваться картами Карно или очень схожими с ними диаграммами Вейча.

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

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

Таблица истинности для четырех переменных включает 16 строк, следовательно, карта Карно должна состоять из 16 клеток, как показано на рис.4.10.1.

`А`В `А В А В А`В

`С`D 1 1

`C D 1 1

C D 1 1

C`D

Рис.4.10.1. Пример карты Карно для 4–х переменных.

У карты Карно для четырех переменных клетки крайнего левого столбца должны рассматриваться как соседние для клеток крайнего правого столбца, а клетки верхней строки, – как соседние для клеток нижней строки. Другими словами можно сказать, что эта карта расположена на поверхности цилиндра (склеили правый край карты с левым), изогнутого и растянутого так, что его верхний срез соединяется с нижним срезом; при этом цилиндр превращается в тор.

Правила упрощения заполненной карты Карно заключаются в следующем:

– соседние две, четыре, восемь, или другое число единиц, равное степени двойки, обводят общим контуром;

– контур должен быть прямоугольным без изгибов или наклонов;

– каждый контур превращает все входящие в него единицы в одну, т.е. объединенные таким образом слагаемые СДНФ булева выражения дают одно слагаемое в упрощенном выражении;

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

Примеры упрощения булевых выражений с помощью карты Карно для 4–х переменных:

1. F1 = `А В`С`D<sub>1</sub> + A B`C`D<sub>2</sub> +`A B`C D<sub>3</sub> + A B`C D₄ +

+ `A`B C`D<sub>5</sub> + `A B C`D₆.

`А`В `А В А В А`В

`С`D 1₁ 1₂ B`C _1,2,3,4

`C D 1<sub>3</sub> 1<sub>4</sub> `A C`D _5,6

C D

C`D 1₅ 1₆

F1 = B C + `A C`D

Рис.4.10.2. Пример минимизации булевой функции F1 с помощью карты Карно для 4–х переменных.

В первом примере минимизации булевой функции F1 нижний контур из двух единиц 1₅ и 1₆ , соответствующие пятому и шестому слагаемым в исходном булевом выражении, дает возможность опустить B и`B. После этого в нем остается произведение `A C`D. В верхнем контуре из четырех единиц 1<sub>1</sub>, 1<sub>2</sub>, 1<sub>3</sub> и 1<sub>4</sub>, соответствующие первым четырем слагаемым в исходном булевом выражении попарно опускаются A и`A, D и`D, так что в результате этого верхний контур дает произведение B C.

.F2 =`А`В`С`D₁ +`A B`C`D<sub>2</sub> + A B`C`D<sub>3</sub> +`A`B C`D₄ +`AB C`D₅

`А`В `А В А В А`В

`С`D 1₁ 1₂ 1₃ B`C`D _2,3

`C D `A`D _1,2,4,5

C D

C`D 1₄ 1₅

F2 =`A`D + B`C`D

Рис.4.10.3. Пример минимизации булевой функции F2 с помощью карты Карно для 4–х переменных.

Во втором примере минимизации булевой функции F2 контур из двух единиц 1₂ и 1₃ , соответствующие второму и третьему слагаемым в исходном булевом выражении, дает возможность опустить А и`А. После этого в нем остается произведение B`C`D. В контуре из четырех единиц 1<sub>1</sub>, 1<sub>2</sub>, 1<sub>4</sub> и 1<sub>5</sub>, соответствующие другим четырем слагаемым из исходного булева выражения, попарно опускаются В и`В, С и`С, так что в результате этого верхний контур дает произведение `A`D. Карта Карно представляется в данном случае свернутой в цилиндр, в котором верхний край совмещается с нижним.

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

Таблица истинности для пяти переменных включает 32 строки, следовательно, карта Карно должна состоять из 32 клеток, как показано на рис.4.10.4. Для шести переменных карта Карно содержит 64 клетки, как показано на рис.4.10.5.

Пример упрощения булевых выражений с помощью карты Карно для 5–ти переменных:

3. F3 = `А`В`С`D E₁ +`A`B`C D E₂ +

+`A`B C`D`E₄ +`A B C`D`E<sub>5</sub> +`A B C D E₆ +

+`А В С D`E₇ +`A B`C D E₈ +`A B`C D`E₉ +

+ A B`C D E<sub>10</sub> + A B`C D`E₁₁ + A B C D E₁₂ +

+ А В С D`E<sub>13</sub> + A`B`C`D E₁₄ + A`B`C D E₁₅.

`А`В`C `А`В C `А В C `А В`C А В`C А В C А`В C А`В`C

`А`В`C `А`В C `А В C `А В`C А В`C А В C А`В C А`В`C

`D`E 1₄ 1₅

`D E 1₁ 1₁₄

D E 1₂ 1₆ 1₈ 1₁₀ 1₁₂ 1₁₅

D`E 1₇ 1₉ 1₁₁ 1₁₃

`A C`D E _4,5 B D _{6,7,8,9,10,11,12,13}

`B`C E _1,2,14,15

F3 = `B`C E _1,2,14,15 +``A C`D E _4,5 + B D _{6,7,8,9,10,11,12,13}

Рис.4.10.4. Пример минимизации булевой функции F3 с помощью карты Карно для 5–ти переменных.

Пример упрощения булевых выражений с помощью карты Карно для 6–ти переменных:

4. F4 = `А`В`С`D E`G <sub>1</sub> +`A`B`C D E`G <sub>2</sub> +`A`B C`D E`G ₃ +

+`A`B C D E`G <sub>4</sub> +`A B C`D E G <sub>5</sub> +`A B C`D`E G ₆ +

+`А В`С`D`E`G <sub>7</sub> +`A B`C`D E`G <sub>8</sub> +`A B`C D E`G ₉ +

+`A B`C D`E`G ₁₀ +`A B`C D`E G <sub>11</sub> +`A B`C D E G ₁₂ +

+`А В`С`D E G <sub>13</sub> +`A B`C`D`E G <sub>14</sub> + A B`C`D`E`G ₁₅ +

+ A B`C`D E`G <sub>16</sub> + A B`C D E`G <sub>17</sub> + A B`C D`E`G ₁₈ +

+ А В`С D`E G ₁₉ + A B`C D E G <sub>20</sub> + A B`C`D E G ₂₁ +