\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{latexsym,polski,geometry}
\geometry{compat2} %vdivide={1in,*,1in}}
%\prefixing
%\documentstyle[12pt]{article}
%\prefixing
%\input{skr-def}
\newcommand{\mod}{\mbox{\rm\ mod\ }}

%\theoremheaderfont{\normalfont\bfseries}
%\theoremseparator{.}
%\theorembodyfont{\normalfont\upshape}
%\theoremstyle{plain}
\newtheorem{zadanie}{Zadanie}
\newcommand{\vph}{\varphi}
\newcommand{\lh}[1]{|#1|}
\newcommand{\po}[1]{\noindent{\bf #1.}}
\newtheorem{thm}{Twierdzenie}[zadanie]
\newcommand{\bth}{\begin{thm}}
\newcommand{\eth}{\end{thm}}
\newtheorem{wni}[thm]{Wniosek}
\newcommand{\bco}{\begin{wni}}
\newcommand{\eco}{\end{wni}}
\newtheorem{fac}[thm]{Fakt}
\newcommand{\bfa}{\begin{fac}}
\newcommand{\efa}{\end{fac}}
\newcommand{\bpf}{\noindent{\bf Dowód.\ }}
\newcommand{\epf}{$\Box$\par\addvspace{4pt}}
\newcommand{\rarr}{\rightarrow}
\newcommand{\eqv}{\Leftrightarrow}
\newcommand{\sm}{\setminus}
\newcommand{\sbs}{\subseteq}
\newcommand{\cla}{{\cal A}}
\newcommand{\clk}{{\cal K}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\begin{document}
\begin{center}
\Large\bf
Rozwiązania niektórych zadań z egzaminu z 14 lutego 2003
\end{center}


\begin{zadanie}
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\dots\vee\psi_n$,
taka że dla każdego $i\leq n$ formuła $\psi_i$ jest koniunkcją zmiennych
oraz $(\phi\eqv\psi)$ jest tautologią.
\end{zadanie}
\po{Szkic rozwiązania 1}
Formuły $\phi$ i $\psi$ będę nazywał równoważnymi wtedy i tylko wtedy, 
gdy formuła $\phi\eqv\psi$ jest tautologią.
Zauważmy, że
\bfa
Formuła $(\vph_1\vee\vph_2)\wedge \psi$ jest równoważna
$(\vph_1\wedge\psi)\vee(\vph_2\wedge \psi)$, czyli
formuła
\[(\vph_1\vee\vph_2)\wedge \psi\eqv(\vph_1\wedge\psi)\vee(\vph_2\wedge \psi)\]
jest tautologią.
\efa
\bfa
Formuła
\[(\vph_1\vee\dots\vee\vph_n)\wedge \psi\eqv(\vph_1\wedge\psi)\vee\dots\vee(\vph_n\wedge \psi)\]
jest tautologią. Tautologią jest także formuła
\[\psi\wedge(\vph_1\vee\dots\vee\vph_n)\eqv(\psi\wedge\vph_1)
\vee\dots\vee(\psi\wedge\vph_n).\]
\efa

\bfa
Formuła
\[(\vph_1\vee\dots\vee\vph_n)\wedge(\vph'_1\vee\dots\vee\vph'_m) \eqv
(\vph_1\wedge\vph'_1)\vee\dots\vee(\vph_n\wedge\vph'_1)\vee\dots\vee
(\vph_1\wedge\vph'_m)\vee\dots\vee(\vph_n\wedge\vph'_m)\]
jest tautologią. 
\efa

Korzystając z ostatniego faktu można dowieść własność podaną 
w zadaniu przez indukcję ze względu na liczbę spójników 
występujących w formule $\phi$.

Jeżeli w formule $\phi$ nie występują spójniki, to jest ona zmienną.
Każda zmienna jest jednoczłonową alternatywą,
której jedynym członem jest jednoczłonowa koniunkcja.
Tak więc w tym przypadku formuła $\phi$ ma odpowiednią postać 
i możemy przyjąć, że $\psi=\phi$.

Jeżeli w formule $\phi$ występuje przynajmniej jeden spójnik, 
to jest ona koniunkcją lub alternatywą formuł z mniejszą
liczbą spójników. W przypadku alternatywy dalszy dowód jest prosty
i zostaje pominięty. Jeżeli $\phi=\phi_1\wedge\phi_2$, 
to na podstawie założenia 
indukcyjnego znajdujemy alternatywy $\psi_1$ i $\psi_2$
wymaganej postaci równoważne odpowiednio $\phi_1$ i $\phi_2$.
Wprowadzając odpowiednie oznaczenia możemy przyjąć, że
lewa strona równoważności z ostatniego faktu jest równa
$\psi_1\wedge\psi_2$. Formułę $\psi$ definiujemy jako
prawą stronę równoważności z tego faktu.
\epf

\po{Inne rozwiązanie}
Najpierw sformalizujemy treść zadania.

Symbolem $\clk$ będziemy oznaczać najmniejszy w sensie inkluzji 
spośród zbiorów $X$ spełniających warunki:
\begin{enumerate}
\item
wszystkie znmienne zdaniowe należą do $X$,
\item
jeżeli $\phi$ i $\psi$ należą do $X$, to także 
formuła $\phi\wedge\psi$ należy do $X$.
\end{enumerate}
Tak więc $\clk$ jest zbiorem koniunkcji zmiennych zdaniowych.
Symbolem $\cla$ będziemy zaś oznaczać najmniejszy w sensie inkluzji 
spośród zbiorów $X$ spełniających warunki:
\begin{enumerate}
\item
$\clk\sbs X$,
\item
jeżeli $\phi$ i $\psi$ należą do $X$, to także 
formuła $\phi\vee\psi$ należy do $X$.
\end{enumerate}
Tak więc $\cla$ jest zbiorem alternatyw koniunkcji zmiennych zdaniowych.
Posługując się wprowadzonymi oznaczeniami rozwiązywane zadanie można
sformułować następująco: dowieść, że
dla każdej formuły $\phi$, w której występują tylko spójniki
$\wedge$ i $\vee$, istnieje formuła $\psi\in\cla$ taka, że
formuła $\phi\eqv\psi$ jest tautologią.

Dowód zostanie przeprowadzony przez indukcję ze względu na liczbę
spójników występujących w formule $\phi$.

Niech $n$ będzie liczbą naturalną, a $\phi$ formułą,
w której występuje $n$ spójników i są to jedynie
spójniki $\wedge$ i $\vee$.
Będziemy zakładać, że jeżeli w pewnej formule
występuje mniej niż $n$ spójników, to jest ona
równoważna formule należącej do $\cla$.
Przy tym założeniu wykażemy, że
$\psi$ też jest równoważna formule należącej do $\cla$.

W dowodzie będziemy rozważać kilka przypadków.
Najpierw przyjmijmy dodatkowo, że $n=0$.
Wtedy w formule $\phi$ nie ma spójników, a więc
$\phi$ jest zmienną i -- w konsekwencji -- należy do $\clk$
oraz do $\cla$. W tym przypadku przyjmujemy, że $\psi=\phi$.
Oczywiście, $\psi\in\cla$, a ponadto, formuły $\phi$ i $\psi$
są w oczywisty sposób równoważne.

Jeżeli $n>0$, to w $\phi$ jest przynajmniej jeden spójnik.
Wtedy $\phi$ jest albo koniunkcją, albo alternatywą
formuł zawierających mniejszą liczbę spójników niż $\phi$.
Najpierw załóżmy, że $\phi=\phi_1\vee\phi_2$.
Dla formuł $\phi_1$ i $\phi_2$ możemy skorzystać
z założenia indukcyjnego. Istnieją więc w $\cla$ formuły
$\psi_1$ i $\psi_2$ równoważne odpowiednio $\phi_1$ i $\phi_2$.
Oczywiście, $\psi_1\vee\psi_2\in\cla$ oraz
$\psi_1\vee\psi_2$ jest równoważne z $\phi_1\vee\phi_2$.

Jeżeli $\phi=\phi_1\wedge\phi_2$, to także znajdujemy w $\cla$ formuły
$\psi_1$ i $\psi_2$ równoważne odpowiednio $\phi_1$ i $\phi_2$.
Formuły z $\cla$ albo należą do $\clk$, albo są alternatywami.

Jeżeli $\psi_1$ i $\psi_2$ należą do $\clk$, to
przyjmujemy, że $\psi=\psi_1\wedge\psi_2$. Także w tym przypadku
jest oczywiste, że
$\psi\in\clk\sbs\cla$ oraz, że $\phi$ jest równoważne $\psi$.

Pozostał do rozważania przypadek, w którym przynajmniej jedna
z formuł $\psi_1$ i $\psi_2$ jest alternatywą.
Załóżmy, że $\psi_1=\psi_{11}\vee\psi_{12}$.
Jeżeli okaże się, że alternatywą jest tylko $\psi_2$
będziemy postępować dokładnie tak samo.
Na mocy prawa rozdzielności koniunkcji względem alternatywy
(prawo $(p\vee q)\wedge r\eqv(p\wedge r)\vee(q\wedge r)$)
otrzymujemy, że formuła
\[\phi=(\phi_{11}\vee\psi_{12})\wedge\phi_2\]
jest równoważna formule
\[(\phi_{11}\wedge\phi_2)\vee(\psi_{12}\wedge\phi_2).\]
Nietrudno zauważyć, że w obu członach tej alternatywy
jest mniej spójników, niż w formule $\phi$.
Do tych członów możemy więc zastosować założenie indukcyjne.
W ten sposób znajdujemy formuły $\psi_1$ i $\psi_2$ takie, że
\[\psi_1\eqv(\phi_{11}\wedge\phi_2)\mbox{ oraz }\psi_2\eqv(\phi_{12}\wedge\phi_2)\]
są tautologiami. Bez trudu dowodzimy, że formuła
\[\phi\eqv(\psi_1\vee\psi_2)\]
jest tautologią.
Ponieważ $\psi_1,\psi_2\in\cla$, więc także
$\psi_1\vee\psi_2\in\cla$. W rozważanym przypadku
możemy przyjąć, że $\psi=\psi_1\vee\psi_2$.
\epf

Przedstawiony dowód można rozbić na dwie części
dowodząc najpierw, że
koniunkcja formuł należących do $\cla$ jest równoważna
formule należącej do $\cla$.



\begin{zadanie}
Niech $f:R\rarr R$. Mówimy, że $x\in R$ jest maksimum lokalnym
funkcji $f$, jeżeli istnieje taka dodatnia liczba rzeczywista $r$, że dla każdego
$y\in R$ 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:R\rarr R$ zbiór jej lokalnych maksimów
jest przeliczalny.
\end{zadanie}

\po{Przykład 1}
Najpierw podam przykłady funkcji, dla których nie można skonstruować 
rodziny parami rozłącznych przedziałów zawierających
wszystkie maksima lokalne, takiej że w każdym przedziale jest najwyżej jedno
maksimum.

Rozważmy funkcję $f_1:R\rarr R$ zdefiniowaną wzorem
\[f_1(x)=\left\{\begin{array}{ll}\displaystyle
sin\left(\frac{1}{x}\right)&\mbox{dla }x\neq 0,\\
2&\mbox{dla }x=0.
\end{array}\right.\]
Łatwo sprawdzić, że funkcja $f_1$ przyjmuje maksimum lokalne dla 
$x=0$ i dla wszystkich $x=\frac{1}{2k\pi}$ dla $k\in Z$.

Podobnie jest w przypadku funkcji $f_2$ zdefiniowanej wzorem 
\[f_2(x)=\left\{\begin{array}{ll}\displaystyle
x^2\left(sin\left(\frac{1}{x}\right)-2\right)&\mbox{dla }x\neq 0,\\
0&\mbox{dla }x=0,
\end{array}\right.\]
która dodatkowo jest ciągła, a nawet różnczkowalna.
\epf

\po{Przykład 2}
Weźmy teraz funkcję $f:R\rarr R$ przyjmującą wartości
\[f(x)=\left\{\begin{array}{ll}\displaystyle
\frac{1}{n}&\mbox{jeżeli }\displaystyle x=\frac{m}{n},\mbox{ gdzie $n$ i $m$ są 
liczbami względnie pierwszymi i }n>0\\
1&\mbox{jeżeli }x=0\\
0&\mbox{jeżeli }x\not\in Q.
\end{array}\right.\]
Dla tej funkcji zbiór lokalnych maksimów jest równy zbiorowi liczb
wymiernych. 
Zauważmy od razu ważną własność funkcji $f$:
dla dowolnej dodatniej liczby $k$ i dla dowolnej liczby całkowitej $a$,
funkcja $f$ nie przyjmuje wartości $1/k$ 
dla argumentów $x\in(a/k,(a+1)/k)$.

Najpierw pokażemy, że $3/7$ jest lokalnym maksimum $f$.
Oczywiście, $f(3/7)=1/7$. Zauważmy, że w przedziale $(2/7, 4/7)$ 
funkcja $f$ przyjmuje wartość 1/7 tylko dla $x=3/7$.
Funkcja $f$ przyjmuje też wartości większe od 1/7
i są to wartości 1, 1/2, 1/3, 1/4, 1/5 i 1/6.
Ale $f$ nie przyjmuje wartości 1 w przedziale $(0,1)$,
nie przyjmuje wartości 1/2 w przedziale $(0,1/2)$,
nie przyjmuje wartości 1/3 dla $x\in(1/3,2/3)$,
wartości 1/4 dla $x\in (1/4,2/4)$, wartości 1/5 dla $x\in(2/5,3/5)$
oraz wartości 1/6 dla $x\in(2/6,3/6)$. Zauważmy, że
do wszystkich wymienionych przedziałow należy 3/7.
Co więcej, dla argumentów należących do przekroju 
wymienionych przedziałów (z wyjątkiem $x=3/7$)
funkcja $f$ nie przyjmuje wartości $\geq 1/7$.
Przekrojem tym jest $(2/5,1/2)$.
Dla $x\in(2/5,1/2)$ z wyjątkiem $x=3/7$ funkcja $f$ przyjmuje wartości
mniejsze od 1/7. Zmnieszając ten przedział można spowodować, że
jego środkiem stanie się punkt 3/7. Tak więc 
3/7 jest jednym z maksimów lokalnych funkcji $f$.
 
 
Przedstawione rozumowanie można powtórzyć dla każdej z liczb wymiernych.
Jeżeli $m/n$ jest nieskracalnym przedstawieniem liczby wymiernej i $n>0$,
to definiujemy
\[a_k=\max\{a\in Z:\frac{a}{k}<\frac{m}{n}\}.\]
Oczywiście, $\frac{a_k}{k}<\frac{m}{n}\leq\frac{a_k+1}{k}$.
Jeżeli $0<k<n$, to także $\frac{m}{n}<\frac{a_k+1}{k}$, gdyż
przedstawienie liczby wymiernej w postaci nieskracalnego ułamka
z dodatnim mianownikiem jest jednoznaczne i liczba $m/n$ nie daje się
przedstawić w postaci $l/k$. 

Przyjmijmy, że 
\[p=\max\{a_1,\dots,a_n\}\mbox{ oraz }q=\min\{a_1+1,\dots,a_{n-1}+1,a_n+2\}.\]
Liczby $p$ i $q$ są tak dobrane, że
\[(p,q)=\bigcap_{k=1}^{n-1}(a_k,a_k+1)\cap(a_n,a_n+2).\]
Oczywiście, $m/n\in(p,q)$. 
Ze wspomnianej własności funkcji $f$ otrzymujemy, że na przedziale
$(p,q)$ nie przyjmuje ona wartości $>1/n$ oraz -- z wyjątkiem argumentu
$m/n$ -- nie przyjmuje wartości $1/n$. Wobec tego, na przedziałach
$(p,m/n)$ i $(m/n,q)$ funkcja $f$ przyjmuje tylko wartości $<1/n$.
Aby wykazać, że liczba $m/n$ spełnia warunek z definicji
maksimum lokalnego wystarczy zastąpić przedział $(p,q)$
mniejszym i symetrycznym względem punktu $m/n$.
\epf

Można konstruować jeszcze bardziej skomplikowane funkcje
o interesujących nas własnościach. Prawdopodobnie można dowieść, 
że dla dowolnego przeliczalnego zbioru $X\sbs R$ istnieje funkcja
$f:R\rarr R$, która ma maksima lokalne dokładnie w punktach należących 
do $X$. 


\po{Rozwiązanie}
Weźmy funkcję $f:R\rarr R$ i zdefiniujmy zbiór
\[M=\{x\in R:x\mbox{ jest maksimum lokalnym funkcji }f\}.\]
Aby rozwiązać zadanie wystarczy dowieść, że $M$ jest przeliczalny.
Przeliczalność zbioru $M$ wykażemy dowodząc, że
istnieje różnowartościowa funkcja
\[g:M\rarr Q\times Q.\]
Od funkcji $g$ będzie wymagać, aby dla argumentu $m\in M$
jej wartością była para liczb wymiernych $r_1$, $r_2$ taka, że
$r_1<m<r_2$ i dla wszystkich $x\in R$ spełniony jest warunek
\[r_1<x<r_2\wedge x\neq m\Rightarrow f(x)<f(m).\]
Oczywiście, dla każdego $m\in M$ takie liczby $r_1$ i $r_2$ istnieją.
Dzięki temu, korzystając z przeliczalności produktu $Q\times Q$
można zdefiniować funkcję $g$ przyjmując, że $g(m)$
pierwszą w ustalonej numeracji zbioru $Q\times Q$
parą o podanych własnościach.

Teraz wystarczy dowieść, że funkcja $g$ jest różnowartościowa.
Przypuśćmy, że mamy dwa różne elementy $m_1,m_2\in M$ takie, że
$g(m_1)=g(m_2)$. Jeżeli $g(m_1)=(r_1,r_2)$, to $m_1,m_2\in(r_1,r_2)$ i
z podanej własności $g$ możemy wywnioskować dwie nierówności:
\[f(m_2)<f(m_1)\mbox{ oraz }f(m_1)<f(m_2).\]
Z drugiej strony, te nierówności nie mogą być jednocześnie prawdziwe.
Uzyskana w ten sposób sprzeczność dowodzi różnowartościowości 
funkcji $g$, a to z kolei implikuje przeliczalność zbioru $M$.
\epf

\end{document}


