\documentclass[12pt,a4paper]{article}
\frenchspacing
\usepackage{fancyhdr}
\lfoot{}
\cfoot{}
\rhead{}
\chead{}
\lhead{}
\renewcommand\headrulewidth{0pt}
\renewcommand\footrulewidth{0pt}
\rfoot{\itshape Ci\k ag dalszy na odwrocie $\rightarrow$}
\pagestyle{empty}
\usepackage[nohead]{geometry}
\usepackage{amssymb}
\usepackage[light,all]{draftcopy}
\draftcopyName{POUFNE}{185}
\usepackage{mathtime,array}
\def\boldmath{\relax}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[polish]{babel}
\geometry{vdivide={.2in,*,.8in},hdivide={.8in,*,.8in},nohead,nofoot}
\newcommand{\rsym}{\mathrel{\shortstack{$\cdot$\\[-1.4ex]$-$}}}
\usepackage{ntheorem}
\theoremheaderfont{\normalfont\bfseries}
\theoremseparator{.}
\theorembodyfont{\normalfont\upshape}
\theoremstyle{plain}
\newtheorem{zadanie}{Zadanie}
\begin{document}
\parindent0pt
\title{Logika dla informatyków}
\author{Egzamin końcowy}
\date{3 lutego 2003}
\maketitle
\thispagestyle{empty}



\begin{zadanie}[16 pkt]
Niech~$\phi$ będzie formułą zdaniową zbudowaną ze zmiennych zdaniowych
i~spójników alternatywy, koniunkcji i negacji. Przez
\emph{wartościowanie} formuły $\phi$ rozumiemy funkcję, która zmiennym
\emph{wystepującym} w formule $\phi$ przyporządkowuje wartości ze zbioru
$\{0,1\}$.

%Przez $\textup{Var}(\phi)$
%oznaczamy zbiór zmiennych występujących
%w~formule~$\phi$, zaś przez~$|\phi|$
%liczbę tych wartościowań zmiennych ze zbioru $\textup{Var}(\phi)$,
%które spełniają formułę $\phi$,~t.j.
%\begin{eqnarray*}
%|\phi|&=&\left|\{\sigma:\textup{Var}(\phi)\to
%\{0,1\}\mid \sigma(\phi)=1\}\right|.
%\end{eqnarray*}

Niech~$n$ będzie dodatnią liczbą naturalną.

\quad\textbf{a)~(6 pkt)}\enskip Udowodnij, że dla każdej liczby
naturalnej~$k\leq 2^n$
istnieje formuła zdaniowa~$\phi$ zawierająca~$n$ zmiennych i~spełniona
 przez dokładnie~$k$ wartościowań.

\quad\textbf{b)~(10 pkt)}\enskip Dla jakich liczb~$k$ istnieje
formuła~$\phi$ zawierająca
$n$~zmiennych, w której każda ze zmiennych występuje dokładnie jeden raz
i~która jest spełniona przez dokładnie $k$~wartościowań?
\end{zadanie}

\begin{zadanie}[15 pkt]
Niech $\alpha:\mathbb{N}\to \{0,1\}$ będzie ciągiem zero-jedynkowym.
Symbolem $\sim_{\alpha}$ oznaczamy relację w~zbiorze
$\{0,1\}^\mathbb{N}$ nieskończonych ciągów
zero-jedynkowych zdefiniowaną formułą
\begin{eqnarray*}
\beta\sim_{\alpha}\gamma&\Leftrightarrow&
(\forall n{\in}\mathbb{N})\;\alpha(n)\beta(n)=\alpha(n)\gamma(n).
\end{eqnarray*}

Czy istnieje taki ciąg $\alpha$, dla którego:

\quad\textbf{a)~(5 pkt)}\enskip relacja $\sim_{\alpha}$ ma przeliczalnie i
nieskończenie wiele klas równoważności?

\quad\textbf{b)~(5 pkt)}\enskip wszystkie klasy równoważności
relacji $\sim_{\alpha}$ są przeliczalne i nieskończone?

\quad\textbf{c)~(5 pkt)}\enskip istnieje przeliczalna i nieskończona
klasa równoważności relacji $\sim_{\alpha}$?
\end{zadanie}

\begin{zadanie}[12 pkt]
Na zbiorze~$X$ określone są takie relacje równoważności $Q$~i~$R$,
że

\quad1.~każda klasa równoważności relacji~$Q$ ma $q$~elementów,

\quad2.~każda klasa relacji~$R$ ma $r$~elementów oraz

\quad3.~istnieje klasa równoważności relacji~$Q$, która ma dokładnie jeden element
wspólny z~każdą klasą równoważności relacji~$R$. 

Ile elementów ma zbiór~$X$?
\end{zadanie}

\begin{zadanie}[15 pkt]
Niech~$\Sigma=\{{+},a\}$ będzie sygnaturą zawierającą dwuargumentowy
symbol funkcji~$+$ i~symbol stałej~$a$. Dla dowolnej
dodatniej liczby naturalnej~$n$ niech $A_n=\{0,1,\ldots,n-1\}$,
${\oplus}_n$ oznacza dodawanie modulo~$n$, zaś~$a_n=0$.
Rozważmy algebry $\mathcal A_n=\langle A_n,{\oplus}_n, a_n\rangle$.
Udowodnij, że jeżeli $k=l\cdot m$, to
istnieje homomorfizm~$h$ algebry~$\mathcal A_k$
na~algebrę~$\mathcal A_l$ (surjekcja) taki, że $|\vec{h}^{-1}(\{0\})|=m$.
Podaj przykład takich~$k$, $l$~i~$m$, dla których istnieją co najmniej
dwa takie homomorfizmy.
Ile jest takich homomorfizmów, jeśli zamiast sygnatury~$\Sigma$ będziemy
rozważać sygnaturę~$\Sigma'=\{{+},a,b\}$ zawierajacą dwa symbole stałych
$a$~i~$b$ oraz algebry $\mathcal A_n'=\langle A_n,\oplus_n, a_n,
b_n\rangle$, gdzie $b_n=1$?
\end{zadanie}

\begin{zadanie}[12 pkt]
Pokaż, że zbior liczb wymiernych ze zwykłym porządkiem i zbiór
niepustych skończonych ciągów liczb wymiernych z porządkiem leksykograficznym
są izomorficzne (rozważamy porządek leksykograficzny
generowany przez zwykły porządek na liczbach wymiernych).

Przypominamy, że~$\preceq$ jest porządkiem
leksykograficznym generowanym przez porządek~$\leq$, jeśli
\begin{eqnarray*}
\langle a_0,a_1,\ldots a_m\rangle\preceq\langle b_0,b_1,\ldots, b_n \rangle
\end{eqnarray*}
wtedy i tylko wtedy, gdy $\langle a_0,a_1,\ldots a_m\rangle$ jest
prefiksem $\langle b_0,b_1,\ldots, b_n \rangle$ lub
\[(\exists\, k)\;\Big(k\leq m \wedge k\leq n
\wedge a_k<b_k\wedge (\forall\, i{<}k)\;a_i=b_i\Big).
\]
\emph{Wskazówka:} Skorzystaj z twierdzenia o gęstych porządkach
udowodnionego na ćwiczeniach. Przytocz sformułowanie tego twierdzenia.

\end{zadanie}


\end{document}

\begin{zadanie}[12 pkt]
Rozważamy algebry sygnatury $\Sigma$ zawierającej jeden symbol
funkcji jednoargumentowej $f$ i jeden symbol funkcji zero-argumentowej
(stałej) $a$. Wiemy, że ${\cal A}= \langle A, f^{\cal A},a^{\cal
 A}\rangle  $ jest algebrą taką, że $A$ jest zbiorem skończonym oraz 

a. Istnieje homomorfizm algebry ${\cal A}$ na (surjekcja)  pewną
   algebrę ${\cal B}= \langle B, f^{\cal B}, a^{\cal B}\rangle$.
taką, że  $B$ ma 5 elementów.

b. Istnieje homomorfizm algebry ${\cal A}$ na (surjekcja)  pewną
   algebrę ${\cal C}= \langle C, f^{\cal C}, a^{\cal C}\rangle$
taką, że  $C=\{0,1,2,3,4\}$, $a^{\cal C}= 0$ oraz $f^{\cal C}$ jest
   dodawaniem modulo 5. 

Jaka jest moc zbioru $A$ przy założeniu a?
Jaka jest moc zbioru $A$ przy założeniu b? 
\end{zadanie}

