Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
П.4.4. Булевы функции.
|
|
Функцией логических переменных X1, X2, …, Xn (булевой функцией) называется выражение:
,
полученное путём инверсии, сложения и умножения исходных логических переменных.
Для каждого n ≥ 0 может быть получено ровно 2(2n) различных булевых функций. Так, функцией одной переменной (n = 1) являются всего четыре:
Y0 = 0; Y1 = X; Y2 = X; Y3 = 1.
В табл.4.1 представлены все функции двух переменных. Из них наиболее важными для технических применений являются функции отрицания произведения (И – НЕ), отрицания суммы (ИЛИ – НЕ)*, логического произведения (И), логического сложения (ИЛИ), инверсии (НЕ) и повторения.
* С точки зрения общепринятой в математике терминологии следовало бы применять обозначения НЕ – ИЛИ вместо ИЛИ – НЕ и Не – И вместо И – НЕ.
Перечисленные функции реализуются в серийно выпускаемых логических микросхемах малой степени интеграции.
Таблица П.4.1
Булевы функции двух логических переменных
| X0 X1 | 1 0 1 0 | Наименование функций | Алгебраические формулы функций |
| Y0 | 1 1 0 0 | Константа нуль | Y0 = 0 |
| Y1 | 0 0 0 1 | Отрицание суммы (операция Пирса, ИЛИ – НЕ) | Y1 = X1 + X0 |
| Y2 | 0 0 1 0 | Запрет по X1 | Y2 = X1 X0 |
| Y3 | 0 0 1 1 | Инверсия Х1 (функция НЕ) | Y3 = X1 |
| Y4 | 0 1 0 0 | Запрет по Х0 | Y4 = X1 X0 |
| Y5 | 0 1 0 1 | Инверсия Х0 (функция НЕ) | Y5 = X0 |
| Y6 | 0 1 1 0 | Неэквивалентность (исключающие ИЛИ) | Y6 = X1 X0 + X1 X0 |
| Y7 | 0 1 1 1 | Отрицание произведения (операция Шеффера, И – НЕ) | Y7 = X1 X0 |
| Y8 | 1 0 0 0 | Логическое произведение (конъюнкция, функция И) | Y8 = X1 X0 |
| Y9 | 1 0 0 1 | Эквивалентность | Y9 = X1 X0 + X1 X0 |
| Y10 | 1 0 1 0 | Повторение Х0 | Y10 = X0 |
| Y11 | 1 0 1 1 | Импликация Х1 и Х0 | Y11 = X1 + X0 |
| Y12 | 1 1 0 0 | Повторение Х1 | Y12 = X1 |
| Y13 | 1 1 0 1 | Импликация Х0 и Х1 | Y13 = X1 + X0 |
| Y14 | 1 1 1 0 | Логическое сложение (дизъюнкция, ИЛИ) | Y14 = X1 + X0 |
| Y15 | 1 1 1 1 | Константа единица | Y15 = 1 |
Булевы функции заданы в табл.4.1 двумя способами: с помощью таблиц истинности и с помощью алгебраических выражений. В таблицах истинности (называемых также таблицами задания) каждому набору аргумента X0 и X1 задано значение функции Yi. В общем случае таблицы истинности полностью определяют значение любой булевой функции, поскольку в них указываются значения функции для всех 2n возможных наборов аргументов (n – число аргументов заданной функции). Однако при n ≥ 5 таблицы истинности становятся громоздкими и употребляются редко. Алгебраические формулы позволяют получить компактную запись булевых функций с помощью операций инверсии, сложения и умножения.
Переход от таблицы истинности к алгебраическому выражению может быть осуществлён путём формирования алгебраической формулы в виде суммы произведений аргументов или их инверсий, называемой дизъюнктивной нормальной формой (ДНФ) булевой функции. Для получения ДНФ необходимо для каждого единичного значения функции, заданного в таблице истинности, сформировать произведение аргументов и их инверсий по правилу: в формируемое произведение ставится сам аргумент, если его значение в таблице истинности равно единице, но ставится инверсия, если значение аргумента в таблице истинности равно нулю. ДНФ формируется в виде полученных таким образом произведений.
Пример П.4.2. Записать по таблице истинности выражение функции Y9 из табл.П.4.1.
Решение. Единичным значением функции Y9 соответствуют два набора аргументов:
1) X0 = 1, X1 = 1;
2) X0 = 0, X2 = 0.
Следовательно, ДНФ функции Y9 должна иметь вид:
Y9 = X1 X0 + X1 X0.
Полученные ДНФ следует по возможности упростить, применяя операции склеивания и поглощения. Рекомендуем получить по таблице истинности выражение функций Y5 и Y14 (см. табл.П.4.1) и упростить их до выражений, приведённых в табл.П.4.1.
Любой аргумент булевой функции сам может быть сколь угодно сложной булевой функцией.