Kiedy formuła jest tautologia?

[Tomasz Rużycki]

Niezbyt trudne, ale wg mnie przyjemne zadanie.

Podac wkw na to, by \(\displaystyle{ \psi(p_1,\ldots ,p_n)}\), ktora zawiera same '\(\displaystyle{ \Leftrightarrow}\)' byla tautologia.

[boo007]

Zmienna \(\displaystyle{ p_{i}}\) musi występować parzystą ilość razy w formule. Dowód indukcyjny po głębokości formuły (napiszę wieczorem ).

[Tomasz Rużycki]

Tak tez rozwiazalismy to zadanie pare tygodni temu.

[boo007]

Mógłbyś zdefiniować głębokość formuły?? Ja nie pamiętam co zaliczamy do formuły o głębokości 0 (same zmienne zdaniowe, czy \(\displaystyle{ \top, \bot}\) i zmienne zdaniowe).

[Tomasz Rużycki]

Wybacz, ale nie, nie spotkalem sie z tym pojeciem. Myslalem, ze chodzi Ci o ilosc zdan tego samego 'typu'...

[boo007]

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.

[mozart_smg]

Zastanawia mnie poniższa linijka:

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.
c.n.d.

Dlaczego w formule FAŁSZ, o głębokości 0, występuje nieparzysta, a w formule PRAWDA parzysta ilość zer?