[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
Zadání
- Find first-order formulae (with symbol $\leq$) expressing about a partially ordered set
- "$x$ is the smallest element", "$x$ is the minimal element"
- "$x$ has an immediate succerssor"
- "every two elements have the greatest common predecessor"
- Find first-order formulae (with use of equality) expressing for a fixed $n > 0$ that
- "there exist at least $n$ elements"
- "there exist at most $n$ elements"
- "there exist exactly $n$ elements"
Řešení
- $((\forall a \in A \exists x \in A )(x < a))$, $((\forall a \in A \exists x \in A )(x \leq a))$
- $((x,a,b \in A)( x < a )((\nexists b)(x < b < a)))$
- $((\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))$
-
- $((\exists x_1 \dots \exists x_n)(\bigwedge \limits _{1 \leq i \leq j \leq n} \rceil (x_i = x_j)))$
- $((\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))))$
- $((\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
Zadání
- Show that in Hilbet's calculus the following is provable for every formulas $\varphi, \psi, \chi$
- $\vdash _H \varphi \rightarrow \varphi$
Řešení
-
-
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$])
Zadání
- Find first-order formulae (with symbol $\leq$) expressing about a partially ordered set
- "$x$ is the smallest element", "$x$ is the minimal element"
- "$x$ has an immediate succerssor"
- "every two elements have the greatest common predecessor"
- Find first-order formulae (with use of equality) expressing for a fixed $n > 0$ that
- "there exist at least $n$ elements"
- "there exist at most $n$ elements"
- "there exist exactly $n$ elements"
Řešení
- $((\forall a \in A \exists x \in A )(x < a))$, $((\forall a \in A \exists x \in A )(x \leq a))$
- $((x,a,b \in A)( x < a )((\nexists b)(x < b < a)))$
- $((\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))$
-
- $((\exists x_1 \dots \exists x_n)(\bigwedge \limits _{1 \leq i \leq j \leq n} \rceil (x_i = x_j)))$
- $((\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))))$
- $((\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
Zadání
- Show that in Hilbet's calculus the following is provable for every formulas $\varphi, \psi, \chi$
- $\vdash _H \varphi \rightarrow \varphi$
Řešení
-
-
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$])
Zadání
- Show that in Hilbet's calculus the following is provable for every formulas $\varphi, \psi, \chi$
- $\vdash _H \varphi \rightarrow \varphi$
Řešení
-
-
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$])
-
1. $(\varphi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \chi))$ (axiom 2)