Логические функции одной и двух переменных

Рассмотрим элемент с одним дискретным входом X и одним дис­кретным вы­ходом Y. Какими нетривиальными функциями может обладать этот «черный ящик»? Составим комбинационную таблицу.

Таблица 6

x	y 0	y 1	y 2	y 3	Рис. 4

Из табл. 6 видно, что нулевой набор (0) и единичный набор (3) не зависят от изменения X, следовательно, это либо «обрыв» связей между X и Y, либо «корот­кое замыкание» выхода Y на источник питания (всегда на выходе 1 независимо от значений Х). Набор (1) повторяет X, и только набор (2) интересен. Для него Y = , т.е. у есть отрицание х, когда X = 0, Y = 1, и наоборот.

Таблица 7

X

Y

&

X

Y

V

≡

→

Теперь рассмотрим преобразователь двух входных переменных (табл. 7). Спрашивается, сколько различных функций возможно определить для Z, если z, x, y {0, 1}. Составим комбинационную таблицу 7, в которой номерами 0, 1, 2, …, 15 обозначены значения различных булевых функций в зависимости от комбинации X, Y.

В четвертой строке табл. 7 помечены обозначения функций. Напри-мер, z = x у есть функция сложения по модулю 2, а ее отрицание = есть функция тождественности z = x ≡ y. Набор (1) есть функция «И». Обозначается эта функция по-разному: z = х & у = х y = ху. Набор 14 – отрицание этой формулы, т.е. = . Точно так же набор (13) есть функ­ция следования z = x → y, a (2) – ее отрицание. Набор (7) есть функция «ИЛИ», т.е. z = х + у = x у, а набор (8) – ее отрицание. Заметим, что в отечественной математической литературе знак конъюнкции виде символа & не используется. Знак «+» вместо символа дизъюнкции «V» читается как логическое сложение, т.е. операция «ИЛИ».

На рис. 4 приведены условия обозначения элементов НЕ (а), ИЛИ (б) и И (в).

В таблице 7 в строке 4 в столбцах 2, 8, 14 применены специальные обозначения вместо слов: отрицание операции следования (), отрицание операции «ИЛИ» (), отрицания операции «И» (). В вычислительной технике используются лишь сами символы (→, V, &), поэтому данную символику для таб­лицы 5 следует рассматривать лишь как сокращение словесных обозна­чений.

Для одного входа n = 1, количество функций N = 4, для двух входов (n = 2) имеем N = 16. Отсюда по индукции для любого п количество раз­личных функций N = . Уже для п = 3, N = 256. Это при одном выходе, а при нескольких (m) выходах изучение всех возможных функций на основе простого перебора практически не­реально. Поэтому функции комбинаци­онных схем уже при п = 3 (и даже для п = 2, m = 2) начинают изучать, фикси­руя конкретную функцию преобразователя инфор­мации для автомата, на­пример суммирование, умножение, преобразование кодов и др.