To może inaczej trochę zrobie, niż miałem zamiar (i są pewne nieścisłości).
Leamt (będzie oznaczony jako L(n)):
Formuła o głębokości n zbudowana z
\(\displaystyle{ \Leftrightarrow}\), nawaisów i zmiennych zdaniowych jest prawdziwa przy wartościowaniu σ, jeśli 0 występuje w formule parzystą ilość razy.
Definicja głębokości formuły po przypisaniu 1 lub 0 zmiennym:
1. O głębokości 0: 1,0
2.
\(\displaystyle{ \phi \Leftrightarrow \psi}\) ma głębokość max(głębokość(
\(\displaystyle{ \phi}\)),głębokość(
\(\displaystyle{ \psi}\)))+1
więcej do dowodu lematu nie potrzeba
Zasada minimum. W każdym niepustym zbiorze liczb naturalnych istnieje liczba najmniejsza.
Dowód lematu (z zasady minimum):
Niech A={n : L(n) nie zachodzi}
Chcemy pokazać, że A jest zbiorem pustym.
Załóżmy, że a nie jest zbiorem pustym, zgodnie z zasady minimum w zbiorze musi istnieć element najmniejszy. Mamy 2 przypadki:
1. min(A)=0
2. min(A)=n takie,że n>0
1. L(0) zachodzi (formuła 0 - nieparzysta ilość zer, formuła fałszywa, formuła 1 - parzysta ilość zer -formuła prawdziwa) , czyli 0 nie należy do A.
2. L(n). Z założenia wiemy, że n jest najmniejszym elementem A, więc L(n-1) zachodzi. Niech
\(\displaystyle{ \delta}\) ma głębokość n. Formułę możemy zapisać jako
\(\displaystyle{ \delta=\phi \psi}\). Rozważmy 4 przypadki:
a. w
\(\displaystyle{ \psi}\) jest parzyście wiele zer, a w
\(\displaystyle{ \phi}\) nieparzyście
b. w
\(\displaystyle{ \psi}\) i
\(\displaystyle{ \phi}\) jest po parzyście wiele zer.
c. w
\(\displaystyle{ \psi}\) i
\(\displaystyle{ \phi}\) jest po nieparzyście wiele zer.
d. przypadek symetryczny do a
a. głębokość(
\(\displaystyle{ \psi}\))q jest równoważne ~q=>~p)
[ Dodano: 22 Październik 2006, 13:32 ]
Formuła zbudowana z równoważności, nawiasów i zmiennych zdaniowych jest tautologią, jeśli każda zmienna występuje tam parzyście wiele razy.
(korzystam, z tego, że p=>q jest równoważne do ~q=>~p, czyli mamy udowodnić: jeśli istnieje zmienna, która wystepuje nieparzyście wiele razy, to formuła nie jest tautologią)
Zakładam, że każda zmienna występuje w formule nieparzyście wiele razy. Jeśli każda zmienna występuje nieparzyście wiele razy, to istnieje wartościowanie, dla którego mamy nieparzyście wiele zer (np. wartościowanie jednej zmiennej nieparzystej ustalamy na fałsz, a reszte wartościowań na prawdę), więc zgodnie z lematem istnieje wartościowanie dle którego formuła jest fałszywa, czyli jest nie jest tautologią.
c.n.d.