Схем автоматов

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

Различные комбинации значений входных переменных называются наборами. Функция является полностью заданной, если указаны ее значения для всех наборов. Количество наборов определяется формулой:

,

(3.1)

где k – количество входных переменных (при k = 2 N = 4).

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

m = 2 .

(3.2)

ЗначенияN иm для различных kприведены в таблице 3.1.

Таблица 3.1

Нетрудно заметить, что прямое изучение логических функций с помощью таблиц истинности практически возможно лишь до k = 3.

Для определения логических функций от большего числа переменных используется принцип суперпозиции. Поэтому в алгебре логики основную роль играют функции одной или двух переменных.