Kolokwium 2010/2011

Zad. 1

Niech \(f\) będzie jednoargumentowym symbolem funcji i niech
\(\mathcal{A}=\bigcup_{n\in \mathbb{N}}Mod(\forall x f^n(x) =x)\),
gdzie \(f^n(x)\) to \(n\)-krotne złożenie \(f(\ldots(f(x))\ldots)\).
Wykazać, że ani \(\mathcal{A}\) nie można zdefiniować żadnym zbiorem zdań logiki pierwszego rzędu, ani
dopełnienia \(\mathcal{A}\) nie można zdefiniować pojedynczym zdaniem logiki pierwszego rzędu.

Zad. 2

Niech dany będzie niesprzeczny, skończony zbióor zdań \(\Delta\) nad pewną ustaloną i również
skończoną sygnaturą \(\Sigma\). Wykazać, że istnieje zbiór \(\Delta_0\subseteq\Delta\) taki, że \(\Delta_0\models\Delta\), a ponadto zdania w \(\Delta_0\) są niezależne: dla każdego \(\varphi\in\Delta_0\) mamy \(\Delta_0\setminus\{\varphi\}\not\models\Delta_0\).

Zad. 3

Niech \(\mathfrak{H}^n\) to struktura której uniwersum to hiperkostka \(H^n=\{0,1\}^n\), a jednyna relacja dwuargumentowa \(E^{\mathfrak{H}^n}\) jest zdefiniowana tak:

\(E^{\mathfrak{H}^n}(x,y)\) wtw, gdy \(x\) i \(y\) różnią się dokładnie na jednej pozycji.

Jakie jest maksymalne \(m\) takie, że gracz II ma strategię wygrywającą w grze Ehrenfeuchta \(G_m(\mathfrak{H}^4,\mathfrak{H}^3)\)?

Egzamin 2010/2011

Zad. 1 (3 punkty)

Rozważamy modele dla PDL postaci skończonego łańcucha złożonego z dwóch programów atomowych: \(u\) i \(v\). Między każdymi dwoma kolejnymi stanami przechodzi jeden i tylko jeden z tych programów. Zmienne zdaniowe są dwie: \(p\) prawdziwa tylko w pierwszym stanie łańcucha i \(k\) prawdziwa tylko w ostatnim stanie. Innych zmiennych zdaniowych nie ma.

Każdą taką strukturę można naturalnie uważać również za strukturę pierwszego rzędu, wówczas \(u\) i \(v\) są relacjami dwuargumentowymi a \(p\) i \(k\) relacjami jednoargumentowymi.

Udowodnić, że dla każdego zdania \(\varphi\) logiki MSO istnieje zdanie \(\phi\) logiki PDL takie, że dla każdej struktury \(\mathfrak{A}\) jak powyżej, \(\varphi\) jest prawdziwe w stanie początkowym struktury \(\mathfrak{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\phi\).

Zad. 2 (3 punkty)

Algebrę relacyjną z liniowym porządkiem na danych można skonstruować na dwa sposoby. Załózmy, że \(\leq\) jest relacją liniowego porządku na wszystkich elementach, które mogą się pojawić w krotkach, a w sygnaturze nie ma stałych.

Pierwszy sposób polega na tym, że do każdej bazy danych wprowadzamy dodatkową tabelę \(LEQ\) o dwóch kolumnach, która zawiera wszystkie krotki \(\langle a,b\rangle\) dla \(a,b\) należacych do aktywnej dziedziny i takich, że \(a\leq b.\) Wówczas zwykłe wyrażenia algebry relacyjnej mogą wykorzystać \(LEQ\) jak każdą inną tabelę. Jednak \(LEQ\) uważamy za część składni zapytań, a nie zwykłą tabelę w bazie.

Drugi sposób polega na tym, że nie zwiększamy liczby tabel, ale poszerzamy składnię i w warunku \(\theta\) selekcji \(\sigma_\theta(E)\) dopuszczamy także nierówności postaci \(i\leq j\) dla \(i,j\) nie większych niż liczba kolumn w \(E\). Semantyka jest oczywista, np. \([\![\sigma_{i\leq j}(E)]\!]=\{\vec{a}\in [\![E]\!]:a_i\leq a_j\}.\)

Pokazać, że zbiory zapytań wyrażalnych w obu formalizmach są takie same.

Zad. 3 (3 punkty)

Wykazać, że dla każdego ustalonego skończonego grafu \(\mathfrak{G}\) (ta litera to gotyckie G) i każdego ustalonego \(m\in\mathbb{N}\), następujący problem decyzyjny może zostać rozstrzygnięty przez deterministyczną maszynę Turinga, która obok taśmy z danymi tylko do odczytu ma taśmę roboczą o długości \(O(\log n)\) (za \(n\) przyjmujemy długość danych wejściowych algorytmu):

Dany: kod skończonego grafu \(\mathfrak{H}\) (gotyckie H) w postaci macierzy incydencji podanej wierszami.
Pytanie: Czy gracz II ma strategię wygrywającą w grze \(G_m(\mathfrak{G},\mathfrak{H})\)?

Zad. 4 (3 punkty)

Czy następująca formuła logiki drugiego rzędu jest tautologią dla \(n>1\):
\(\forall E\left[\left(\begin{array}{c}\forall xE(x,x)\land\\ \forall xy(E(x,y)\to E(y,z))\land\\ \forall xyz((E(x,y)\land E(y,z))\to E(x,z)))\end{array}\right)\to\forall x_{1}\dots x_{n}\ \bigvee _{{0\leq i< j\leq n}}E(x_{i},x_{j}))\right]\) \(\to\) \((\exists y_{1}\ldots y_{{n-1}}\forall z\bigvee _{{i=1}}^{{n-1}}y_{i}=z)\)

Zad. 5 (1.5 punkta)

Odpowiedz TAK lub NIE na wybrane trzy spośród poniższych pytań. Każda poprawna odpowiedź daje \(0.5\) punkta, każda niepoprawna \(-0.5\) punkta. W razie udzielenia odpowiedzi na więcej pytań, do wyniku zaliczymy trzy najgorsze z nich. Odpowiedzi proszę pisać na tej kartce!

• Czy teoria pierwszego rzędu ciała liczb zespolonych \(\mathfrak{C}=\langle\mathbb{C},+,\cdot,0,1\rangle\) jest rozstrzygalna?
• Czy dla każdego zbioru zdań \(\Gamma\) istnieje minimalny ze względu na zawieranie podzbiór \(\Gamma^{{\prime}}\subseteq\Gamma\) spełniający \(\Gamma^{{\prime}}\models\Gamma\)?
• Czy problem SAT dla zdaniowej logiki trójwartościowej Bochvara jest NP-zupełny?
• Czy formuła \(p\lor(q\to\lnot p)\) jest tautologią zdaniowej logiki intuicjonistycznej?

Egzamin poprawkowy 2010/2011

Zad. 1 (3 punkty)

Rozważamy skończone grafy \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\).

Napisać zdanie \(\varphi\) logiki egzystencjalnej drugiego rzędu (tzn. postaci \(\exists R_{1}\ldots\exists R_{k}\psi(R_{1},\ldots,R_{k}),\) w którym \(\psi\) jest zdaniem pierwszego rzędu) takie, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 2 (3 punkty)

Pokazać, że żadne zdanie \(\varphi\) logiki pierwszego rzędu nie ma tej własności, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 3 (3 punkty)

Niech wyrażenie \(E\) algebry relacyjnej ma taką właściwość, że żadne podwyrażenie \(E\) nie ma więcej niż \(k\) kolumn. Pokazać, że istnieje algorytm obliczający wartość \([\![E]\!]\) w bazie strukturze \(\mathfrak{A}\), który działa w czasie \(O(n^{k}\log n),\) gdzie \(n\) to liczność dziedziny aktywnej \(\mathfrak{A}\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z \(\mathfrak{A}\) są przekazywane do algorytmu właśnie w takich tablicach: relacja o \(l\) kolumnach jest reprezentowana przez \(l\) tablic, a dane zajmują początkowe indeksy.

Zad. 4 (3 punkty)

Rozważamy skończone drzewa binarne \(\mathfrak{T}\) (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.

Udowodnić, że dla każdego naturalnego \(n\) istnieje zdanie \(\varphi _{n}\) logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego \(\mathfrak{T}\) zachodzi równoważność: \(\mathfrak{T}\models\varphi _{n}\) wtw \(\mathfrak{T}\) jest pełnym drzewem binarnym o głębokości \(n\).

Zad. 5 (3 punkty)

Sygnatura składa się z dwuargumentowego symbolu funkcyjnego \(\circ\), jednoargumentowego symbolu funkcyjnego \(inv\) i symbolu stałej \(id\). Model \(\mathfrak{F}\) (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji \(f:A\to A\) dla pewnego zbioru \(A,\) a operacje mają następujące interpretacje: \(\circ^{\mathfrak{F}}\) to operacja składania funkcji, \(inv^{\mathfrak{F}}\) to operacja brania funkcji odwrotnej, a \(id^{\mathfrak{F}}\) to funkcja indentycznościowa z \(A\) w \(A\).

Udowodnić, że nie istnieje zbiór \(\Gamma\) zdań logiki pierwszego rzędu taki, że \(\mathfrak{B}\models\Gamma\) wtedy i tylko wtedy, gdy \(\mathfrak{B}\) jest izomorficzny do pewnej grupy bijekcji.

Egzamin po-poprawkowy 2010/2011 (dla osób z przedłużeniem sesji)

Zad. 1 (3 punkty)

Rozważamy skończone grafy nieskierowane \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu
można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego
symbolu relacyjnegoE.
Napisć zdanie logiki MSO postaci \(\forall X_1\ldots\forall X_k\psi(X_1,\ldots,X_k)\), w którym \(\psi\) jest
zdaniem pierwszego rzędu takie,że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność:
\(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) jest drzewem (nieskierowanym).

Zad. 2 (3 punkty)

Pokazć, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla
każdego nieskierowanego (skończonego lub nie) grafu \(\mathfrak{G}\) zachodzi równoważność:
\(\mathfrak{G}\models\varphi\) wtw każdy wierzchołek \(\mathfrak{G}\) należy do pewnego cyklu w tym grafie.

Zad. 3 (3 punkty)

Dane są dwie tabele \(A\) i \(B\) o dwóch kolumnach każda. Ta pierwsza składa się z \(n_A\)
wierszy.
Zaprojektowć algorytm wyliczenia wartości wyrażenia algebry relacyjnej

\(A\setminus\pi_{12}(\sigma_{1=3}(A\times B))\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb
całkowitych typu integer, a do dyspozycji są dwukolumnowe tablice, których wiersze
indeksowane są nieujemnymi liczbami całkowitymi i zawierają takież liczby.
W algorytmie należy użyć dokładnie jednej takiej tablicy o rozmiarze \(n_A\) wierszy i
kilku dodatkowych zmiennych typu integer. Oznacza to,że wykorzystujemy dokładnie
tyle pamięci, ile zajmie wynik. Proszę nie używć wskaźników, rekursji i innych metod
ukrytego alokowania dodatkowej pamięci.

Tabele \(A\) i \(B\) są tylko do odczytu, przy czym można założyć, że są one posortowane.
Jeśli rozwiązanie będzie z tego korzystć, proszę o tym założeniu wspomnieć.

Zad. 4 (3 punkty)

Rozważamy skończone skierowane cykle \(\mathfrak{C}\) (ta litera to gotyckie C, w rozwiązaniu
można pisć zwykłe C) nad sygnaturą składającą się z jednego dwuargumentowego
symbolu relacyjnego \(E\).

Udowodnić, że dla każdego naturalnego \(n\) istnieje formuła
\(\varphi_n(x,y,z)\) logiki pierwszego rzędu, w której występują tylko trzy zmienne (które można rekwantyfikowć
tak często jak potrzeba), takie że dla każdego skończonego cyklu \(\mathfrak{C}\) zachodzi równoważność:
\((\mathfrak{C}, x : a, y : b, z : c)\models\varphi_n(x,y,z)\) wtw \(\mathfrak{C}\) ma \(3n\) krawędzi, a skierowane
odległości z \(a\) do \(b\), z \(b\) do \(c\) i z \(c\) do \(a\) wszystkie wynoszą po \(n\).

Zad. 5 (3 punkty)

Niech \(\varphi\) będzie zdaniem \(\forall x\forall y(y =f(g(x)) \to(\exists u(u=f(x)\land y =g(u))))\) oraz
niech \(\psi\) będzie zdaniem
\(\forall x[f(g(f(x))) =g(f(f(x)))]\). Czy \(\{\psi\}\models\varphi\)?

Kolokwium 2011/2012

Mid-term test 2011/2012

Problem 1A

Let signature \(\Sigma=\{+, s, f, 0\}\) consist only of function symbols, and let + be binary, \(s\) and \(f\) unary, 0 constant. In the algebra \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A},f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) the function \(f^\mathfrak{A}\) is said to be periodic, if there exists\(k \in A\), \(k \not =0^\mathfrak{A}\) such tha tfor every \(x\in A\) holds \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\).
\(f^\mathfrak{A}\) is standard periodic, if there exists \(k=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)\) such that for each \(x\in A\) holds \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\).

For each of the following classes of structures determine, if it is
i) axiomatisable by a single sentence
ii) axiomatisable by a set of sentences, but not by a single sentence
iii) is not axiomatisable by any set of sentences

1. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is periodic

2. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is standard periodic

3. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is not standard periodic

Problem 2A

We work with the class of directed graphs (self-loops are permitted). Give an example of two such graphs \(\mathfrak{G}_1\) and \(\mathfrak{G}_2\) such that:

1. For each graph \(\mathfrak{H}\) with at most 7 vertices, \(\mathfrak{G}_1\) contains an induced subgraph isomorphic to \(\mathfrak{H}\) if and only if \(\mathfrak{G}_2\) contains an induced subgraph isomorphic to \(\mathfrak{H}\).
2. Player I has a winning strategy in the game \(G_7(\mathfrak{G}_1,\mathfrak{G}_2).\)

Problem 3A
We consider the structure
\(\mathfrak{P}=\langle \mathbb{R}^3,B^\mathfrak{P}\rangle\), where the relation \(B^\mathfrak{P}\) is 3-ary and defined as follows:

\(B^\mathfrak{P}(a,b,c)\) holds if and only if \(a,b,c\) are all different and collinear, and moreover \(b\) belongs to the line segment connecting \(a\) and \(c\).

Write a first-order formula \(\varphi\) such that

\((\mathfrak{P},x_1:a_1,x_2:a_2,x_3:a_3,x_4:a_4)\models\varphi\) if and only of the points \(a_1,a_2,a_3,a_4\) lay on a common plane.

Egzamin 2011/2012

   *      *      *      *                        *      *      *    
   |      |      |      |                        |      |      |    
 *-*-*  *-*-*  *-*-*  *-*-*                    *-*-*  *-*-*  *-*-*  
   |      |      |      |                        |      |      |    
   *      *      *      *                        *      *      *    
 

Egzamin poprawkowy 2011/2012

    *        *        *    
    |        |        |    
 *--*--*  *--*--*  *--*--*

Kolowium 2012/2013

Monoid to struktura \(\mathfrak{M}=\langle M,\circ,e\rangle\), w której
dwuargumentowa operacja \(\circ\) jest łączna, a stała \(e\) jest jej
elementem neutralnym.

Monoid \(\mathfrak{M}\) jest skończenie generowany, jeśli istnieje
skończenie wiele elementów \(a_1,\ldots,a_n\in M\) takich, że każde
\(a\in M\) można wyrazić za pomocą \(\circ\) stosowanej do tych
elementów. Na przykład monoid \(\langle
A^*,\cdot,\varepsilon\rangle\) słów nad alfabetem \(A\) z konkatenacją i
słowem pustym jest skończenie generowany wtedy i tylko wtedy, gdy \(A\)
jest skończony.

Monoid \(\mathfrak M=\langle M,\circ,e\rangle\) jest definiowany w
\(\mathfrak{N}\) formułami \(\mu(x), \ \nu(x,y,z)\) i \(\epsilon(x)\) nad
sygnaturą arytmetyki, jeśli
\(M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}\), dla
dowolnych \(a,b,c\in M\) zachodzi: \(a\circ b=c\) wtedy i tylko wtedy, gdy
\((\mathfrak{N},x:a,y:b,z:c)\models\ \nu\) oraz \(e\) jest jedynym elementem
\(M\) dla którego \((\mathfrak{N},x:e)\models\epsilon.\)

Zad. 1

Wykaż, ze klasa monoidów skończenie generowanych nie jest
aksjomatyzowalna żadnym zbiorem zdań.

Zad. 2

Dla danych \(\mu(x),\ \nu(x,y,z)\) i \(\epsilon(x)\) nad sygnaturą arytmetyki, które
definiują monoid w \(\mathfrak{N}\), napisz zdanie \(\gamma\) nad sygnaturą
arytmetyki, używające ich jako podformuł, takie że

\(\mathfrak{N}\models \gamma\) wtedy i tylko wtedy, gdy monoid definiowany
przez \(\mu,\ \nu\) i \(\epsilon\) jest skończnie generowany.

Zad. 3

Rozważamy dwa grafy \(\mathfrak{T}_1=\langle T_1,E_1\rangle\) i
\(\mathfrak{T}_2=\langle T_2,E_2\rangle\) określone jak następuje:

\(T_1=\{1,2,\ldots,15\},\) \(E_1=\{\langle n,2n+1\rangle~|~n,2n+1\in T_1\}\)

\(T_2=\{1,2,\ldots,11\},\) \(E_2=\{\langle n,2n+1\rangle~|~n,2n+1\in T_2\}\)

Napisz zdanie o minimalnej randze kwantyfikatorowej, które rozróżnia
\(\mathfrak{T}_1\) i \(\mathfrak{T}_2\). Należy uzasadnić poprawność
zdania, można nie uzasadniać jego minimalności.

Mid-term test 2012/2013

A {\em monoid} is a structure \(\mathfrak{M}=\langle M,\circ,e\rangle\),
where binary operation \(\circ\) is associative and constant \(e\) is its
neutral element.

Monoid \(\mathfrak{M}\) is finitely generated, if there exist
finitely many elements \(a_1,\ldots,a_n\in M\) such that every \(a\in M\) can be
expressed using those elements and \(\circ\). For example, the monoid
\(\langle A^*,\cdot,\varepsilon\rangle\) of words over an alphabet \(A\) with
concatenation and empty word is a finitely generated iff \(A\) is finite.

Monoid \(\mathfrak M=\langle M,\circ,e\rangle\) is defined in
\(\mathfrak N\) by formulas \(\mu(x),\ \nu(x,y,z)\) and \(\epsilon(x)\) over the
signature of arithmetics, if
\(M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}\), for every
\(a,b,c\in M\) the equality \(a\circ b=c\) holds if and only if
\((\mathfrak{N},x:a,y:b,z:c)\models\nu\) and \(e\) is the only element of
\(M\) such that \((\mathfrak{N},x:e)\models\epsilon.\)

Problem 1

Prove that the class of finitely generated monoids is not
axiomatizable by any set od sentences of FO.

Problem 2

For given \(\mu(x),\ \nu(x,y,z)\) and \(\epsilon(x)\) over the signature
of arithmetics, which define a monoid in \(\mathfrak{N}\), write a
sentence \(\gamma\) over the signature of arithmetics, which may use
them as subformulas, and such that

\(\mathfrak{N}\models \gamma\) if and only if the monoid defined by
\(\mu,\ \nu\) and \(\epsilon\) is finitely generated.

Problem 3

We consider two graphs \(\mathfrak{T}_1=\langle T_1,E_1\rangle\) and
\(\mathfrak{T}_2=\langle T_2,E_2\rangle\) defined as follows:

\(T_1=\{1,2,\ldots,15\},\) \(E_1=\{\langle n,2n+1\rangle~|~n,2n+1\in T_1\}\)

\(T_2=\{1,2,\ldots,11\},\) \(E_2=\{\langle n,2n+1\rangle~|~n,2n+1\in T_2\}\)

Write a sentence of minimal possible quantifier rank, which
distinguishes \(\mathfrak{T}_1\) and \(\mathfrak{T}_2\). You should prove
the correcntess of your sentence, but you do not have to prove its
minimality.

Egzamin 2012/2013

Egzamin poprawkowy 2012/2013

Zadanie 1 (10 punktów) Niech sygnatura \(\Sigma\) składa
się tylko z symboli relacyjnych: dwuargumentowego \(E\) i jednoargumentowego \(P\). Rozważmy klasę \(\mathcal{A}\) struktur \(\mathfrak{A}=(A, E^{\mathfrak{A}}, P^{\mathfrak{A}})\) nad sygnaturą \(\Sigma\), w których \(E^{\mathfrak{A}}\) jest symetryczna i takich, że w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) istnieje wierzchołek spełniający \(P^{\mathfrak{A}}\).

Określ, czy klasa \(\mathcal{A}\) jest (i) aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu, (ii) aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem, (iii) nieaksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Zadanie 2 (10 punktów) Prosty graf nieskierowany (zwany dalej grafem) to struktura \(\mathfrak{G}\) nad
sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), taka że relacja \(E^{\mathfrak{G}}\) jest symetryczna (tzn. jeśli \((x,y)\in E^{\mathfrak{G}}\) to \((y,x)\in E^{\mathfrak{G}}\)) i antyzwrotna (tzn. nie ma takich \(x\) że \((x,x)\in E^{\mathfrak{G}}\)). Dopełnieniem grafu \(\mathfrak{G}\) jest graf \(\overline{\mathfrak{G}}\) o tym samym zbiorze wierzchołków co \(\mathfrak{G}\), w którym występują dokładnie te krawędzie, które nie występują w \(\mathfrak{G}\).

Dla (i) \(n=5\) oraz dla (ii) \(n=6\) narysuj taki graf \(\mathfrak{G}\) o \(n\) wierzchołkach, żeby Gracz II miał strategię wygrywającą w grze Ehrenfeuchta-Fra\"{\i}ss\'e o możliwie wielu rundach na grafie \(\mathfrak{G}\) i jego dopełnieniu \(\overline{\mathfrak{G}}\). Im więcej rund uzyskasz, tym lepsze rozwiązanie. Napisz ile rund uzyskałeś/aś i, o ile to możliwe, podaj formułę logiczną o możliwie małej głębokości kwantyfikatorowej, która rozróżnia \(\mathfrak{G}\) i \(\overline{\mathfrak{G}}\).

Zadanie 3 (10 punktów) Napisz zdanie w monadycznej logice drugiego rzędu MSO, które definiuje klasę \(\mathcal{A}\) z zadania 1.

Zadanie 4 (10 punktów) Niech \(\mathfrak{A}=\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A},U^\mathfrak{A}\rangle,\) gdzie \(E\) jest symbolem relacji dwuargumentowej a \(U\) jest symbolem relacji jednoargumentowej. \(\langle x,y\rangle E^\mathfrak{A}\langle x',y'\rangle\) zachodzi wtedy i tylko wtedy, gdy (\(x=x'\) i \(|y-y'|=1\)) lub (\(|x-x'|=1\) i \(y=y'\)). Zatem \(\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A}\rangle\) to przeliczalny graf nieskierowany w kształcie kraty.

(i) Napisz zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych wierszy lub pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).

(ii) Udowodnij, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).

TEST

Pytanie 1 (2 punkty) Czy istnieje liczba \(k\) taka, że dla każdego zdania \(\varphi\) logiki
pierwszego rzędu istnieje formuła \(\psi\) w której nie występują
kwantyfikatory, ciąg kwantyfikatorów
\(Q_1,\ldots,Q_k\in\{\forall,\exists\}\) i ciąg zmiennych \(x_1,\ldots,
x_k\) taki że tautologią jest
\[
\varphi \leftrightarrow Q_1x_1\cdots Q_kx_k\psi \qquad ?
\]

Pytanie 2 (2 punkty) Czy następujące zdanie logiki drugiego rzędu SO, nad sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), jest tautologią?
\begin{align*}
\exists R &[\forall x\forall y(E(x,y)\to R(x,y))
\ \land\ \forall x\forall y\forall z(R(x,y)\land R(y,z)\to R(x,z))
\ \land\ \exists x\exists y\neg R(x,y)] \\
\rightarrow \\
\exists P &[\exists x P(x)\ \land\ \exists x\neg P(x)
\ \land\ \forall x\forall y(P(x)\land E(y,x)\to P(y))]
\end{align*}

Pytanie 3 (2 punkty) Czy rozstrzygalny jest następujący problem:

Dane: zdanie \(\varphi\) logiki drugiego rzędu SO oraz skończony model \(\mathfrak{A}\) nad tą samą sygnaturą.

Pytanie: czy \(\mathfrak{A} \models \varphi\)?

Pytanie 4 (2 punkty) Czy dla każdej sygnatury \(\Sigma\) i każdej struktury \(\mathfrak{A}\) mocy \(\mathfrak{c}\) nad \(\Sigma\) istnieje przeliczalna struktura \(\mathfrak{B}\) nad \(\Sigma\) taka, że \(\mathfrak{A}\equiv\mathfrak{B}\)?

Pytanie 5 (2 punkty) Czy język słów nad alfabetem \(\{0,1\}\), które są palindromami jest definiowalny w logice pierwszego rzędu nad sygnaturą modeli-słów, w tym wypadku złożoną z binarnego \(\leq\) i unarnego \(X\)? Zakładamy, że prawdziwość \(X\) oznacza literę 1, a fałszywość literę 0.

Kolokwium 2013/2014

Kolokwium z logiki dla informatyków 2013/2014

Zadanie 1 Rozważamy klasę \(\mathcal{A}\) wszystkich struktur, które są izomorficzne do struktury postaci \(\langle A^\mathbb{N},R\rangle\), gdzie \(A\) jest dowolnym niepustym zbiorem, \(A^\mathbb{N}\) jest zbiorem wszystkich nieskończonych ciągów elementów \(A\), zaś \(xRy\) zachodzi wtedy i tylko wtedy, gdy zbiór pozycji na których \(x\) i \(y\) się różnią, jest skończony.

Udowodnij że \(\mathcal{A}\) nie jest akjomatyzowalne żadnym zbiorem zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z \(R\).

Zadanie 2 Niech struktura \(\mathfrak{A}=\langle A,<^\mathfrak{A}\rangle\) będzie liniowym porządkiem na \(A\) takim, że \(\mathfrak{A}\) jest 2-elementarnie równoważne strukturze \(\mathfrak{N}=\langle \mathbb{N}, <\rangle\). Czy z tego wynika, że

* \(A\) jest nieskończone;
* \(A\) ma element najmniejszy;
* Każdy element \(A\) ma tylko skończenie wiele elementów mniejszych od siebie?

Odpowiedzi uzasadnij.

Zadanie 3 Rozstrzygnij, czy następujące formuły mają dowód w systemie Gentzena dla logiki zdaniowej:

* \( (p\to q) \lor (q\to p)\)
* \((p\to ( q \to p)) \to p\)

Egzamin 2013/2014

  *        *-*       *-*-*
 / \      /   \     /     \
*   *    *     *   *       *   ...
 \ /      \   /     \     /
  *        *-*       *-*-*

  *        *-*       *-*-*                  *-*-*-*-*...
 / \      /   \     /     \                /     
*   *    *     *   *       *   ...        *
 \ /      \   /     \     /                \
  *        *-*       *-*-*                  *-*-*-*-*...

 * - *                     * - *   
 |   |                     | \ |
 * - *                     * - *

Egzamin poprawkowy 2013/2014

Zadanie 1 (10 punktów) Rozważamy klasę grafów, czyli symetrycznych struktur (skończonych lub nieskończonych) bez pętli nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E.\) Graf \(\mathfrak{G}=\langle V,E\rangle\) jest dwudzielny gdy istnieją niepuste rozłączne podzbiory \(A,B\subseteq V\) takie, że \(E\subseteq (A\times B)\cup(B\times A)\).

Dla każdej z poniższych klas grafów

1. grafy dwudzielne
2. grafy nie-dwudzielne

określ, czy jest ona

1. aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu
2. aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem
3. nieaksjomatyzowalna żadnym zbiorem zdań logiki pierwszego rzędu

Zadanie 2 (10 punktów)
Relacja \(E\subseteq A\times A\) ma \textit{własność Churcha-Rossera} jeśli dla każdych \(a,b,c\) takich, że istnieją ścieżki od \(a\) do \(b\) i od \(a\) do \(c,\) istnieje \(d\), osiągalne ścieżkami zarówno z \(b\) jak i z \(c\). (Takie relacje są istotne w badaniach rachunku \(\lambda.\))

Udowodnij, że istnieje zdanie logiki MSO \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność Churcha-Rossera.

Zadanie 3 (10 punktów)

Dla przypomnienia, spektrum \(\mathit{Spec}(\varphi)\) zdania \(\varphi\) to zbiór \(\{n\in\mathbb{N}~|\)istnieje model zdania \(\varphi\) mocy \(n\}.\)

Niech z zdaniu \(\varphi\) występują wyłącznie jednoragumentowe symbole relacyjne. Udowodnij, że \(\mathit{Spec}(\varphi)\) jest albo skończony, albo jego dopełnienie jest skończone.

Zadanie 4 (10 punktów)

Udowodnić, że struktury \(\langle\mathbb{Q}\times\mathbb{Z},\leq\rangle\) i \(\langle\mathbb{R}\times\mathbb{Z},\leq\rangle\), uporządkowane leksykograficznie z użyciem naturalnych porządków na \(\mathbb{Z}\), \(\mathbb{Q}\) i \(\mathbb{R},\) są elementarnie równoważne.

TEST

1.
Dana jest struktura \(\mathfrak{A}=\langle \{a,b\}^*,\cdot,a,b,\varepsilon\rangle\) słów nad alafabetem \(\{a,b\}\) z operacją konkatenacji oraz słowami jednoliterowymi \(a\) i \(b\) i słowem pustym jako stałymi. Czy istnieje formuła \(\varphi(x)\) logiki pierwszego rzędu z jedną zmienną wolną \(x\) taka, że język \(\{w~|~(\mathfrak{A},x:w)\models\varphi\}\) nie jest regularny?

2. Logikę \(L\) nazywamy \textit{monotoniczną}, jeśli z tego, że \(\Delta\models\varphi\) oraz \(\Gamma\supseteq\Delta\) wynika, że \(\Gamma\models\varphi.\)

Dla logiki trójwartościowej Sobocińskiego określamy, że \(\Delta\models\varphi\), gdy dla każdego wartościowania zmiennych zdaniowych wartościami ze zbioru \(\{0,\frac12,1\}\), jeśli wartości wszystkich zdań z \(\Delta\) wynoszą 1, to także wartość \(\varphi\) wynosi 1.

Czy logika trójwartościowa Sobocińskiego jest monotoniczna?

3. Czy gracz II ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fraisse o 4 rundach na następujących dwóch grafach nieskierowanych o 10 wierzchołkach:

       *                       *    
       |                       |
   * - * - *               * - * - *
                               |
                               *
 
 
       *                       *   
       |                       |
   * - * - *               * - * - *
      /  \                     |
     *    *                    *

4. Czy sekwent \(\{p,q\to p,\lnot q\}\vdash\{p,q\}\) jest dowodliwy w systemie Gentzena dla logiki zdaniowej?

5. Czy sekwent \(\vdash(\forall x P(x) \to \exists y \forall z R(y, z) ) \to \exists x \forall z (\lnot P(x) \lor R(x, z))\) jest dowodliwy w systemie Hilberta dla logiki pierwszego rzędu?

Kolokwium 2014/2015

Egzamin 2014/2015

Egzamin poprawkowy 2014/2015

Dwa z zadań są osnute wokół Lematu Koeniga w następującym sformułowaniu:
Założenie: Graf \(\mathfrak{T}\) (gotyckie T) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.
Teza: W drzewie \(\mathfrak{T}\) istnieje nieskończona ścieżka.

Zadanie 1 (10 punktów)

Sformalizuj jednym zdaniem pełnej logiki drugiego rzędu SO założenie Lematu Koeniga: napisz zdanie \(\varphi\) takie, że jeśli graf skierowany \(\mathfrak{T}\models\varphi,\) to \(\mathfrak{T}\) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.

Zadanie 2 (10 punktów)

Udowodnij, że nie istnieje zbiór zdań \(\Delta\) logiki pierwszego rzędu formalizujący negację tezy Lematu Koeniga, czyli taki, że dla każdego grafu skierowanego \(\mathfrak{T}\), jeśli \(\mathfrak{T}\models\Delta\) to albo \(\mathfrak{T}\) nie jest drzewem, albo nie zawiera nieskończonej ścieżki.

Zadanie 3 (10 punktów, po 5 za każdą z części)

Kwadrat kartezjański \(\mathfrak{G}^2\) grafu \(\mathfrak{G}=\langle G,E^\mathfrak{G}\rangle\) to struktura
\(\langle G\times G,E\rangle\), w której \(\langle(g,h),(g',h')\rangle \in E\) zachodzi wtedy i tylko wtedy, gdy \(\langle g,g'\rangle \in E^\mathfrak{G}\) i \(\langle h,h'\rangle \in E^\mathfrak{G}\).

1. Wykaż, że dla każdego skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach zachodzi \(\mathfrak{G}^2\not\equiv_{n+1}\mathfrak{G}.\)
2. Podaj przykład skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach spełniającego \(\mathfrak{G}^2\equiv_n\mathfrak{G}.\)

Zadanie 4 (10 punktów)

Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) nad sygnaturą \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\)istnieje struktura \(\mathfrak{A}\) mocy \(n\) spełniająca \(\varphi\}.\)

Udowodnij, że zbiór \(\{ m+n~|~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).

Zadanie 5 (10 punktów)

Dla danej formuły \(\varphi(x)\) w języku arytmetyki skonstruuj formułę \(\#\varphi(x)\), również w języku arytmetyki, o następującej własności:

\((\mathbb{N},x:n)\models \#\varphi(x)\) wtw \(|\{m\in\mathbb{N}~|~(\mathbb{N},x:m)\models\varphi(x)\}|=n.\)

Kolokwium 2015/2016

Egzamin 2015/2016

*---*
|\ /|
| * |
|/ \|
*---*

*   *   *
|   |
*   *

Egzamin poprawkowy 2015/2016

Egzamin poprawkowy z Logiki dla informatyków, 22/02/2016

Zadanie 1 (10 punktów)
Relacja \(E\subseteq A\times A\) ma własność silnej normalizacji jeśli dla każdego \(a\in A\) każda ścieżka zaczynająca się od \(a\) jest skończonej długości. (Takie relacje są istotne w badaniach systemów przepisywania termów i rachunku \(\lambda\).)

Udowodnij, że nie istnieje zdanie logiki pierwszego rzędu \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność silnej normalizacji.

Zadanie 2 (10 punktów)
Udowodnij, że istnieje zdanie logiki MSO \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność silnej normalizacji (zdefiniowaną w Zadaniu 1).

Zadanie 3 (10 punktów)
Zadanie dotyczy klasycznej logiki zdaniowej. Wykaż, że istnieją interpolanty \(\varphi_n\) zawierające wyłącznie zmienne zdaniowe \(p_1,\ldots,p_n\) oraz długości \(O(n),\), takie, że tautologiami są formuły
\(\left((p_1\lor z_1)\land(\lnot z_1\lor p_2\lor z_2)\land(\lnot z_2\lor p_3\lor z_3)\land\ldots\land(\lnot z_{n-2}\lor p_{n-1}\lor z_{n-1})\land(\lnot z_{n-1}\lor p_n)\right)\to\varphi_n\)
oraz
\(\varphi_n\to\left[\left((p_1\to x_1)\land((x_1\lor p_2)\to x_2)\land((x_2\lor p_3)\to x_3)\land\ldots\land((x_{n-1}\lor p_{n})\to x_n)\right)\to x_n\right].\)

Zadanie 4 (10 punktów)
To zadanie dotyczy algebry relacji. Antyzłączenie (ang. antijoin) dwóch wyrażeń \(E\) i \(F\) o odpowiednio \(m\) i \(n \) kolumnach, oznaczane \(E \triangleright_{i=j} F\), ma następującą semantykę:

\([[E \triangleright_{i=j} F]]=\{\vec{a}\in[[E]]~|~\)nie istnieje \(\vec{b}\in[[F]]\) takie, że \(a_i=b_j\}\).

Napisz wyrażenie standardowej algebry relacji, które jest równoważne \(E \triangleright_{i=j} F\).

TEST

1.
Czy dla każdej klasy \(\mathcal{A}\) skończonych grafów, która jest zamknięta na izomorfizmy, istnieje zbiór \(\Delta\) uniwersalnych zdań logiki pierwszego rzędu taki, że dla każdego skończonego grafu \(\mathfrak{A}\) zachodzi równoważność: \(\mathfrak{A}\in\mathcal{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\Delta.\) Czy i jakie modele nieskończone ma \(\Delta\) jest tu bez znaczenia.

Zdanie jest uniwersalne, gdy ma postać \(\forall x_1\ldots\forall x_n\varphi,\) gdzie \(\varphi\) nie zawiera kwantyfikatorów.

2.
Dla przypomnienia, spektrum \(\mathit{Spec}(\varphi)\) zdania \(\varphi\) to zbiór \(\{n\in\mathbb{N}~|\)istnieje model zdania \(\varphi\) mocy \(n\}.\) Wiadomo, że jeśli w zdaniu \(\varphi\) występują wyłącznie jednoragumentowe symbole relacyjne, to \(\mathit{Spec}(\varphi)\) jest albo skończony, albo jego dopełnienie jest skończone.

Czy istnieje zdanie \(\varphi\), w którym występuje wyłącznie jeden jednoragumentowy symbol funkcyjny, oraz \(\mathit{Spec}(\varphi)\) nie jest ani skończony, ani jego dopełnienie nie jest skończone?

3.
Czy poniższa formuła poprawnie formalizuje własność: "istnieje dokładnie jeden element, który spełnia formułę \(\varphi(x)\)":
\[\exists x\forall y(\forall z((z=x \lor z=y)\to\varphi(z))\to x=y).\]

4.
Formuła Peirce'a \(((p\to q)\to p)\to p\) nie jest twierdzeniem zdaniowej logiki intuicjonistycznej. Czy istnieje model Kripkego o jednym stanie, w którym ta formuła nie jest wymuszona?

5.
Czy istnieje formuła \(\varphi(n,m)\) w języku arytmetyki taka, która orzeka w standardowym modelu arytmetyki, że \(m\)-tą cyfrą rozwinięcia dziesiętnego liczby \(\pi=3.14\ldots\) jest \(n.\) Na przykład miałyby zachodzić
\((\mathfrak{N},m:1,n:3)\models\varphi\), \((\mathfrak{N},m:2,n:1)\models\varphi\), \((\mathfrak{N},m:3,n:2)\not\models\varphi\).

Kolokwium 2016/2017

Zadanie 1
Częściowy porządek \(\mathfrak{A}=\langle A,\leq\rangle\) należy do klasy \(\mathcal{A}\) wtedy i tylko wtedy, gdy:

(a) zawiera nieskończenie wiele elementów minimalnych;

(b) każdy nie-minimalny element \(a\in A\) jest supremum pewnego skończonego zbioru elementów minimalnych w \(\mathfrak{A}\).

Czy klasa \(\mathcal{A}\) jest aksjomatyzowalna jednym zdaniem, aksjomatyzowalna zbiorem zdań ale nie jednym zdaniem, bądź nieaksjomatyzowalna nawet zbiorem zdań?

Zadanie 2
Gra w życie toczy się na nieskończonej planszy \(\mathbb{Z}\times\mathbb{Z}\). Sąsiadami komórki \((x,y)\) jest osiem komórek \((x',y')\neq (x,y)\) dla których \(|x-x'|\leq 1\) i \(|y-y'|\leq 1.\)

Każda komórka może znajdować się w jednym z dwóch stanów: może być albo żywa, albo martwa. Czas jest dyskretny, stany komórek zmieniają się synchronicznie wedle następujących reguł: martwa komórka, która ma dokładnie 3 żywych sąsiadów, staje się w następnym kroku żywa, a żywa komórka z 2 albo 3 żywymi sąsiadami pozostaje nadal żywa, w przeciwnym przypadku umiera.

Dana jest struktura \(\mathfrak{A}=\langle\mathbb{Z}\times\mathbb{Z},\leq_1,\leq_2,U\rangle,\) gdzie \((x_1,x_2)\leq_i(y_1,y_2)\) wtw \(x_i\leq y_i\). \(U\) jest relacją unarną, którą traktujemy jako wkazanie żywych komórek na planszy do gry w życie. Wykaż, że dla każdego \(k\) istnieje formuła \(\varphi_k(x)\) z jedną zmienną wolną, dla której zachodzi:

\((\mathfrak{A},x:a)\models\varphi\) wtw komórka \(a\) jest żywa po \(k\)-tym kroku gry w życie, startującej z pozycji opisanej przez \(U.\)

Zadanie 3
Zadanie dotyczy klasycznej logiki zdaniowej nad zbiorem zmiennych zdaniowych \(\{p_0,p_1,\ldots\}.\)

Skonstruować bądź udowodnić że nie istnieje zbiór \(\Delta\) zdań logiki zdaniowej taki, że wartościowania \(v\) spełniające zbiór \(\Delta\) to dokładnie takie, dla których zbiór \(\{i\in\mathbb{N}~|~v(p_i)=1\}\) jest skończony.

Egzamin 2016/2017

  A                   A'
  *--*--*--...--*--*--*
  |  |  |       |  |  |
  |  |  |  ...  |  |  |
  |  |  |       |  |  |
  *--*--*--...--*--*--*
  B                   B'

              * not(p)
            /
           /
not(p)*
          \
           \
             * p

Egzamin poprawkowy 2016/2017

zadania 2003

1. Proszę zdefiniować relację izomorfizmu.
2. Proszę zdefiniować relację \(m\)-izomorfizmu i omówić jej związek z grą Ehrenfeuchta-Fraïsségo.
3. Proszę opisać grę Ehrenfeuchta-Fraïsségo i omówić jej związek z \(m\)-izomorfizmem.
   
4. Proszę zdefiniować pojęcie podstruktury indukowanej.
5. Proszę zdefiniować pojęcie podalgebry generowanej.
6. Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie zmiennych wolnych danej formuły.
7. Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie rangi kwantyfikatorowej danej formuły.
   
8. Proszę zdefiniować relację \(\mathbb{A}\models\varphi[s].\)
9. Proszę zdefiniować sekwent.
10. Proszę zdefiniować pojęcie sekwentu wyprowadzalnego (nie trzeba znać wszystkich reguł systemu Gentzena, tylko mieć orientację o ich postaci).
11. Proszę zdefiniować relację \(\Gamma\models\varphi,\) gdzie \(\Gamma\) to zbiór zdań.
12. Proszę zdefiniować pojęcie tautologii.
13. Proszę zdefiniować pojęcie twierdzenia.
14. Proszę sformułować twierdzenie o pełności.
15. Proszę sformułować twierdzenie o zwartości.
16. Proszę sformułować twierdzenie Skolema-Löwenheima.
17. Proszę sformułować twierdzenie o niezupełności.

W poniższych zadaniach proszę rozstrzygnąć, czy podana formuła jest tautologią czy nie, oraz czy jest spełnialna czy nie. W czasie odpowiedzi wymagane będzie uzasadnienie.
Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\)
Standardowy model arytmetyki to struktura \(\mathbb{N}=\langle\omega,*^{\mathbb}{N},+^{\mathbb}{N},0^{\mathbb}{N},1^{\mathbb}{N},\leq^{\mathbb}{N}\rangle.\)

1. \((\forall x\exists y\ r(x,y))\to(\exists y_{1}\exists y_{2}\forall x\ r(x,y_{1})\lor r(x,y_{1})).\)
2. \((\forall x\ f(f(x))=x)\to(\forall x\forall y\ x\neq y\to f(x)\neq f(y)).\)
3. \((\forall x_{1}\forall x_{2}\forall x_{3}(x_{1}=x_{3}\lor(x_{2}=x_{3}\lor x_{1}=x_{2})))\to(\forall x\exists y\ x\neq y).\)
4. \(\forall x\forall y\exists z\ f(x,z)=y.\)
5. \(\forall x\forall y\exists z\ f(x,y)=z.\)
6. \((\forall x\forall y\exists z\ f(x,z)=y)\to(\exists x\ f(x,x)=x)\).
7. \(\exists x\exists y\ (f(x)=x\to f(y)=y).\)
8. \(\exists x\forall y\ (f(x)=x\to f(y)=y).\)
9. \((\forall x_{1}\forall x_{2}\forall x_{3}(x_{1}=x_{3}\lor(x_{2}=x_{3}\lor x_{1}=x_{2})))\to\)\(((\forall y\exists x\ f(y)=x)\to(\forall x\forall y((x\neq y)\to f(x)\neq f(y)))).\)
10. \((\exists x\ f(x)\neq x)\to(\exists x\exists y\ x\neq y)\).
11. \((\forall x(\forall y\ f(x)\neq y)\to(f(x)\neq x)).\)
12. \((\forall x\forall y\ f(x,y)=f(y,x))\to(\forall x\ f(x,f(f(x,x),x))=f(f(x,x),f(x,x))).\)
13. \(\forall x\forall y\ f(x)=y.\)
14. \((\forall x\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x)))\land(\forall y\ \lnot r(y,y)).\)
15. \((\forall x(\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x))\land(\forall y\ \lnot r(y,y)))).\)
16. \((\exists x(p(x)\to(\forall y\ q(y))))\to(\exists x\forall y\ p(x)\to q(y))\).
17. \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\forall y\ q(y)\to p(x))\).
18. \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\ q(x)\to p(x))\).
19. \((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\).
20. \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\).
21. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)
22. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)\mathbb
23. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)\mathbb
24. Znale”zć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)
25. Znale”zć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)
26. Znale”zć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(y\) jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli \(x.\)

e

1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2},\) przy czym dla wszystkich \(m,n\in\omega\)

   \(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$.}\)\(m\) i \(n\).

   Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest liczb"a pierwsz"a.}\)\(v(x)\) jest liczbą pierwszą.

2. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}},\leq^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(S\in\Sigma^{F}_{1},\) \(\beta\in\Sigma^{F}_{3}\) oraz \(\leq\in\Sigma^{R}_{2},\) przy czym dla każdych \(n,t,p,i\in\omega\)

   \(\displaystyle S^{\mathbb{Y}}(n) =n+1\) ⁢ S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p,i) =\text{$\beta$}(t,p,i),\)\(\beta\) t p i ⁢ β Y t p i = ⁢ β t p i

   gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(\leq^{\mathbb{Y}}\) to zwykła nierówność.

   Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)

3. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

   Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.

4. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma tylko modele nieskończone, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
5. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

   Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.

6. Niech \(\varphi\) będzie zdaniem

   \(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)

   oraz niech \(\psi\) będzie zdaniem

   \(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)

   Czy \(\{\psi\}\models\varphi?\)

7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
8. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

   Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji \(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)

9. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
10. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.

Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 7 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.

Każde zadanie proszę napisać na osobnej kartce, podpianej imieniem, nazwiskiem i numerem indeksu.

Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.

Egzamin z logiki, 04/09/2000

1. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

   Mówimy, że funkcja \(F:\omega\to\omega\) jest definiowalna, gdy istnieje formuła \(\varphi(x,y)\) nad sygnaturą arytmetyki taka, że każdego wartościowania \(v:X\to\omega\) zachodzi

   \(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=F(v(x)).\)

   Udowodnić, że jeśli funkcja \(F:\omega\to\omega\) jest definiowalna, to jest też definiowalna funkcja \(G:\omega\to\omega\) dana wzorem

   \(G(n)=\begin{cases}0&\text{gdy $n=0,$}\\ F(G(n-1))&\text{gdy $n>0.$}\end{cases}\)

2. Niech \(\mathcal{A}\) będzie klasą algebr nad pewną algebraiczną sygnaturą \(\Sigma.\) Niech \(Spec(\mathcal{A})\) oznacza, tak jak niegdyś na kolokwium, spektrum \(\mathcal{A},\) czyli zbiór \(\{ n\in\omega~/~\text{istnieje $\mathbb{A}\in\mathcal{A}$ takie, \.{z}e $|A|=n.$}\}.\)\(\mathbb{A}\in\mathcal{A}\) takie, że \(|A|=n.\)

   Udowodnić, że jeśli \(\mathcal{A}\) jest rozmaitością algebr, to \(Spec(\mathcal{A})\) jest zamknięte na mnożenie: jeśli \(m,n\in Spec(\mathcal{A}),\) to \(m\cdot n\in Spec(\mathcal{A}).\)

   Podać przykład takiej klasy algebr \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (która też jest do wyboru), która jest definiowalna, ale jej spektrum nie jest zamknięte na mnożenie.

3. Niech \(\Sigma\) będzie sygnaturą algebraiczną, składającą się z jednego symbolu \(f\in\Sigma^{F}_{2}.\) Rozpatrujemy algebrę \(\mathbb{E}=\langle\omega,f^{\mathbb{E}}\rangle,\) gdzie

   \(f(x,y)=\begin{cases}x^{{2\cdot y}}&\text{gdy $x\neq 0$ lub $y\neq 0$,}\\ 0&\text{gdy $x=0$ i $y=0$.}\end{cases}\).

   Napisać taką formułę pierwszego rzędu \(\varphi(x)\) nad \(\Sigma,\) z jedną zmienną wolną \(x\), która definiuje liczbę \(1,\) t.j., taką, że dla każdego wartościowania \(v:X\to\omega\) zachodzi \(\mathbb{E}\models\varphi[v]\) wtw \(v(x)=1.\)

4. Niech dany będzie niesprzeczny, skończony zbiór zdań \(\Delta\) nad pewną ustaloną i również skończoną sygnaturą \(\Sigma.\) Wykazać, że istnieje zbiór \(\Delta _{0}\subseteq\Delta\) taki, że \(\Delta _{0}\models\Delta,\) a ponadto zdania w \(\Delta _{0}\) są niezależne: dla każdego \(\varphi\in\Delta _{0}\) mamy \(\Delta _{0}\setminus\{\varphi\}\not\models\varphi.\)
5. Podać charakteryzację zbioru wszystkich liczb kardynalnych (mocy) \(\mathfrak{n}\) takich, że zachodzi następująca własność:

   Dla każdej sygnatury \(\Sigma\) i każdej klasy \(\mathcal{A}\) struktur nad \(\Sigma,\) jeśli klasa \(\mathcal{A}\) jest aksjomatyzowalna, to jest też aksjomatyzowalna podklasa \(\mathcal{A}\), składająca się ze struktur mocy nie większej niż \(\mathfrak{n}.\)

6. Równość \(s=t\) nad sygnaturą algebraiczną \(\Sigma\) nazywamy dziwną, gdy \(FV(s)\cap FV(t)=\emptyset,\) a ponadto żaden z termów \(s,t\) nie jest zmienną.

   Przypuśćmy, że \(E\) jest zbiorem wszystkich równości dziwnych nad \(\Sigma,\) oraz że \(\mathbb{A}\) jest algebrą nad \(\Sigma\) taką, że \(\mathbb{A}\models E.\) Udowodnić, że dla każdego \(n\in\omega\) i każdego \(f\in\Sigma^{F}_{n},\) \(f^{\mathbb{A}}\) jest funkcją stałą. Czy z powyższych założeń wynika też, że \(|A|=1?\)

7. Niech \(\varphi\) będzie zdaniem

   \(\bigl(\forall x\, f(a_{1}(x),a_{2}(x))=x\bigr)\land\bigl(\forall x\forall y\, a_{1}(f(x,y))=x\land a_{2}(f(x,y))=y\bigr).\)

   Czy \(\varphi\) ma model o co najmniej dwóch elementach?

8. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która nie zawiera dwóch klas abstrakcji równej mocy, nie jest aksjomatyzowalna.
9. Niech \(\mathbb{B}\) będzie wolną algebrą Boole'a (t.j., algebrą wolną w klasie wszystkich algebr Boole'a) ze zbiorem wolnych generatorów \(G\) o mocy \(\mathfrak{c}\). Jakiej mocy jest zbiór wszystkich podalgebr \(\mathbb{B}?\)
10. Niech sygnatura algebraiczna \(\Sigma\) zawiera wyłącznie jeden symbol \(f\) operacji jedoargumentowej. Zakładamy, że \(3\)-elementowa algebra \(\mathbb{A}\) nad \(\Sigma\) ma dokładnie dwie kongruencje. Udowodnić, że istnieje pojedynczy element \(x\in A\) taki, który generuje całą algebrę \(\mathbb{A},\) t.j., \([x]=\mathbb{A}.\)

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.

Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 7 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.

Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.

Egzamin poprawkowy z Logiki dla Informatyków, 2010

Zad. 1 (3 punkty)

Rozważamy skończone grafy \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\).

Napisać zdanie \(\varphi\) logiki egzystencjalnej drugiego rzędu (tzn. postaci \(\exists R_{1}\ldots\exists R_{k}\psi(R_{1},\ldots,R_{k}),\) w którym \(\psi\) jest zdaniem pierwszego rzędu) takie, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 2 (3 punkty)

Pokazać, że żadne zdanie \(\varphi\) logiki pierwszego rzędu nie ma tej własności, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 3 (3 punkty)

Niech wyrażenie \(E\) algebry relacyjnej ma taką właściwość, że żadne podwyrażenie \(E\) nie ma więcej niż \(k\) kolumn. Pokazać, że istnieje algorytm obliczający wartość \([\![E]\!]\) w bazie strukturze \(\mathfrak{A}\), który działa w czasie \(O(n^{k}\log n),\) gdzie \(n\) to liczność dziedziny aktywnej \(\mathfrak{A}\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z \(\mathfrak{A}\) są przekazywane do algorytmu właśnie w takich tablicach: relacja o \(l\) kolumnach jest reprezentowana przez \(l\) tablic, a dane zajmują początkowe indeksy.

Zad. 4 (3 punkty)

Czy następująca formuła logiki drugiego rzędu jest tautologią dla \(n>1\):
\(\forall E\left[\left(\begin{array}{c}\forall xE(x,x)\land\\ \forall xy(E(x,y)\to E(y,z))\land\\ \forall xyz((E(x,y)\land E(y,z))\to E(x,z)))\end{array}\right)\to\forall x_{1}\dots x_{n}\ \bigvee _{{0\leq i< j\leq n}}E(x_{i},x_{j}))\right]\) \(\to\) \((\exists y_{1}\ldots y_{{n-1}}\forall z\bigvee _{{i=1}}^{{n-1}}y_{i}=z)\)

Zad. 5 (1.5 punkta)

Odpowiedz TAK lub NIE na wybrane trzy spośród poniższych pytań. Każda poprawna odpowiedź daje \(0.5\) punkta, każda niepoprawna \(-0.5\) punkta. W razie udzielenia odpowiedzi na więcej pytań, do wyniku zaliczymy trzy najgorsze z nich. Odpowiedzi proszę pisać na tej kartce!

• Czy teoria pierwszego rzędu ciała liczb zespolonych \(\mathfrak{C}=\langle\mathbb{C},+,\cdot,0,1\rangle\) jest rozstrzygalna?
• Czy dla każdego zbioru zdań \(\Gamma\) istnieje minimalny ze względu na zawieranie podzbiór \(\Gamma^{{\prime}}\subseteq\Gamma\) spełniający \(\Gamma^{{\prime}}\models\Gamma\)?
• Czy problem SAT dla zdaniowej logiki trójwartościowej Bochvara jest NP-zupełny?
• Czy formuła \(p\lor(q\to\lnot p)\) jest tautologią zdaniowej logiki intuicjonistycznej?

Egzamin poprawkowy z Logiki dla Informatyków, 2010 popr

Zad. 1 (3 punkty)

Rozważamy skończone grafy \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\).

Napisać zdanie \(\varphi\) logiki drugiego rzędu postaci \(\exists R_{1}\ldots\exists R_{k}\psi(R_{1},\ldots,R_{k}),\) w którym \(\psi\) jest zdaniem pierwszego rzędu takie, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 2 (3 punkty)

Pokazać, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 3 (3 punkty)

Niech \(k\in\mathbb{N}\) będzie stałą. Wykazać, że jeśli \(E\) jest wyrażeniem algebry relacyjnej i maksymalna liczba kolumn w podwyrażeniach \(E\) wynosi \(k\), to istnieje algorytm obliczający wartość \([\![E]\!]\) w każdej strukturze \(\mathfrak{A}\) i działający w czasie \(O(n^{k}\log n),\) gdzie \(n\) to liczność dziedziny aktywnej \(\mathfrak{A}\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z \(\mathfrak{A}\) są przekazywane do algorytmu właśnie w takich tablicach: relacja o \(l\) kolumnach jest reprezentowana przez \(l\) tablic, a dane zajmują początkowe indeksy. Wynik obliczenia zwraca się analogicznie.

Zad. 4 (3 punkty)

Rozważamy skończone drzewa binarne \(\mathfrak{T}\) (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.

Udowodnić, że dla każdego naturalnego \(n\) istnieje zdanie \(\varphi _{n}\) logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego \(\mathfrak{T}\) zachodzi równoważność: \(\mathfrak{T}\models\varphi _{n}\) wtw \(\mathfrak{T}\) jest pełnym drzewem binarnym o głębokości \(n\).

Zad. 5 (3 punkty)

Sygnatura składa się z dwuargumentowego symbolu funkcyjnego \(\circ\), jednoargumentowego symbolu funkcyjnego \(inv\) i symbolu stałej \(id\). Model \(\mathfrak{F}\) (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji \(f:A\to A\) dla pewnego zbioru \(A,\) a operacje mają następujące interpretacje: \(\circ^{\mathfrak{F}}\) to operacja składania funkcji, \(inv^{\mathfrak{F}}\) to operacja brania funkcji odwrotnej, a \(id^{\mathfrak{F}}\) to fukcja indentycznościowa z \(A\) w \(A\).

Udowodnić, że nie istnieje zbiór \(\Gamma\) zdań logiki pierwszego rzędu taki, że \(\mathfrak{B}\models\Gamma\) wtedy i tylko wtedy, gdy \(\mathfrak{B}\) jest izomorficzny do pewnej grupy bijekcji.

egzamin

1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}},1^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2}\) oraz \(1\in\Sigma^{F}_{0},\) przy czym dla wszystkich \(m,n\in\omega\)

   \(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$,}\)\(m\) i \(n\),

   zaś \(1^{\mathbb{A}}\) to zwykła jedynka.

   Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być kwadratem liczby pierwszej”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest kwadratem liczby pierwszej.}\)\(v(x)\) jest kwadratem liczby pierwszej.

2. Niech \(\mathbb{X}=\langle\omega,+^{\mathbb{X}}, beta^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(0,1\in\Sigma^{F}_{0}\) i \(+,\beta\in\Sigma^{F}_{2},\) przy czym dla każdych \(t,p\in\omega\)

   \(\beta^{\mathbb{X}}(t,p)=\text{$\beta$}(t,p),\)

   gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(+^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}\) to zwykłe dodawanie, 0 i 1.

   Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą mnożenie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ v(x)*v(y)=v(z).\)

3. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z dwóch symboli \(S\in\Sigma^{F}_{1}\) i \(\beta\in\Sigma^{F}_{2},\) przy czym dla każdych \(n,t,p\in\omega\)

   \(\displaystyle S^{\mathbb{Y}}(n) =n+1\) ⁢ S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p) =\text{$\beta$}(t,p),\)\(\beta\) t p ⁢ β Y t p = ⁢ β t p

   gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu.

   Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)

4. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)
5. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol relacyjny \(A.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{A}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},A\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(A\subseteq R\) jest dowolny.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{A}\models\varphi\) wtw \(A\) jest zbiorem domkniętym.

6. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

   Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.

7. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma model nieskończony, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
8. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

   Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.

9. Niech \(\varphi\) będzie zdaniem

   \(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)

   oraz niech \(\psi\) będzie zdaniem

   \(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)

   Czy \(\{\psi\}\models\varphi?\)

10. Rozważmy algebrę \(\mathbb{A}=\langle\omega,f^{\mathbb{A}},\rangle,\) gdzie \(f\in\Sigma^{F}_{2}\) oraz

    \(f^{\mathbb{A}}(m,n)=m\;\;(\textrm{mod}n)=\text{reszta z dzielenia $m$ przez $n$},\)\(m\) przez \(n\)

    przy czym przyjmujemy, że \(m\;\;(\textrm{mod}0)=m\) dla każdego \(m.\)
    Udowodnić, że w tej algebrze są tylko dwie kongruencje.
    [Szkic dowodu: Niech \(\sim\) będzie kongruencją.
    (*) Jeśli \(m\sim n\) dla pewnych \(0< m< n,\) to wtedy \(m=m\;\;(\textrm{mod}n)\sim n\;\;(\textrm{mod}n)=0,\) więc \(m,n\) są kongruentne z \(0.\)
    (**) Jeśli \(m\sim 0\) dla pewnego \(m>0,\) to dla każdego \(0< i< m\) mamy \(i=(m+i)\;\;(\textrm{mod}m)\sim m+i\;\;(\textrm{mod}0)=m+i,\) więc \(i\sim 0\) na mocy (*).
    (***) Jeśli \(m\sim 0\) dla pewnego \(m>0,\) to dla każdego \(n>m\) mamy \(n=n\;\;(\textrm{mod}0)\sim n\;\;(\textrm{mod}m)< m< n,\) więc \(n\sim 0\) na mocy (*).
    (****) Jeśli teraz \(m\sim n\) dla pewnych \(m\neq n,\) to albo jedno z \(m,n\) jest zerem i na mocy (**) i (***) wszystkie liczby są kongruentne z \(0,\) albo \(m,n\) są niezerowe, ale wtedy na mocy (*) \(m\sim 0\) i znowu jesteśmy w przypadku poprzednim.
    Szkoda by mi było wyrzucić to zadanie, ale chyba jest za trudne.]

11. Opisać wszystkie kongruencje grupy \(\mathbb{Z}_{4}.\)
12. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
13. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

    Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji P\(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)

14. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.
Wszystkie zadania są oceniane w skali 0-1-2 punkty. Na piątkę wystarcza 7 punktów, na czwórkę 5 punktów, a na trójkę 4 punkty. Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpianej imieniem, nazwiskiem i numerem indeksu.
Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.

Egzamin z logiki, 13/06/2001

1. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego \(f.\) Czy klasa wszystkich algebr \(\mathbb{A}\) nad \(\Sigma\) takich, że \(f^{\mathbb{A}}\) jest bijekcją, jest rozmaitością algebr?
2. Niech \(\mathbb{Z}=\langle Z,+^{\mathbb{Z}},*^{\mathbb{Z}},-^{{\mathbb{Z}}},0^{\mathbb{Z}},1^{\mathbb{Z}}\rangle\) będzie zwykłym pierścieniem liczb całkowitych, oraz niech \(\mathcal{Z}\) będzie najmniejszą rozmaitością algebr zawierającą \(\mathbb{Z}.\) W jaki sposób należy określić operacje w zbiorze \(\mathbb{Z}[X]\) wielomianów jednej zmiennej \(X\) nad \(\mathbb{Z},\) aby tak otrzymana algebra była wolna w \(\mathcal{Z}\) nad pewnym jednoelementowym zbiorem wolnych generatorów? (Wystarczy podać jeden sposób.)
3. Niech \(\mathbb{Q}=\langle Q,+^{\mathbb{Q}},*^{\mathbb{Q}},0^{\mathbb{Q}},1^{\mathbb{Q}}\rangle\) będzie pierścieniem liczb wymiernych, przy czym wszystkie operacje i stałe mają swoje zwykłe znaczenie. Udowodnić, że jeśli \(h:\mathbb{Q}\to\mathbb{Q}\) jest homomorfizmem, to \(h=\mathrm{id}.\)
4. Niech \(\varphi _{1},\varphi _{2},\dots\) oraz \(\psi\) będą zdaniami na pewną ustaloną sygnaturą. Niech \(T\) będzie zbiorem zdań

   \(\{\varphi _{2}\to\varphi _{1},\varphi _{3}\to(\varphi _{1}\land\varphi _{2}),\varphi _{4}\to(\varphi _{1}\land\varphi _{2}\land\varphi _{3}),\dots\}.\)

   Czy musi istnieć \(n\) takie, że dla każdego \(\psi\), \(T\models\psi\) implikuje \(\varphi _{n}\models\psi\)?

5. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów, skończonych i nieskończonych, które zawierają cykl. Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
6. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

   Napisać formułę \(\varphi(x,y)\) nad sygnaturą arytmetyki definiującą funkcję \(y=\lfloor\log _{2}x\rfloor,\) tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor\log _{2}v(x)\rfloor.\)

7. Niech \(\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,\) gdzie \(+\in\Sigma^{F}_{2}\), a \(+^{{\mathbb{Z}_{n}}}\) jest operacją dodawania modulo \(n.\)

   Ile jest różnych funkcji dwóch argumentów \(x\) i \(y\), definiowalnych za pomocą termów \(t(x,y)\) w algebrze \(\mathbb{Z}_{n}?\)

8. Niech \(FINSAT_{\Sigma}\) będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą \(\Sigma,\) które są spełnialne w pewnej skończonej strukturze nad \(\Sigma.\)

   Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.

9. Niech \(\mathbb{A}\) będzie algebrą, której krata kongruencji ma następującą postać:

   \(\xymatrix{&*+{A\times A}&\\ *+{r_{1}}\ar[ur]&&*+{r_{2}}\ar[ul]\\ &*+{\mathrm{id}_{A}}\ar[ul]\ar[ur]}\) \xymatrix Align Align \ar Align Align \ar Align \ar \ar

   Udowodnić, że algebra \(\mathbb{A}/r_{1}\) ma tylko dwie kongruencje: relację totalną i identyczność.

10. Niech \(\mathbb{F}=\langle\omega^{\omega},\circ,\mathrm{id}\rangle\) będzie algebrą, w której \(\omega^{\omega}\) to zbiór wszystkich funkcji z liczb naturalnych w liczby naturalne, \(\circ\) to operacja składania funkcji (dla przypomnienia: \((f\circ g)(x)=f(g(x))\)), zaś \(\mathrm{id}\) to funkcja identycznościowa.

    Udowodnić, że

    \(\mathbb{F}\models\forall f([\exists g\, g\circ f=\mathrm{id}]\to[\forall g_{1}\forall g_{2}\,((f\circ g_{1}=f\circ g_{2})\to g_{1}=g_{2})]).\)

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 8 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, która odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.

Egzamin z logiki dla MSUI, 27/06/2001

1. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura jest do wyboru i może zależeć od \(k\)) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)
2. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów (nieskierowanych), skończonych i nieskończonych, których wszystkie składowe spójne są skończone. Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
3. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)
   Napisać formułę \(\varphi(x,y,z)\) nad sygnaturą arytmetyki definiującą funkcję \(y=\lfloor\sqrt[z]{x}\rfloor,\) tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor(v(x))^{{\frac{1}{v(z)}}}\rfloor.\)

4. Niech \(\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,\) gdzie \(+\in\Sigma^{F}_{2}\), a \(+^{{\mathbb{Z}_{n}}}\) jest operacją dodawania modulo \(n.\)

   Ile jest różnych funkcji dwóch argumentów \(x\) i \(y\), definiowalnych za pomocą termów \(t(x,y)\) w algebrze \(\mathbb{Z}_{n}?\)

5. Niech \(FINSAT_{\Sigma}\) będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą \(\Sigma,\) które są spełnialne w pewnej skończonej strukturze nad \(\Sigma.\)

   Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.

6. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E.\)

   Niech \(\varphi\) będzie zdaniem \(\forall x\forall y\forall z[R(x,y)\land R(x,z))\to y=z],\) zaś \(\psi\) zdaniem \(\forall x\exists y[R(x,y)\land\forall z\,(R(x,z)\to y=z)].\) Rozstrzygnąć, czy \(\varphi\models\psi\) oraz czy \(\psi\models\varphi.\)

Czas na rozwiązanie zadań to 2 godziny 30 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Z zadań należy wybrać dowolne trzy i je rozwiązać. Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 7 punktów (w tym 3 zadania na co najmniej 2 punkty), na czwórkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 3 punktów (w tym co najmniej 1 zadanie na co najmniej 2 punkty). Każdej osobie, która odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze trzy spośród nich.
Można jednak oddać także czwarte zadanie, specjalnie oznaczone jako dodatkowe, którego wynik 3 pkt. będzie umożliwiał dostanie szóstki (oczywiście tylko tym, którzy z pozostałych trzech zadań dostali piątkę).
Każde zadanie proszę napisać na osobnej, podpisanej kartce.

Egzamin ze wstępu do logiki, ZSI, 2005/2006.

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}\ \ \ \ \)

Egzamin z logiki, 06/09/2001

1. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego \(f.\) Udowodnić, że każda algebra \(\mathbb{A}\) sygnatury \(\Sigma\) o więcej niż jednym elemencie ma nietrywialny (tzn. różny od identyczności) homomorfizm \(h:\mathbb{A}\to\mathbb{A}\).
2. Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) sygnatury \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\text{istnieje struktura $\mathbb{A}$ nad $\Sigma$ t.że $|A|=n$ i $\mathbb{A}\models\varphi$}\}.\)\(\mathbb{A}\) nad \(\Sigma\) t.że \(|A|=n\) i \(\mathbb{A}\models\varphi\)}.

   Udowodnić, że zbiór \(\{ m+n~/~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).

3. 1. Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dwoma różnymi niepustymi zbiorami wolnych generatorów \(G_{1},G_{2}\) takimi, że \(G_{1}\cap G_{2}=\emptyset.\)
   2. Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dokładnie jednym niepustym zbiorem wolnych generatorów.
4. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów, skończonych i nieskończonych, które są \(n\)-dzielne, dla pewnego \(n\in\mathbb{N}.\) Graf \(\mathbb{G}\) jest \(n\)-dzielny jeśli istnieje podział jego zbioru wierzchołków \(G\) na niepuste i rozłączne podzbiory \(G_{1},\dots,G_{n}\) tak, że każda z podstruktur indukowanych \(\mathbb{G}_{{|G_{i}}}\) nie zawiera żadnych krawędzi. Przykładowo, graf pełny o \(n\) wierzchołkach \(\mathbb{K}_{n}\) jest \(n\)-dzielny, ale nie \(m\)-dzielny dla \(m< n.\)

   Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.

5. Niech \(\mathbb{W}=\langle\{ 0,1\}^{+},\circ^{\mathbb{W}},0^{\mathbb{W}},1^{\mathbb{W}},r^{\mathbb{W}}\rangle\) będzie strukturą, w której \(\{ 0,1\}^{+}\) to zbiór wszystkich niepustych skończonych ciągów zerojedynkowych, \(\circ^{\mathbb{W}}\) to operacja konkatenacji ciągów (\(\langle x_{1}\dots x_{n}\rangle\circ^{\mathbb{W}}\langle y_{1}\dots y_{m}\rangle=\langle x_{1}\dots x_{n}y_{1}\dots y_{m}\rangle,\) \(0^{\mathbb{W}}\) i \(1^{\mathbb{W}}\) to ciągi jednoelementowe \(\langle 0\rangle\) i \(\langle 1\rangle\), zaś \(r^{\mathbb{W}}\) jest relacją jednoargumentową określoną przez \(r^{\mathbb{W}}(w)\) wtw. gdy każdy prefiks \(w\) zawiera nie więcej jedynek niż zer, a w całym ciągu \(w\) ilość jednek i zer jest jednakowa.

   Udowodnić, że
   \(\mathbb{W}\models\forall x([\exists y_{1}\exists y_{2}\exists y_{3}\, x=(y_{1}\circ y_{2})\circ y_{3}]\to\\ .\)

6. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

   Napisać formułę \(\varphi(x)\) nad sygnaturą arytmetyki definiującą relację ,,\(x\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym”, tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\) zachodzi równoważność \(\mathbb{N}\models\varphi[v]\) wtw \(v(x)\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym.

7. Niech \(\mathbb{Z}_{{8}}=\langle\{ 0,1,\dots,7\},S^{{\mathbb{Z}_{{8}}}},0^{{\mathbb{Z}_{{8}}}}\rangle,\) gdzie \(S^{{\mathbb{Z}_{{8}}}}\) jest operacją następnika modulo \(8,\) zaś \(0^{{\mathbb{Z}_{{8}}}}\) to \(0.\)

   Proszę opisać wszystkie kongruencje algebry \(\mathbb{Z}_{{8}}.\)

8. Niech sygnatura algebraiczna \(\Sigma\) składa się z symboli stałych \(a,b,c\) i nie zawiera innych symboli. Niech \(\mathbb{A}\) i \(\mathbb{B}\) będą dwuelementowymi algebrami sygnatury \(\Sigma\) takimi, że \(a^{\mathbb{A}}=b^{\mathbb{A}}\neq c^{\mathbb{A}},\) zaś \(a^{\mathbb{B}}\neq b^{\mathbb{B}}=c^{\mathbb{B}}.\) Udowodnić, że każda rozmaitość algebr nad \(\Sigma\) zawierająca jednocześnie \(\mathbb{A}\) i \(\mathbb{B}\) zawiera wszystkie algebry nad \(\Sigma.\)
9. Niech \(c,d\) będą dwoma symbolami pewnej sygnatury algebraicznej \(\Sigma,\) która poza tym może zawierać także inne symbole funkcyjne, o różnych ilościach argumentów. Zbiór \(E\) równości nad \(\Sigma\) nazwiemy symetrycznym, gdy każda równość \(t=s\) należy do \(E\) wtedy i tylo wtedy, gdy równość otrzymana z \(t=s\) przez (jednoczesną) zamianę wystąpień \(c\) na \(d\) oraz \(d\) na \(c,\) też należy do \(E.\)

   Udowodnić, że jeśli zbiór równości \(E\) nad \(\Sigma\) jest symetryczny, to zbiór\(\{ t=s~/~E\models t=s\}\) też jest symetryczny.

10. PDF wygląda inaczej

    Rozstrzygnąć, czy \(\{\varphi _{1},\varphi _{2},\varphi _{3}\}\models\{\psi _{1},\psi _{2}\}.\)

    \(\displaystyle \varphi _{1}: ~~~\forall x_{1}\forall x_{2}\, E(x_{1},x_{2})\to E(x_{2},x_{1})\) φ 1 : → ∀ ⁢ x 1 ∀ ⁢ x 2 E x 1 x 2 ⁢ E x 2 x 1 \(\displaystyle \varphi _{2}: ~~~\forall x\,\lnot E(x,x)\) φ 2 : ∀ ⁢ x ¬ E x x \(\displaystyle \varphi _{3}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\exists x_{4}\exists x_{5}\,\bigwedge _{{1\leq i< j\leq 5}}x_{i}\neq x_{j}\) φ 3 : ≠ ∃ ⁢ x 1 ∃ ⁢ x 2 ∃ ⁢ x 3 ∃ ⁢ x 4 ∃ ⁢ x 5 ⋀ 1 ≤ i < j ≤ 5 x i x j \(\displaystyle \psi _{1}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\, E(x_{1},x_{2})\land E(x_{2},x_{3})\land E(x_{3},x_{1})\) ψ 1 : ∧ ∃ ⁢ x 1 ∃ ⁢ x 2 ∃ ⁢ x 3 E x 1 x 2 ⁢ E x 2 x 3 ⁢ E x 3 x 1 \(\displaystyle \psi _{2}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\,\lnot(E(x_{1},x_{2})\lor E(x_{2},x_{3})\lor E(x_{3},x_{1}))\) ψ 2 : ∃ ⁢ x 1 ∃ ⁢ x 2 ∃ ⁢ x 3 ¬ ∨ ⁢ E x 1 x 2 ⁢ E x 2 x 3 ⁢ E x 3 x 1

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 8 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, która odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.

Kolokwium poprawkowe z logiki, 31/05/2001

1. Skonstruuj przykłady dwóch nieizomorficznych nieskończonych grafów \(\mathbb{A}\) i \(\mathbb{B}\) takich, że istnieją różnowartościowe homomorfizmy grafów \(g:\mathbb{B} \to \mathbb{A}\) i \(\mathbb{A} \cong \mathbb{B}.\)

   Funkcja \(h:A\to\ B\) jest homomorfizmem grafów \(\mathbb{A}\) i \(\mathbb{B},\) gdy dla wszystkich \(a,a^{{\prime}}\in A\), \(\langle a,a^{{\prime}}\rangle\in E^{\mathbb{A}}\) implikuje \(\langle h(a),h(a^{{\prime}})\rangle\in E^{\mathbb{B}}\).

2. Niech \(\varphi _{0}\equiv\exists x\exists y(x\neq y),\)
   \(\varphi _{1}\equiv\forall x(\lnot E(x,x))\),
   \(\varphi _{2}\equiv\forall x\forall y(E(x,y)\to E(y,x)),\)
   \(\varphi _{3}\equiv\forall x\forall y((x\neq y)\to\exists z(E(x,z)\land E(y,z))).\)
   Udowodnić, że \(\{\varphi _{0},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)
3. Klasa \(\mathcal{A}\) jest złożona z wszystkich nieskierowanych grafów (skończonych lub nie) \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) (nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\)) o następującej własności: każda składowa spójna \(\mathbb{A}\) jest skończona.

   Udowodnić, że klasa \(\mathcal{A}\) nie jest aksjomatyzowalna, tj., że nie istnieje zbiór \(T\) zdań taki, że \(\mathcal{A}=Mod(T).\)

4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał z porządkiem, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci

   \(\mathbb{A}=\langle R,+^{\mathbb{A}},*^{\mathbb{A}},-^{\mathbb{A}},0^{\mathbb{A}},1^{\mathbb{A}},\leq^{\mathbb{A}},f^{\mathbb{A}}\rangle,\)

   gdzie \(R\) to zbiór liczb rzeczywistych, \(+,*,-,0,1,\leq\) mają zwykłe interpretacje (takie, jak w liczbach rzeczywistych), zaś \(f^{\mathbb{A}}:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{A}\models\varphi\) wtw \(f^{\mathbb{A}}\) jest funkcją okresową o najmniejszym okresie \(1.\)

Z powyższych zadań należy wybrać i rozwiązać dwa. Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Wykryte przypadki ściągania (także na etapie sprawdzania prac) będziemy karać.
Zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 4 punktów. Osobie, kóra odda więcej niż dwa zadania, do wyniku zostaną policzone najsłabsze dwa sposród nich, czyli nie opłaca się oddawać więcej niż dwóch zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem, grupą (nazwisko prowadzącego i termin zajęć) i adresem poczty elektronicznej, na który ma być wysłany wynik kolokwium.

KP_PDF - Kolokwium poprawkowe z logiki, 31/05/2001

1. Skonstruuj przykłady dwóch nieizomorficznych nieskończonych grafów \(\mathbb{A}\) i \(\mathbb{B}\) takich, że istnieją różnowartościowe homomorfizmy grafów \(g:\mathbb{B}\to\mathbb{A}\) i \(h:\mathbb{A}\to\mathbb{B}.\)

   Funkcja \(h:A\to\ B\) jest homomorfizmem grafów \(\mathbb{A}\) i \(\mathbb{B},\) gdy dla wszystkich \(a,a^{{\prime}}\in A\), \(\langle a,a^{{\prime}}\rangle\in E^{\mathbb{A}}\) implikuje \(\langle h(a),h(a^{{\prime}})\rangle\in E^{\mathbb{B}}\).

2. Niech \(\varphi _{0}\equiv\exists x\exists y(x\neq y),\)\(\varphi _{1}\equiv\forall x(\lnot E(x,x))\),\(\varphi _{2}\equiv\forall x\forall y((x\neq y)\to\exists z(E(x,z)\land E(y,z))).\)

   Jaka jest najmniejsza możliwa liczba krawędzi w grafie \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle,\) który jest modelem zbioru \(\{\varphi _{0},\varphi _{1},\varphi _{2}\}?\)

3. Klasa \(\mathcal{A}\) jest złożona z wszystkich częściowych porządków o tej własności, że żaden zawarty w nich skończony łańcuch nie jest maksymalny.

   Skonstruować zbiór zdań \(T\) nad zwykłą sygnaturą porządków \(\Sigma,\) taki, że \(\mathcal{A}=Mod(T).\)

4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał z porządkiem, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci

   \(\mathbb{A}=\langle R,+^{\mathbb{A}},*^{\mathbb{A}},-^{\mathbb{A}},0^{\mathbb{A}},1^{\mathbb{A}},\leq^{\mathbb{A}},f^{\mathbb{A}}\rangle,\)

   gdzie \(R\) to zbiór liczb rzeczywistych, symbole \(+,*,-,0,1,\leq\) mają zwykłe interpretacje (takie, jak w liczbach rzeczywistych), zaś \(f^{\mathbb{A}}:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{A}\models\varphi\) wtw \(f^{\mathbb{A}}\) jest funkcją okresową o najmniejszym dodatnim okresie \(1.\)

Z powyższych zadań należy wybrać i rozwiązać dwa. Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Wykryte przypadki ściągania (także na etapie sprawdzania prac) będziemy karać.
Zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 4 punktów. Osobie, kóra odda więcej niż dwa zadania, do wyniku zostaną policzone najsłabsze dwa sposród nich, czyli nie opłaca się oddawać więcej niż dwóch zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem, grupą (nazwisko prowadzącego i termin zajęć).

Kolokwium poprawkowe z logiki, 31/05/200

1. Udowodnij, że istnieją nieskończone nieizomorficzne grafy \(\mathbb{A}\not\cong\mathbb{B}\) takie, że istnieją przekształcenia \(h:\mathbb{A}\to\mathbb{B}\) i \(g:\mathbb{B}\to\mathbb{A},\) które są różnowartościowymi homomorfizmami grafów.
2. Niech \(\varphi _{0}\equiv\exists x\exists yx\neq y,\) \(\varphi _{1}\equiv\forall x\lnot E(x,x)\), \(\varphi _{2}\equiv\forall x\forall y(x\neq y)\to\exists z(E(x,z)\land E(z,y)).\)

   Czy \(\{\varphi _{)},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)

3. Udowodnij, że klasa \(\mathcal{A}\) złożona z wszystkich (być może nieskończonych) grafów regularnych, tj., grafów których wszystkie wierzchołki mają ten sam stopień, nie jest definiowalna.
4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{f}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},f\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(f:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{f}\models\varphi\) wtw \(f\) jest funkcją różniczkowalą w \(0.\)

Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu (także na etapie sprawdzania prac) będziemy karać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 5 punktów (w tym 2 zadania na co najmniej 2 punkty). Każdej osobie, kóra odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż trzech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i adresem poczty elektronicznej, pod który ma być wysłany wynik.

Kolokwium z logiki, 19/04/2001

1. Udowodnij, że jeżeli przekształcenia \(h:\mathbb{A}\to\mathbb{B}\) i \(g:\mathbb{B}\to\mathbb{A}\) są różnowartościowymi homomorfizmami grafów, to \(\mathbb{A}\cong\mathbb{B}.\)
2. Niech \(\varphi _{0}\equiv\exists x\exists yx\neq y,\) \(\varphi _{1}\equiv\forall x\lnot E(x,x)\), \(\varphi _{2}\equiv\forall x\forall y(E(x,y)\to E(y,x)),\) \(\varphi _{3}\equiv\forall x\forall y(x\neq y)\to\exists z(E(x,z)\land E(y,z)).\)

   Udowodnić, że \(\{\varphi _{)},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)

3. Udowodnij, że klasa \(\mathcal{A}\) złożona z wszystkich (być może nieskończonych) grafów regularnych, tj., grafów których wszystkie wierzchołki mają ten sam stopień, nie jest definiowalna.
4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{f}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},f\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(f:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{f}\models\varphi\) wtw \(f\) jest funkcją różniczkowalą w \(0.\)

Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu (także na etapie sprawdzania prac) będziemy karać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 5 punktów (w tym 2 zadania na co najmniej 2 punkty). Każdej osobie, kóra odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż trzech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i adresem poczty elektronicznej, pod który ma być wysłany wynik.

Zadania przygotowawcze z logiki Wersja 2.

O zadaniach. Zadania są podzielone na kilka grup. Niektóre zadania są dosyć trudne. Pewne zadania powtarzają się w kilku grupach, aby zachęcić studentów do rozwiązania ich różnymi metodami.
Przy niektórych zadaniach (z działów ,,Tw. o zwartości” i ,,Tw. Skolema-Löwenheima”) należy się posłużyć pełną wersją twierdzenia Skolema-Löwenheima poniżej, która zostanie podana na najbliższym wykładzie:
Jeśli \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma\) który ma nieskończony model, to \(\Delta\) ma model dowolnej mocy \(\mathfrak{m}\geq|\Sigma|.\)

Formalizowanie zadanych własności. Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\) Standardowy model arytmetyki to struktura \(\mathbb{N}=\langle\omega,*^{\mathbb{N}},+^{\mathbb{N}},0^{\mathbb{N}},1^{\mathbb{N}},\leq^{\mathbb{N}}\rangle.\)

1. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)
2. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)
3. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)
4. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n~/~n\in\mathbb{N}\ \text{i $n$ jest liczb"a z"lo"ron"a}\}.\)\(n\) jest liczbą złożoną}.
5. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.\)
6. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n\) nieizomorficznych modeli mocy \(n.\)
7. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(2^{n}\) nieizomorficznych modeli mocy \(n.\)
8. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n!\) nieizomorficznych modeli mocy \(n.\)
9. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)
10. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n^{k}\) nieizomorficznych modeli mocy \(n.\)
11. Znaleźć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)
12. Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)
13. Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(y\) jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli \(x.\)

Szukanie modeli dla zadanych formuł. W zadaniach ,,Pokazać, że zbiór zdań \(\Delta\) jest niezależny”, należy za każdym razem udowodnić, że dla każdego \(\varphi\in\Delta,\) \(\Delta\setminus\{\varphi\}\not\models\varphi,\) poprzez wskazanie modelu \(\Delta\setminus\{\varphi\},\) który nie jest modelem \(\varphi.\)

1. Pokazać, że zbiór aksjomatów relacji równoważności

   \(\left\{\begin{array}[]{c}\forall x\forall y(Exy\to Eyx)\\ \forall x\ Exx\\ \forall x\forall y\forall z((Exy\land Eyz)\to Exz)\end{array}\right\}\)

   jest niezależny.

2. Pokazać, że zbiór aksjomatów liniowych porządków

   \(\left\{\begin{array}[]{c}\forall x\forall y((x\leq y)\lor(y\leq x))\\ \forall x\forall y((x\leq y\land y\leq x)\to x=y)\\ \forall x\forall y\forall z((x\leq y\land y\leq z)\to x\leq z)\end{array}\right\}\)

   jest niezależny.

3. Pokazać, że zbiór aksjomatów teorii grup (w zapisie multiplikatywnym, nad sygnaturą

   \(\Sigma^{F}_{{2}}=\{*\},\Sigma^{F}_{0}=\{ 1\}\))
   \(\left\{\begin{array}[]{c}\forall x((1*x=x)\land(x*1=x))\\ \forall x\forall y\forall z((x*y)*z=x*(y*z))\\ \forall x\exists y((x*y=1)\land(y*x=1))\end{array}\right\}\)

   jest niezależny.

4. Pokazać, że zdanie \((\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy)\) nie jest tautologią.
5. Pokazać, że zdanie

   \((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\)

   nie jest tautologią. Czy jego negacja ma model skończony?

6. Pokazać, że zdanie \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\) nie jest tautologią. Ile nieizomorficznych modeli skończonych ma to zdanie?

Tw. Fraïssé, gra Ehrenfeuchta.

1. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.
2. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.
3. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest definiowalna.
4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.

Tw. o zwartości.

1. Pokazać, że jeśli klasa \(\mathcal{A}\) struktur nad sygnaturą \(\Sigma\) jest aksjomatyzowalna i jej dopełnienie \(Mod(\Sigma)\setminus\mathcal{A}\) struktur sygnatury \(\Sigma,\) ktore nie nalezą do \(\mathcal{A},\) jest aksjomatyzowalne, to obie klasy są w istocie definiowalne.

   Wskazówka: Założyć, że pierwsza klasa jest aksjomatyzowalna przez \(\Delta\), a druga przez \(\Delta^{{\prime}},\) ale żaden skończony podzbiór \(\Delta\) nie jest aksjomatyzacją \(\mathcal{A}.\) Pokazać, że \(\Delta\cup\Delta^{{\prime}}\) spełnia założenia tw. o zwartości.

2. Pokazać następujące tw. Robinsona: Jeśli \(\Delta,\Delta^{{\prime}}\) są spełnialnymi zbiorami zdań nad pewną sygnaturą \(\Sigma,\) zaś \(\Delta\cup\Delta^{{\prime}}\) nie jest spełnialny, to istnieje zdanie \(\varphi\) takie, że \(\Delta\models\varphi\) oraz \(\Delta^{{\prime}}\models\lnot\varphi.\)

   Wskazówka: Założyć, że dla każdego \(\varphi\) takiego, że \(\Delta\models\varphi\) zachodzi \(\Delta^{{\prime}}\not\models\lnot\varphi.\) Pokazć, że w tej sytuacji \(\Delta^{{\prime}}\cup\{\varphi\}\) jest spełnialny, a stąd, że \(\Delta\cup\Delta^{{\prime}}\) spełnia zalożenia tw. o zwartości.

3. Pokazać, że jeśli \(\Delta\) jest pewnym zbiorem zdań \(\varphi\) takich, że \(Spec(\lnot\varphi)\) jest skończone, oraz \(\Delta\models\psi,\) to także \(Spec(\lnot\psi)\) jest skończone.
4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.
5. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest aksjomatyzowalna.
6. Pokazać, że klasa wszystkich algebr \(\mathbb{A}=\langle A,f^{\mathbb{A}}\rangle,\) gdzie \(f\) jest symbolem jednoragumentowej funkcji, oraz takich, że \(|\vec{f}(A)|< |A|\) nie jest aksjomatyzowalna.
7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.
8. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.

Tw. Skolema-Löwenheima.

1. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=2^{{|A\setminus r^{\mathbb{A}}|}}\) nie jest aksjomatyzowalna.
2. Udowodnić, że klasa wszystkich struktur izomorficznych do struktury postaci \(\mathbb{A}=\langle\mathcal{P}(A),\cup^{\mathbb{A}},\cap^{\mathbb{A}},\subseteq^{\mathbb{A}}\rangle,\) gdzie \(\cup^{\mathbb{A}},\cap^{\mathbb{A}}\) oraz \(\subseteq^{\mathbb{A}}\) są odpowiednio prawdziwymi sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna.
3. Udowodnić następujące tw. Hessenberga: Dla każdej nieskończonej mocy \(\mathfrak{m}\) zachodzi \(\mathfrak{m}^{2}=\mathfrak{m}.\)

   Wskazówka: Napisać zdanie pierwszego rzędu, z którego wynika, że uniwersum modelu jest mocy nie mniejszej niż moc jego kartezjańskiego kwadratu. Pokazać, że zdanie to ma model nieskończony i skorzystać z tw. Skolema-Löwenheima.

zadania_egz

1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2},\) przy czym dla wszystkich \(m,n\in\omega\)

   \(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$.}\)\(m\) i \(n\).

   Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest liczb"a pierwsz"a.}\)\(v(x)\) jest liczbą pierwszą.

2. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}},\leq^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(S\in\Sigma^{F}_{1},\) \(\beta\in\Sigma^{F}_{3}\) oraz \(\leq\in\Sigma^{R}_{2},\) przy czym dla każdych \(n,t,p,i\in\omega\)

   \(\displaystyle S^{\mathbb{Y}}(n) =n+1\) ⁢ S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p,i) =\text{$\beta$}(t,p,i),\)\(\beta\) t p i ⁢ β Y t p i = ⁢ β t p i

   gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(\leq^{\mathbb{Y}}\) to zwykła nierówność.

   Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)

3. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

   Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.

4. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma model nieskończony, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
5. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

   Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.

6. Niech \(\varphi\) będzie zdaniem

   \(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)

   oraz niech \(\psi\) będzie zdaniem

   \(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)

   Czy \(\{\psi\}\models\varphi?\)

7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
8. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

   Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji \(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)

9. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
10. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)

"Naiwna" teoria mnogości

"Naiwna" indukcja

"Naiwne" dowody niewprost

Test 1

Czy zbiór bocianów jest elementem zbioru wszystkich ptaków?

Język logiki zdaniowej

Aksjomatyka Klasycznego Rachunku Zdań

Aksjomatyka Klasycznego Rachunku Zdań

Aksjomaty

Wielu matematyków zgadza się dzisiaj co do tego, że zdania pasujące do poniższych schematów powinny być uznane za prawdziwe:

Definicja 3.1 Aksjomaty klasycznego rachunku zdań

1. \( (\phi \Rightarrow (\psi \Rightarrow \phi)) \) (formuła ta jest nazywana aksjomatem K),
2. \( (\phi \Rightarrow (\nu \Rightarrow \psi)) \Rightarrow ((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \psi) ) \) (formuła ta jest nazywana aksjomatem S),
3. \( (\neg \phi \Rightarrow \psi) \Rightarrow ((\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi) \) (tzw. schemat dowodu niewprost)

Zdania pasujące do powyższych schematów to wszystkie zdania, które można otrzymać, podstawiając w miejsce \( \phi, \nu, \psi \) dowolne formuły.

Reguła dowodzenia

Przyglądnijmy się teraz jak posługujemy się implikacją we wnioskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:
jeśli \( {\phi} \) to \( {\psi} \).
W takim przypadku, jeśli akceptujemy powyższą implikacjię jako zdanie prawdziwe oraz jeśli zdanie \( {\phi} \) jako prawdziwe, to powinniśmy także zaakceptować \( {\psi} \). Przedstawiony sposób wnioskowania nosi nazwę reguły Modus Ponens (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób
\( \frac{\phi \Rightarrow \psi, \phi} {\psi}. \)
Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów o ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych aksjomatów, definiujemy poniżej pojęcie dowodu.

Definicja 3.2

Ciąg formuł \( \phi_0, \dots ,\phi_n \) jest dowodem formuły \( {\psi} \) wtedy i tylko wtedy, gdy:

1. \( \phi_n \) jest formułą \( {\psi} \),
2. dla każdego \( i\leq n \) formuła \( \phi_i \) jest aksjomatem lub istnieją \( j,k < i \) takie, że formuła \( \phi_i \) jest wynikiem zastosowania reguły modus ponens do formuł \( \phi_j, \phi_k \).

W drugim punkcie powyższej definicji, jeśli formuła \( \phi_i \) nie jest aksjomatem (a więc powstaje przez zastosowanie MP), to formuły \( \phi_j,\phi_k \) muszą pasować do przesłanek reguły MP, a więc \( \phi_j \) musi być postaci \( \phi_k \Rightarrow \phi_i \) lub \( \phi_k \) postaci \( \phi_j \Rightarrow \phi_i \).
Definicja 3.3
Formułę nazywamy twierdzeniem klasycznego rachunku zdań jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań 3.1

Przykład

Zastanówmy się na formułą postaci \( \phi \Rightarrow \phi \). Intuicja podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów, użyliśmy nawiasów kwadratowych dla nawiasów, które pochodzą ze schematów.

1. \( [\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow\phi]] \) formuła ta jest aksjomatem zgodnym ze schematem S,
2. \( \phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi] \) aksjomat zgodny ze schematem K,
3. \( (\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi) \) z modus ponens z formuł 1 i 2,
4. \( \phi \Rightarrow [q \Rightarrow \phi] \) aksjomat zgodny ze schematem K,
5. \( (\phi \Rightarrow \phi) \) z modus ponens z formuł 3 i 4.

Podsumowanie

Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za prawdziwe, zdefiniowaliśmy, wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły Modus Ponens. Warto zwrócić uwagę, że pomimo tego, iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.

Uwaga 3.4

Warto przyglądnąć się przyjętym aksjomatom i zastanowić się jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni uznać je za prawdziwe. Pomocne może być interpretowanie formuł postaci \( \phi \Rightarrow (\nu \Rightarrow \psi) \) jako „jeśli prawdziwe jest \( {\phi} \) i prawdziwe jest \( \nu \) to prawdziwe jest \( {\psi} \)”. W kolejnych rozdziałach przekonamy się, że taka interpretacja jest uzasadniona.

Matryca boolowska

Systemy funkcjonalnie pełne

Postacie normalne

Logika intuicjonistyczna

Język rachunku predykatów

Aksjomatyka Rachunku Predykatów

Aksjomatyka Rachunku Predykatów

Rachunek predykatów podobnie jak klasyczny rachunek zdań może być wprowadzony aksjomatycznie. Pierwsza grupa aksjomatów to aksjomaty klasycznego rachunku zdań. Druga dotyczy kwantyfikatora \( \forall \) oraz jego interakcji z implikacją. Przypomnijmy, że kwantyfikator \( \exists \) traktujemy jako pewien skrót zapisu.

Definicja 3.1. Schematy aksjomatów rachunku predykatów

1. (Aksjomaty logiki zdaniowej) Każda formuła pasująca do któregokolwiek z poniższych schematów jest tautologią

(a) \( (\phi \Rightarrow (\psi \Rightarrow \phi)) \)

(b) \( (\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow ((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \psi) ) \)

(c) \( (\neg \phi \Rightarrow \psi) \Rightarrow ((\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi) \)

2. (Aksjomaty dotyczące kwantyfikatora)

(a) Dla dowolnej formuły \( \phi \) oraz termu \( t \) następująca formuła jest aksjomatem \( \forall_x \phi \Rightarrow (\phi [x arrow t]) \) (uwaga na podstawienie)

(b) Dla dowolnej formuły \( \phi \) oraz zmiennej \(\mathrm {x} \), która nie ma wolnych wystąpień w \( \phi \) następująca formuła jest aksjomatem \( \phi \Rightarrow \forall_x \phi \)

(c) Dla dowolnych formuł \( {\phi} \) i \( {\psi} \) aksjomatem jest formuła \( \forall_x(\phi \Rightarrow \psi) \Rightarrow ((\forall_x \phi)\Rightarrow(\forall_x \psi)) \)

Poza tym do aksjomatów dorzucamy również wszystkie generalizacje formuł pasujących do powyższych schematów. Generalizacja formuły jest to ta sama formuła poprzedzona blokiem kwantyfikatorów ogólnych - dla dowolej formuły \( \phi \) oraz dowolnych zmiennych \( x_1,\dots,x_k \) formuła \( \forall_{x_1} \dots \forall_{x_k} \phi \) jest generalizacją \( \phi \).

Podobnie jak w rachunku zdań dowodem formuły \( {\phi} \) nazwiemy ciąg formuł \( \phi_0, \dots, \phi_n \) taki, że \( \phi_n \) jest tym samym napisem co \( {\phi} \) a każda formuła \( \phi_i \) dla \( i < n \) jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły Modus Ponens z Wykładu 2.

Definicja 3.2.

Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.

Przykład 3.3.

Formalne dowody twierdzeń rachunku predykatów są zwykle skomplikowane. Dlatego w rozważanym przykładzie poczynimy kilka uproszczeń. Będziemy się zajmować formułą \( \displaystyle p(t) \Rightarrow \exists_x p(x). \)

Zamiast dowodzić dokładnie powyższą formułę, dowiedziemy podobny fakt, a mianowicie, że jeśli dołączymy do zbioru aksjomatów formułę \( \displaystyle p(t) \), to będziemy w stanie udowodnić \( \displaystyle \exists_x p(x) \). Twierdzenie o dedukcji, które można znaleźć w wykładzie Logika dla informatyków, mówi, że te podejścia są równoważne.

W poniższym dowodzie pominiemy również dowód formuły \( \displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x) \). Formuła ta pasuje do schematu \( \displaystyle \neg \neg \phi \Rightarrow \phi \). Łatwo więc sprawdzić, że formuła \( \displaystyle \neg \neg \phi \Rightarrow \phi \) jest tautologią klasycznego rachunku zdań, a więc -- w myśl twierdzenia Posta (patrz Wykład 2, Twierdzenie 4.4) -- ma dowód. Po zastąpieniu w tym dowodzie zmiennej \( \displaystyle \phi \) formułą \( \displaystyle \forall_x \neg p(x) \), otrzymamy dowód formuły \( \displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x) \).

Przestawiamy uproszczony dowód formuły \( \displaystyle p(t) \Rightarrow \exists_x p(x) \):

1. \( \displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x) \) (patrz komentarz powyżej)
2. \( \displaystyle (\forall_x \neg p(x)) \Rightarrow \neg p(t) \) (aksjomat 2a)
3. \( \displaystyle [(\forall_x \neg p(x)) \Rightarrow \neg p(t)] \Rightarrow ([\neg \neg \forall_x \neg p(x)] \Rightarrow [(\forall_x \neg p(x)) \Rightarrow \neg p(t)]) \) (aksjomat 1a)
4. \( \displaystyle [\neg \neg \forall_x \neg p(x)] \Rightarrow [(\forall_x \neg p(x)) \Rightarrow \neg p(t)] \) (MP z 2 i 3)
5. \( \displaystyle ([\neg \neg \forall_x \neg p(x)] \Rightarrow [(\forall_x \neg p(x)) \Rightarrow \neg p(t)]) \Rightarrow [(\neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x)) \Rightarrow [(\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)]] \) (aksjomat 1b)
6. \( \displaystyle (\neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x)) \Rightarrow [(\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)] \) (MP z 4 i 5)
7. \( \displaystyle (\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t) \) (MP z 6 i 1)
8. \( \displaystyle p(t) \Rightarrow ([\neg \neg \forall_x \neg p(x)]\Rightarrow p(t)) \) (aksjomat 1a)
9. \( \displaystyle p(t) \) (dołączyliśmy tę formułę jako aksjomat)
10. \( \displaystyle [\neg \neg \forall_x \neg p(x)]\Rightarrow p(t) \) (MP z 8 i 9)
11. \( \displaystyle ([\neg \neg \forall_x \neg p(x)]\Rightarrow p(t)) \Rightarrow [((\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)) \Rightarrow \neg \forall_x \neg p(x)] \) (aksjomat 1c)
12. \( \displaystyle (\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)) \Rightarrow \neg \forall_x \neg p(x) \) (MP z 10 i 11)
13. \( \displaystyle \neg \forall_x \neg p(x) \) (MP z 7 i 12)

Ostatnia formuła to dokładnie \( \displaystyle \exists_x p(x) \) po rozpisaniu skrótu \( \displaystyle \exists \).

Przykład teorii w rachunku predykatów

W oparciu o logikę predykatów możemy budować nowe teorie, dokładając inne, tzw. pozalogiczne aksjomaty. W językach wielu teorii pojawia się symbol predykatywny \( =^2 \), mający symbolizować równość. Ponieważ zwykle wymagamy aby te same własności były spełnione dla \( =^2 \), zostały wyodrębnione specjalne aksjomaty dla równości. Aksjomaty, te to wszystkie formuły oraz ich generalizacje odpowiadające poniższym schematom:

1. \( t=t \), dla każdego termu \( t \)

2. \( ( t_1=t_1' \wedge \ldots \wedge t_k= t_k' ) \Rightarrow f(t_1,\ldots,t_k) = f(t_1', \ldots,t_k') \), dla dowolnego symbolu funkcyjnego \( f \), oraz dowolnych termów \( t_1,\ldots,t_k, t_1', \ldots, t_k' \), gdzie \( k \) jest ilością argumentów symbolu \( f \)

3. \( ( t_1=t_1' \wedge \ldots \wedge t_k= t_k' ) \Rightarrow ( p(t_1,\ldots,t_k) \Rightarrow p(t_1', \ldots,t_k') ) \), dla dowolnego symbolu predykatywnego \( p \), oraz dowolnych termów \( t_1,\ldots,t_k, t_1', \ldots, t_k' \), gdzie \( k \) jest ilością argumentów symbolu \( p \)

Rozważmy język, w którym mamy jeden binarny symbol predykatywny \( =^2 \), jeden symbol stałej \( 0 \) oraz symbole funkcyjne \( s^1, +^2, \times^2 \). Zgodnie z przyjętą konwencją termy i formuły będziemy zapisywać infixowo. Do aksjomatów logicznych, oraz aksjomatów dla równości, dokładamy następujące aksjomaty:

1. \( \forall_x \forall_y (s(x)=s(y) \Rightarrow x=y) \)

2. \( \forall_x \neg s(x)=0 \)

3. \( \forall_x (\neg (x=0) \Rightarrow (\exists_y s(y)=x)) \)

4. \( \forall_x x+0=x \)

5. \( \forall_x \forall_y x+s(y)=s(x+y) \)

6. \( \forall_x x\times 0= 0 \)

7. \( \forall_x \forall_y x\times s(y)=x \times y+y \)

Teorią Q nazwiemy wszystkie formuły w ustalonym języku które da się udowodnić z aksjomatów logiki predykatów z dołączonymi aksjomatami równości oraz 1-7. Nietrudno się przekonać, że wszystkie twierdzenia teorii Q są prawdziwe w liczbach naturalnych, przy naturalnej interpretacji występujących symboli (\( s(x) \) interpretujemy jako \( x+1 \)). W następnym wykładzie (patrz Wykład 4) przedstawiamy aksjomatyczną teorię w rachunku predykatów nazywaną teorią mnogości ZFC.

Modele

Podstawowe definicje

Podstawowe definicje

Aksjomatyczna teoria mnogości jest oparta o rachunek predykatów posługujący się jedynym symbolem predykatowym. Symbol ten jest dwuargumentowy i oznaczamy go przez

\( \in \)

Predykat ten jest najczęściej interpretowany w modelu jako symbol przynależności do zbioru. Zbiór, który jest wartością zmiennej po lewej stronie symbolu jest elementem zbioru, który jest wartością zmiennej występującej po prawej.
Dla ułatwienia posługiwania się formalizmem związanym z aksjomatyczną teorią mnogości używamy wielu skrótów pozwalających na bardziej zwięzłe zapisywanie formuł. Często używany symbol \( \notin \) jest skrótem mówiącym, że dwa elementy nie są ze sobą w relacji \( \in \), to znaczy

\( x \notin y \stackrel{\textrm{def}}{\equiv} \lnot x\in y. \)

Kolejny skrót oznaczamy przez \( = \) i definiujemy go w następujący sposób,

\( x = y \stackrel{\textrm{def}}{\equiv} \forall z ( z\in x\iff z\in y). \)

Zgodnie z intuicją wyniesioną z naiwnej teorii zbiorów skrót ten definiuje dwa zbiory jako równe, jeśli dla każdego wartościowania zmiennej \( z \) element jest w zbiorze \( x \) wtedy i tylko wtedy, kiedy jest w zbiorze \( y \). Nieformalnie, dwa zbiory są równe jeśli posiadają dokładnie te same elementy. W naszym języku nie mamy możliwości zdefiniowania pojedynczego bytu w modelu, gdyż nie mamy wpływu na to, jak interpretowane są predykaty. Będziemy mówić, że zbiór posiadający daną cechę jest unikalny, jeśli wszystkie zbiory posiadające tą cechę są równe.
Podobnie do równości jesteśmy w stanie zdefiniować zawieranie, czyli inkluzji zbiorów

\( x \subset y \stackrel{\textrm{def}}{\equiv} \forall z ( z\in x \Longrightarrow z\in y). \)

Inkluzja ta spełnia własności, które pochodzą z naiwnej teorii mnogości. Przede wszystkim, dwa zbiory są sobie równe wtedy i tylko wtedy, kiedy jeden jest podzbiorem drugiego, a drugi pierwszego.

Fakt 2.1.

Następująca formuła jest prawdziwa w aksjomatycznej teorii mnogości

\( \forall x \forall y ( x = y \iff x\subset y \land y\subset x). \)

Dowód

Zastępując skróty przez odpowiadające im napisy, otrzymujemy:

\( \forall x \forall y [ \forall z ( z\in x\iff z\in y) \iff \forall z ( z\in x \Longrightarrow z\in y)\land \forall z ( z\in y \Longrightarrow z\in x)]. \)

Używając podstawowych własności rachunku predykatów, otrzymujemy:

\( \forall x \forall y [\forall z ( z\in x\iff z\in y) \iff \forall z ( (z\in x \Longrightarrow z\in y)\land ( z\in y \Longrightarrow z\in x))] \)

i dalej

\( \forall x \forall y [\forall z ( z\in x\iff z\in y) \iff \forall z (z\in x\iff z\in y)], \)

co jest tautologią rachunku predykatów.

W bardzo podobny sposób możemy pokazać, że

\( \forall x \forall y \forall z (x\subset y \land y\subset z ) \Longrightarrow x\subset z. \)

Czyli, że zawieranie zbiorów zdefiniowane w rachunku predykatów jest przechodnie.

Aksjomat zbioru pustego

Aksjomat zbioru pustego

Aksjomat zbioru pustego Zakładamy, że następująca formuła, zwana aksjomatem zbioru pustego, jest prawdą

\( \exists x \forall y\; y\notin x, \)

a zbiór \( x \) spełniający ten warunek nazywamy zbiorem pustym i oznaczamy przez \( \emptyset \).

Aksjomat zbioru pustego mówi, że istnieje zbiór nieposiadający elementów. Dokładnie, definiująca go formuła mówi, że każdy \( y \) nie należy do \( \emptyset \). Symbol \( \emptyset \) oznacza dokładnie jeden zbiór, czego dowodzą poniższe fakty.

W następującym fakcie pokażemy, że istnieje nie więcej niż jeden zbiór pusty. Aksjomat zbioru pustego gwarantuje nam istnienie przynajmniej jednego zbioru pustego i w związku z tym zbiór pusty jest dokładnie jeden.

Fakt 3.1.

Istnieje co najwyżej jeden zbiór pusty, czyli następująca formuła jest prawdziwa

\( \forall x\forall y \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow x=y. \)

Dowód

Niewątpliwie

\( \forall x\forall y \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow (\forall z\,(z\notin x\land z\notin y )) \)

skąd możemy wnioskować, że

\( \forall x\forall y \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow (\forall z\,z\in x\iff z\in y ) \)

gdzie prawa strona implikacji jest definicją równości zbiorów. Intuicyjnie dowód przebiega następująco. Dwa zbiory są sobie równe, jeśli każdy element albo należy do obu z nich równocześnie, albo do żadnego. Weźmy dwa zbiory puste i dowolny element. Element ten nie należy do żadnego z tych zbiorów. Wnioskujemy, że zbiory te muszą być sobie równe.

Aksjomat Pary

Aksjomat Sumy

Schemat aksjomatu wyróżniania

Aksjomat Nieskończoności

Aksjomat Nieskończoności

Następujący aksjomat gwarantuje istnienie zbiorów nieskończonych. Działanie tego aksjomatu jest podobne do działania indukcji matematycznej omawianej wcześniej. Intuicyjnie aksjomat ten gwarantuje nam istnienie przynajmniej jednego zbioru zawierającego wszystkie liczby naturalne. Zbiór taki musi być nieskończony.

Aksjomat Nieskończoności Zakładamy, że następująca formuła, zwana aksjomatem nieskończoności, jest prawdą:

\( \exists x\; (\emptyset\in x \land (\forall y\; y\in x\Longrightarrow y\cup\{y\}\in x )). \)

Rozważmy zbiór \( x \), którego istnienie jest gwarantowane przez aksjomat nieskończoności. Niewątpliwie \( \emptyset\in x \). Na podstawie drugiej części definicji wnioskujemy, że \( \emptyset\cup \{\emptyset\}=\{\emptyset\}\in x \). Stosując drugą część definicji raz jeszcze, otrzymujemy dalej \( \{\emptyset\}\cup\{\{\emptyset\}\}=\{\emptyset,\{\emptyset\}\}\in x \). Powtarzając tę operację za każdym razem, otrzymujemy nowy element zbioru \( x \). Intuicyjnie, wymagania stawiane zbiorowi \( x \) w definicji gwarantują, że, na zasadzie podobnej do zasady indukcji matematycznej, będzie on posiadał "nieskończenie" wiele elementów. Zbiór ten może posiadać inne elementy niż te, które udają się skonstruować za pomocą procedury wymienionej powyżej.

Zbiór, którego istnienie gwarantuje aksjomat nieskończoności, jest używany do konstruowania liczb naturalnych. W konstrukcji liczb naturalnych opartej na liczbach porządkowych wprowadzonych po raz pierwszy przez Johna von Neumanna wyżej wymienione zbiory to kolejne liczby naturalne.

\( \begin{array} {ll} \text{liczba naturalna zero to zbiór } & \emptyset \\ \text{liczba naturalna jeden to zbiór } & \{\emptyset\} \\ \text{liczba naturalna dwa to zbiór } & \{\emptyset,\{\emptyset\}\} \\ \text{liczba naturalna trzy to zbiór } & \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \\ \text{i tak dalej\dots} & \text{ } \end{array} \)

W powyższej konstrukcji liczba naturalna to bardzo konkretny zbiór. Zbiór będący liczbą naturalną ma, intuicyjnie mówiąc, tyle elementów, jaka jest wartość tej liczby, choć nie każdy zbiór posiadający tyle elementów jest liczbą naturalną. Wykład 7 jest w całości poświęcony konsekwencjom tego aksjomatu; uzyskany tam zbiór liczb naturalnych jest najmniejszym \( x \) spełniającym warunki aksjomatu nieskończoności.

Aksjomat Zbioru Potęgowego

Schemat Aksjomatu Zastępowania

Schemat Aksjomatu Zastępowania

Kolejnym aksjomatem lub raczej schematem aksjomatu jest aksjomat zastępowania. Aksjomat ten, wraz z aksjomatem zbioru pustego, implikuje aksjomat wyróżniania i dlatego aksjomat wyróżniania jest często omijany w liście aksjomatów. Intuicyjna interpretacja tego aksjomatu jest następująca. Jeśli pewna własność, opisana formułą, ma cechy funkcji, to obrazem każdego zbioru, względem tej własności, jest również zbiór.

Aksjomat Zastępowania Dla dowolnej formuły \( \varphi \) nieposiadającej zmiennych wolnych innych niż \( w \) i \( v \) następująca formuła jest prawdą:

\( (\forall w \exists u \forall v\; \varphi \Longrightarrow u=v) \Longrightarrow (\forall x \exists y\forall v\; (v\in y \iff \exists w\; w\in x \land \varphi)) \)

Aksjomat zastępowania posiada specyficzną formę. Istnienie zbioru \( y \) jest zagwarantowane pod warunkiem, że formuła \( \varphi \) spełnia wymaganą własność. Formuła \( \varphi \) musi działać jak "funkcja częściowa", to znaczy, że jeśli jest spełniona dla zbiorów \( w,v \), to nie może być prawdą dla żadnych innych zbiorów \( w,v' \). Nieformalnie, formuła \( \varphi \) przyporządkowuje jednoznacznie pewnym zbiorom inne zbiory. Pod tym warunkiem istnieje zbiór bytów przyporządkowany bytom z danego zbioru \( x \). Zupełnie nieformalnie możemy stwierdzić, że dla zdefiniowanej formułą częściowej funkcji, jeśli jako dziedzinę weźmiemy dowolny zbiór \( x \), to przeciwdziedzina tej funkcji również jest zbiorem.

Aksjomat zastępowania nie był jednym z aksjomatów zaproponowanych przez Ernsta Zermelo. Został on dodany później przez Adolfa Abrahama Halevi Fraenkela i jest stosowany obecnie jako część aksjomatyki, którą nazywamy potocznie ZF. Pokażemy teraz, że aksjomat zastępowania implikuje aksjomat wyróżniania.

Rozpoczynając dowód, ustalamy \( x \) i \( \varphi \), do których chcielibyśmy zastosować aksjomat wyróżniania. Jedyną zmienną wolną w \( \varphi \) jest \( z \) i aksjomat wyróżniania gwarantuje istnienie zbioru \( y \) będącego podzbiorem \( x \) i składającego się dokładnie z tych elementów, dla których \( \varphi \) jest prawdą. Aby istnienie zbioru \( y \) zostało zagwarantowane przez aksjomat zastępowania, musimy zmienić formułę \( \varphi \). Nowa formuła \( \varphi' \) wygląda następująco

\( \exists z\; \varphi \land z=w=v. \)

Formuła \( \varphi' \) posiada dwie zmienne wolne \( w \) i \( v \) i spełnia warunek jednoznaczności, gdyż jeśli jest prawdą dla \( w \) i \( v \), to niewątpliwie \( w=v \). Co więcej formuła jest prawdą dla wyłącznie tych \( w=v \), dla których \( \varphi \) jest prawdą przy założeniu, że \( z=w=v \). Stosując aksjomat zastępowania dla tego samego \( x \), dla którego chcielibyśmy stosować aksjomat wyróżniania, otrzymujemy zbiór tych \( v \), dla których \( \varphi' \) jest prawdą dla pewnego \( w\in x \). Ale skoro tak, to \( w=z=v \) i \( \varphi \) jest prawdą dla \( z \), co dowodzi, że otrzymaliśmy dokładnie ten sam zbiór. Dowiedliśmy, że aksjomat zastępowania implikuje aksjomat wyróżniania.

Aksjomat Regularności

Aksjomat Regularności

W skład zestawu aksjomatów zaproponowanych przez Ernsta Zermelo i uzupełnionych później przez Adolfa Abrahama Halevi Fraenkela wchodzą dodatkowe dwa aksjomaty. Pierwszym z nich jest aksjomat regularności.