Вопрос про булевы кубы и прочее

advocat

Есть специалисты в этой области?
Есть небольшой вопрос, связанный с расположением интервалов в булевых кубах (а точнее с окрестностью первого порядка конъюнкции из сокр. ДНФ).

Dallas

пиши вопрос, тебе ответят

advocat

Не могу формально показать, что не может быть следующего:
Рассматриваем сокр.днф, некую конъюнкцию, её окрестность 1-го порядка.
Надо показать, что не может быть такой ситуации: интервал покрывается интервалами из этой окрестности, но сам с исходным интервалом не пересекается.
Здесь суть в том, что именно окрестность 1го порядка, т.к. для 2го и выше такая ситуация может быть (пример легко приводится).
А с 1ой окр-тью туплю уже который день
Помогите пож-та.

Dallas

что такое интервал?

advocat

Интервал - интерпретация конъюнкции на графе. Ещё гранью называют, так наверное правильнее. Я привыкла к интервалу.

Dallas

Тогда это неверно.
Рассматриваем сокр.днф, некую конъюнкцию, её окрестность 1-го порядка.
Надо показать, что не может быть такой ситуации: интервал покрывается интервалами из этой окрестности, но сам с исходным интервалом не пересекается.
Контрпример. Возьмём интервал, состоящий из 1 точки, которая входит в окрестность, но не входит в интервал, соответствующий конъюнкции. Тогда он покрывается интервалами из окрестности (например, самим собой но с исходным интервалом не пересекается.

advocat

Что за бред, прости?
Ясен пень, тут имеется в виду, что интервал - не любой от балды, а который соответствует конъюнкции из исходной ДНФ.

Dallas

Понял.
Схема доказательства.
Пусть A - исходная грань, C1,...,Cm - её окрестность, грань B не пересекается с A, покрывается гранями C1,...,Cm.
Будем обозначать грани векторами (a1,...,an где ai - 0, 1 или *.
Пусть A = (a1,....,an).
Для любого вектора x из B^n обозначим F(x) грань (f1,...,fn) такую, что при всех i: fi = *, если ai != xi и ai != *, xi в противном случае.
Если X - грань, то F(X) - объединение F(x) по всем x из X (легко заметить, что это грань).
Утверждение 1. Если грани A и C пересекаются, x принадлежит C, то F(x) - подмножество C.
Это легко проверить.
Утверждение 2. При любом x: x принадлежит F(x).
Из этих утверждений следует, что F(Ci)=Ci при всех i. Кроме того, из покрываемости B гранями Ci следует, что объединение F(Ci) содержит F(B). То есть, Ci покрывают F(B).
Из того, что A и B не пересекаются, следует, что F(B) - строгое надмножество B (например потому, что F(x) пересекается с A при любом x). Это противоречит тому, что грани взяты из сокращённой ДНФ (B можно расширить до F(B в сокращённой ДНФ грани нерасширяемы).

advocat

Если X - грань, то F(X) - объединение F(x) по всем x из X (легко заметить, что это грань).
Здесь подразумеваешь, что грань X - это одна из C1,...,Cm, да?
Объединение F(x)UF(y как я понимаю, это так x1 U y1 = x1, если они равны, иначе = *

Dallas

Здесь подразумеваешь, что грань X - это одна из C1,...,Cm, да?
Не обязательно. X - абсолютно любая грань.
Объединение F(x)UF(y как я понимаю, это так x1 U y1 = x1, если они равны, иначе = *
Нет, я имею в виду обычное теоретико-множественное объединение (множеств векторов из B^n).
Можно показать, что если X=(x1,...,xn то F(X)=(f1,...,fn где
fi = *, если ai != xi и ai, xi != *, xi в противном случае.
Оставить комментарий
Имя или ник:
Комментарий: