ТутРешу.Ру

Скажите пажалуста как упростить вырожение

Задание:

Скажите пажалуста как упростить вырожение

Решение:

В общем случае логическое выражение упростить (или привести к нужной форме) очень сложно, чем больше переменных, тем сложнее. А если взять логическое выражение, состоящее только из равенств? Пусть есть n объектов a_1, a_2, … a_n. Равенство между объектами обладает обычными свойствами: объект равен сам себе, коммутативность, транзитивность. Каждая элементарная конъюнкция содержит равенства (или их отрицания — неравенства) всевозможных пар объектов. Естественно, не все сочетания совместимы, так как, например, (a_1=a_2)*(a_1=a_3)*(a_2<>a_3)=0. Как я понимаю, количество всех таких возможных конъюнкций равно количеству разбиений множества объектов на классы эквивалентности, поскольку каждая конъюнкция соответствует классу эквивалентности. Этих классов довольно много. Теперь рассмотрим подмножество всех таких конъюнкций и составим из них дизъюнкцию. Что насчет задачи упрощения такого выражения? Может, она проще, ведь там много упрощений возможно? С другой стороны, теперь в выражение входят уже не переменные, а их пары




Знаете другой ответ?

Отправить свой ответ