Компьютерная схемотехника (стр. 3 из 32)
Функция двоичных переменных также равная одному из двух значений (нулю или единице) - называется переключательной (логической) функцией (ПФ).
Логические функции обозначаются прописными буквами F или Y, а двоичные переменные - А, В, С, D, E, ... или строчной буквой икс с индексом, например, x1, х2, х3 ... .
ПФ может быть выражена (задана):
- словесно;
- алгебраическим (булевым) выражением;
- таблицей истинности;
- диаграммой Вейча (картой Карно).
Примеры задания переключательной функции (ПФ):
1) словесно: функция двух переменных принимает значение логической единицы, если обе переменные также равны единице, в противном случае, она равна нулю;
2) выражением:
3) таблицей истинности (таблица 3.1)
Таблица включает наборы (комбинации) логических переменных, которые должны быть упорядочены по возрастанию или убыванию их десятичных эквивалентов, а также значения функции на каждом наборе. Каждый набор имеет номер, равный десятичному эквиваленту двоичного числа, если наборы упорядочены по возрастанию. Если число переменных равно n, то количество наборов N = 2n. Номера наборов изменяются от 0 до (2n-1). Общее число переключательных функций n – переменных
.(3.1)
Таблица 3.1
| № набора | В | А | F |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 |
| 3 | 1 | 1 | 1 |
Представление переключательной функции диаграммой Вейча (картой Карно) будет рассмотрено позднее при изучении вопроса минимизации ПФ.
3.2 Переключательные функции одной переменной (n=1)
Если n=1, то число наборов N=21=2, а количество ПФ
(таблица 3.2)Таблица 3.2
| N набора | A | F0 | F1 | F2 | F3 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
Функция F0 называется константой нуля, так как на всех наборах принимает нулевое значение (F0=0). Функция F3 - константа единицы, так как всегда равна единице (F3=1). Функция F2=A называется повторением, а
– инверсией (отрицанием – не А).3.3 Переключательные функции двух переменных (n=2)
Если n=2, то число наборов N=22 =4, а количество ПФ
(таблица 3.3)Отметим из этих шестнадцати функций 2-х переменных наиболее часто использующиеся:
F0 – константа нуля;
F15 – константа единицы;
F8=А 
В=А*В – конъюнкция (логическое умножение (логическое “И”));
F14=А 
В=А+В – дизъюнкция (логическое сложение (логическое “ИЛИ”));
F6= 
– исключающее ИЛИ (сумма по модулю два, неравнозначность, неэквивалентность);
– равнозначность (эквивалентность); 
– ИЛИ-НЕ; 
– И - НЕ.Таблица 3.3
| № набора | В | А | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 2 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3.4 Базисные логические функции
Любую логическую функцию можно представить совокупностью элементарных логических функций: дизъюнкцией, конъюнкцией, инверсией или их суперпозицией. Набор элементарных функций ИЛИ, И, НЕ называют функционально полным или базисным (базисом). Кроме того существуют еще два базиса: И-НЕ; ИЛИ-НЕ.
3.5 Принцип двойственности булевой алгебры
Если в выражении F8=А 
В конъюнкцию заменить на дизъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции
. Аналогично, если в выражении F14=А 
В дизъюнкцию заменить на конъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции 
.Указанные свойства логических функций отражают принцип двойственности булевой алгебры.
3.6 Основные тождества булевой алгебры
А+0=А;А+1=1;
А+А=А;А+ 
=1;
А*0=0;А*1=А;
А*А=А;А* =0; 
=А.
3.7 Основные законы и теоремы булевой алгебры
Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.
Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).
Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).
Поглощения: А+А*В=А; А*(А+В)=А.
Склеивания:
Де Моргана. Существует две формы записи теоремы де Моргана:
Форма 1:
(3.1.1)Форма 2:
(3.1.2)Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).
Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:
(3.1.3)Два полезных соотношения:
(3.1.4)
3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений
СДНФ является одной из аналитических форм представления переключательных функций. Булевы выражения простых логических функций можно записать по их словесному описанию. В общем случае для получения аналитической формы (булевого выражения) используют таблицы истинности.
Предположим, логическая функция трех переменных задана таблицей истинности (таблица 3.4).
Таблица 3.4
| №набора | С | В | А | F |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 0 |
Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы – это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера
; 
.Булево выражение ПФ в СДНФ представляет сумму конституент единицы:
.(3.2)
Поскольку конституенты единицы записываются в виде конъюнкций, то СДНФ представляет сумму конъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде не более одного раза. Очевидно, что логическая функция имеет единственное булево выражение в СДНФ, что следует из методики его получения.