# Pog3

## zadanie 1 kox
$P_3(a,b) \equiv \exists y_1y_2 E(a,y_1) \land E(y_1,y_2) \land E(y_2,b)$
$P_4(a,b) \equiv \exists y_1y_2y_3 E(a,y_1) \land E(y_1,y_2) \land E(y_2,y_3) \land E(y_3,b)$
$P_3(a,b) \equiv \exists y_1y_2y_3y_4 E(a,y_1) \land E(y_1,y_2) \land E(y_2,y_3) \land E(y_3,y_4) \land E(y_4,b)$

### Lemat:
Niech $\{a_i\}$ będzie dowolnym ciągiem liczb naturalnych wtedy używając perspektyw $P_{a_i}$ oraz operatorów koniunkcji i kwantyfikatorów egzystencjalnych można uzyskać formułę $\psi$ która jest równoważne perspektywie $P_j$ wtedy i tylko wtedy gdy $j$ jest równy pewnej kombinacji liniowej $a_i$ oraz współczynniki tej kombinacji są większe bądź równe 0 (tzn. $j = \sum\limits_{i}b_ia_i$ gdzie $b_i \geq 0$).

### Dowód lematu
$\rightarrow$
Weźmy dowolną formułę $\psi$ składającą się z kwantyfikatorów egzystencjonlnych, koniunkcji oraz perspektyw $P_{a_i}$. Dodatkowo załóżmy, że każda zmienna wolna może wystąpić raz jako "wyjście" i raz jako "wejście" (tzn. w formule może być np. $P_{3}(a,b) \land P_4(b,c)$ ale nie $P_3(a,b)\land P_4(a,b)$, bo jak można łatwo zauważyć ta druga formuła nie dostarczają żadnej nowej formuły którą moglibyśmy uzyskać korzystając z dodatkowego założenia).
Dowód indukcyjny
Podstawa:
Weźmy dowolną formułę $\phi$ składającą się z jednego znaku koniunkcji oraz egzystencjonalnego. Wtedy $\phi \equiv \exists yP_{a}(x,y)\land P_b(y,z)$ gdzie $a,b \in \{a_i\}$, zauważmy że ta formuła "mówi", że istnieje pewna ścieżka długości $a$ z $x$ do $y$ i pewna ścieżka długości $b$ z $y$ do $z$, a zatem istnieje ścieżka długości $a+b$ z $x$ do $z$. Zauważmy korzystając z algebry, że $a+b = \sum\limits_{i}b_ia_i$ bo $a,b \in \{a_i\}$.
Krok
Załóżmy że dla każdego $2\leq i \leq n$ zachodzi tez pokażmy, że zachodzi też dla n+1. Szkic dowodu wygląda tak że dzielimy wyrażenie na dwie części korzystam z założenia a potem z podstawy.

$\leftarrow$
Mówimy że było albo na logice albo na algebrze i gitowo.

Na mocy lematu i wiedzy z algebry nie da się przedstawić 5 jako kombinacje liniową 3 i 4 zatem nie da się uzyskać tego przy pomocy zadanej formuły zdefiniowanej w zadaniu.

^
Wsm bardzo podobnie zrobiłem, ale bez lematu. Wprost powiedziałem, że z podanej formuły koniunkcyjnej z relacjami atomowymi $P_3, P_4$ możemy skonstruować digraf gdzie każdy krawędź ma długość 3 lub 4, więc droga od $x$ do $y$ musi mieć rozwiązanie w $\mathbb{Z}^+$ dla równania $4A + 3B$. Lemat może się przydać dla kolejnych zadań. ~Czarek

## Zadanie 2

Literalnie niemożliwe
$P_5(x,y) \equiv \exists z P_4(x,z) \land \forall w P_3(w,z) \implies P_4(w,y)$

## Zadanie 3 kox

1)
weźmy dowolny graf G'. G' jest k-kolorowalny dla pewnego k.
Wtedy istnieje homomorfizm $h: G' -> K_k$, $K_k$ to klika k-elementowa. Wtedy funkcja h mapuje wierzchołki z G' o tych samych kolorach na wierzchołki z kliki.

2)
*literalnie z wykładu zajebane tak o*

Mamy graf I i graf I' (na rogach są wierzchołki). Możemy nadac im kolory i h1: I -> I' mapuje wierzchołki na odpowiednie kolory, h2: I' -> I tak samo. Nie istnieje bijekcja.

## Zadanie 4 kox


Każdy cykl parzysty jest 2-kolorowalny, więc można spokojnie jebnąć ładny homomorfizm. Weźmy cykle $C$ i $C'$. $h:C\rightarrow C'$ bierzemy dowolne dwa sąsiadujące wierzchołki $u$ i $v$ z $C'$ i przyporządkowujemy wierzchołki z $C$ do odpowiednich wierzchołków $u,v$ według kolorów.

## Zadanie 5 upo

## Info do dalszych zadań


## Zadanie 6 kox


Generalnie chyba to jest po prostu zbiór krotek bez null'i. Jeśli w krotce $t$ występuje jakiś null, to w zbiorze zdefiniowanym wyżej, pojawi się ona w wielu postaciach, np. jeśli $t=(325, 6234, NULL)$, to otrzymamy różne wartościowania bazy danych $D$, gdzie $t$ będzie miało różne wartości pod $NULL$em. Więc nie trafi do części wspólnej.

Przykład:
Mamy bazę danych $D$, gdzie wygląda ona następująco: $\{(Jacek, NULL), (Patryk, 3)\}$.

Wtedy zbiór z każdym $I$ wygląda tak: $\{\{(Jacek, 1), (Patryk, 3)\}, \{(Jacek, 2), (Patryk, 3)\}, \{(Jacek, 3), (Patryk, 3)\}, ...\}$, więc przekrój tego zbioru będzie równy $\{(Patryk, 3)\}$.

## Zadanie 7

Dwie możliwość obliczenia bazy.
1. Podstaw pod wszystkie wystąpienia $D$ formułę $Q'$ w formule $Q''$.
2. Najpierw oblicz ${Q'}_D$, a potem to włóż do $Q''$.

Jak obliczymy ${Q'}_D$, to przechodzimy przez operację przekroju. Więc z automatu tracimy dużo krotek.

Podstawiając formułę $Q'$ pod $Q''$, nie robimy przekroju aż do końca, trzymając większość krotek przy sobie.