# Logika - ćwiczenia 5

**Dla ustalenia uwagi:**
phi - φ - $\varphi$
psi - trójząb ψ $\psi$
w podstawieniu piszemy czasem [p->False] mając na myśli mapowanie $[p \mapsto \bot]$, pisane przez niektórych tak $[p := \bot]$ albo tak $[\bot / p]$, albo dla zmyłki tak $[p / \bot]$
:)

\forall - ∀ - $\forall$
\exists - ∃ - $\exists$

## Zad 2.1.2
Show that one can define the natural order “≤” on R² as a formula φ(x,y) of first-order logic of two free variables x,y, using only the following symbols: 0,1,+,*, = ,

$φ(x,y) \equiv \exists z. x + z * z = y$

$\mathbb{R}, \rho \vDash \varphi$
wtw
$\rho(x) ≤ \rho(y)$

${\cal A}, \rho \vDash \exists z. x + z * z = y$

${\cal A} = \langle A, +^{\cal A}, *^{\cal A} ... \rangle$

## Zad 2.1.6
Napisz formułę φ, mówiącą, że struktura ma co najmniej n elementów

${\cal A} \vDash φ$
wtw
nośnik ${\cal A}$ ma co najmniej n elementów

$\varphi = \exists a_1, ..., \exists a_n. a_1 \neq a_2 \land a_1 \neq a_3 \land \ldots \land a_1 \neq a_n \land \ldots \land a_{n-1} \neq a_n$

Czy da się wyrazić to samo używając formuły postaci $\beta = \forall x_1...\forall x_n. \alpha$, gdzie $\alpha$ jest bez kwantyfikatorów?

NIE, bo formuły tej postaci mają "własność podmodelu", czyli:
jesli A |= \beta, to dla dowolnego B \subseteq A mamy B |= \beta;
a to co chcemy wyrazić czyli "mieć co najmniej n elementów" nie ma tej własności.

$\forall a_1, ..., \forall a_n. (a_1 = a_2 \lor a_1 = a_3 \lor \ldots \lor a_{n-1} = a_n) \to \bot$ - ta formuła jest zawsze fałszywa

## Zad 2.1.7
Napisz formułę $\psi$, mówiącą, że struktura ma co najwyżej n elementów

${\cal A} \vDash \psi$
wtw
nośnik ${\cal A}$ ma co najwyżej n elementów

$\psi = \forall a_1, ..., \forall a_{n+1}. a_1 = a_2 \lor a_1 = a_3 \lor \ldots \lor a_1 = a_{n+1} \lor \ldots \lor a_n = a_{n+1}$

$\psi' = \exists a_1, ..., a_n. \forall a( a = a_1 \lor a = a_2 \lor ... \lor a = a_n)$

One są równoważne, ale tylko dlatego, że nie rozpatrujemy pustych modeli.

P(x,y) -> (forall a. a=a ∧ a \neq b) -> P(a,x)
P(x,y) -> (forall a( a=a ∧ a \neq b)) -> P(a,x)

P(x,y) -> (forall a a=a ∧ a \neq b) -> P(a,x)
P(x,y) -> ((forall a a=a) ∧ a \neq b) -> P(a,x)

Napisz formułę psi (bez kwantyfikatorów), spełnialna tylko w modelach o własności "cośtam"

A , \rho |= psi

A |= exists x_1..x_n. psi

Formuła psi jest prawdziwa w danym modelu
A |= psi
wtw dla każdego \rho
A, \rho |= psi
wtw
A |= forall x_1...x_n. psi

## Zad 2.1.8

Weźmy dowolna strukturę skończoną ${\cal A}$. Udowodnić, że istnieje $\varphi$, która charakteryzuje ${\cal A}$ z dokładniością do izomorfizmu, czyli dla dowolnego ${\cal B}$, jeśli ${\cal B} \vDash \varphi$ to $\cal B$ jest izomorficzne z ${\cal A}$ czyli istnieje bijekcja $f : {\cal A} \to {\cal B}$ zgodna ze wszystkimi działaniami i relacjami.

Dla symbolu relacyjnego R (np. binarnego)
(a_1,a_2) \in R^{cal A} wtw (f(a_1), f(a_2)) \in R^{cal B}

Dla symbolu funkcyjnego g (np. binarnego)
g^{cal A}(a_1,a_2)=a_3 wtw g^{cal B}(f(a_1),f(a_2))=f(a_3)

Załóżmy na początek, że mamy sygnaturę relacyjną (tzn. bez symboli funkcyjnych i stałych)

${\cal B} \vDash \varphi$ to oznacza:
dla dowolnego wartościowania $\rho$ zachodzi
${\cal B}, \rho \vDash \varphi$.

Dla tej konkretnej struktury
${\cal A} = \langle \{1,2,3\}, ≤ \rangle$
mielibyśmy formułę:
$\exists x_1, x_2, x_3. x_1 \neq x_2 \land x_1 \neq x_3 \land x_2 \neq x_3 \land (\forall x. x = x_1 \lor x = x_2 \lor x = x_3) \\ \land x_1 ≤ x_1 \land x_1 ≤ x_2 \land x_1 ≤ x_3 \land x_2 ≤ x_2 \land x_2 ≤ x_3 \land x_3 ≤ x_3 \\ \land \neg (x_2 ≤ x_1) \land \neg (x_3 ≤ x_1) \land \neg (x_3 ≤ x_2)$

%\alpha(x) = \forall y, x ≤ y

Z funkcjami możemy postąpić podobnie...
g(x_1)=x_2 rg(x_1,x_2)

## Zad 2.3.1
W jakich strukturach jest spełnialna nast. formuła:
φ(x) ≡ ∃y.y≠x

Formuła jest spełnialna w strukturze A wtw istnieje wartościowanie \rho t. że
A, \rho |= φ(x)

W tym wypadku chodzi o struktury co najmniej dwuelementowe.

\psi ≡ ∃y.y≠y
Takie psi jest zawsze fałszywe - przy podstawianiu musimy uważać, by nie "złapały" nam się zmienne

Powinno być:
φ(y) ≡ ∃z.z≠y