Здравствуйте, 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))
}
Здравствуйте, 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>А что за теория эти "решетки" изучает? Теория множеств?
Решетки изучает теория решеток!
А вообще есть такое понятие как отношение, которое может обладать различным набором свойств, а решетки это множество с определенным типом отношения и парой операторов(по сути 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>Для чисел в диапазоне от 0 до 1 если за операторы + и * взять max и min, то данное множество будет кольцом. Надо еще получается доказать остальные свойства кольца для данного множества. А это не представляет труда кроме одного. Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще
С кольцом не выйдет. Если только полукольцо, но их свойства я не изучал особо. Рылся в сети, ничего найти стоящего про решетки не смог. Своими силами рассказывать эту теорию я не буду(оффтоп(хотя итак уже)). Так что, если действительно надо — научная библиотека единственное, что я могу посоветовать.
Есть там: a+(-a)=a-a=0. Как определить обратные операторы? Туманно еще
M>В исходной задаче приведен пример обратного оператора для кольца (0, 1) : -a <=> 1 — a.
Здравствуйте, 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
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
M>Ну как никак? Очень даже как.
M>max(0,1-0) = 1 <>0 M>max(1,1-1) = 1 <>0
M>
Кто-то кого-то не понял похоже
Мы вроде ищем -a, т.е. b такое что max(a,b) = 0(ну или min(a,b)=0). Кольцу необязательно по "умножению" иметь обратные элементы, даже еденицу не надо, а вот по "сложению" надо абелеву группу — именно здесь вся загвоздка.
Здравствуйте, DOOM, Вы писали:
DOO>С кольцом не выйдет. Если только полукольцо, но их свойства я не изучал особо. Рылся в сети, ничего найти стоящего про решетки не смог. Своими силами рассказывать эту теорию я не буду(оффтоп(хотя итак уже)). Так что, если действительно надо — научная библиотека единственное, что я могу посоветовать.
Где-то я это встречал... Полгода назад гуглем находил, а сейчас — фигушки.
Кстати, нужно отметить такую вещь.
min — эквивалент and
max — эквивалент or
(для булевой алгебры на множестве 0,1).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, DOOM, Вы писали:
DOO>>С кольцом не выйдет. Если только полукольцо, но их свойства я не изучал особо. Рылся в сети, ничего найти стоящего про решетки не смог. Своими силами рассказывать эту теорию я не буду(оффтоп(хотя итак уже)). Так что, если действительно надо — научная библиотека единственное, что я могу посоветовать.
К>Где-то я это встречал... Полгода назад гуглем находил, а сейчас — фигушки.
К>Кстати, нужно отметить такую вещь. К>min — эквивалент and К>max — эквивалент or К>(для булевой алгебры на множестве 0,1).
К>Булевы алгебры случаем не являются решетками?
В принципе булева алгебра — это решетка на определенном множестве(линейно-упорядоченное оно должно быть, больше вроде и не надо), на которую посмотрели как на кольцо. Но множество должно быть от силы счетно, а [0;1] — не катит в этом плане
К>Блин, всю абстрактную алгебру позабывал!!!
Зря. Очень красивые вещи бывают там(нк матроиды к примеру в жизни очень даже полезно знать).
Здравствуйте, DOOM, Вы писали:
M>>Ну как никак? Очень даже как.
M>>max(0,1-0) = 1 <>0 M>>max(1,1-1) = 1 <>0
M>>
DOO>Кто-то кого-то не понял похоже
Друг-друга.
DOO>Мы вроде ищем -a, т.е. b такое что max(a,b) = 0(ну или min(a,b)=0). Кольцу необязательно по "умножению" иметь обратные элементы, даже еденицу не надо, а вот по "сложению" надо абелеву группу — именно здесь вся загвоздка.
"ну или min(a,b)=0" если именно это надо, то определение обратного элемента подходит.
А с чего взяли, что min(a,b) — это умножение в кольце (0, 1)?
Это и есть самое настоящее сложение.
Вот max() — сложением, как ни печально, не является. Несмотря даже на то, что ему эквивалентен or в булевой алгебре.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, DOOM, Вы писали:
DOO>В принципе булева алгебра — это решетка на определенном множестве(линейно-упорядоченное оно должно быть, больше вроде и не надо), на которую посмотрели как на кольцо. Но множество должно быть от силы счетно, а [0;1] — не катит в этом плане
Почему?
and -- min
or -- max
xor -- +
not -- 1-x
К>>Блин, всю абстрактную алгебру позабывал!!!
DOO>Зря. Очень красивые вещи бывают там(нк матроиды к примеру в жизни очень даже полезно знать).
Здравствуйте, mrhru, Вы писали:
К>>Кстати, нужно отметить такую вещь. К>>min — эквивалент and К>>max — эквивалент or К>>(для булевой алгебры на множестве 0,1).
M>Кто-то уже такую весчь отмечал.
Я так понял, and — это псевдоним min для булевой алгебры как решетки.
Причем, для любой булевой алгебры над любым множеством.
А xor — это, соответственно, псевдоним + для булевой алгебры как абелевой группы.
Ну или, если найдешь, Асанов М.О., Баранский В.А., Расин В.В.Дискретная математика: графы, матроиды, алгоритмы.(в яндексе мне сразу море ссылок на эти три фамилии кинуло).
2-е Мы все дальше уходим от темы. Идет оооочень жесткий оффтоп. Наверное модераторам не понравится это обсуждение основ алгебры. Может стоит уже закругляться??
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mrhru, Вы писали:
К>>>Кстати, нужно отметить такую вещь. К>>>min — эквивалент and К>>>max — эквивалент or К>>>(для булевой алгебры на множестве 0,1).
M>>Кто-то уже такую весчь отмечал.
К>Я так понял, and — это псевдоним min для булевой алгебры как решетки. К>Причем, для любой булевой алгебры над любым множеством.
К>А xor — это, соответственно, псевдоним + для булевой алгебры как абелевой группы.
Мамочка рОдная! Что же это с нашим образованием-то творится?!!!
А ведь практически у всех оно тут высшее....
Никого не хочу обидеть, но:
1. Если на множестве можно ввести отношение частичного порядка и для любых двух елементов существуют верхняя и нижняя грань, то такое множество является решеткой
2. Любая цепь является решеткой, как частный случай.
3. У решетки всегда есть наименьшая нижняя и наибольшая верхняя грани, которые называются соответственно нулем и единицей решетки.
4. Операции объединения (V) и пересечения (&) двух элементов на решетке вводятся как наименьшая верхняя грань и наибольшаяя нижняя грань соответственно.
5. Если рассмотреть множество точек отрезка [0;1] и ввести на этом множестве отношение строгого порядка (очевидно как), то получим цепь.
6. Решетка является модулярной, если для любых трех елементов выполняется xV(y&z) = (xVy)&z. Факт, что если какая-либо решека собержит немодулярную подрешетку, то она не модулярна является теоремой и не может служить определением.
7. Решетка является дистрибутивной, если для любых 3х элементов выполняется xV(y&z)=(xVy)&(xVz). Кстати, любая модулярная решека дистрибутивна.
Теперь о примере. Если мы имеем цепь, то действительно min(x,y)=x&y, а max(x,y)=xVy. Таким образом получаем, что нужно доказать: xV(y&z)=(xVy)&(xVz)
Для этого можно воспользоваться теоремой, что всякая цепь является дистрибутивной решеткой.
Ролучили примитивное доказательство, но только в том случае, если не надо доказывать теоремы алгебры множеств...
A>Мамочка рОдная! Что же это с нашим образованием-то творится?!!! A>А ведь практически у всех оно тут высшее.... A>Никого не хочу обидеть, но: A>1. Если на множестве можно ввести отношение частичного порядка и для любых двух елементов существуют верхняя и нижняя грань, то такое множество является решеткой
Такое множество называется решеточно упорядоченным.
A>2. Любая цепь является решеткой, как частный случай. A>3. У решетки всегда есть наименьшая нижняя и наибольшая верхняя грани, которые называются соответственно нулем и единицей решетки. A>4. Операции объединения (V) и пересечения (&) двух элементов на решетке вводятся как наименьшая верхняя грань и наибольшаяя нижняя грань соответственно.
А вот множество с этими операциями и будет решеткой.
A>5. Если рассмотреть множество точек отрезка [0;1] и ввести на этом множестве отношение строгого порядка (очевидно как), то получим цепь.
A>6. Решетка является модулярной, если для любых трех елементов выполняется xV(y&z) = (xVy)&z. Факт, что если какая-либо решека собержит немодулярную подрешетку, то она не модулярна является теоремой и не может служить определением.
??? Что-то тут не так...(в определении модулярности).
А приведенная теорема по поводу пентагонов — критерий. Так что можно и за определение выдавать
A>7. Решетка является дистрибутивной, если для любых 3х элементов выполняется xV(y&z)=(xVy)&(xVz). Кстати, любая модулярная решека дистрибутивна.
???? Вот это ооочень странно. Не согласен. Модулярность более слабое свойство, чем дистрибутивность.
Рассмотрим "бриллиант"
b
/ | \
x-y-z
\ | /
a
Он модулярный(не веришь — проверь), но не дистрибутивный:
xV(y&z) = x
(xVy)&(xVz) = a x<>a. Вот так вот.
A>Теперь о примере. Если мы имеем цепь, то действительно min(x,y)=x&y, а max(x,y)=xVy. Таким образом получаем, что нужно доказать: xV(y&z)=(xVy)&(xVz) A>Для этого можно воспользоваться теоремой, что всякая цепь является дистрибутивной решеткой. A>Ролучили примитивное доказательство, но только в том случае, если не надо доказывать теоремы алгебры множеств...
Здравствуйте, DOOM, Вы писали:
DOO>Здравствуйте, Alik, Вы писали:
DOO> A>>Мамочка рОдная! Что же это с нашим образованием-то творится?!!! A>>А ведь практически у всех оно тут высшее.... A>>Никого не хочу обидеть, но: A>>1. Если на множестве можно ввести отношение частичного порядка и для любых двух елементов существуют верхняя и нижняя грань, то такое множество является решеткой DOO>Такое множество называется решеточно упорядоченным.
Такое множество является решеткой, потому что на есть операции верхняя и нижняя грань.
Формально решетка — это четверка <A, R, U, W>, где
A — исходное множество
R — отношение частичного порядка на A
U — отображение AхA->A нижняя грань
W — отображение AхA->A верхняя грань
Ее по-разному записывают при формализации, но все записи изоморфны
DOO> A>>6. Решетка является модулярной, если для любых трех елементов выполняется xV(y&z) = (xVy)&z. Факт, что если какая-либо решека собержит немодулярную подрешетку, то она не модулярна является теоремой и не может служить определением. DOO>??? Что-то тут не так...(в определении модулярности).
Чем же оно не так? Определение, как определение. Я даже сверился только что с конспектом...
DOO>А приведенная теорема по поводу пентагонов — критерий. Так что можно и за определение выдавать
Критерий дает достаточное условие. Определение должно задавать необходимое и достаточное.
A>>7. Решетка является дистрибутивной, если для любых 3х элементов выполняется xV(y&z)=(xVy)&(xVz). Кстати, любая модулярная решека дистрибутивна.
DOO>???? Вот это ооочень странно. Не согласен. Модулярность более слабое свойство, чем дистрибутивность.
Согласен. Опечатка. Собирался написать наоборот: любая немодулярная решека недистрибутивна. Таки надо перечитывать письма перед оправкой.
A>>Теперь о примере. Если мы имеем цепь, то действительно min(x,y)=x&y, а max(x,y)=xVy. Таким образом получаем, что нужно доказать: xV(y&z)=(xVy)&(xVz) A>>Для этого можно воспользоваться теоремой, что всякая цепь является дистрибутивной решеткой. A>>Ролучили примитивное доказательство, но только в том случае, если не надо доказывать теоремы алгебры множеств...
DOO>Ну а это верно!
Здравствуйте, Alik, Вы писали: DOO>>??? Что-то тут не так...(в определении модулярности).
A>Чем же оно не так? Определение, как определение. Я даже сверился только что с конспектом...
Блин, я забыл свериться. По-моему там какие-то элементы д.б. сравнимы
DOO>>А приведенная теорема по поводу пентагонов — критерий. Так что можно и за определение выдавать A>Критерий дает достаточное условие. Определение должно задавать необходимое и достаточное.
???Видимо сказываются различные математические школы(я всегда считал, что критерий это необходимые и достаточные условия ):
Решетка модулярна тогда и только тогда, когда она не содержит пентагонов в качестве подрешеток.
Кстати необходимость просто очевидна, так как пентагон не модулярен, а значит не для любой тройки элементов выполняется условие модулярности.
Господа, это все очень интересно, но мне кажется, что должно быть проще.
Если результат min и max это один из аргументов в зависимости от значения отношения строгого порядка <, а на линейно упорядоченном множестве имеет место транзитивность: если а<b и b<c то a<c, то мне кажется что этого должно быть достаточно. Хотя все равно кроме как перебором пока не знаю как доказать.
В принципе не критично — контрольная то не моя, но все равно интересно — такой простой случай, а простого решения нет.
Здравствуйте, IO, Вы писали:
IO>Здравствуйте, DOOM, Вы писали:
IO>Господа, это все очень интересно, но мне кажется, что должно быть проще. IO>Если результат min и max это один из аргументов в зависимости от значения отношения строгого порядка <, а на линейно упорядоченном множестве имеет место транзитивность: если а<b и b<c то a<c, то мне кажется что этого должно быть достаточно. Хотя все равно кроме как перебором пока не знаю как доказать.
IO>В принципе не критично — контрольная то не моя, но все равно интересно — такой простой случай, а простого решения нет.
Сумнения ваши понятны — если небольшим перебором можно решить задачу, то в случае длинных выражений возникнут проблемы.
Поэтому предложение:
самому убедиться в справедливости нескольких тождеств, достаточных для последующих преобразований.
Отталкиваться можно от частного случая множеств — (0, 1). Как уже говорилось, для них операции min() и max() тождественны and и or. Этот набор [(0, 1), and, or] составляют булеву алгебру, или, чтобы не вызывать двусмысленности, алгебру Буля .
(удобнее обозначать and как * и or как +.)
max(A, min(B,C)) = A + B*C;
min(max(A,B),max(A,C)) =
= (A + B) * (A + C) =
= A*A + A*C + A*B + B*C = //транзитивность (a + b) * с = а *с + b * c
= A + A(C + B) + B*C = //(не помню названия :) ) a + a * b = a
= A + B*C;
Для того, чтобы перенести решение с множества (0, 1) на более общее, на убедиться в спаведливости
Здравствуйте, 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]
Здравствуйте, 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 и min через элементарные функции и модуль! Почему-то мало кто это знает! Короче max(x,y)=max(x-y,0)+y, а max(x,0)=(|x|+x)/2! Ну а дальше дело техники!
)
Перекуём баги на фичи!
(давно это было)).
