Возможно ли программным путём получить логическое выражение по таблице истинности?

Question

Например, есть две переменные X и Y. Каждая может принимать значения 0 или 1. Нужно вывести зависимость между значениями и ответами. Не вручную найти, а написать программу возможно?

X	Y	Result
0	0	0
0	1	0
1	0	1
1	1	0

Answer 1

Оставив в стороне вопрос о разумности выбранного подхода, ответ да, можно.

Если коротко - то строится нейросеть. Обучается "на большом количестве данных", потом используется. Только странное это занятие - для логической схемы строить нейросеть. Про качество (точность) решения - даже не говорю.

Вот тут объясняется подробнее: https://habr.com/ru/post/516572/

Answer 2

Это задача восстановления логической формулы по таблице истинности, одна из задач математической логики (например, получение СДНФ или СКНФ - в данном случае без разницы какой конкретно, результат будет эквивалентный).

Про СДНФ, СКНФ см.: Совершенная дизъюнктивная нормальная форма, Совершенная конъюнктивная нормальная форма

Для получения СДНФ нужно:

Отобрать только строки таблицы истинности, где результат равен 1
Внутри каждой строки там где 1 - берем просто соответствующую букву, где 0 - отрицание этой буквы, потом все буквы объединяем конъюнкцией (логическим "и")
Все обработанные строки объединяем дизъюнкцией (логическим "или")

Для СКНФ - по сути все то же самое, только наоборот)

Пример получения текстовой формулы СДНФ:

def get_sdnf(table):
    result = []
    for inputs, row_result in table.items():
        if row_result:
            row = []
            for value, letter in zip(inputs, 'XYZIJK'):
                row.append(('' if value else 'not ') + letter)
            
            result.append('({})'.format(' and '.join(row)))
    
    return ' or '.join(result)


# Ключи словаря - входы, значения - выходы
table = {
    (0, 0): 0,
    (0, 1): 0,
    (1, 0): 1,
    (1, 1): 1
}

print(get_sdnf(table))

Вывод:

(X and not Y) or (X and Y)

Для вашей таблицы истинности выведет просто (X and not Y)

Скобки на самом деле не нужны, т.к. у and более высокий приоритет, чем у or, но для удобства восприятия оставлю.

СДНФ и СКНФ могут получиться избыточными (например, по таблице истинности обычного or получится СДНФ вида (not X and Y) or (X and not Y) or (X and Y), или могут остаться переменные, от которых результат вообще никак не зависит), и следующим шагом может быть получение минимальной дизъюнктивной нормальной формы (МДНФ) или минимальной конъюнктивной нормальной формы (МКНФ). Это может потребоваться, например, для реализации таблицы истинности минимальным количеством электронных компонентов. Но в условии вашей задачи ничего про минимальность не говорится, поэтому формально хватит и просто СДНФ. Если интересно, можете почитать про минимизацию методом Куайна.

БЛОГ НА HUSL

Возможно ли программным путём получить логическое выражение по таблице истинности?

Ответы (2 шт):