Цифровые и логические устройства, страница 2

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

Приведем определения и тождества алгебры логики. Определены три логические операции.

 0  1

 1  0

1. Инверсия (отрицание, не). Обозначения: .

Операция определена таблицей справа.

Инверсия есть унарная операция (один операнд).

 0  0  1  1

 

 0  1  0  1

 0  0  0  1

2. Логическое умножение (и, and, конъюнкция).
Обозначения: , . Определение задано таблицей справа. Эта операция совпадает с арифметическим умножением двух двоичных цифр.

  

 0  0  1  1

  

 0  1  0  1

 0  1  1  1

3. Логическое сложение (или, or, дизъюнкция). 
Обозначения: . Определение задано таблицей. Эта операция отличается от обычного арифметического сложения двух двоичных цифр только для последнего набора. Две единицы при обычном сложении дают двоичное число 10, содержащее 2 разряда.

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

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

Логические тождества приведены в таблице.

1

двойное отрицание

2

3

4

операции с константами

5

коммутативность

6

ассоциативность

7

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

8

дуальность, равенства де Моргана

9

«поглощение»

10

«склеивание»

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

8.1.3.  Полные наборы операций

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

1. Две операции, инверсия и умножение. Тогда сложение реализуется с помощью равенства де Моргана. .

2. Две операции, инверсия и сложение. Тогда .

3. Одна операция, "и-не", операция Шеффера – . Эта операция в силу важности имеет свое название и стандартное обозначение в виде косой черты между операндами (штрих Шеффера).  .  Выразим три логические операции с помощью операции Шеффера.  ; .

4. Одна операция, "или-не", операция Пирса – . Эта операция тоже имеет свое обозначение в виде стрелки между операндами (стрелка Пирса), . Выразим три логические операции через операцию Пирса. ; .

8.1.4.  Функции двух переменных.

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