Релейно–контактные схемы

Реле нормально разомкнутое, реле нормально замкнутое.

Соединение контактов, распараллеливание выходов. Соединение схем: последовательное и параллельное. Конъюнкция, дизъюнкция.

Проводимость РКС – булева функция, вычисляемая схемой.

Задачи:

1) анализ РКС;

2) синтез РКС;

3) минимизация РКС.

Будем рассматривать формулу Ф(x₁, x₂,…, x_n) над каким-то произвольным фиксированным множеством функций F как «чёрный ящик», некое устройство, на которое подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции f, представляемой формулой Ф.

Чтобы понять, как устроен ящик, мы должны разобрать процесс построения формул из подформул. Добираясь до «базисных» подформул, т.е. элементов множества F, мы приходим к структурным элементам, из которых собран ящик, вычисляющий функцию f. Каждая функция базиса уже рассматривается как неделимая, и её внутренняя структура не анализируется.

Пример – эквиваленция над стандартным базисом.

Каждой формуле соответствует граф: вершинам соответствуют функции, ребра изображают последовательность вхождений; очевидно понятие глубины. Если приписать этому графу реальные логические устройства – «и», «или», «не» и т.д. – получится реальная схема, вычисляющая значения функции. Можно вводить в схемы и более сложные устройства, с большим числом входов и выходов. Дальнейший шаг – соединение схем в сети, вычисление нескольких функций (булева оператора) и т.д.

Задачи для СФЭ – те же, что и для РКС плюс новые: минимизация по числу элементов, по типу элементов, с учётом ограничений на их число и т.д.