Logika, zadanie nr 2044

Autor	Zadanie / Rozwiązanie
zieloniutka postów: 9	2014-01-30 21:34:04 1. Rozwazamy zbiór T=(2,3,...,15)wraz z relacją podzielności ograniczoną do elementów tego zbioru. a) Narysować diagram relacji b) Wskazać elementy wyróżnione c) Wskazać wszystkie łańcuchy długości 3 2. Zbiró <X,R^-1> nazywamy dualnym do <X,R>. a) Udowodnić, że jeżeli <X,R> jest zbiorem częściowo uporządkowanym, to <X,R^-1> także jest zbiorem częściowo uporządkowanym. b) Czy analogiczne twierdzenie jest prawdziwe, jeśli <X,R> jest zbiorem liniowo uporządkowanym? c) Czy analogiczne twierdzenie jest prawdziwe, jeśli <X,R> jest zbiorem dobrze uporządkowanym? d) Jaki jest związek elementów wyróżnionych w <X,R> i w <X,R^-1>? Proszę o DOKŁADNE wyjaśnienie, krok po kroku zaczynając od definicji

tumor postów: 8070	2014-05-14 13:39:20 1. No nie narysuję. Ale chyba umiesz. Elementy minimalne w sensie relacji podzielności to takie, które dzielą się tylko przez siebie. Zatem minimalne są $2,3,5,7,11,13$ Jeśli jest więcej niż jeden minimalny, to już na pewno nie ma najmniejszego. Podobnie elementy maksymalne to takie, które nie są dzielnikami innych elementów. Maksymalne są $15,14,13,12,11,10,9,8,$ I analogicznie rozumując nie ma elementu największego. Łańcuchy o długości 3: 2,4,8 2,4,12 2,6,12

tumor postów: 8070	2014-05-14 13:46:52 2. a) b) Jeśli relacja $R$ jest zwrotna, to $R^{-1}$ też jest zwrotna. Niech $R$ będzie relacją przechodnią. Jeśli $cR^{-1}b$ oraz $bR^{-1}a$, to $aRb$ i $bRc$, wówczas $aRc$ czyli $cR^{-1}a$, zatem także $R^{-1}$ jest relacją przechodnią. Niech $R$ będzie słabo antysymetryczna. Jeśli $aR^{-1}b$ i $bR^{-1}a$, to $aRb$ i $bRa$, wówczas $a=b$, czyli także $R^{-1}$ jest słabo antysymetryczna. Wreszcie niech $R$ jest spójna. Jeśli $aRb$ to $bR^{-1}a$, jeśli $bRa$ to $aR^{-1}b$, a jeśli żadne z wcześniejszych to $a=b$, zatem $R^{-1}$ jest spójna. Zatem jeśli $R$ jest porządkiem częściowym (liniowym) to $R^{-1}$ jest porządkiem częściowym (liniowym).

tumor postów: 8070	2014-05-14 13:52:52 2. d) c) Elementy maksymalne w sensie relacji $R$ są minimalne w sensie $R^{-1}$, analogicznie minimalne w sensie $R$ są maksymalne w sensie $R^{-1}$, element najmniejszy w sensie $R$ jest elementem największym w sensie $R^{-1}$, element największy w sensie $R$ jest elementem najmniejszym w sensie $R^{-1}$. Zatem jeśli $<X,R>$ jest porządkiem dobrym, czyli każdy podzbiór $ X$ ma element najmniejszy w sensie $R$, to wiemy, że każdy podzbiór $X$ ma element największy w sensie $R^{-1}$, to jednak za mało, by $<X,R^{-1}>$ było dobrym porządkiem. Dla przykładu $<N,\le >$ jest dobrym porządkiem, ale $<N,\ge>$ nie jest dobrym porządkiem.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj