---
# System prepended metadata

title: Logika dla informatyków ćwiczenia 3

---

# Logika dla informatyków ćwiczenia 3

## 333

![](https://i.imgur.com/XQTFPML.jpg)


Dowód, że $f$ jest na. Weźmy dowolny $y \in \mathbb{Z}$. Pokażemy, że istnieje $x \in \mathbb{N}$ taki, że $f(x)=y$.


Rozważmy dwa przypadki:
* $y \leq 0$. Wtedy niech $x=-2y$. Wtedy $f(x)=-x/2 = --2y/2=y$.
* $y>0$. Wtedy niech $x=2y-1$. Wtedy $f(x)=\frac{x+1}{2} = \frac{2y-1+1}{2}=y$

Dowód, że $f$ jest różnowartościowa. ...


## A8

Lemat: Jeśli $w \sim_{L}^{inf} v$, to $w \sim_{L} v$.
Dowód: Niech $w \sim_{L}^{inf} v$. Z definicji oznacza to, że $\forall_{x, y \in \sum^*} xwy \in L \iff xvy \in L$. W szczególności, dla $x = \epsilon$ zachodzi $\forall_{y \in \sum^*} wy \in L \iff vy \in L$. Jest to definicja $w \sim_{L} v$, zatem teza zachodzi.

Oznacza to, że dla każdej klasy abstrakcji należącej do $\sum^*/\sim_{L}^{inf}$ ta klasa abstrakcji jest podzbiorem jakiejś klasy abstrakcji należącej do $\sum^*/\sim_{L}$.

Teraz możemy stworzyć funkcję $f: \sum^*/\sim_{L} \rightarrow \sum^*/\sim_{L}^{inf}$, która każdej klasie abstrakcji z $\sum^*/\sim_{L}$ przypisuje pewną klasę abstrakcji z $\sum^*/\sim_{L}^{inf}$ taką, że jest ona podzbiorem tej wybranej klasie abstrakcji z $\sum^*/\sim_{L}$. Jest ona różnowartościowa, ponieważ każda klasa abstrakcji z $\sum^*/\sim_{L}^{inf}$ może być podzbiorem tylko jednej klasy abstrakcji z $\sum^*/\sim_{L}$, jako że klasy abstrakcji są rozłączne.


# Agenda:
## Przerwa do 13:14
## A6 Aleksander	Pogoda
## A7 Anna	Krysta
## A8 Antoni	Śmidoda
## A10 Karolina	Lubczańska


## 
