Дискретная математика без формул
Шрифт:
Более интересными являются другие отношения, очень похожие на отношения порядка. Например, «быть немного выше ростом». Это антисимметричное, но нетранзитивное отношение. Иван немного выше ростом Петра, Петро немного выше ростом Егора. Но Иван намного выше ростом Егора. Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ. Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, ящерицы «плавно» превращаются в птиц и т.п.
Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные, на которые накладывают ряд дополнительных свойств, изучаются в рамках раздела математики
Можно предположить, что название «решетки» возникло в связи с использованием так называемых диаграмм Хассе, которые может и напоминают экстравагантные решетки для окон… Но мы договорились без формул, а тем более без рисунков. Рисунки, в отличие от формул, народ любит. Но рисовать картинки в Ворде еще противнее, чем формулы, поэтому постараемся, насколько, конечно, возможно, компенсировать и их красноречием…
Начнем с примеров решеток.
Возьмем слова: о, ор, вор, ворот, кол, олово, коловорот, и упорядочим их по вхождению одних слов в другие (не забывая, что каждое слово входит в само себя). Это будет наша первая решетка.
Можно убедиться, что здесь выполняются все свойства частичного порядка. А о дополнительных свойствах поговорим позже.
Числа: 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить нацело, так же образуют решетку.
Обычные действительные числа с отношением «больше или равно» дают одну из самых распространенных решеток. Хотя для нас она менее экзотическая. Можно сказать, простая как бревно…
Множество всех подмножеств какого-то множества с отношением включения также дает решетку, причем, с рядом замечательных свойств.
Для определения решетки договоримся называть элемент НАИБОЛЬШИМ (НАИМЕНЬШИМ), если он больше (меньше) любого другого элемента частично-упорядоченного множества– кратко ЧУМ. За математиками иногда можно заметить педантичность до занудства, а иногда непонятную приблизительность. Строже и точнее было бы здесь и далее, вопреки сложившейся традиции, применительно к ЧУМ, обладающим свойством рефлексивности, говорить «больше или равно» " НАИБОЛЬШИЙ ИЛИ РАВНЫЙ" и т.п. Но мы тоже будем говорить кратко «больше», подразумевая эти более длинные и точные словосочетания. Наибольший элемент, если таковой существует – единственный. На то он и наибольший. С наименьшим все аналогично.
МАКСИМАЛЬНЫМ (МИНИМАЛЬНЫМ)называется элемент ЧУМ, больше (меньше) которого в этом множестве нет элементов. На первый взгляд это определение повторяет предыдущее. Но максимальных элементов в ЧУМможет быть и несколько. Если рассматривать современный мир, упорядоченный по этажам власти, то все главы государств «максимальны», но каждый в своей стране, поскольку главнее его нет. Но каждый из них не главнее другого главы. Главы всей планеты не существует и даже Генсек ООН его не заменит. Если бы, следуя фантастическим романам, существовал глава Земли, то он был бы и максимальным и наибольшим элементом.
Если, далее, возьмем множество студентов потока и наведем в нем частичный порядок. Имеется в виду не «всеми доступными средствами», а лишь отношением «учится лучше (или одинаково)», считая, что ради такого дела можно для любых двух студентов решить, который лучше… Из этого множества выделим группу ух-005 и найдем студентов потока,
которые учатся лучше всех студентов группы ух-005. То есть найдем на потоке студентов, «наибольших» для этой группы. Таких студентов может оказаться несколько, если только «наибольший» студент группы не является одновременно наибольшим элементом всего потока. Такое множество наибольших элементов называется множеством МАЖОРАНТ. Рассматривая наименьших студентов, получим множество МИНОРАНТ. А теперь в самом множестве мажорант (минорант) найдем наименьший (наибольший) элемент [это не опечатка!]. Для данного примера это будут лучший и худший студенты самой группы ух-005. Такие элементы называются соответственно СУПРЕМУМи ИНФИМУМ. Или кратко, supи inf.Для множества чисел 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить, возьмем подмножество чисел 3, 6, 9. Для него множество мажорант будет 12, 36. Множество минорант – 3, 1. супремум – 12, инфимум – 3.
РЕШЕТКОЙназывается ЧУМ, в котором для любого непустого подмножества существуют супремум и инфимум.
Решетки, которые получаются как множества подмножеств данного конечного множества, с отношением включения, относятся к БУЛЕВЫМ РЕШЕТКАМ. Для тех, кто знают про булеву алгебру, добавим, что традиционная булева алгебра есть решетка из двух элементов: «истина», «ложь», с отношением порядка «более истинный».
Определить решетку можно и «алгебраически». Если для элементов множества с отношением частичного порядка (частично-упорядоченным множеством) выполняются законы коммутативный, ассоциативный, поглощения и идемпотентности, то такое частично-упорядоченное множество называется решеткой.
Если, кроме того, выполняется дистрибутивный закон – то решетка называется дистрибутивной.
Тут уж поверьте на слово – с помощью решеток решен ряд важных проблем. В том числе и теоретического программирования.
Лекция 6. МАТЕМАТИЧЕСКАЯ ЛОГИКА (БЕССМЫСЛЕННАЯ ЛОГИКА)
Обычно, настоящие математики не приспособлены к жизни. Посмотрите на них, если имеете возможность. Они где-то витают… Казалось бы, следует сделать исключение для логиков. Хотя бы потому, что поступки логиков должны быть наиболее логичны. Как бы не так! Все как раз наоборот! На самом-то деле логика строго оговаривает свои «правила игры» и действует пунктуально до беспощадности, граничащей с идиотизмом, в рамках этих правил. При этом их логика с «логикой жизни» имеет не больше общего, чем вы найдете общего в шахматной и Бородинской битвах… Но все-таки есть что-то похожее… Когда страсти с обеих противоборствующих сторон накаляются и дело доходит до рукопашной!…
Кстати, основной клоунский прием: с фанатичным исступлением совершать некие формально логичные, но с точки зрения жизненной реальности абсурдные до идиотизма, действия. Всем, прежде всего детям, очевиден полный идиотизм происходящего, но клоун продолжает поступать ЛОГИЧНО! И ничто не в силах свернуть его с этого пути.
Вообще-то всяких разных логик много. Выражаясь более конкретно – бесконечно много. Поэтому будем говорить не о логике вообще, как это любят делать в некоторых учебниках для юристов, а о математической логике. Тем более, что логики у юристов часто даже меньше, чем у политиков… А от политики предпочтительно держаться подальше… Математическая логика понятие тоже достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл… Логично?