Ćwiczenia 13: logika

Zadania

1. Zapisać następujące stwierdzenia w języku arytmetyki liczb naturalnych \((+, \cdot, 0, 1, =)\) używając symboli logicznych i kwantyfikatorów:
   a) Liczba a jest mniejsza lub równa liczbie b.
   b) Liczba a jest resztą z dzielenia b przez c.
   c) Liczba a jest pierwsza.
   d) Liczba a jest największym wspólnym dzielnikiem liczb b i c chyba, że jest parzysta.
   e) Liczby x i y mają te same dzielniki pierwsze.
2. Sformułować poprawne zaprzeczenia stwierdzeń:
   a) Liczby m i n są pierwsze.
   b) Liczby m in są względnie pierwsze.
3. Dla każdej z następujących par struktur wskazać formułę prawdziwą w jednej, a w drugiej nie.
   a) \(\langle \mathbb{Q}, +, \cdot, 0, 1\rangle\) i \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\),
   b) \(\langle \mathbb{N}, +, 0\rangle\) i \(\langle \mathbb{R}, +, 0 \rangle\),
   c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\mathbb{R}^2\),
   d) \(\langle P_2, \bot\rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_n\) to zbiór prostych w \(\mathbb{R}^n\)
   e) \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\) i \(\langle P(\mathbb{N}), \cup, \cap, \emptyset, \mathbb{N}\rangle\),
   f) \(\langle \mathbb{N}, \leq, 0\rangle\) i \(\langle \mathbb{R}, \leq, 0\rangle\),
   g) \(\langle \mathbb{N}, \leq\rangle\) i \(\langle \mathbb{R}, \leq\rangle\),
   h) \(\langle \mathbb{N}, +,  0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).
4.  Czy następujące formuły są tautologiami? Czy są spełnialne?
   a) \(\forall x (p(x) \to q(x)) \vee \forall x (q(x) \to p(x))\),
   b) \(\exists x (P(x) \to \forall y P(y))\),
   c) \( (\exists x \exists y P(x,y) \to \forall y R(y)) \to \forall x(P(x,x) \to R(x)) \),
   d) \( \forall x \exists y \forall u \exists v P(x,y,u,v) \to  \forall u \exists v \forall x \exists y  P(x,y,u,v) \).