Matematyka.pl

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)}\)

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

A dlaczego możemy rozdzielić te kwantyfikatory tak jak zrobiłeś w pierwszej lini?

\(\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

\(\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

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