N = 2n. (1.1)
Число же всевозможных логических функций тогда можно рассчитать по формуле
M = 2N = . (1.2)
Как видно из формулы (1.2), число булевых (логических) функций быстро растёт с увеличением числа аргументов n. Так, при n =2 получим N=22=4, а М=24=16, т.е. шестнадцать логических функций от двух аргументов.
В табл. 1.3 приведены названия и обозначения функций, их значения на том или ином наборе значений аргументов a и b, а также алгебраические выражения этих функций в дизъюнктивной совершенной нормальной форме (ДСНФ) и конъюнктивной совершенной нормальной форме (КСНФ).
Из анализа этой таблицы следует, что среди множества приведённых функций есть функции-константы «нулевая» и «единичная», функции «повторения» и «инверсии» (функции НЕ) входных переменных a и b, фактически являющиеся функциями одного аргумента, и есть функции, которые существенно зависят от двух аргументов.
В приведённых алгебраических выражениях знаком + (плюс) обозначена операция логического сложения (дизъюнкции), чертой над переменной или над логическим выражением обозначена операция инверсии, а символы логического умножения (произведения) пропущены.
Таблица 1.3
Логические функции двух аргументов
|
№ п/п |
Название функции |
Значения функции при значениях аргументов |
Обозначение |
Алгебраические формы функций |
|||||
|
а b |
0 |
0 |
1 |
1 |
ДСНФ |
КСНФ |
|||
|
0 |
1 |
1 |
0 |
||||||
|
V0 |
Нулевая |
0 |
0 |
0 |
0 |
0 |
- |
||
|
V1 |
Запрет b |
0 |
0 |
0 |
1 |
a¬b |
|
||
|
V2 |
Конъюнкция (И) |
0 |
0 |
1 |
0 |
a&b или ab |
ab |
||
|
V3 |
Повторение а |
0 |
0 |
1 |
1 |
а |
|||
|
V4 |
Запрет а |
0 |
1 |
0 |
0 |
b¬a |
|
||
|
V5 |
Неравнозначность |
0 |
1 |
0 |
1 |
aÅb |
|
|
|
|
V6 |
Повторение b |
0 |
1 |
1 |
0 |
b |
|||
|
V7 |
Дизъюнкция (функция ИЛИ) |
0 |
1 |
1 |
1 |
a+b |
|
a+b |
|
|
V8 |
Пирса (ИЛИ-НЕ) |
1 |
0 |
0 |
0 |
|
|
||
|
V9 |
Инверсия b (НЕ ) |
1 |
0 |
0 |
1 |
|
|||
|
V10 |
Равнозначность |
1 |
0 |
1 |
0 |
|
|
|
|
|
V11 |
Импликация b |
1 |
0 |
1 |
1 |
b®a |
|||
|
V12 |
Инверсия а |
1 |
1 |
0 |
0 |
|
|||
|
V13 |
Шеффера (И-НЕ) |
1 |
1 |
0 |
1 |
||||
|
V14 |
Импликация а |
1 |
1 |
1 |
0 |
a®b |
|||
|
V15 |
Единичная |
1 |
1 |
1 |
1 |
1 |
- |
||
Функции-константы фактически выражают независимость от аргументов и, в то же самое время, их можно считать «функциями» от большого числа аргументов. Обратите внимание, нулевая функция не имеет ДСНФ, поскольку она никогда не принимает значение лог.1, а единичная функция не имеет КСНФ, так как она никогда не принимает значение лог.0. Отсюда следует вывод, что ДСНФ соответствует описанию (заданию) логических функций по условиям истинности (по лог.1), а КСНФ - по условиям ложности (по лог.0). Любая логическая функция, кроме функций-констант, имеет как ДСНФ, так и КСНФ. Это соответствует тому, что любое логическое устройство (сколь сложно оно ни было бы) можно описать по условиям срабатывания и по условиям несрабатывания.
Значения функций «повторения» и «инверсии» (V3, V6, V9, V12) либо повторяют значения одного из аргументов, либо принимают противоположные (инверсные) ему значения. Поэтому они и получили такие названия.
Функции инверсии чаще всего называют функциями НЕ. Эти функции реализуются логическими элементами НЕ (или инверторами). Функции повторения реализуются повторителями. Принято говорить, что функции инверсии и повторения «несущественно» зависят от второго аргумента, хотя их можно представить как функции двух, трёх и большего числа аргументов.
В технике функции «Неравнозначности» и «Равнозначности» более известны под названиями «сумма по модулю два (по mod 2)» и «инверсия суммы по mod 2» соответственно. Функции Шеффера и Пирса, соответственно, известны под названиями «инверсия логического произведения» (функции И-НЕ) и «инверсии логической суммы» (ИЛИ-НЕ). Эти функции реализуются одноимёнными по названию логическими элементами.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
