\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={.0in,*,.0in},hdivide={.8in,*,.8in},nohead,nofoot}
\newcommand{\rsym}{\mathrel{\shortstack{$\cdot$\\[-1.4ex]$-$}}}
\newcommand{\real}{\mathbb R}
\newcommand{\nat}{\mathbb N}
\usepackage{ntheorem}
\theoremheaderfont{\normalfont\bfseries}
\theoremseparator{.}
\theorembodyfont{\normalfont\upshape}
\theoremstyle{plain}
\newtheorem{zadanie}{Zadanie}
\begin{document}
\parindent0pt
\title{Logika dla informatyków}
\author{Egzamin poprawkowy}
\date{14 lutego 2003}
\maketitle
%\thispagestyle{empty}
\thispagestyle{fancy}




\begin{zadanie}[14 pkt]
Podaj przykład przeliczalnego liniowego porządku, takiego że każ\-dy
element posiada następnik, istnieje element najmniejszy, każdy element
prócz najmniejszego posiada poprzednik, ale
nie izomorficznego ze zbiorem liczb naturalnych ze zwykłym porządkiem.
\end{zadanie}

\begin{zadanie}[15 pkt]
Udowodnij, że zbiór~$\mathcal{R}$ relacji
równoważności określonych na ustalonym zbiorze~$X$ uporządkowany przez relację
zawierania jest kratą.

Czy zbiór~$\mathcal{C}$ relacji
częściowego porządku na zbiorze~$X$ uporządkowany przez relację
zawierania jest kratą?
\end{zadanie}

\begin{zadanie}[14 pkt]
Wykaż przez indukcję, że dla każdej formuły zdaniowej~$\phi$ zbudowanej
ze zmiennych oraz spójników $\wedge$~i~$\vee$ istnieje formuła~$\psi$ postaci
$\psi_{1}\vee\psi_{2}\vee\ldots\vee\psi_{n}$, taka że
dla każdego $i\leq n$ formuła $\psi_{i}$ jest koniunkcją zmiennych oraz
$(\phi\Leftrightarrow\psi)$ jest tautologią.
\end{zadanie}

\begin{zadanie}[14 pkt]
\noindent
Udowodnij, że dla dowolnej rodziny zbiorów
$\{A_{t,s}\}_{t\in T,s\in S}$
%$\{A_{t,s}\}_{\shortstack{\tiny$t\in T$\\[-.3ex]\tiny$s\in S$}}$
zachodzi zawieranie
\[\bigcup\limits_{t\in T}\bigcap\limits_{s\in S}A_{t,s}\subseteq
  \bigcap\limits_{s\in S}\bigcup\limits_{t\in T}A_{t,s}.\]
Czy zachodzi inkluzja odwrotna?
\end{zadanie}


\begin{zadanie}[15 pkt]
Wykaż, że zbiory $\real^\nat$~i~$\real$ są równoliczne ($\real$
oznacza zbiór liczb rzeczywistych, a~$\nat$  zbiór liczb naturalnych). 
\end{zadanie}

\begin{zadanie}[15 pkt]
Niech $f:\real\rightarrow\real$. Mówimy, że $x\in\real$ jest lokalnym
maksimum funkcji~$f$, jeżeli istnieje taka dodatnia liczba rzeczywista~$r$,
że dla każdego $y\in\real$ jest spełniony warunek
\[(x-r<y<x+r\wedge x\neq y)\Rightarrow f(x)>f(y)\]
Udowodnij, że dla każdej funkcji $f:\real\rightarrow\real$
zbiór jej lokalnych maksimów jest przeliczalny.
\end{zadanie}

\begin{zadanie}[13 pkt]

Funkcje $f:\mathbb N\rightarrow\{0,1\}$ oraz $g:\mathbb N\rightarrow\{0,1\}$
są \emph{równe prawie wszędzie}, jeśli zbiór
\[\{n\in\mathbb N\mid f(n)\neq g(n)\}\]
jest skończony. Zapis $f\approx g$ oznacza, że funkcje~$f$~i~$g$ są
równe prawie wszędzie.
Funkcja $f:\mathbb N\rightarrow\{0,1\}$ \emph{majoryzuje} funkcję
$g:\mathbb N\rightarrow\{0,1\}$, jeśli zbiór
\[\{n\in\mathbb N\mid f(n)<g(n)\}\]
jest skończony. Zapis $g\preceq f$ oznacza, że funkcja~$f$ majoryzuje
funkcję~$g$.
Na zbiorze
$\mathcal F=\{[f]_\approx\mid f:\mathbb N\to\{0,1\}\}$ klas
abstrakcji relacji~$\approx$ wprowadzamy relację~$\preceq$ przyjmując, że
\begin{eqnarray*}
[f]_\approx\preceq[g]_\approx&\Leftrightarrow&f\preceq g
\end{eqnarray*}

Niech $\{A_i\mid i\in\mathbb N\}$ będzie podziałem zbioru $\mathbb N$
na zbiory nieskończone. Definiujemy ciąg funkcji $\{f_j\mid j\in\mathbb N\}$
kładąc
\begin{eqnarray*}
f_j(n)&=&\cases{1,&jeżeli $n\in\bigcup_{i=1}^jA_i$\cr
0,&w przeciwnym przypadku}
\end{eqnarray*}

Niech $g:\mathbb N\to\{0,1\}$. Napisz, nie używając symbolu $\approx$,
symboli oznaczających klasy
abstrakcji ani symbolu relacji majoryzowania, co to znaczy, że $[g]_\approx$
jest ograniczeniem górnym zbioru $\{[f_j]_\approx\mid j\in\mathbb
N\}$. Napisz, co to znaczy, że $[g]_\approx$
nie jest kresem górnym tego zbioru. Możesz używać kwantyfikatorów,
spójników logicznych, nawiasów, formuł $|A|<\infty$ i $|A|=\infty$
oznaczających, że zbiór $A$ jest, odpowiednio, skończony bądź
nieskończony
oraz zapisu $\{n\in\mathbb N \mid \Phi\}$, gdzie~$\Phi$ oznacza
dowolną
formułę utworzoną z~symboli $g(n)$, $f_j(n)$, $\leq$, $=$ oraz $<$. 

\end{zadanie}



\end{document}
