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

### Zápočet

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"
##### Řešení
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$])