Rozwiązania niektórych zadań z egzaminu z 14 lutego 2003

Zadanie 1 Wykaż przez indukcję, że dla każdej formuły zdaniowej ϕ zbudowanej ze zmiennych oraz spójników ∧ i ∨ istnieje formuła ψ postaci ψ_{1} ∨ ψ_{2} ∨ … ∨ ψ_{n}, taka że dla każdego i ≤ n formuła ψ_{i} jest koniunkcją zmiennych oraz (ϕ ⇔ ψ) jest tautologią.

Szkic rozwiązania 1. Formuły ϕ i ψ będę nazywał równoważnymi wtedy i tylko wtedy, gdy formuła ϕ ⇔ ψ jest tautologią. Zauważmy, że

Fakt 1.1 Formuła (φ_{1} ∨ φ_{2}) ∧ ψ jest równoważna (φ_{1} ∧ ψ) ∨ (φ_{2} ∧ ψ), czyli formuła

(φ_{1} ∨ φ_{2}) ∧ ψ ⇔ (φ_{1} ∧ ψ) ∨ (φ_{2} ∧ ψ)

jest tautologią.

Fakt 1.2 Formuła

(φ_{1} ∨ … ∨ φ_{n}) ∧ ψ ⇔ (φ_{1} ∧ ψ) ∨ … ∨ (φ_{n} ∧ ψ)

jest tautologią. Tautologią jest także formuła

ψ ∧ (φ_{1} ∨ … ∨ φ_{n}) ⇔ (ψ ∧ φ_{1}) ∨ … ∨ (ψ ∧ φ_{n}).

Fakt 1.3 Formuła

(φ_{1} ∨ … ∨ φ_{n}) ∧ (φ′_{1} ∨ … ∨ φ′_{m}) ⇔ (φ_{1} ∧ φ′_{1}) ∨ … ∨ (φ_{n} ∧ φ′_{1}) ∨ … ∨ (φ_{1} ∧ φ′_{m}) ∨ … ∨ (φ_{n} ∧ φ′_{m})

jest tautologią.

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 ϕ.

Jeżeli w formule ϕ 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 ϕ ma odpowiednią postać i możemy przyjąć, że ψ = ϕ.

Jeżeli w formule ϕ 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 ϕ = ϕ_{1} ∧ ϕ_{2}, to na podstawie założenia indukcyjnego znajdujemy alternatywy ψ_{1} i ψ_{2} wymaganej postaci równoważne odpowiednio ϕ_{1} i ϕ_{2}. Wprowadzając odpowiednie oznaczenia możemy przyjąć, że lewa strona równoważności z ostatniego faktu jest równa ψ_{1} ∧ ψ_{2}. Formułę ψ definiujemy jako prawą stronę równoważności z tego faktu. □

Inne rozwiązanie. Najpierw sformalizujemy treść zadania.

Symbolem K będziemy oznaczać najmniejszy w sensie inkluzji spośród zbiorów X spełniających warunki:

1. wszystkie znmienne zdaniowe należą do X,

2. jeżeli ϕ i ψ należą do X, to także formuła ϕ ∧ ψ należy do X.

Tak więc K jest zbiorem koniunkcji zmiennych zdaniowych. Symbolem A będziemy zaś oznaczać najmniejszy w sensie inkluzji spośród zbiorów X spełniających warunki:

1. K ⊆ X,

2. jeżeli ϕ i ψ należą do X, to także formuła ϕ ∨ ψ należy do X.

Tak więc A 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 ϕ, w której występują tylko spójniki ∧ i ∨, istnieje formuła ψ ∈ A taka, że formuła ϕ ⇔ ψ jest tautologią.

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

Niech n będzie liczbą naturalną, a ϕ formułą, w której występuje n spójników i są to jedynie spójniki ∧ i ∨. 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 A. Przy tym założeniu wykażemy, że ψ też jest równoważna formule należącej do A.

W dowodzie będziemy rozważać kilka przypadków. Najpierw przyjmijmy dodatkowo, że n = 0. Wtedy w formule ϕ nie ma spójników, a więc ϕ jest zmienną i – w konsekwencji – należy do K oraz do A. W tym przypadku przyjmujemy, że ψ = ϕ. Oczywiście, ψ ∈ A, a ponadto, formuły ϕ i ψ są w oczywisty sposób równoważne.

Jeżeli n > 0, to w ϕ jest przynajmniej jeden spójnik. Wtedy ϕ jest albo koniunkcją, albo alternatywą formuł zawierających mniejszą liczbę spójników niż ϕ. Najpierw załóżmy, że ϕ = ϕ_{1} ∨ ϕ_{2}. Dla formuł ϕ_{1} i ϕ_{2} możemy skorzystać z założenia indukcyjnego. Istnieją więc w A formuły ψ_{1} i ψ_{2} równoważne odpowiednio ϕ_{1} i ϕ_{2}. Oczywiście, ψ_{1} ∨ ψ_{2} ∈ A oraz ψ_{1} ∨ ψ_{2} jest równoważne z ϕ_{1} ∨ ϕ_{2}.

Jeżeli ϕ = ϕ_{1} ∧ ϕ_{2}, to także znajdujemy w A formuły ψ_{1} i ψ_{2} równoważne odpowiednio ϕ_{1} i ϕ_{2}. Formuły z A albo należą do K, albo są alternatywami.

Jeżeli ψ_{1} i ψ_{2} należą do K, to przyjmujemy, że ψ = ψ_{1}∧ψ_{2}. Także w tym przypadku jest oczywiste, że ψ ∈ K ⊆ A oraz, że ϕ jest równoważne ψ.

Pozostał do rozważania przypadek, w którym przynajmniej jedna z formuł ψ_{1} i ψ_{2} jest alternatywą. Załóżmy, że ψ_{1} = ψ_{11} ∨ ψ_{12}. Jeżeli okaże się, że alternatywą jest tylko ψ_{2} będziemy postępować dokładnie tak samo. Na mocy prawa rozdzielności koniunkcji względem alternatywy (prawo (p ∨ q) ∧ r ⇔ (p ∧ r) ∨ (q ∧ r)) otrzymujemy, że formuła

ϕ = (ϕ_{11} ∨ ψ_{12}) ∧ ϕ_{2}

jest równoważna formule

(ϕ_{11} ∧ ϕ_{2}) ∨ (ψ_{12} ∧ ϕ_{2}).

Nietrudno zauważyć, że w obu członach tej alternatywy jest mniej spójników, niż w formule ϕ. Do tych członów możemy więc zastosować założenie indukcyjne. W ten sposób znajdujemy formuły ψ_{1} i ψ_{2} takie, że

ψ_{1} ⇔ (ϕ_{11} ∧ ϕ_{2}) oraz ψ_{2} ⇔ (ϕ_{12} ∧ ϕ_{2})

są tautologiami. Bez trudu dowodzimy, że formuła

ϕ ⇔ (ψ_{1} ∨ ψ_{2})

jest tautologią. Ponieważ ψ_{1}, ψ_{2} ∈ A, więc także ψ_{1} ∨ ψ_{2} ∈ A. W rozważanym przypadku możemy przyjąć, że ψ = ψ_{1} ∨ ψ_{2}. □

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

Zadanie 2 Niech f : R → R. Mówimy, że x ∈ R jest maksimum lokalnym funkcji f, jeżeli istnieje taka dodatnia liczba rzeczywista r, że dla każdego y ∈ R jest spełniony warunek

(x − r < y < x + r ∧ x ≠ y) ⇒ f(x) > f(y).

Udowodnij, że dla każdej funkcji f : R → R zbiór jej lokalnych maksimów jest przeliczalny.

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 → R zdefiniowaną wzorem

f_{1}(x) = \{ \begin{matrix}sin (\frac{1}{x}) & dla x ≠ 0, \\ 2 & dla x = 0. \end{matrix}

Łatwo sprawdzić, że funkcja f_{1} przyjmuje maksimum lokalne dla x = 0 i dla wszystkich x = \frac{1}{2kπ} dla k ∈ Z.

Podobnie jest w przypadku funkcji f_{2} zdefiniowanej wzorem

f_{2}(x) = \{ \begin{matrix}x^{2} (sin (\frac{1}{x}) − 2) & dla x ≠ 0, \\ 0 & dla x = 0, \end{matrix}

która dodatkowo jest ciągła, a nawet różnczkowalna. □

Przykład 2. Weźmy teraz funkcję f : R → R przyjmującą wartości

f(x) = \{ \begin{matrix}\frac{1}{n} & jeżeli x = \frac{m}{n}, gdzie n i m są liczbami względnie pierwszymi i n > 0 \\ 1 & jeżeli x = 0 \\ 0 & jeżeli x ∉ Q. \end{matrix}

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 ∈ (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 ∈ (1/3, 2/3), wartości 1/4 dla x ∈ (1/4, 2/4), wartości 1/5 dla x ∈ (2/5, 3/5) oraz wartości 1/6 dla x ∈ (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 ≥ 1/7. Przekrojem tym jest (2/5, 1/2). Dla x ∈ (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 ∈ Z : \frac{a}{k} < \frac{m}{n}\}.

Oczywiście, \frac{a_{k}}{k} < \frac{m}{n} ≤ \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}, …, a_{n}} oraz q = min{a_{1} + 1, …, a_{n−1} + 1, a_{n} + 2}.

Liczby p i q są tak dobrane, że

(p, q) = ⋂_{k=1}^{n−1}(a_{k}, a_{k} + 1) ∩ (a_{n}, a_{n} + 2).

Oczywiście, m/n ∈ (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. □

Można konstruować jeszcze bardziej skomplikowane funkcje o interesujących nas własnościach. Prawdopodobnie można dowieść, że dla dowolnego przeliczalnego zbioru X ⊆ R istnieje funkcja f : R → R, która ma maksima lokalne dokładnie w punktach należących do X. Rozwiązanie. Weźmy funkcję f : R → R i zdefiniujmy zbiór

M = {x ∈ R : x 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 → Q × Q.

Od funkcji g będzie wymagać, aby dla argumentu m ∈ M jej wartością była para liczb wymiernych r_{1}, r_{2} taka, że r_{1} < m < r_{2} i dla wszystkich x ∈ R spełniony jest warunek

r_{1} < x < r_{2} ∧ x ≠ m ⇒ f(x) < f(m).

Oczywiście, dla każdego m ∈ M takie liczby r_{1} i r_{2} istnieją. Dzięki temu, korzystając z przeliczalności produktu Q × Q można zdefiniować funkcję g przyjmując, że g(m) pierwszą w ustalonej numeracji zbioru Q × 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} ∈ M takie, że g(m_{1}) = g(m_{2}). Jeżeli g(m_{1}) = (r_{1}, r_{2}), to m_{1}, m_{2} ∈ (r_{1}, r_{2}) i z podanej własności g możemy wywnioskować dwie nierówności:

f(m_{2}) < f(m_{1}) 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. □