Раздел 3. Основы теории конечных автоматов

В этом разделе дискретной математики особую роль будут играть двухэлементное множество В и двоичные переменные, принимающие значение из В. Его элементы часто обозначают 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – логическая: "да" - "нет", "истинно"(И) и "ложно" (Л). В контексте, содержащем одновременно логические и арифметические величины, эта интерпретация обычно фиксируется явно: так в языках программирования вводится специальный тип переменной – логическая переменная, значение которой обозначается true и false.

Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики. Логической функцией от n переменных называется n – арная операция на В. Итак, логическая функция f(x₁, ... , x_n) – это функция принимающая значение 0, 1. Множество всех логических функций обозначается Р₂, множество всех логических функций n переменных – Р₂(n).

Алгебра, образованная k-элементным множеством вместе со всеми операциями на нем, называют алгеброй k-значной логики, а n – арные операции на k – элементном множестве называются k – значными логическими функциями n переменных; множество всех k – значных логических функций обозначается Р_k.

В дальнейшем будем рассматривать только логические функции из Р₂. Пример такой функции показан в табл. 3.1.

Таблица 3.1 – Пример логической функции

Всякая логическая функция n – переменных может быть задана таблицей, в левой (верхней) части которой перечислены все 2ⁿ наборов значений переменных, а в правой части – значения функций на этих наборах. Например, таблица 3.1 задает функцию трех переменных. В этой таблице наборы расположены в лексико - графическом порядке, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочением будем пользоваться и в дальнейшем.

При любом фиксированном упорядоченном наборе логическая функция n переменных полностью определяется вектор – столбцом значений функции, т.е. 2ⁿ элементами. Переменная х_i в функции f(x) называется несущественной, если изменение ее значений не изменяет значения f(x). В этом случае функция f(x) по существу зависит от n-1 переменных, т.е. представляет собой новую функцию g(x) от n – 1 переменных. Говорят, что функция g(x) получена из функции f(x) путем удаления фиктивной переменной.