1.1 Основные определения
Для формального описания цифровых автоматов(ЦА) широко применяют аппарат алгебры логики (АЛ), являющейся одним из разделов математической логики. Создатель алгебры логики - английский математик Джордж Буль (1815 - 1864).
Определение 1. Основное понятие АЛ - высказывание. Высказывание - некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Любое высказывание можно обозначить символом, например, X и считать, что X=1, если высказывание истинно, X=0 если высказывание ложно.
Определение 2. Логическая (Булева) переменная - такая величина X, которая может принимать только два значения: X = { 0, 1 }.
Определение 3. Высказывание абсолютно истинно, если соответствующая ей логическая величина X принимает единичное значение при любых условиях.
Определение 4. Высказывание абсолютно ложно, если соответствующая ей логическая переменная X принимает нулевое значение при всех условиях.
Логическая функция (функция алгебры логики - ФАЛ) - функция ¦ , принимающая значение, равное нулю или единице на наборе логических переменных
Рассмотрим множество векторов , где - (координаты векторов) могут принимать значения 0 или 1. Таким образом, множество состоит из различных векторов. Совокупность координат некоторого фиксированного вектора из множества будем называть двоичным набором. Сопоставим каждому вектору из число 0 и 1, т. е. произведем однозначное отображение множества на множество Y { 0, 1}.
Определение 5 Функцией алгебры логики (ФАЛ) называется функция, дающая однозначное отображение X в Y.
Т. к. число различных наборов значений аргументов является конечным, то любая ФАЛ может быть полностью задана конечной таблицей. В левой части этой таблицы перечислены все наборы значений аргументов этой функции, а в правой части - значения функции на этих наборах.
Логические переменные | Функция | |||||||
... | ... | ... | ... | ¦ | ||||
... | ... | ... | ... | |||||
... | ... | ... | ... | ... | ||||
... | ... | ... | ... | ... | ... | ... | ... | ... |
... | ... | ... | ... | |||||
... | ... | ... | ... | ... | ... | ... | ... | ... |
Определение 6. Если две ФАЛ ¦ () и ¦ () принимают на всех возможных наборах значений аргументов одинаковые значения, то функции ¦ и ¦ называются равносильными или равными, т.е.:
¦ () = ¦ ()
Определение 7. Функция ¦ () существенно зависит от аргумента , если имеет место соотношение:
¦ () ¹ ¦ ()
В противном случае говорят, что от функция зависит несущественно и является фиктивным аргументом. ФАЛ не изменится, если к ее аргументам дописать любое число фиктивных аргументов, или зачеркнуть все фиктивные аргументы.
Теорема 1.1 Число различных ФАЛ, зависящих от n аргументов конечно и равно .
Для доказательства составим таблицу:
0 0... 0 0 | |
0 0... 0 1 | |
0 0... 1 0 | |
... | ... |
1 1... 1 1 |
В этой таблице справа стоит одна из ФАЛ, зависящая от n аргументов. Задавая тот или иной конкретный двоичный набор < >, мы будем тем самым задавать одну из возможных функций алгебры логики. Но различное число таких наборов равно . Теорема доказана.
Значения функции могут быть заданы не на всех возможных наборах аргументов. На некоторых наборах значения ФАЛ могут быть не определены. Такие ФАЛ называют не полностью определенными или не- доопределенными. Функцию можно доопределить. Если ФАЛ не определена на m наборах аргументов, то путем ее произвольного доопределения можно получить различных полностью определенных функций.