Как упростить логическое выражение с равенствами?

[Dims]

В общем случае логическое выражение упростить (или привести к нужной форме) очень сложно, чем больше переменных, тем сложнее.

А если взять логическое выражение, состоящее только из равенств?

Пусть есть n объектов a_1, a_2, ... a_n. Равенство между объектами обладает обычными свойствами: объект равен сам себе, коммутативность, транзитивность.

Каждая элементарная конъюнкция содержит равенства (или их отрицания -- неравенства) всевозможных пар объектов. Естественно, не все сочетания совместимы, так как, например, (a_1=a_2)*(a_1=a_3)*(a_2<>a_3) = 0.

Как я понимаю, количество всех таких возможных конъюнкций равно количеству разбиений множества объектов на классы эквивалентности, поскольку каждая конъюнкция соответствует классу эквивалентности. Этих классов довольно много.

Теперь рассмотрим подмножество всех таких конъюнкций и составим из них дизъюнкцию.

Что насчёт задачи упрощения такого выражения? Может, она проще, ведь там много упрощений возможно? С другой стороны, теперь в выражение входят уже не переменные, а их пары.

Где-нибудь такое исследовалось?

[maxal]

Сначала нужно определить, что такое "упрощение"?

Приведите пример исходного выражения и "упрощенного" и объясните почему оно "проще".

P.S. Если рассматривать равенства как ребра графа, соединяющие элементы-вершины, то минимальное (по числу равенств) описание того же отношения эквивалетности - это ни что иное как остовной лес графа (или его транзитивного замыкания).

[Dims]

Упростить выражение -- значит сделать в нём меньше букв, где буквой считается отдельное записанное равенство.

Например,

(ac + ad + bc + bd) = (a + b)(c + d)

слева 8 букв, справа 4.

(каждая буква -- это равенство)

P.S. Да, но граф кодирует только одну конъюнкцию. Можно ли рассмотреть "суперпозицию" графов? Действительно, если одно ребро встречается во всех конъюнкциях, то его можно вынести за скобки, а на "суперпозиции" отобразить жирно. Но как быть с другими упрощениями?

Добавлено спустя 6 минут 12 секунд:

Собственно, мне главное не упростить, а найти способ представления. Упростить -- это вторичное требование, вытекающее из мысли хранить выражение в виде выражения. Если хранить его как перечень всевозможных конъюнкций, то забьётся память.

[maxal]

Dims писал(а):

Как я понимаю, количество всех таких возможных конъюнкций равно количеству разбиений множества объектов на классы эквивалентности, поскольку каждая конъюнкция соответствует классу эквивалентности. Этих классов довольно много.

Нет. Каждая конъюнкция действительно задает класс эквивалентности, но один и тот же класс при этом можно задать разными конъюкциями. Поэтому количество конъюнкций будет больше количества разбиений множества объектов на классы эквивалентности.

[Dims]

Да, не учёл. И тем не менее, вопрос остаётся...

Добавлено спустя 22 минуты 19 секунд:

Может быть, зайти с другой стороны, со стороны классов эквивалентности?

Ведь классы эквивалентности взаимно не пересекаются и в сумме дают 1. Значит, если в каком-то месте один и тот же класс эквивалентности встречается в нескольких разбиениях, его можно "вынести за скобки". Оставшихся элементов будет меньше, а описание их дизъюнкции должно будет производиться по тем же принципам.

Или вообще. Можно ведь "вынести за скобки" не только целый класс эквивалентности, но и его подмножество, общее для нескольких разбиений. Остаток всё равно будет выражением того же рода.

Можно ли как-то построить какую-нибудь иерархию этих классов эквивалентности и так хранить?

[Dims]

Не пойму.

Допустим, у нас три объекта: a, b, c. И в суперпозиции присутствуют все возможные связи, то есть

[a=b][b=c][a=c] + [a≠b][b≠c][a≠c] + [a=b][b≠c][a≠c] + [a≠b][b=c][a≠c] + [a≠b][b≠c][a=c]

Мне почему-то кажется, что в сумме должна получиться единица. Но не получается что-то...

[bot]

Dims писал(а):

Допустим, у нас три объекта: a, b, c. И в суперпозиции присутствуют все возможные связи, то есть

[a=b][b=c][a=c] + [a≠b][b≠c][a≠c] + [a=b][b≠c][a≠c] + [a≠b][b=c][a≠c] + [a≠b][b≠c][a=c]

Мне почему-то кажется, что в сумме должна получиться единица. Но не получается что-то...

Видимо потому, что не учитываете логическую зависимость высказываний.
Например $[a=b][b=c] \Rightarrow [a=c]$
Именно их зависимость позволяет сократить число слагаемых в ДНФ с 8 до 5.

Добавлено спустя 3 минуты 31 секунду:

Чтобы получить 1 чисто логически надо просто добавить ложные высказывания типа $[a=b][b=c][c\ne a]$

[PAV]

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

[maxal]

Если речь идет таки о программировании, то у меня есть готовая реализация классов эквивалентности (примерно такая как описал PAV) на C++.

[Dims]

bot писал(а):

Чтобы получить 1 чисто логически надо просто добавить ложные высказывания типа $[a=b][b=c][c\ne a]$

Непонятно. Как можно, добавляя к сумме нули, добиться получения 1?

Добавлено спустя 2 минуты 49 секунд:

PAV писал(а):

Если я правильно понял проблему, то я бы решал так. У нас есть множество объектов, некоторые из которых могут быть "равными".

Не совсем. Такая информация находится лишь в одной конъюнкции, то есть, в одном разбиении на классы эквивалентности. А вот их сумма уже не сводится к возможности быть только равными или не равными. Объекты могут быть "полуравными", могут коррелировать с равенством или неравенством других объектов и так далее.

Добавлено спустя 6 минут 8 секунд:

maxal писал(а):

Если речь идет таки о программировании, то у меня есть готовая реализация классов эквивалентности (примерно такая как описал PAV) на C++.

У меня уже голова от этого пухнет. Я написал уже и реализацию через логические выражения (на Джаве). Очень удобно получилось: можно формировать логические выражения, преобразовывать их и так далее. Но как гарантированно упростить не понимаю. Я перетряхиваю всё выражение через дистрибутывные законы, применяю закон де Моргана, чтобы отрицания спустились до самых нижних членов, выполняю аксиомы... И всё равно остаётся ощущение, что я учитываю не все возможности и как то это некрасиво. Потом я написал пакет с разбиениями на классы эквивалентности. Тут совсем непонятно, как упрощать... Сейчас решил тупо хранить всю совокупность. Может быть хоть в простых случаях хватит мощности?

[bot]

Dims писал(а):

Непонятно. Как можно, добавляя к сумме нули, добиться получения 1?

Я же говорил чисто логически:
$ABC \vee \vee AB'C' \vee A'BC' \vee A'B'C \vee A'B'C' $
$\vee ABC' \vee AB'C \vee A'BC = 1$
Здесь штрих - отрицание, $A=[b=c], \ B=[c=a], \ C=[a=b]$, последние три слагаемые ложны.

[Dims]

Ну да, ну вот.

Но вот можно ли как-то НЕ ДОБАВЛЯЯ ложных слагаемых, увидеть, что сумма И РАНЬШЕ была равна единице?

Ведь если нельзя, то получается, что машина должна как-то угадывать, какие ложные слагаемые следует добавить, хотя их добавление ведёт к временному усложнению выражения.

[bot]

Dims писал(а):

Но вот можно ли как-то НЕ ДОБАВЛЯЯ ложных слагаемых, увидеть, что сумма И РАНЬШЕ была равна единице?

Так или иначе ведь надо описывать отношение эквивалентности.
Если из соображений экономии выбрать инцидентности графа, замыкание которых по тразитивности даст нам нужную эквивалентность, то за это придётся платить алгоритмически - описывать механизм получения такого замыкания.
Возможно тут может помочь язык Пролог - он специально создан под импликации. Только я по нему не спец - знаю в общих чертах.

[eugrita]

Тема упрощения логического выражения по моему родственна теме построения дерева арифметического выражения т.е. классической задаче разбора выражения с последующим его вычислением. Но в логике правила конъюнкции отличны от умножения т.е $a \bigwedge a =a$ поэтому не случайно там рассматриваются ДНФ и СДНФ. Может быть для произвольной логической формулы сначала реализовать алгоритм СДНФ а потом уже по нему построить дерево?

[arseniiv]

eugrita в сообщении #686850 писал(а):

Может быть для произвольной логической формулы сначала реализовать алгоритм СДНФ а потом уже по нему построить дерево?

Как вы собираетесь строить СДНФ без уже построенного дерева? Опишите, если не трудно. А то, что конъюнкция не ведёт себя как умножение, не имеет значения.

P. S. Последнее сообщение темы было написано в 2007 году.