# ISOSQ x BD 2k21
###### tags: `Bazy Danych` `Logika 2: Electric Boogaloo`
[**ŚCIĄGAWKA Z LATEXA**](https://www.overleaf.com/learn/latex/List_of_Greek_letters_and_math_symbols)
# Lista 1

## Zadanie 1

**Def monotoniczności**
Mamy operację $\oplus$, $R_1 \subseteq R_2$ i $S_1 \subseteq S_2$, jeżeli $R_1 \oplus S_1 \subseteq R_2 \oplus S_2$ to $\oplus$ jest operacją monotniczną.

***Fakt z wykładu***
$\pi, \sigma, \rho, \times, \cup$ są monotoniczne, $\setminus$ nie jest.
Złożenie operacji monotonicznych jest monotoniczne.

**Dowód**

Załóżmy nie wprost że możemy przedstawić rożnicę za pomocą wyrażenia $\oplus$ złożonego z operatorów $\pi, \sigma, \rho, \times, \cup$. Wiemy, że te operatory są monotoniczne, więc wyrażenie z nich złożone także będzie monotoniczne. Zatem różnica przedstawiona tym wyrażeniem też będzie.
**Daje to nam sprzeczność**.

**Kontrprzykład**
Niech $\oplus$ będzie naszą $\setminus$ zapisaną jak w zadaniu.
Weźmy dwie relacje $A$ i $B$, wtedy $A\oplus B=C$. Weźmy krotkę $x \in A$ i $x\notin B$. Dodajmy ją do $B$. Wtedy $B'=B \cup \{x\}$. Niech $C'=A\oplus B'$. Skoro zarówno $\oplus$ i $\cup$ są monotoniczne, to $C \subseteq C'$, a wiemy, że $A\setminus B'=C\setminus\{x\}$, a $C \nsubseteq C \setminus \{x\} $.

## Zadanie 2

Student (debil) nie powinien użyć tego rozwiązania, ponieważ jak Y jest pusty lub Z jest pusty (jedno z nich), to wszystko się psuje.
Jak student (debil) powinien odpowiedzieć:
$X \setminus ((X \setminus Y) \setminus Z)$
## Zadanie 3

$G_{f_A(X_1,...,X_n)}(R) = {(x_1,...,x_n,a) | (x_1,...,x_n) \in \pi_{X_1,...,X_n}(R)}$ oraz $a=f_A(\sigma_{X_{1}=x_{1} \wedge ... \wedge X_{n} = x_{n}}(R))$

**a)**
**$G_{count_{sok}}(bar)(\pi_{bar,sok}(B \bowtie P))$**

* $f_A = count_{sok}(bar)$
* $R = \pi_{bar,sok}(B \bowtie P)$
* $a = count_{sok}(\pi_{bar,sok}(B \bowtie P))$

więc $G$ zwraca pary $(bar, n)$ takie, że w barze $bar$ bywa przynajmniej jedna osoba i w barze $bar$ podawane jest $n$ soków.

**b)**
pary (osoba,bar) takie, że $osoba$ lubi co najmniej 5 soków podawanych w barze $bar$.

$R = \pi_{osoba,bar,sok}(L \bowtie P)$
$G_{count_{sok}}(osoba, bar)(R)$ - zwróci krotki $(osoba, bar, n)$ takie, że dana $osoba$ lubi dokładnie $n$ soków w barze $bar$.

$\pi_{osoba,bar}(\sigma_{n>=5}(G_{count_{sok}}(osoba, bar)(R)))$

**c)**
$R = \pi_{osoba, sok, cena}(B \bowtie P)$
$f_A = min_{cena}(osoba,sok)$

$G_{min_{cena}}(osoba,sok)(R)$ - to zwróci (osoba, sok, cena) zwróci
minimalną ceną soku $sok$ ze wszystkich barów w których bywa osoba $osoba$

**d)**
:::danger
$R = \pi_{osoba, sok, bar, cena}(B \bowtie P)$
$f_A = min_{cena}(osoba,sok, bar)$

$\pi_{osoba, sok, bar}(G_{min_{cena}}(osoba,sok, bar)(R))$ - to zwróci (osoba, sok, bar) takie jak ma być essa
:::
- - -
$R = \pi_{osoba, sok, bar, cena}(B \bowtie P)$
$D = G_{min_{cena}}(osoba,sok)(R)$ -> (osoba, sok, najniższa cena sok w barach do których chodzi)
$\pi_{osoba, sok, bar}D\bowtie P$

- - -
$R = B \bowtie P$
$D = G_{min_{cena}}(osoba,sok)(R)$
$\pi_{osoba, sok, bar} D \bowtie P$
- - -

OD LASKOSIA
$R = B \bowtie P$
$D = G_{min_{cena}}(osoba,sok)(R)$
$D'=\rho_{min→cena}(D)$
$\pi_{osoba, sok, bar} D' \bowtie P$

## Zadanie 4
a)
:::success
π name, last_name, genre (σ year < 1960 (ρ movie_id ← id (movies)) ⨝ movies_genres ⨝ (ρ director_id ← id (directors)) ⨝ movies_directors )
:::
:::success
π name, last_name, genre (σ year<1960 (movies ⨝ id=movie_id movies_directors ⨝ movies_genres ⨝ directors.id=director_id directors))
:::

b)
:::success
( π first_name, last_name (actors) ) - ( π first_name, last_name ((π movie_id σ director_id=78273 ((ρ movie_id←id (movies))⨝movies_directors))⨝roles⨝(ρ actor_id←id (actors))))
:::
::: success
π first_name, last_name actors - π actors.first_name, actors.last_name (σ directors.last_name='Tarantino' (actors ⨝ id=actor_id roles ⨝ movies_directors ⨝ director_id=directors.id directors))
:::
c)
::: success
X = (ρ xid←actor_id, xmov_id←movie_id, xr←role (roles))
Y = (ρ yid←actor_id, ymov_id←movie_id, yr←role (roles))
X_x_Y = X ⨯ Y
R = (π xid (σ xid = yid ∧ xmov_id ≠ ymov_id (X_x_Y)))
π first_name, last_name (actors - ((ρ id←xid ( R ))⨝actors))
:::
d)
:::success
π name (σ movies_genres.genre='Sci-Fi' (π movies_genres.movie_id (σ genre='Drama' (movies_genres ⨝ id=movie_id movies)) ⨝ movies_genres) ⨝ ρ movie_id ← id (movies))
:::
:::success
π name ((σ movies_genres.genre='Sci-Fi' (( π movies_genres.movie_id (σ genre='Drama' (movies_genres ⨝ id=movie_id movies))) ⨝ movies_genres)) ⨝ movies_genres.movie_id=movies.id movies)
:::
:::success
X=π name, genre ( σ movies_genres.genre='Drama' ∨ movies_genres.genre='Sci-Fi' ((ρ movie_id←id (movies))⨝movies_genres))
Y=ρ name1←name, genre1←genre (X)
π name σ name = name1 ∧ genre ≠ genre1 (X ⨯ Y)
:::
e)
:::success
movies - π id, name, year, rank σ rank<rank1 (movies ⨯ (ρ id1←id, name1←name, year1←year, rank1←rank movies))
:::
:::success
X = (ρ xid←id, xname←name, xyear←year, xrank←rank (movies))
movies - π id, name, year, rank σ rank< xrank (movies ⨯ X)
:::

f)
:::success
X = (ρ xid←actor_id, xmov_id←movie_id, xr←role (roles))
Y = (ρ yid←actor_id, ymov_id←movie_id, yr←role (roles))
X_x_Y = X ⨯ Y
R = (π xid (σ xid = yid ∧ xmov_id ≠ ymov_id ∧ xr = yr (X_x_Y)))
π last_name ((ρ id←xid ( R ))⨝actors)
:::

g)
:::success
(pi last_name (directors)) - (pi last_name (σ genre = 'Horror' (movies_directors⨝(ρ director_id←id (directors))⨝movies_genres)))
:::

h)

:::success
π last_name (π director_id ((π id (movies) - (π roles.movie_id σ actors.gender='F' (roles ⨝ ρ actor_id ← id (actors)))) ⨝ (ρ id ← movies_directors.movie_id (movies_directors))) ⨝ ρ director_id ← id (directors))
:::

Puchacz_count
:::danger
c)
σ m_starred=1 γ actor_id; count(actor_id)-> m_starred (roles)

d)
σ no=2 γ name; count(name)→no ( σ movies_genres.genre='Drama' ∨ movies_genres.genre='Sci-Fi' ((ρ movie_id←id (movies))⨝movies_genres))
:::

# Lista 2

::: success
zrobione
:::
::: info
do sprawdzenia
:::
:::danger
niedokończone
:::

DUDUDUPA
$\pi, \sigma, \rho, \times, \cup$

## Zadanie 1 done

:::danger

Wystarczy że będziemy w stanie przedstawić każdy z operatorów $\pi, \sigma, \rho, \times, \cup$ za pomoca rrk albo rrd.

* $\pi_{a_1, ..., a_n}R \equiv \{a_1,...,a_n|\exists_{r\in R} R(r) \wedge r.a_1=a_1 \wedge \cdots \wedge r.a_n=a_n \}$

* $\rho_{b_1, ..., b_n}R \equiv \{b_1,...,b_n|\forall_{r\in R} R(r) \wedge r.a_1=b_1 \wedge \cdots \wedge r.a_n=b_n \}$

* $A\times B\equiv \{a,b|\forall_{a \in A, b \in B} A(a) \wedge B(b) \}$

* $A \setminus B\equiv \{a|A(a) \wedge \neg B(a) \}$

* $\sigma_F(R)$
dla $F=k_1 \oplus k_2$
$\sigma_F(R) \equiv \{r| R(r) \wedge r.k_1 \oplus r.k_2 \}$

dla $F = A \wedge B$ możemy zapisać wyrażenie jako $\sigma_A(\sigma_B(R))$, które jest równoważne

Negacja
niech $A = \sigma_F(r)$, które umiemy otrzymać. Wtedy
$\sigma_{\neg F}(R) \equiv \{r|R(r) \wedge \neg A(r)\}$

Alternatywa
$F = A \lor B = \neg(\neg A \wedge \neg B)$

Złożenia możemy otrzymywać składając.
:::

:::success
Wystarczy, że będziemy w stanie przedstawić każdy z operatorów $\pi, \sigma, \rho, \times, \cup$ za pomocą rrk albo rrd.

* (rrk) $\pi_{a_1, ..., a_n}R \equiv \{r'|\exists_{r} R(r) \wedge r.a_1=r'.a_1 \wedge \cdots \wedge r.a_n=r'.a_n \}$

* (rrk) $\rho_{b_1, ..., b_n}R \equiv \{r'|\exists_{r} R(r) \wedge r.a_1=r'.b_1 \wedge \cdots \wedge r.a_n=r'.b_n \}$

* (rrd) $A\times B\equiv \{(a_1,\cdots,a_n,b_1,\cdots,b_n)| A(a_1,\cdots,a_n) \wedge B(b_1,\cdots,b_n) \}$

* (rrk) $A \setminus B\equiv \{a|A(a) \wedge \neg B(a) \}$

* $\sigma_F(R)$
* dla $F=k_1 \oplus k_2$
$\sigma_F(R) \equiv \{r| R(r) \wedge r.k_1 \oplus r.k_2 \}$

* dla $F = A \wedge B$ możemy zapisać wyrażenie jako $\sigma_A(\sigma_B(R))$, które jest równoważne

* Negacja
niech $A = \sigma_F(r)$, które umiemy otrzymać. Wtedy
$\sigma_{\neg F}(R) \equiv \{r|R(r) \wedge \neg A(r)\}$

* Alternatywa
$F = A \lor B = \neg(\neg A \wedge \neg B)$
* Alternatywa
$A_i = \sigma_{F_i}(R)$
$\sigma_{F_1\lor F_2}(R) = \{r| A_1(r) \lor A_2(r)\}$

Złożenia otrzymujemy składając powyższe definicje.
:::

:::info
1. $e = \pi_{A_{1},...,A_{k}}(e_{1})$ gdzie zapytanie $e_{1}$ jest długości $n$.
Wówczas w rrk mamy: $\{ x^{[A_{1},...,A_{k}]} | x \in e_{1}' \}$, gdzie $e_{1}'$ to $e_{1}$ wyrażone w rrk.
2. $e = \rho_{S(A_{1},...,A_{k})}(e_{1})$ gdzie zapytanie $e_{1}$ jest długości $n$.
Wówczas w rrk mamy: $\{ x^{[A_{1},...,A_{k}]} | (\exists y)(y \in e_{1}' \wedge (\forall i \in [1, k] \cap N)(x.A_{i} = y.i)) \}$, gdzie $e_{1}'$ to $e_{1}$ wyrażone w rrk.
3. $e = \sigma_{F}(e_{1})$ gdzie zapytanie $e_{1}$ jest długości $n$, oraz F spełnia warunki zadania. Wówczas w rrk mamy: $\{ x | x \in e_{1}' \wedge F \}$, gdzie $e_{1}'$ to $e_{1}$ wyrażone w rrk.
4. $e = e_{1} \times e_{2}$ gdzie zapytania $e_{1}$ i $e_{2}$ to zapytania o sumarycznej długości równej $n$. Wówczas w rrk mamy: $\{ x | (\exists a,b)(a \in e_{1}' \wedge b \in e_{2}' \wedge x = a|b) \}$, gdzie $e_{1}'$ i $e_{2}'$ to odpowiednio $e_{1}$ i $e_{2}$ wyrażone w rrk.
5. $e = e_{1} \setminus e_{2}$ gdzie zapytania $e_{1}$ i $e_{2}$ to zapytania o sumarycznej długości równej $n$. Wówczas w rrk mamy:
$\{ x | x \in e_{1}' \wedge \neg(x \in e_{2}&apos \}$, gdzie $e_{1}'$ i $e_{2}'$ to odpowiednio $e_{1}$ i $e_{2}$ wyrażone w rrk.
:::

## Zadanie 2 done
Wtedy, kiedy k jest nullem lub jest równe jakiemuś R.a
:::success
$\{ k | k \neq NULL \wedge \neg (\exists_{r \in R, s \in S} s.z=k \wedge k = r.a) \}$
:::
## Zadanie 3 done

R=(pensja, profesor).
T=(temat, profesor)

### 1.
:::success
$\{ a | (∃b)(R(a, b) ∧ ¬((∃a') a'> a ∧ (∃b') (R(a', b'))))\}$
Zapytanie o najwyższą pensję.
:::

Formuła jest niezależna od dziedziny, ponieważ występują w niej tylko kwantyfikatory $\exists$

:::success
$\pi_a(R) - \pi_a (\sigma_{a<a'} (R\times (\rho_{a', b'} R)))$
:::

### 2.
:::success
$\{ a, b | (∀c)(T(c, a) ∨ T(c, b) ∨ (∀d)(¬T(c, d)))\}$
Para profesorów którzy razem znają wszystkie tematy, poza tematami o których nikt nic nie wie
:::

Formuła nie jest niezależna od dziedziny, ponieważ nie znamy dziedziny $c$ i $d$. Formuła może być spełniona lub nie w zależności od ich dziedziny np.:
$c ∈ \{1000,2000,..., 10000\}$
$T$ zawiera krotki:
$(1000, Abacki)$
$(5000, Cebacki)$
w takim przypadku nastąpni sytuacja nazywana potocznie *'wypierdolką'*

:::info
**STUŁA**
Pary a,b elementów wystepujących w drugiej kolumnie relacji T, takie, że każdy element c wystepujący w pierwszej kolumnie relacji T jest w relacji z a lub b.

Formuła nie jest bezpieczna, np kiedy relacja T jest pusta, dowolna para a,b spełnia tą formułę.

Każda formuła algebry relacji jest bezpieczna, zatem nie istnieje formuła algebry relacji równoważna tej formule.
:::

:::success
Pilarczyk
$O=\pi_{profesor} T, P=\pi_{temat}T$

$A = O\times\rho_{o1}(O)\times\rho_{o2}(O)\times P$ `- 3 x osoby + tematy `
$B = \sigma_{\neg T(p, o) \land \neg T(p, o1) \land T(p, o2)}(A)$ `- 1. os nie zna tem, 2. os nie zna tem i 3. os zna tem`
$C = \pi_{o,o1}(B)$ `- ani 1. os ani 2. os nie zna jakiegoś tematu`
$res =\sigma_{o\neq o1} (O\times\rho_{o1}(O)) \setminus C$
$$
:::

## Zadanie 4 done
:::warning
:::

:::success
1. ok
Wybieramy takie osoby, dla których nie istnieje bar, do którego by chodziły, a który podawałaby same soki nielubiane przez osobę. Czyli w barach do kórych chodzą podadje się conajmniej jeden lubiany.
2. nie ok
Wybieramy takie osoby, dla których nie istnieje bar, do którego by chodziły, a w którym osoba lubi wszystkie podawane soki. Wykluczamy więc przypadek, który tym bardziej powinniśmy wybrać.
3. ok
Wybieramy takie osoby, dla których jeśli chodzą one do danego baru, to ten bar podaje lubiany przez nie sok (a więc przynajmniej jeden), zapytanie najbardziej zbliżone do języka naturalnego.
4. nie ok
Wybieramy takie osoby, które chodzą do wszystkich barów i w każdym z tych barów podają sok lubiany przez tą osobę. Warunki zbyt silne. Odrzucimy chociażby osoby uczęszczające do tylko jednego z wielu barów.
bo osoba, która nie tylko do baru b1, a w reszczie do której chodzi podawane są jej soki, które lubi nie zostanie uwzględniona
:::
## Zadanie 5 done

:::success
1. nie ok
Wybieramy osoby, które chodzą do jakiegoś baru b i nie chodzą do baru b′. b może być równe b′, więc dostaniemy sprzeczność typu p ∧ ¬p.
2. nie ok
Wybieramy osoby, które chodzą do jakiegokolwiek baru, a nie tylko do jednego.
3. ok
Wybieramy osoby, które chodzą do baru b i nie chodzą do baru b′, uszczególniając, że bar b i b′ nie są tym samym barem.
4. ok
Sens jest ten sam co w podpunkcie 3. Dodajemy dodatkowo zmienną o′, ale dalej traktujemy ją jak o, więc wyniki pozostają takie same.
:::

## Zadanie 6 done
:::success
**ARSENICRO**
:::
### 1.

$\{a ∈ A | \forall_{f1,f2∈F} \exists_{r1,r2∈R}(r1.pseudo = a.pseudo \wedge r2.pseudo = a.pseudo \wedge\\ r1.idf = f1.idf \wedge r2.idf = f2.idf) \implies f1.rokProd = f2.rokProd \}$

$\{a ∈ A | (\forall_{f1,f2∈F}) (\exists_{r1,r2∈R}(r1.pseudo = a.pseudo \wedge r2.pseudo = a.pseudo \wedge\\ r1.idf = f1.idf \wedge r2.idf = f2.idf) \implies f1.rokProd = f2.rokProd \}$

Jeśli dla każdych dwóch filmów $f1$, $f2$ istnieje taka para ról $r1$, $r2$, że są to te same role w filmach odpowiednio $r1$ w $f1$ i $r2$ w $f2$ to filmy $f1$ i $f2$ zostały wyprodukowane w tym samym roku.

### 2.

$\{f∈F| \forall_{f2∈F} f2.rez = f.rez \implies f.rokProd \geq f2.rokProd \}$

### 3.

$\{psd, idf, gaza|(\exists_a A(a) \wedge a.psd = psd) \wedge (\exists_f F(f) \wedge f.idf = idf) \wedge\\ (\exists_p R(psd,idf,p,gaza) \wedge (\forall_r R(r) \wedge r.idf = idf \implies r.gaza \leq gaza)) \}$

::: info
$\{(pseudo,idf,gaza)|(\exists_{postac})(R(pseudo,idf,postac,gaza) \wedge (\forall_{pseudo_2,postac_2,gaza_2}) \\
(R(pseudo_2,idf,postac_2,gaza_2) \implies gaza_2 \leq gaza))\}$
:::
### 4.

$\{a ∈ A|\forall_{m1,m2 ∈ M} (m1.rok > m2.rok \implies m1.gaza \geq m2.gaza) \}$

## Zadanie 7

# Lista 3
dupa i chuj
::: success
zrobione
:::
::: info
do sprawdzenia
:::
:::danger
niedokończone
:::

Rozgrzewka:
(Ey1,y2) P3(x, y1) i P2(y1, y2) i P2(y2, z)

### definicje

chuuuj


## Zadanie 1
:::info
$3+4>5 \wedge 4+3>5 \implies$ nie istnieje
(do sprawdzenia)
:::

:::danger
student debil moment, zostaniesz zlinczowany przez ćwiczneiowca za to
trzeba udowodnić że nie da się w żaden inny sposób zkonstruować rozwiązania
:::
## Zadanie 2

## Zadanie 3
### 1.

:::success
graf G - pojedynczy wierzchołek z krawędzią do samego siebie
E(1, 1), więc homomorfizm do niego to f(x) = 1, dla każdego wierzchołka x z G'
:::
### 2.

:::info
Tutaj wystarczy pokazać dwa grafy co są cyklami o długości parzystej i z zadania 4 wiemy że są homomorficznie równoważne. Jak mają różne rozmiary to nie ma między nimi izomorfizmu (różna liczba wierzchołków).
:::

:::success
G1

digraph finite_state_machine {
    rankdir=LR;
    size="8,5"
    node [shape = circle];
    0 -> 0;
}

G2

digraph finite_state_machine {
    rankdir=LR;
    size="8,5"
    node [shape = circle];
    1 -> 1;
    1 -> 2;
    2 -> 1;
}

h1: G1 -> G2: 0 -> 1
h2: G2 -> G1: 1 -> 0, 2 -> 0
Istnieją homomomorfizmy h1 i h2, więc G1 i G2 są homomorficznie rownoważne, ale mają różne liczby wierzchołków, więc h1 i h2 nie są bijekcjami, więc nie ma izomorfizmu
:::

:::info


##### 1.
Niech graf $G$ będzie zbudowany z jednego, zapętlonego wierzchołka:

Wtedy dla dowolnego grafu $G'$ istnieje taki homomorfizm, że:
$\forall v \in V(G'): v \rightarrow x$

W ten sposób każda para wierzchołków w $G'$, po zastosowaniu homomorfizmu zostanie zamieniona na wierzchołek $x$ połączony krawędzią ze sobą. W szczególności, te wierzchołki, które były połączone krawedzią w $G'$, będą złączone po zastosowaniu homomorfizmu.

##### 2.
Kontrprzykład:

Homomorfizm z $G_1$ do $G_2$:
$1 \rightarrow 1$
$2 \rightarrow 2$
$3 \rightarrow 1$
$4 \rightarrow 2$

Homomorfizm z $G_2$ do $G_1$:
$1 \rightarrow 1$
$2 \rightarrow 2$

Zatem grafy $G_1$ i $G_2$ są homomorficznie równoważne.

>Izomorfizm to taka bijekcja, która jest homomorfizmem, i jej funkcja odwrotna też jest homomorfizmem.

Już po ilości wierzchołków widać jednak, że nie są izomorficzne - nie istnieje między nimi żadna bijekcja.

Zatem warunek mówiący, że grafy są homomorficznie równoważne nie jest równoważny z tym, że istnieje izomorfizm $f: G_1 \rightarrow G_2$.
:::

## Zadanie 4
:::danger
Mamy dwa cykle A, B o różnej, parzystej ilości wierzchołków (gdy są takie same no to oczywiście, że jest homomorfizm w dwie strony h(x) = x)

$|dom(A)| < |dom(B)|$ (cykl A jest krótszy)

1. najpierw w lewo B -> A:
//$h(b) = b$ dla $b <= |dom(A)|$
//$h(b) = |dom(A)|$ dla $b > |dom(A)|$ tutaj na zmiane XD
$h(b) = b \mod |dom(A)|$
Czyli wypełniamy większy cykl po kolei numerami wierzchołków z mniejszego, a potem do końca tą największą. Każda relacja $R(b_1, b_2)$ w grafie A będzie zachodzić jako $R(h(b_1), h(b_2))$ na grafie B.

2. w prawo A -> B:
h(a) = a
ten mniejszy cykl zostaje jaki jest zasadniczo
:::

:::info
Zacznijmy od spostrzeżenia, że każdy graf cykliczny parzysty jest dwudzielny (można go tak narysować). Dodatkowo każdy graf dwudzielny jest homomorficznie równoważny z K2. Dodatkowo, równoważność z definicji jest relacją zwrotną, symetryczną i przechodnią, zatem dla dowolnych dwóch cykli parzystych G1 i G2: G1 jest homomorficznie równoważny z K2, G2 jest homomorficznie równoważny z K2, więc G1 jest homomorficznie równoważny z G2.
Graf K2:

graph finite_state_machine {
    rankdir=LR;
    size="8,5"
    node [shape = circle];
    1 -- 2;
}

:::

:::warning
Kontprzykład jeśli krawędź skierowana:

Weźmy graf:
$1 -> 2 -> 1 -> \ldots$
Oraz
$1 -> 2 -> 3 -> 4 -> 1 -> \ldots$

To dla $G_1$ bez straty ogólności $h(1) = 1$ ale ponieważ jest krawędź z $1$ do $2$ to $h(2) = 2$. No ale nie ma teraz krawędzi z $2$ do $1$ więc jest problem.

Konstrukcja dla nieskierowanego (numerujemy od 0):

0 -> 1 -> ... -> n -> 0

Mamy $h_1(i) = h_2(i) = i \bmod 2$

Wtedy para $\{u, (u + 1) \bmod 2\}$ przejdzie na $\{0, 1\}$
:::

### M. Serzysko
Weźmy dowolne dwa grafy $G$ i $G'$ będące cyklami parzystej długości. Niech wierzchołki $v_1, v_2, \dots, v_n$ będą wierzchołkami $G$, a $w_1, w_2, \dots, w_m$ wierzchołkami z $G'$.
Zauważmy, że w obydwu grafach sąsiadami dowolnego wierzchołka są wierzchołki o innej parzystości indeksu. Wtedy $h: G -> G'$ t.ż. $h(v_i) = w_{(i \mod 2) + 1}$ oraz $h': G' -> G$ t.ż. $h'(w_i) = v_{(i \mod 2) + 1}$ są homomorfizmami, zatem grafy $G$ i $G'$ są homomorficznie równoważne.

M. Grzymek

Aby skonstruować homomorfizm z dowolnego cyklu parzystego $A$ w inny $B$ wybierzmy parę wierzchołków $w,v$ że $Bwv$ i przypiszmy wierzchołkom z $A$ $w$ oraz $v$ na zmianę (co jest możliwe dzięki parzystości). Wtedy dla dwóch wierzchołków połączonych w $A$ przypisane im są $w$ i $v$ które są połączone w $B$. Homomorfizm w drugą stronę istnieje z tego samego rozumowania z zamienionymi literkami A,B.
## Zadanie 5

## Zadanie 6

# Lista 4

## Zadanie 1


## Zadanie 2

:::success

T(X, Y) :- E(X,Y)
T(X, Y) :- T(X,Z), T(Z,Y)

Można traktować jako: $T(X,Y) = E(X,Y) \vee \exists{z}(T(X, Z) \vee T(Z, Y))$

#### Teza:
$i \in N_+ \implies T^i$ = $\{(a,b) |$ istnieje ścieżka z $a$ do $b$ o długości$\ < 2^i\}$

#### Lemat:
$T^n = \bigcup_{i=1}^{2^{n-1}} E^i, T^0=\emptyset$

#### Dowód:
dla $n = 1$:
$T^0 = \emptyset$
$T^1 = E \cup \emptyset = E$
gra

#### założenie indukcyjne: działa dla n
#### krok
$T^{n+1} \overset{1}{=} E \cup (T^n \times T^n) \overset{2}{=} E \cup (\bigcup_{i=1}^{2^{n-1}} E^i \times \bigcup_{i=1}^{2^{n-1}} E^i) = E \cup E^2 \cup \dots \cup E^{2*2^{n-1}} = \bigcup_{i=1}^{2^{n}} E^i$
1 -> z def. dataloga
2 -> z zał. indukcyjnego
gra

z lematu bezpośrenio wynika teza

pewnie jeszcze by trzeba przemianować (X,Y) na (a,b) ale no kurwa
:::
#### notatki typu brudne
$T^0 = \emptyset$
$T^1 = E \cup \emptyset$ (E z pierwszej reguły, emptyset z drugiej bo T puste)
$T^2 = E \cup (E,E) = E \cup E^2$ (ta notacja na pewno nie jest poprawna)
$T^3 = E \cup (E \cup E^2, E \cup E^2) = E \cup E^2 \cup E^3 \cup E^4$
...
$T = E \cup \pi_{1,4}(\sigma_{2=3} T \times T)$

## Zadanie 3

:::danger
### 1)

T(X) :- E(n,X).
T(X) :- E(m,X).
T(X) :- E(n,Z), T(Z,X).
T(X) :- E(m,Z), T(Z,X).

:::

:::success
### 1)

T(X) :- E(n,X).
T(X) :- E(m,X).
T(X) :- E(Y,X), T(Y).

### 2)

M(X) :- E(m,X).
M(X) :- E(Y,X), M(Y).
N(X) :- E(n,X).
N(X) :- E(Y,X), N(Y).
T(X) :- M(X), N(X).

### 3)

T(X,Y) :- E(n,X), E(n,Y).
T(X,Y) :- E(D,X), E(A,Y), T(D,A).

### 4)

T(X,Y) :- E(n,X), E(n,Z), E(Z,Y).
T(X,Y) :- E(Z,Y), T(X,Z).
T(X,Y) :- E(Z,X), E(A,Y), T(Z,A).

:::


## Zadanie 4

Zapytanie P(X, Y) jest prawdziwe, jeżeli istnieje ścieżka parzystej długości między X i Y.

P(X, Y) :- E(X, Z), E(Z, Y)
P(X, Y) :- P(X, Z), P(Z, Y)
Q() :- P(X, Y), E(Y, X)

Q() jest prawdziwe gdy istnieje jakaś para wierzchołków X, Y takich, że jest ścieżka parzystej długości od X do Y i jest krawędź od Y do X, czyli istnieje jakiś cykl nieparzystej długości.
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Ma być cykl o nieparzystej długości.

ODD(X, Y) :- E(X, Y).
ODD(X, Y) :- E(Z, Y), EVEN(X, Z).
EVEN(X, Y) :- E(Z, Y), ODD(X, Z).
Q() :- ODD(X, X).

## Zadanie 5

### 1
Zapytanie S(X) jest prawdziwe gdy da się dojść od n do X.

S(X) :- E(n, X)
S(X) :- S(Y), E(Y, X)

I tu bym powiedział że odpowiedź to zanegowane S(m) tylko kurwa w datalogu nie ma negacji XDD

### 2
#### 1.

Co mamy do dyspozycji?

$E(x, y)$ - mamy krawędź z $x$ do $y$
$T(x, y) = T(\ldots) T(\ldots) T(\ldots) E(\ldots) E(\ldots)$

Dla grafu:
$E(1, 1)$

$T(1, 1)$ powinno być fałszem (bo jest ścieżka z 1 do 1).

Ale $T$ składa się z $E$ albo rekurencyjnie z samego siebie. $E$ zawsze będzie prawdziwe (baza). Rekruencyjne T też będzie prawdziwe (założenie).

#### 2.

To samo co w poprzednim punkcie uwala tezę.

#### alternatywne

Datalog robi tak, że jak zwróci się prawda dla jakiś danych, to dla większych też.
No bo w tych korkach rekursji będzie mógł co najwyżej dodać nowy atom.

To weźmy graf, który ma dwa wierzchołki. I nie ma krawędzi.
Weźmy jakieś zapytanie datalogowe, które jest poprawne i zwraca prawdę.
Dodajmy krawędź. Wtedy to zapytanie powinno być fałszywe - ale będzie spełnione, bo wciąż znalazł każdy atom, który był wcześniej.

Sprzeczność.

punkt 2 analogicznie
## Zadanie XD (ostrożnie!)

# PRACOWNIA 1
### 1) instalacja postgresa - kompletnie żadnych problemów. wszystko jak na skosie

### 3

SELECT date_trunc('day', w1.data-w2.data)

FROM wybor w1 JOIN grupa USING(kod_grupy)

      JOIN wybor w2 USING(kod_grupy)

WHERE w1.data>w2.data AND

      grupa.kod_grupy=5649

ORDER BY 1 desc LIMIT 1;

### 4

SELECT COUNT(DISTINCT kod_przed)
FROM przedmiot JOIN przedmiot_semestr USING(kod_przed)
JOIN grupa USING(kod_przed_sem)
WHERE rodzaj_zajec='e' AND rodzaj='o';