Это задание из курса "Принятие решений", вроде несложное, а не могу решить, кроме как брутфорсом.

Итак, пусть А,В,С — числа (в диапазоне [0;1] но это не важно).
Доказать,что max(A,min(B,C))=min(max(A,B),max(A,C)).

Подсказка, но мне она не помогла: max(x,y)=~max(~x,~y), где ~ — преобразование (напр. y=1/x, или y=1-x для диапазона [0;1]

IO>Подсказка, но мне она не помогла: max(x,y)=~max(~x,~y), где ~ — преобразование (напр. y=1/x, или y=1-x для диапазона [0;1]

Может быть max(x,y)=~min(~x,~y)?

min(max(a,b),max(a,c))=
max(min(a,a),min(a,c),min(a,b),min(b,c))=
max(a,min(a,c),min(a,b),min(b,c))=
max(max(a,min(a,c),min(a,b)),max(min(b,c)))=
max(a,min(b,c))

Здравствуйте, Gasy, Вы писали:

G>Может быть max(x,y)=~min(~x,~y)?
Конечно, я ошибся. Писал после бутылки пива

Здравствуйте, Gasy, Вы писали:

G>min(max(a,b),max(a,c))=
G>max(min(a,a),min(a,c),min(a,b),min(b,c))=
...
Не очень понял переход. Что-то смахивает на брутфорс. Можно привести формулу, которой Вы пользовались.

Здравствуйте, IO, Вы писали:

IO>Это задание из курса "Принятие решений", вроде несложное, а не могу решить, кроме как брутфорсом.

IO>Итак, пусть А,В,С — числа (в диапазоне [0;1] но это не важно).
IO>Доказать,что max(A,min(B,C))=min(max(A,B),max(A,C)).

IO>Подсказка, но мне она не помогла: max(x,y)=~max(~x,~y), где ~ — преобразование (напр. y=1/x, или y=1-x для диапазона [0;1]

возьмем max(A,min(B,C))<=min(max(A,B),max(A,C))

A<=max(A,min(B,C))
min(B,C)<=max(A,min(B,C))

два случая
1)
{
B<=max(A,min(B,C))
A<=max(A,min(B,C))
max(A,B)<=max(A,min(B,C))
}

2)
{
C<=max(A,min(B,C))
A<=max(A,min(B,C))
max(A,C)<=max(A,min(B,C))
}

соединяем
min(max(A,B),max(A,C))<=max(A,min(B,C))

из этого следует, что два неравенства (в начале и в конце) возможны только при строгом равенстве

Здравствуйте, IO, Вы писали:

IO>Это задание из курса "Принятие решений", вроде несложное, а не могу решить, кроме как брутфорсом.

IO>Итак, пусть А,В,С — числа (в диапазоне [0;1] но это не важно).
IO>Доказать,что max(A,min(B,C))=min(max(A,B),max(A,C)).

IO>Подсказка, но мне она не помогла: max(x,y)=~max(~x,~y), где ~ — преобразование (напр. y=1/x, или y=1-x для диапазона [0;1]

Люди добрые!!! Это ж всего лишь дистрибутивность пересечения относительно объединения. Есть во всех дистрибутивных решетках, каковой линейно-упорядоченное множество(отрезок [0;1]) очевидно является.

Здравствуйте, IO, Вы писали:
...
IO>Итак, пусть А,В,С — числа (в диапазоне [0;1] но это не важно).

(может оказаться важно )

IO>Доказать,что max(A,min(B,C))=min(max(A,B),max(A,C)).

IO>Подсказка, но мне она не помогла: max(x,y)=~max(~x,~y), где ~ — преобразование (напр. y=1/x, или y=1-x для диапазона [0;1]

1) Для доказательства выражения

max(A,min(B,C))=min(max(A,B),max(A,C)).

над числами [0, 1], достаточно заметить, что

max(x, y) = x or y // логическое ИЛИ, удобнее обозначать как "+"
min(x, y) = x and y // логическое И, удобнее обозначать как "*"

при этом, само доказательство становится тривиальным.

max(A, min(B,C)) = A + B*C;

min(max(A,B),max(A,C)) = max(A,B) * max(A,C) =
= (A + B) * (A + C) = (A + B) * (A + C) =
= A*A + A*C + A*B + B*C = A + A(C + B) + B*C = A + B*C;

ч.т.д.

Здравствуйте, DOOM, Вы писали:

DOO>Люди добрые!!! Это ж всего лишь дистрибутивность пересечения относительно объединения. Есть во всех дистрибутивных решетках, каковой линейно-упорядоченное множество(отрезок [0;1]) очевидно является.


Вот! А еще люди спрашивают, "нафига нам спецразделы высшей математики", в то время как всякий головняк может оказаться частным случаем простой абстракции.

Приводим к теории множеств... Ниже уже всё объяснили...

Здравствуйте, DOOM, Вы писали:

DOO>Люди добрые!!! Это ж всего лишь дистрибутивность пересечения относительно объединения. Есть во всех дистрибутивных решетках, каковой линейно-упорядоченное множество(отрезок [0;1]) очевидно является.

Совершенно верно. А свойства дистрибутивности для трех множеств постулируются или доказываются? В Кормене "Алгоритмы ..." доказательства нет. То есть можно конечно построить диаграммы Венна и убедиться в их правильности, но все таки это теоремы или аксиомы?

Здравствуйте, IO, Вы писали:

IO>Это задание из курса "Принятие решений", вроде несложное, а не могу решить, кроме как брутфорсом.
IO>Итак, пусть А,В,С — числа (в диапазоне [0;1] но это не важно).
IO>Доказать,что max(A,min(B,C))=min(max(A,B),max(A,C)).

Не очень понял, что ты имеешь в виду под словом брутфорс и почему это плохо, но зачем ломать долго голову, если имеется всего 6 вариантов взаимной расстановки ABC и для всех них равенство справедливо? Имхо это абсолютно законное и вполне изящное доказательство.

Здравствуйте, IO, Вы писали:

IO>Совершенно верно. А свойства дистрибутивности для трех множеств постулируются или доказываются? В Кормене "Алгоритмы ..." доказательства нет. То есть можно конечно построить диаграммы Венна и убедиться в их правильности, но все таки это теоремы или аксиомы?


Это теорема. И полностью звучит так: модулярная решетка является дистрибутивной т.т.т.к. она не содержит "бриллиантов", т.е. подрешеток вида:

*
/|\
| | |
* * *
| | |
\|/
*

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

/*\
* \
| *
* /
\*/

Здравствуйте, DOOM, Вы писали:

DOO>Это теорема. И полностью звучит так: модулярная решетка является дистрибутивной т.т.т.к. она не содержит "бриллиантов", т.е. подрешеток вида:

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

А что за теория эти "решетки" изучает? Теория множеств?

Здравствуйте, IO, Вы писали:


IO>А что за теория эти "решетки" изучает? Теория множеств?

Решетки изучает теория решеток!

А вообще есть такое понятие как отношение, которое может обладать различным набором свойств, а решетки это множество с определенным типом отношения и парой операторов(по сути max и min). Короче, если интересно, почитай Куроша или Лидла с Пильцем — это основы алгебры(у нас изучалось на 3-ем семестре).

Здравствуйте, DOOM, Вы писали:

DOO>Решетки изучает теория решеток!

DOO>А вообще есть такое понятие как отношение, которое может обладать различным набором свойств, а решетки это множество с определенным типом отношения и парой операторов(по сути max и min). Короче, если интересно, почитай Куроша или Лидла с Пильцем — это основы алгебры(у нас изучалось на 3-ем семестре).
Поднял Куроша, справочник Корнов и не нашел решеток.
Нашел только "кольцо" из абстрактной алгебры — множество с определенной парой операторов (абстрактные + и *), одним из свойств которого является дистрибутивность.
Для чисел в диапазоне от 0 до 1 если за операторы + и * взять max и min, то данное множество будет кольцом. Надо еще получается доказать остальные свойства кольца для данного множества. А это не представляет труда кроме одного. Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще

Здравствуйте, IO, Вы писали:

IO>Здравствуйте, DOOM, Вы писали:

DOO>>Решетки изучает теория решеток!

DOO>>А вообще есть такое понятие как отношение, которое может обладать различным набором свойств, а решетки это множество с определенным типом отношения и парой операторов(по сути max и min). Короче, если интересно, почитай Куроша или Лидла с Пильцем — это основы алгебры(у нас изучалось на 3-ем семестре).
IO>Поднял Куроша, справочник Корнов и не нашел решеток.
IO>Нашел только "кольцо" из абстрактной алгебры — множество с определенной парой операторов (абстрактные + и *), одним из свойств которого является дистрибутивность.
IO>Для чисел в диапазоне от 0 до 1 если за операторы + и * взять max и min, то данное множество будет кольцом. Надо еще получается доказать остальные свойства кольца для данного множества. А это не представляет труда кроме одного. Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще

В исходной задаче приведен пример обратного оператора для кольца (0, 1) : -a <=> 1 — a.

Здравствуйте, IO, Вы писали:


IO>Поднял Куроша, справочник Корнов и не нашел решеток.
IO>Нашел только "кольцо" из абстрактной алгебры — множество с определенной парой операторов (абстрактные + и *), одним из свойств которого является дистрибутивность.
IO>Для чисел в диапазоне от 0 до 1 если за операторы + и * взять max и min, то данное множество будет кольцом. Надо еще получается доказать остальные свойства кольца для данного множества. А это не представляет труда кроме одного. Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще

С кольцом не выйдет. Если только полукольцо, но их свойства я не изучал особо. Рылся в сети, ничего найти стоящего про решетки не смог. Своими силами рассказывать эту теорию я не буду(оффтоп(хотя итак уже)). Так что, если действительно надо — научная библиотека единственное, что я могу посоветовать.

Здравствуйте, mrhru, Вы писали:

Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще

M>В исходной задаче приведен пример обратного оператора для кольца (0, 1) : -a <=> 1 — a.

Не верно. max(a,1-a)<>0 ну никак.

Здравствуйте, DOOM, Вы писали:

M>>В исходной задаче приведен пример обратного оператора для кольца (0, 1) : -a <=> 1 — a.

DOO>Не верно. max(a,1-a)<>0 ну никак.

Ну как никак? Очень даже как.

max(0,1-0) = 1 <>0
max(1,1-1) = 1 <>0