ЧАСТЬ ПЕРВАЯ. СИНТЕЗ И АНАЛИЗ СХЕМ, РАБОТА КОТОРЫХ НЕ ЗАВИСИТ ОТ ВРЕМЕНИ

ГЛАВА ПЕРВАЯ. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ И ИХ ОСНОВНЫЕ СВОЙСТВА

1-1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Рассмотрим множество векторов Будем предполагать, что координаты этих векторов могут принимать значения 0 или 1. Таким образом, множество X состоит из различных векторов. Совокупность координат некоторого фиксированного вектора X из множества X будем называть двоичным набором или просто набором. Наборы будем обозначать следующим образом: сохраним для обозначения произвольного вектора из X.

Сопоставим каждому вектору из X число 0 или 1, т. е. произведем однозначное отображение множества X на множество

Определение 1-1. Функцией алгебры логики называется функция, дающая однозначное отображение X в

Сокращенно функции алгебры логики мы будем обозначать ФАЛ. Наборы могут рассматриваться как наборы значений аргументов функции алгебры логики.

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

Определение 1-2. Если две функции алгебры логики принимают на всех возможных наборах значений аргументов одинаковые значения, то функции и называются равными.

Факт равенства функций записывается обычным образом

Определение 1-3. Функция существенно зависит от аргумента если имеет место соотношение

В противном случае говорят, что от X; функция зависит несущественно и х, является ее фиктивным аргументом. Функция алгебры логики не изменится, если к ее аргументам дописать любое число фиктивных аргументов или зачеркнуть те аргументы, которые для данной функции являются фиктивными.

Для нахождения несущественных аргументов таблично заданной функции алгебры логики можно поступить следующим образом. Разбиваем множество наборов аргументов заданной функции на два подмножества: подмножество, на котором заданная функция принимает значение 1, и подмножество, на котором заданная функция принимает значение 0. Для проверки фиктивности аргумента х вычеркиваем столбец, ему соответствующий, и проверяем, не появились ли в обоих подмножествах одинаковые наборы. Если таких наборов не появилось, то является фиктивным аргументом.

Пример 1-1. Пусть функция задана следующей таблицей:

(см. скан)

Произведем разбиение набора аргументов:

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

Теорема 1-1. Число различных функций алгебры логики, зависящих от аргументов, конечно и равно .

Для доказательства теоремы составим следующую таблицу:

В этой таблице справа стоит одна из функций алгебры логики, зависящая от аргументов. Задавая тот или иной конкретный двоичный набор мы будем тем самым задавать одну из возможных функций алгебры логики. Но различное число таких наборов равно Теорема доказана.

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

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

Пример 1-2. На рис. 1-1 геометрически задана функция получающаяся из функции примера 1-1 после выбрасывания фиктивного аргумента

Вершины, относящиеся к подмножеству могут быть, например, зачернены.

Значения функции могут быть заданы не на всех возможных наборах аргументов. На некоторых наборах значения функции могут быть не определены. Такие функции мы будем называть неполностью определенными или недоопределенными. В таблице задания функции против наборов, на которых функция не определена, ставится звездочка. Пусть, например, задана следующей таблицей:

Рис. 1-1.

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