Ć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) 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}, +,  0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).
4. Jakiej mocy jest zbiór wszystkich ciągłych w \(\mathbb{R}\)?