\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={1.2in,*,1.2in},hdivide={1.2in,*,1.2in},nohead}
\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 połówkowy}
\date{30 listopada 2002}
\maketitle
\thispagestyle{fancy}

\noindent
Za dzisiejszy egzamin można otrzymać od $-40$ do $40$ punktów, za
egzamin końcowy zaś od $-60$ do $60$ punktów. Łącznie można więc
otrzymać od $-100$ do $100$ punktów. Jeżeli punktacja
za zadanie egzaminacyjne wynosi $n$, znaczy to, że za rozwiązanie
tego zadania można otrzymać od $-n$ do $n$ punktów. Punkty
ujemne będą przyznawane za umieszczenie w rozwiązaniu odpowiedzi
kompromitująco fałszywych. Za brak rozwiązania zadania otrzymuje się 0
punktów. Punkty z egzaminu zasadniczego przeliczają się na oceny
zgodnie z tabelką:
\begin{center}
\begin{tabular}{>{$}r<{$}@{${}\div{}$}>{$}r<{$}l}
-100&32&ndst\\
33&45&dst\\
46&58&dst+\\
59&71&db\\
72&84&db+\\
85&100&bdb\\
\end{tabular}
\end{center}
Czas trwania egzaminu wynosi 3 godziny zegarowe.


\begin{zadanie}[8 punktów]
Niech~$I$ oznacza relację identyczności na zbiorze~$X$.
Udowodnij, że relacja $R\subseteq X\times X$ jest relacją
równoważności wtedy i tylko wtedy, gdy spełniony jest warunek
\[I\subseteq R \wedge R^{-1}=R \wedge RR\subseteq R.\]
\end{zadanie}

\begin{zadanie}[6 punktów]
Pokaż, że
\[(A_1\cup A_2)\rsym(B_1\cup B_2)\subseteq (A_1\rsym B_1)\cup(A_2\rsym B_2).\]
Czy zawieranie
\[(A_1\cap A_2)\rsym(B_1\cap B_2)\subseteq (A_1\rsym B_1)\cup(A_2\rsym B_2)\]
jest prawdziwe dla dowolnych zbiorów $A_1$, $A_2$, $B_1$ i $B_2$?

Odpowiedź uzasadnij.
\end{zadanie}


\begin{zadanie}[4 punkty]
Udowodnij, że dla dowolnych rodzin zbiorów $\{A_t:t\in T\}$ i~$\{B_t:t\in T\}$
zachodzi inkluzja
\[\bigcap_{t\in T} A_t \cup \bigcap_{t\in T} B_t \subseteq \bigcap_{t\in T}
(A_t \cup B_t).\]
Czy zachodzi też inkluzja odwrotna? Odpowiedź uzasadnij.
\end{zadanie}



\begin{zadanie}[4 punkty]
Używając tylko kwantyfikatorów, zmiennych, nawiasów, spójników
logicznych oraz symboli $\in$, $\mathbb{N}$, $+$,
$\times$, $=$ i~$\leq$ napisz formułę mówiącą, że wśród każdych trzech
liczb naturalnych zawsze znajdą się dwie, których różnica jest nieujemna
i~parzysta. Czy taką formułę można zapisać używając wyłącznie
kwantyfikatorów, zmiennych, nawiasów, spójników logicznych oraz symboli
$\in$, $\mathbb{N}$, $+$ i $=$~?

Używając tylko kwantyfikatorów, zmiennych, nawiasów, spójników
logicznych oraz~symboli $\in$, $\mathbb{N}$, $+$,
$\times$, $=$, $<$ i~symbolu~$f$ napisz formułę mówiącą, że jeśli funkcja
$f:\mathbb{N}\to\mathbb{N}$ jest silnie rosnąca (dla większych
argumentów ma większe wartości), to jej wartości są nieograniczone.
\end{zadanie}

\begin{zadanie}[7 punktów]
Dla jakich zbiorów $C$ prawdziwe jest zdanie:
dla dowolnych zbiorów $A$ i~$B$ zachodzi
\[A\times C\subseteq B\times C\;\Rightarrow\;A\subseteq B\]
\end{zadanie}

\begin{zadanie}[11 punktów]
Zbiory~$A$ i~$B$ są równoliczne. Pokaż, że dla dowolnego zbio\-ru~$C$
równoliczne są zbiory:
\begin{enumerate}\itemsep0pt
\item $C\times A$ i $C\times B$,
\item $C^A$ i $C^B$,
\item $A^C$ i $B^C$.
\end{enumerate}
\end{zadanie}

\begin{zadanie}[bonusowe, 15 punktów]
Niech~$A$ będzie zbiorem, a~$f$ --- bijekcją przekształcającą
zbiór~$A$ w~$A$. Zdefiniujmy relację $R\subseteq A^2$
przyjmując, że
\[xRy\;\Leftrightarrow\;f(x)=y.\] 
Symbolem $R_\infty$ oznaczamy przechodnie domknięcie relacji~$R$,
czyli relację $\bigcup_{n=1}^\infty R^n$, gdzie $R^1=R$ oraz $R^{n+1}=R^nR$.
Czy
\begin{enumerate}\itemsep0pt
\item $R_\infty$ jest relacją równoważności?
\item $R_\infty$ jest relacją równoważności, jeśli~$A$ jest zbiorem skończonym?
\end{enumerate}
Odpowiedzi uzasadnij.
\end{zadanie}\begin{zadanie}[bonusowe, 5 punktów]
Niech $A, B$ będą dowolnymi zbiorami. Kiedy równanie
\[A\cup X=B\]
\begin{enumerate}\itemsep0pt
\item ma dokładnie jedno rozwiązanie,
\item ma nieskończenie wiele rozwiązań,
\item nie ma rozwiązań?
\end{enumerate}

Odpowiedź uzasadnij.
\end{zadanie}
\end{document}
