Informatyka MIMUW

Zasady punktacji i wystawiania ocen są następujące:
Z całości egzaminu można otrzymac następujące oceny: bardzo dobrą, bardzo dobrą minus, dobrą plus, dobrą, dobrą minus, dostateczną plus, dostateczną lub niedostateczną.
Za każde zadanie można otrzymac maksymalnie jeden punkt (oceny wystawiane są z dokładnością do 0.1 punkta). Policzone zostaną trzy najlepiej rozwiązane zadania - dwóch pozostałych nie będziemy brać pod uwagę.
Uzyskanie łącznie 2.9 punktów daje ocenę dobrą plus, 2.5 punkta daje ocenę dobrą, 2.1 punkta ocenę dostateczną plus oraz 1.6 punkta ocenę dostateczną. Na życzenie studenta oceny te zostaną wpisane do indeksu. Każdą ocenę (także niedostateczną) można będzie podnieść o maksymalnie dwa poziomy (aż do piątki włącznie) na ustnym egzaminie z teorii, który będzie się odbywać w przyszłym tygodniu. W wypadku niezadowalających odpowiedzi ocena z egzaminu pisemnego może się obniżyć o maksymalnie jeden poziom.
Osoby, które z kolokwium uzyskały minimum 1.5 punkta, mogą zamiast rozwiązań zadań 1 i 2 oddać kartkę z życzeniem, żeby za te zadania przyznane zostały punkty uzyskane na kolokwium. Jeśli jednak oddadzą rozwiązania któregoś z tych zadań, to zostaną one sprawdzone i dostaną za nie na egzaminie tyle punktów na ile te rozwiązania ocenimy, bez względu na to, ile punktów dostały na kolokwium.
W poniższych zadaniach odpowiedzi należy uzasadniać. Odpowiedź bez uzasadnienia nie liczy się w ogóle jako rozwiązanie.

1. Proszę rozstrzygnąć, czy następujące zdanie jest tautologią i czy jest spełnialne:

   \((\forall x\forall y\forall z\ (R(x,z)\land R(z,y))\to R(x,y))\ \to\ (\exists x\exists y\exists z\ R(x,y)\land R(y,z)\land R(z,x)).\)

2. Dana jest struktura \(\mathbb{P}=\langle P,r^{\mathbb{P}}\rangle,\) której uniwersum \(P\) stanowi zbiór wszystkich okręgów o promieniu 1 na płaszczyźnie, a dwuargumentowa relacja \(r^{\mathbb{P}}\) jest określona w ten sposób, że \(r^{\mathbb{P}}(o_{1},o_{2})\) wtw \(o_{1}\) i \(o_{2}\) są styczne zewnętrznie.

   Proszę napisać formułę \(\varphi(x,y)\) taką, że \(\mathbb{N}\models\varphi[o_{1},o_{2}]\) wtedy i tylko wtedy, gdy odległość pomiędzy środkami okręgów \(o_{1}\) i \(o_{2}\) jest większa niż 4.

3. Dane są dwie struktury relacyjne \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle\) i \(\mathbb{B}=\langle B,r^{\mathbb{B}}\rangle\) nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. \(A=\{ 0,1,2,\dots,6\}\) oraz \(B=\{ 1,2,\dots,6\}\), a relacje określone są jak następuje:
   \(r^{\mathbb{A}}(x,y)\) wtw \(x\equiv y-1\;\;(\textrm{mod}3),\)
   \(r^{\mathbb{B}}(x,y)\) wtw \(x\equiv y-1\;\;(\textrm{mod}3).\)

   Proszę podać przez ile rund może się bronić drugi gracz w grze Ehrenfeuchta–Fraïssé'go rozgrywanej na tych strukturach, jeśli gracz pierwszy gra optymalnie dla siebie.

4. Proszę wyprowadzić w systemie Gentzena sekwent

   \(\forall x\exists y(R(x)\to S(y))\vdash(\exists xR(x))\to(\exists yS(y)).\)

5. Pokazać, że w logice Sobocińskiego nie można za pomocą alternatywy, koniunkcji i negacji zdefiniować alternatywy z logiki Heytinga-Kleene-Łukasiewicza.

HKL=Heyting-Kleene-Łukasiewicz
S= Sobociński

\(\begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\land _{{S}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&0&0\\ 1&0&1&1\\ \bot&0&1&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|c|}\hline\omit\span\omit\sim x\\ \hline\hline x&\sim x\\ \hline 0&1\\ \hline 1&0\\ \hline\bot&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\lor _{{S}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&1&0\\ 1&1&1&1\\ \bot&0&1&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\lor _{{HKL}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&1&\bot\\ 1&1&1&1\\ \bot&\bot&1&\bot\\ \hline\end{array}\ \ \ \ \)