LCME Понедельник, 25.09.2017, 05:24
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Форум » Билеты к экзаменам » Программирование » 06 Лемма о транзитивном замыкании (В листках Штукенберга)
06 Лемма о транзитивном замыкании
freidomДата: Понедельник, 28.12.2009, 18:18 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
Если отношение R обладает ромбовидным свойством, то его транзитивное замыкание Z=R^ также обладает ромбовидным свойством.

Должно быть у всех в листках Штукенберга, стр. 39-40. Я вряд ли смогу объяснить лучше, чем там.

 
джужинаторДата: Понедельник, 28.12.2009, 22:24 | Сообщение # 2
Рядовой
Группа: Пользователи
Сообщений: 11
Репутация: 0
Статус: Offline
Леммаю Если отношение R обладает р.с, то его транзитивное замыкание R^ тоже обладает р.с.
Доказательство:
Д-во будет состоять из 2-х утверждений.
Утв 1. Возьмём некоторые a,b и c? что aR^b и aRc, то есть существует такая последовательность х1,х2,...,хn, что х1=а, xn=b и xiRxi+1 для 1=<i<n. Тогда найдется d, что bRd и cR^d, а точнее, сушествует последовательность y1,y2,...yn, где y1=c, yn=d и yiRyi+1.
Доказательство будет вестись индукцией по n.
Бза: n=1. По р.с отношения R должен существовать такой d, что bRd и cRd. Значит, bR^d и cR^d.
Переход: Пусть утверждение справедливо для n-1. Покажем, что оно справедливо и для n. То есть, возьмемм некоторые элементы b и c, такие, что aR^b и aRc, при этом существует такая последовательность х длины n, что х1,х2,...хn, где x1=a, xn=b, xiRxi+1.
Из индукцишнного предположения следует, что для хn-1 существует d, что bRd и последовательность y длины n-1: y1,y2,...yn-1, где y1=c, yn-1=d, yiRyi+1.
Т.к хn-1Rxn и xn-1Rd, то по р.с должен найтись такой t, что xnRt и dRt. Тогда этот t и будет искомым: возьмем новую последовательность:
y1,y2,..yn-1,t
Поскольку yn-1=d, то yn-1Rt и, значит y1R^t, т.е сR^t. Кроме того, мы уже установили, что xnRt (т.е bRt)ю Отсюда следует, что bR^t и сR^t.

Утв 2. Возьмем некоторые а,b и с, что aR^b И aR^c, т.е существуют такие последовательности:
x1,x2,...xn, что х1=а, xn=b и xiRxi+1 для 1=<i<m
p1,p2,...pm, что p1=а, pm=c и piRpi+1 для 1=<i<m
Тогда найдется такое d, что bR^d и cR^d, точнее, существуют такие последовательности
q1,q2,...qm, что q1=b, qm=d и qiRqi+1 для 1=<i<m
y1,y2,...yn, что y1=c, yn=d и yiRyi+1 для 1=<i<m
Доказательство аналогично предыдущему случаю, только вместо р.с нужно напрямую использовать утв 1. Получив по предположению индукции , что для а,b и pm-1 (aR^B и aR^pm-1) найдется такой t, что bR^t и pm-1R^t, применим к pm-1R^t и pm-1Rpm утверждение и получим, что существует d, что bR^d и cR^d. Формально это рассуждение проводить не будем, а ограничимся лишь соответствующей ему картинкой (дальше приводится картинка и д-во заканчивается). smile smile smile

 
freidomДата: Понедельник, 28.12.2009, 22:41 | Сообщение # 3
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
Не впадлу было?
 
джужинаторДата: Вторник, 29.12.2009, 09:57 | Сообщение # 4
Рядовой
Группа: Пользователи
Сообщений: 11
Репутация: 0
Статус: Offline
надо было на плеер закачать... happy
 
Форум » Билеты к экзаменам » Программирование » 06 Лемма о транзитивном замыкании (В листках Штукенберга)
Страница 1 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz