Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2  След.
Автор Сообщение
 Не в сети
 Как упростить логическое выражение с равенствами?
Сообщение21.08.2007, 04:23 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
В общем случае логическое выражение упростить (или привести к нужной форме) очень сложно, чем больше переменных, тем сложнее.

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

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

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

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

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

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

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
Сообщение было изменено. Нажмите для получения дополнительной информации 
Сообщение21.08.2007, 04:30 
Модератор
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 11/01/06
Сообщения: 4757
Сначала нужно определить, что такое "упрощение"?

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

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

 Профиль  
                  
 Не в сети
 
Сообщение21.08.2007, 04:42 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
Упростить выражение -- значит сделать в нём меньше букв, где буквой считается отдельное записанное равенство.

Например,

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

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

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

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

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

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
 Re: Как упростить логическое выражение с равенствами?
Сообщение21.08.2007, 04:44 
Модератор
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 11/01/06
Сообщения: 4757
Dims писал(а):
Как я понимаю, количество всех таких возможных конъюнкций равно количеству разбиений множества объектов на классы эквивалентности, поскольку каждая конъюнкция соответствует классу эквивалентности. Этих классов довольно много.

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

 Профиль  
                  
 Не в сети
 
Сообщение21.08.2007, 05:32 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
Да, не учёл. И тем не менее, вопрос остаётся...

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

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

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

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

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
 
Сообщение23.08.2007, 11:21 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
Не пойму.

Допустим, у нас три объекта: 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]

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
 
Сообщение23.08.2007, 11:43 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 21/12/05
Сообщения: 4666
Откуда: Новосибирск
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]$

_________________
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего. :)

 Профиль  
                  
 Не в сети
 
Сообщение23.08.2007, 12:32 
Супермодератор
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 29/07/05
Сообщения: 8248
Откуда: Москва
Если я правильно понял проблему, то я бы решал так. У нас есть множество объектов, некоторые из которых могут быть "равными". Надо эту информацию максимально компактно хранить. Если есть возможность для каждого объекта хранить ссылку на какой-нибудь другой объект, то тогда это решается сравнительно просто. В начале каждый объект указывает на себя. В процессе работы строятся деревья (направленные), где каждый объект хранит ссылку на своего предка - некоторый другой объект, который ему равен. Тот хранит ссылку на своего предка и так далее. Как только мы по ссылкам доходим до объекта, который указывает на себя (корень дерева), то он считается базовым, определяющим весь класс. Более того, если нам в процессе работы пришлось для некоторого объекта найти его базовый, то можно заодно сразу поменять ссылку так, чтобы этот объект сразу указывал на свой базовый. Операция добавления нового сравнения к уже существующим сводится к проверке того, не являются ли данные объекты уже равными (для этого нужно найти для каждого из них их базовые), а если нет - то один из базовых приклеиваем к другому. По-моему, технически это очень просто и работать должно вполне эффективно.

 Профиль  
                  
 Не в сети
 
Сообщение23.08.2007, 18:33 
Модератор
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 11/01/06
Сообщения: 4757
Если речь идет таки о программировании, то у меня есть готовая реализация классов эквивалентности (примерно такая как описал PAV) на C++.

 Профиль  
                  
 Не в сети
 
Сообщение24.08.2007, 05:20 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
bot писал(а):
Чтобы получить 1 чисто логически надо просто добавить ложные высказывания типа $[a=b][b=c][c\ne a]$

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

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

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

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

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

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

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
 
Сообщение24.08.2007, 05:54 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 21/12/05
Сообщения: 4666
Откуда: Новосибирск
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]$, последние три слагаемые ложны.

_________________
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего. :)

 Профиль  
                  
 Не в сети
 
Сообщение24.08.2007, 08:13 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 16/03/06
Сообщения: 395
Откуда: Moscow
Ну да, ну вот.

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

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

_________________
Димс
http://www.relativity.ru

 Профиль  
                  
 Не в сети
 
Сообщение24.08.2007, 08:40 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 21/12/05
Сообщения: 4666
Откуда: Новосибирск
Dims писал(а):
Но вот можно ли как-то НЕ ДОБАВЛЯЯ ложных слагаемых, увидеть, что сумма И РАНЬШЕ была равна единице?

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

_________________
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего. :)

 Профиль  
                  
 Не в сети
Сообщение было изменено. Нажмите для получения дополнительной информации Re: Как упростить логическое выражение с равенствами?
Сообщение22.02.2013, 04:15 
Годы на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 15/04/10
Сообщения: 553
Откуда: г.Москва
Тема упрощения логического выражения по моему родственна теме построения дерева арифметического выражения т.е. классической задаче разбора выражения с последующим его вычислением. Но в логике правила конъюнкции отличны от умножения т.е $a \bigwedge a =a$ поэтому не случайно там рассматриваются ДНФ и СДНФ. Может быть для произвольной логической формулы сначала реализовать алгоритм СДНФ а потом уже по нему построить дерево?

 Профиль  
                  
 В сети
 Re: Как упростить логическое выражение с равенствами?
Сообщение22.02.2013, 19:09 
Заслуженный участник
Аватара пользователя
Годы на форумеГоды на форумеГоды на форумеГоды на форуме
Появился: 27/04/09
Сообщения: 8199
Откуда: Уфа
eugrita в сообщении #686850 писал(а):
Может быть для произвольной логической формулы сначала реализовать алгоритм СДНФ а потом уже по нему построить дерево?
Как вы собираетесь строить СДНФ без уже построенного дерева? Опишите, если не трудно. А то, что конъюнкция не ведёт себя как умножение, не имеет значения.

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

_________________
Человек хочет сказать $\tiny A$, пишет $\tiny B$, а понимают это как $\tiny C$. Неприятнее всего ситуация $\tiny A \approx B \ne C$.
Рисуйте больше картинок и схем! «Внутри головы много не помещается, и глубоко не разрабатывается. Пока вы носите что-то внутри головы, вы топчетесь на месте». — Munin.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Links go here: