Алгоритм нахождения формулы, соединяющей входы и выходы

Question

Кажется, я вспомнил, что узнал метод нахождения формулы, которая соединяет входы и выходы из таблицы. Например:

a b c | r
1 1 0 | 0
0 1 1 | 1
1 1 1 | 1

где «r» - результат, а a, b и c - входные данные. Метод включал уравнения со многими неизвестными и в итоге получил формулу, которая все это объяснила. (Это пример, который не имеет особого значения, так как r = c, но вы поняли).

Однако я не могу вспомнить подробности и недостаточно ключевых слов, чтобы можно было найти его в Интернете. Предмет, обучающий этому методу, также включал много булевой алгебры.

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

Answer 1

Вы имеете в виду карты Карно ?

Answer 2

Существуют дизъюнктивные и конъюнктивные нормальные формы. В зависимости от того, что вы хотите, вы можете построить их из (полных) логических таблиц, построив термины для результатов 0 или 1 с помощью ors или ands и комбинируя эти термины с ands и ors (а остальные соответствуют 1 или 0). Здесь это звучит сложнее. Вики / Google дадут вам несколько примеров, когда вы ищете конъюнктивную или дизъюнктивную нормальную форму.

РЕДАКТИРОВАТЬ: Вот пример из вики для обеих форм (DNF = дизъюнктивная нормальная форма, KNF = конъюнктивная нормальная форма):

Answer 3

Я думаю, что вы имеете в виду Cunjunctive Normal Form .Для этого вам нужна полная таблица истинности.