Инструменты пользователя

Инструменты сайта


Боковая панель

Регистрация

Учебные курсы

Учебные проекты

Материалы к экзаменам

Полезная информация

Обратная связь

textbooks:prepodavatelyu:teoria_reshetok:primery_reshetok

Настало время пополнить основные сведения о ре¬шетках и рассмотреть некоторые примеры, которые мож¬но отнести к школьной математике. “В предыдущей главе мы определили решетку как упорядоченное множество W = (Р, ≤), в котором для любых двух элементов a, b ϵ Р существуют sup(W){a, b} и inf(W) {а, b}. Обе эти записи достаточно ясно выра¬жают, какие элементы соответствуют паре а, b, но они неудобны своей громоздкостью. Поэтому в теории реше¬ток принято соглашение вместо sup(W){a, b} писать a^b, а вместо inf(W){а, b} писать а V b[5,c.26]. “ В том случае, когда а =b, эти определения расширяют, полагая a V а = а ^ а = а. Запись с = a V b (соответственно d = а ^ b) читаем: «с равно объединению а и b» (соот¬ветственно «d равно пересечению а и b»). Элемент с на¬зывается объединением элементов а и b, элемент d назы¬вается их пересечением. В каждой решетке W=(Р, ≤) для всех а, b, с ϵ Р истинны следующие соотношения: a) а V b = b V а, а ^b = b ^ а; b) (а V b)V с = а V (b V с), (а ^ b) ^ с = а ^{b ^ с)*); c) если а ^ b, то а ^ b = а и b = а V b; d) а^ b ≤ а, a ≤ а V b; e) а V(а ^ b)= а, а ^(а V b)= а; f) если а ^ b = а V b, то а = b.”[5,c.37]

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

Tеорема 1. Решетка W с наименьшим и наибольшим элементами тогда и только тогда является булевой ре¬шеткой, когда для любых ее элементов а, b, с таких, что а ≤ b ≤ с, существует в точности одно относительное дополнение элемента b в интервале [а, с]. Доказательство. Ввиду результата задачи 1 достаточно доказать, что решетка W с указанным свой¬ством дистрибутивна, а это вытекает из теоремы 2, и что она является решеткой с дополнениями, что непосред¬ственно следует из условия, если выбрать в качестве а наименьший, а в качестве с наибольший элемент ре¬шетки W”[6,c.48]. “Какая задача 1 и что за теорема 2?”-спросите вы…

Задача 1: Докажите, что в любой булевой решетке для каждого элемента b ϵ [а, с] существует единствен¬ное относительное дополнение в интервале [а, с]. Док-во: Пусть W - дистрибутивная решетка. То¬гда в ней выполняется следующее условие: (7) если элементы а, b, с, А, В, С таковы, что A≤а≤b≤с≤С, A≤B≤C и b V В=С, b ^ В = А, то существует в точности одно относительное дополнение b 1 элемента b в интервале [а, c].

Задача 2. Нужно доказать, что если решетка 5s со¬держит подрешетку с диаграммой , то W не дистрибутивна. Решение. Действительно, а V (b ^ с) = а V 0 = а, но (а V b) ^(а V с) = i ^(а V с) = а V с ≠ а.

Теорема 2: “Решетка W дистрибутивна тогда и только тогда, когда в ней выполняется условие (7). Доказательство. 1) Согласно результату док-ва задачи 1, в любой дистрибутивной решетке имеет место (7). 2) Предположим, что W - решетка, в которой выпол¬няется условие (7). Поскольку прямое доказательство слишком длинно, используем результат замечания задачи 2. Если W содержит подрешетку с диаграммой, то обозначим элементы этих реше¬ток в соответствии с обозначениями из (7) . Для элемента b в обоих случаях существует два разных относительных дополнения (b1 и b2) в интервале [а, с]. Это несовместимо с предположением об истинности (7), и полученное противоречие доказывает, что решетка W дистрибутивна. Решетка W с наименьшим элементом 0 и наибольшим элементом 1, в которой для любого элемента существует хотя бы одно дополнение, называется решеткой с допол¬нениями. Дистрибутивная решетка с дополнениями на¬зывается булевой решеткой”[8,c.54].

textbooks/prepodavatelyu/teoria_reshetok/primery_reshetok.txt · Последние изменения: 2014/11/27 09:04 (внешнее изменение)