Hej, czy powie mi ktoś jak przeprowadza się dowody tutaj?
a) \(\displaystyle{ \mathcal{R}}\) - przechodnia \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ \mathcal{R}^2 \subset \mathcal{R}}\)
b) \(\displaystyle{ \mathcal{R}}\) - przechodnia \(\displaystyle{ \wedge}\) \(\displaystyle{ \mathcal{R}}\)- zwrotna \(\displaystyle{ \Rightarrow }\) \(\displaystyle{ \mathcal{R}^2 \subset \mathcal{R}}\)
W a) zaczynam od wypisania definicji relacji przechodniej, ale potem nie mam pojęcia jak ruszyć. Nie znam w ogóle "schematu" postępowania tutaj. Umiem zamienić prawą stronę na rachunek zdań, ale nie potrafię do niej dojść z lewej.
Relacja przechodnia - dowód
-
salvia_palth
- Użytkownik
- Posty: 10
- Rejestracja: 1 paź 2020, o 19:27
- Płeć: Mężczyzna
- wiek: 19
- Podziękował: 4 razy
-
Jan Kraszewski
- Administrator
- Posty: 34314
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Relacja przechodnia - dowód
Dowód nie polega na sprowadzaniu do rachunku zdań, tylko na zapisaniu prostego rozumowania zdaniami w języku polskim (nie wystarczy zatem wypisać znaczki, trzeba je jeszcze skomentować).
W podpunkcie a) musisz pokazać dwa wynikania, w podpunkcie b) - jedno. Skoro masz wynikanie, to masz założenie i tezę. Patrzysz na tezę i zastanawiasz się, co zrobić, żeby ją udowodnić. Przy czym zakładam, że w podpunkcie b) masz pomyłkę i teza to \(\displaystyle{ R^2=R}\) (a nie \(\displaystyle{ R^2 \subseteq R}\)).
Np. w podpunkcie b) masz udowodnić, że dla relacji \(\displaystyle{ R}\) zachodzi równość \(\displaystyle{ R^2 = R}\). Z podpunktu a) wiesz, że skoro relacja \(\displaystyle{ R}\) jest przechodnia, to \(\displaystyle{ R^2 \subseteq R}\), pozostaje Ci zatem pokazać, że \(\displaystyle{ R \subseteq R^2}\), czyli że dla dowolnej pary \(\displaystyle{ \left\langle x, y\right\rangle }\) jeśli \(\displaystyle{ \left\langle x,y\right\rangle\in R }\), to \(\displaystyle{ \left\langle x,y\right\rangle\in R^2.}\)
Ustalasz zatem dowolną parę \(\displaystyle{ \left\langle x,y\right\rangle\in R }\). Chcesz pokazać, że \(\displaystyle{ \left\langle x,y\right\rangle\in R^2=R\circ R}\) (co z definicji złożenia relacji oznacza, że istnieje "świadek "\(\displaystyle{ t}\) taki, że \(\displaystyle{ \left\langle x,t\right\rangle\in R }\) i \(\displaystyle{ \left\langle t,y\right\rangle\in R}\)). Ponieważ relacja \(\displaystyle{ R}\) jest zwrotna, więc wiesz, że w szczególności \(\displaystyle{ \left\langle y,y\right\rangle\in R }\), co - w połączeniu z założeniem, że \(\displaystyle{ \left\langle x,y\right\rangle\in R }\) - pozwala Ci przyjąć właśnie \(\displaystyle{ y}\) jako "świadka" na to, że \(\displaystyle{ \left\langle x,y\right\rangle\in R\circ R}\) i już.
JK
W podpunkcie a) musisz pokazać dwa wynikania, w podpunkcie b) - jedno. Skoro masz wynikanie, to masz założenie i tezę. Patrzysz na tezę i zastanawiasz się, co zrobić, żeby ją udowodnić. Przy czym zakładam, że w podpunkcie b) masz pomyłkę i teza to \(\displaystyle{ R^2=R}\) (a nie \(\displaystyle{ R^2 \subseteq R}\)).
Np. w podpunkcie b) masz udowodnić, że dla relacji \(\displaystyle{ R}\) zachodzi równość \(\displaystyle{ R^2 = R}\). Z podpunktu a) wiesz, że skoro relacja \(\displaystyle{ R}\) jest przechodnia, to \(\displaystyle{ R^2 \subseteq R}\), pozostaje Ci zatem pokazać, że \(\displaystyle{ R \subseteq R^2}\), czyli że dla dowolnej pary \(\displaystyle{ \left\langle x, y\right\rangle }\) jeśli \(\displaystyle{ \left\langle x,y\right\rangle\in R }\), to \(\displaystyle{ \left\langle x,y\right\rangle\in R^2.}\)
Ustalasz zatem dowolną parę \(\displaystyle{ \left\langle x,y\right\rangle\in R }\). Chcesz pokazać, że \(\displaystyle{ \left\langle x,y\right\rangle\in R^2=R\circ R}\) (co z definicji złożenia relacji oznacza, że istnieje "świadek "\(\displaystyle{ t}\) taki, że \(\displaystyle{ \left\langle x,t\right\rangle\in R }\) i \(\displaystyle{ \left\langle t,y\right\rangle\in R}\)). Ponieważ relacja \(\displaystyle{ R}\) jest zwrotna, więc wiesz, że w szczególności \(\displaystyle{ \left\langle y,y\right\rangle\in R }\), co - w połączeniu z założeniem, że \(\displaystyle{ \left\langle x,y\right\rangle\in R }\) - pozwala Ci przyjąć właśnie \(\displaystyle{ y}\) jako "świadka" na to, że \(\displaystyle{ \left\langle x,y\right\rangle\in R\circ R}\) i już.
JK