LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sav08:homework10 [2008/04/30 16:10]
piskac
sav08:homework10 [2015/04/21 17:30] (current)
Line 4: Line 4:
  
 Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees) and let $r$ be the implication relation on formulas: Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees) and let $r$ be the implication relation on formulas:
-\[+\begin{equation*}
    r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \}    r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \}
-\]+\end{equation*}
 Check whether $r$ is reflexive, antisymmetric,​ and transitive relation. Check whether $r$ is reflexive, antisymmetric,​ and transitive relation.
  
Line 18: Line 18:
  
 Let function $f : A \to A$ be given by Let function $f : A \to A$ be given by
-\[+\begin{equation*}
     f(x) = \left\{\begin{array}{l}     f(x) = \left\{\begin{array}{l}
 \frac{1}{2} + \frac{1}{4}x,​ \mbox{ if } x \in [0,​\frac{2}{3}) \\ \frac{1}{2} + \frac{1}{4}x,​ \mbox{ if } x \in [0,​\frac{2}{3}) \\
Line 24: Line 24:
 \frac{3}{5} + \frac{1}{5}x,​ \mbox{ if } x \in [\frac{2}{3},​1] \frac{3}{5} + \frac{1}{5}x,​ \mbox{ if } x \in [\frac{2}{3},​1]
 \end{array}\right. \end{array}\right.
-\]+\end{equation*}
 (It may help you to try to draw $f$.) (It may help you to try to draw $f$.)
  
Line 37: Line 37:
 === Part c) === === Part c) ===
  
-Define $iter(x) = \sqcup \{ f^n(x) \mid n \in \{0,​1,​2,​\ldots \}\}$. ​ (This is in fact equal to $\lim_{n\to\infty} f^n(x)$.)+Define $iter(x) = \sqcup \{ f^n(x) \mid n \in \{0,​1,​2,​\ldots \}\}$. ​ (This is in fact equal to $\lim_{n\to\infty} f^n(x)$ ​when $f$ is a monotonic bounded function.)
  
-Compute $iter(0)$ (if you can, prove that the computed value is correct by definition of $iter$). ​ Is $iter(0)$ a fixpoint of $f$?  Is $iter(iter(0))$ a fixpoint of $f$? Is $f$ an $\omega$-continuous function?+Compute $iter(0)$ (prove that the computed value is correct by definition of $iter$, that is, that the value is indeed $\sqcup$ of the set of values).  Is $iter(0)$ a fixpoint of $f$?  Is $iter(iter(0))$ a fixpoint of $f$? Is $f$ an $\omega$-continuous function?
  
 === Optional part d) === === Optional part d) ===
  
 Define a monotonic function $f : A \to A$ such that, for every natural number $k$, the value $iter^k(0)$ is not a fixpoint of $f$.  (It may be difficult to draw $f$.) Define a monotonic function $f : A \to A$ such that, for every natural number $k$, the value $iter^k(0)$ is not a fixpoint of $f$.  (It may be difficult to draw $f$.)
-