Pokazywanie postów oznaczonych etykietą logika. Pokaż wszystkie posty
Pokazywanie postów oznaczonych etykietą logika. Pokaż wszystkie posty

11 grudnia 2017

Ćwiczenia 11: logika

Zadania

  1. W strukturze \(\mathcal{A} =\langle \NN, P^{\mathcal{A}},Q^{\mathcal{A}}\rangle\), gdzie:
    \( \langle a,b \rangle \in P^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(a+b \geq 6\),
    \( \langle a,b \rangle \in Q^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(b = a + 2\),
    wyznaczyć wartość
    a) formuły \(\forall x P(x,y) \to \exists xQ(x,y)\),
    b) formuły \(\forall x P(x,y) \to \exists xQ(x,z)\),
    przy wartościowwaniu \(v(y) = 7, v(z)=1\).
  2. Podać przykład modelu i wartościowania, przy którym formuła
    \[ P(x,f(x)) \to \forall x \exists y P(f(y), x) \]
    jest a) spełniona b) niespełniona.
  3. Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):
    a) \(\langle \QQ, +, \cdot, 0, 1\rangle\) i \(\langle \RR, +, \cdot, 0, 1\rangle\),
    b) \(\langle \NN, +, 0 \rangle\) i \(\langle \NN, \cdot, 1\rangle\),
    c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\),
    d) \(\langle \NN, \leq \rangle\) i \(\langle \ZZ, \leq\rangle\).
  4. 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 liczby b przez c.
    c) Liczba jest pierwsza.
  5. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch jednoargumentowych symboli relacyjnych R, S i jednego jednoragumentowego symbolu funkcyjnego f.
    a) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których obraz zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\) zawiera się w zbiorze \(S^{\mathcal {A}}\).

Praca domowa

Zadania 563 d,e i 569 e,g.

2 października 2017

Ćwiczenia 1: powtórzenie z logiki, indukcja

Zadania

  1. Zaznaczyć na rysunku zbiory:
    a) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid x^2 + y^2 >1  \to y+x > 0\}\),
    b) \[\{\langle x, y\rangle \in \mathbb{R}^2 \mid(x^2 + y^2 >1 ) \to (x^2 + y^2 \leq 2) \wedge ( \neg (x \cdot y = 0) \to |y| = |x|)  \}\]
    c) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  (\forall z(z+y < 0)) \to y+x<0 \}\),
    d) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  x^2 + y^2 >1  \to \exists z (x^2 + (y-z)^2 \leq \frac{1}{4})\}\).
  2. Zaznaczyć na rysunku zbiory:
    a) \( \{z \in \mathbb{R} \mid \forall x \exists x (x=1)\} \),
    b) \( \{z \in \mathbb{R} \mid \exists x \forall x (x=1)\} \),
    c) \( \{x \in \mathbb{R} \mid \forall x \exists x (x=1)\} \).
  3. Udowodnić, że \(1 + 2 + 4 + \ldots + 2^n = 2^{n+1} -1\).

Praca domowa

Zadania 4b i 7c ze zbioru zadań.