Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:graphs_as_interpretations [2008/03/19 16:37] vkuncak |
sav08:graphs_as_interpretations [2008/03/25 16:07] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Graphs as Interpretations ====== | ====== Graphs as Interpretations ====== | ||
| - | Directed graph is is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$. Graph is therefore specified by an [[First-Order Logic Semantics|interpretation]] $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$. | + | Directed graph is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$. Graph is therefore specified by an [[First-Order Logic Semantics|interpretation]] $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$. |
| Example: $D = \{1,2,3,4\}$, $\alpha(edge) = \{ (1,2), (2,3), (1,3), (3,4) \}$. | Example: $D = \{1,2,3,4\}$, $\alpha(edge) = \{ (1,2), (2,3), (1,3), (3,4) \}$. | ||
| Line 19: | Line 19: | ||
| **Tournament:** | **Tournament:** | ||
| \[ | \[ | ||
| - | \forall x, y.\ (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x)) | + | (\forall x, y.\ x \neq y \rightarrow (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x))) \land (\forall x. \lnot edge(x,x)) |
| \] | \] | ||