[NAIL062] Výroková a predikátová logika


There will be two tests throughout the semester. For the credit from the seminar you need to obtain at least 2/3 points from tests. Additional points can be obtained for activity during the seminars or homeworks.

Domácí úkoly

Cvičení 1 - 5. 10. 2016

  1. Find first-order formulae (with symbol $\leq$) expressing about a partially ordered set
    1. "$x$ is the smallest element", "$x$ is the minimal element"
    2. "$x$ has an immediate succerssor"
    3. "every two elements have the greatest common predecessor"
  2. Find first-order formulae (with use of equality) expressing for a fixed $n > 0$ that
    1. "there exist at least $n$ elements"
    2. "there exist at most $n$ elements"
    3. "there exist exactly $n$ elements"
    1. $((\forall a \in A \exists x \in A )(x < a))$, $((\forall a \in A \exists x \in A )(x \leq a))$
    2. $((x,a,b \in A)( x < a )((\nexists b)(x < b < a)))$
    3. $((\forall x, y, b \in A \exists a \in A)(a \leq x)(a \leq y)(b \leq x)(b \leq y)(a \leq b))$
    1. $((\exists x_1 \dots \exists x_n)(\bigwedge \limits _{1 \leq i \leq j \leq n} \rceil (x_i = x_j)))$
    2. $((\exists x_1 \in X \dots \exists x_n \in X)(\bigwedge \limits _{i \geq n} ((x_i \geq x_n)(x_i \notin X))))$
    3. $((\exists x_1 \in X \dots \exists x_n \in X)(\bigwedge \limits _{i \geq n \leq j} (((x_i \geq x_n)\vee(x_j \leq x_n))((x_i \notin X)\vee (x_j \notin X))))$

Cvičení 6 - 9. 11. 2016

  1. Show that in Hilbet's calculus the following is provable for every formulas $\varphi, \psi, \chi$
    1. $\vdash _H \varphi \rightarrow \varphi$
    1. 1. $(\varphi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \chi))$ (axiom 2)
      2. $(\omega \rightarrow ((\omega \rightarrow \omega) \rightarrow \omega)) \rightarrow ((\omega \rightarrow (\omega \rightarrow \omega)) \rightarrow (\omega \rightarrow \omega))$ (from 1. by substitution [$\omega/\varphi$, $\omega \rightarrow \omega/\psi$, $\omega/\chi$])
      3. $\varphi \rightarrow (\psi \rightarrow \varphi)$ (axiom 1)
      4. $\omega \rightarrow ((\omega \rightarrow \omega) \rightarrow \omega)$ (from 3. by substitution [$\omega/\varphi$, $\omega \rightarrow \omega/\psi$])
      5. $(\omega \rightarrow (\omega \rightarrow \omega)) \rightarrow (\omega \rightarrow \omega)$ (from 2. and 4. by modus ponens)
      6. $\omega \rightarrow (\omega \rightarrow \omega)$ (from 3. by substitution [$\omega/\varphi$, $\omega/\psi$])
      7. $\omega \rightarrow \omega$ (from 5. and 6. by modus ponens)
      8. $\varphi \rightarrow \varphi$ (from 7. by substitution [$\varphi/\omega$])

Poslední aktualizace: 16. 11. 2016 15:35:37 CET