Mam takie polecenie, że mam napisać co wymaga graf relacji od tak zapisanej formuły, czyli np jeśli wychodzi polaczenie z wierzchołka to ma być tam też petelka itd:
\(\displaystyle{ \exists x\forall y\left(\left\langle x,x\right\rangle \in R\rightarrow\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right)}\)
Grafy relacji
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Grafy relacji
Lepiej przedstawić tę formułę w postaci równoważnej:
\(\displaystyle{ \exists x\left(\left\langle x,x\right\rangle \in R\rightarrow\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right).}\)
No i polecenie jest dość... nieprecyzyjne. Tym bardziej, że ta formuła wygląda podejrzanie, bo łączy kwantyfikator szczegółowy z implikacją, więc po kolejnym równoważnym przekształceniu dostajemy
\(\displaystyle{ \exists x\left(\left\langle x,x\right\rangle \notin R\lor\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow \exists x\left\langle x,x\right\rangle \notin R\lor\exists x\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right).}\)
Zatem w grafie relacji, dla której ta formuła jest prawdziwa, albo istnieje wierzchołek bez pętelki, albo każdy wierzchołek ma pętelkę i jest wierzchołek, z którego wychodzą dwustronne strzałki do wszystkich innych wierzchołków.
JK
\(\displaystyle{ \exists x\left(\left\langle x,x\right\rangle \in R\rightarrow\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right).}\)
No i polecenie jest dość... nieprecyzyjne. Tym bardziej, że ta formuła wygląda podejrzanie, bo łączy kwantyfikator szczegółowy z implikacją, więc po kolejnym równoważnym przekształceniu dostajemy
\(\displaystyle{ \exists x\left(\left\langle x,x\right\rangle \notin R\lor\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow \exists x\left\langle x,x\right\rangle \notin R\lor\exists x\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right).}\)
Zatem w grafie relacji, dla której ta formuła jest prawdziwa, albo istnieje wierzchołek bez pętelki, albo każdy wierzchołek ma pętelkę i jest wierzchołek, z którego wychodzą dwustronne strzałki do wszystkich innych wierzchołków.
JK
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Grafy relacji
\(\displaystyle{ \exists x\forall y\left(\left\langle x,x\right\rangle \in R\rightarrow\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow }\)
Prawo eliminacji implikacji.
\(\displaystyle{ \Leftrightarrow \exists x\forall y\left(\red{\left\langle x,x\right\rangle \notin R\ \lor}\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow}\)
Czerwony fragment nie zależy od zmiennej \(\displaystyle{ y}\), więc mogę wyciągnąć go przed kwantyfikator.
\(\displaystyle{ \Leftrightarrow \exists x\left(\red{\left\langle x,x\right\rangle \notin R\ \lor}\ \forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow}\)
Ponownie prawo eliminacji implikacji.
\(\displaystyle{ \Leftrightarrow \exists x\left(\left\langle x,x\right\rangle \in R\rightarrow\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right).}\)
Przy czym w dalszej części rozwiązania czwarta linijka jest zbędna, bo zajmuję się przekształcaniem formuły z trzeciej linijki.
JK
Prawo eliminacji implikacji.
\(\displaystyle{ \Leftrightarrow \exists x\forall y\left(\red{\left\langle x,x\right\rangle \notin R\ \lor}\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow}\)
Czerwony fragment nie zależy od zmiennej \(\displaystyle{ y}\), więc mogę wyciągnąć go przed kwantyfikator.
\(\displaystyle{ \Leftrightarrow \exists x\left(\red{\left\langle x,x\right\rangle \notin R\ \lor}\ \forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right) \Leftrightarrow}\)
Ponownie prawo eliminacji implikacji.
\(\displaystyle{ \Leftrightarrow \exists x\left(\left\langle x,x\right\rangle \in R\rightarrow\forall y\left(\left\langle x,y\right\rangle \in R\ \land\ \left\langle y,x\right\rangle \in R\right)\right).}\)
Przy czym w dalszej części rozwiązania czwarta linijka jest zbędna, bo zajmuję się przekształcaniem formuły z trzeciej linijki.
JK
-
- Użytkownik
- Posty: 95
- Rejestracja: 20 sty 2021, o 10:40
- Płeć: Mężczyzna
- wiek: 18
- Podziękował: 1 raz
- Pomógł: 1 raz
Re: Grafy relacji
\(\displaystyle{ \forall x\exists y((<x,y>\in R\ \land\ <y,x>\in R)\rightarrow\ <x,x>\in R)}\)
Jeśli są dwa dla każdego to wtedy: dla kazdego elementu jeśli jest połączenie przychodzace i wychodzące to element ma pętelke.
Nie potrafie zrozumieć co zmieni isntnieje
Jeśli są dwa dla każdego to wtedy: dla kazdego elementu jeśli jest połączenie przychodzace i wychodzące to element ma pętelke.
Nie potrafie zrozumieć co zmieni isntnieje
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Grafy relacji
A ja nie rozumiem tego, co napisałeś.
Ta formuła znów jest "lewa", bo ma kwantyfikator egzystencjalny z implikacją (co wyklucza "intuicyjnie rozsądne" interpretacje). Przekształcamy równoważnie:
\(\displaystyle{ \forall x\exists y((\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\rightarrow\left\langle x,x\right\rangle \in R) \Leftrightarrow \\
\forall x\exists y(\neg(\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\lor\left\langle x,x\right\rangle \in R)\Leftrightarrow \\
\forall x\left( \left\langle x,x\right\rangle \in R\lor \exists y \neg(\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\right) \Leftrightarrow \\
\forall x\left( \left\langle x,x\right\rangle \notin R \rightarrow \exists y (\left\langle x,y\right\rangle \notin R\ \lor\left\langle y,x\right\rangle \notin R)\right).}\)
I teraz widać, że ta formuła jest prawdziwa dla dowolnej relacji. Jeśli bowiem dla jakiegoś \(\displaystyle{ x}\)-a nie ma pętelki, czyli \(\displaystyle{ \left\langle x,x\right\rangle \notin R}\), to oczywiście istnieje \(\displaystyle{ y}\), dla którego prawdziwy jest warunek \(\displaystyle{ \left\langle x,y\right\rangle \notin R\ \lor\left\langle y,x\right\rangle \notin R}\), mianowicie \(\displaystyle{ y=x}\). Co oznacza, że ta formuła nie niesie dokładnie ŻADNEJ informacji o relacji \(\displaystyle{ R}\).
JK
Ta formuła znów jest "lewa", bo ma kwantyfikator egzystencjalny z implikacją (co wyklucza "intuicyjnie rozsądne" interpretacje). Przekształcamy równoważnie:
\(\displaystyle{ \forall x\exists y((\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\rightarrow\left\langle x,x\right\rangle \in R) \Leftrightarrow \\
\forall x\exists y(\neg(\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\lor\left\langle x,x\right\rangle \in R)\Leftrightarrow \\
\forall x\left( \left\langle x,x\right\rangle \in R\lor \exists y \neg(\left\langle x,y\right\rangle \in R\ \land\left\langle y,x\right\rangle \in R)\right) \Leftrightarrow \\
\forall x\left( \left\langle x,x\right\rangle \notin R \rightarrow \exists y (\left\langle x,y\right\rangle \notin R\ \lor\left\langle y,x\right\rangle \notin R)\right).}\)
I teraz widać, że ta formuła jest prawdziwa dla dowolnej relacji. Jeśli bowiem dla jakiegoś \(\displaystyle{ x}\)-a nie ma pętelki, czyli \(\displaystyle{ \left\langle x,x\right\rangle \notin R}\), to oczywiście istnieje \(\displaystyle{ y}\), dla którego prawdziwy jest warunek \(\displaystyle{ \left\langle x,y\right\rangle \notin R\ \lor\left\langle y,x\right\rangle \notin R}\), mianowicie \(\displaystyle{ y=x}\). Co oznacza, że ta formuła nie niesie dokładnie ŻADNEJ informacji o relacji \(\displaystyle{ R}\).
JK