---
title: Logika nr 110
---
Zadanie 110:
Pokaż że zbiór {$\vee$ $\neg$}
Skorzystamy z omówionego na wykładzie fartu, że zbiór {$\vee \wedge \neg$} jest zupełny. Za pomocą tego pokażmy, że zbiór {$\vee \neg$} jest zupełny.
Teza: dla każdej formuły zbudowanej z dowolnych zmiennych zdaniowych oraz spójników ze zbioru {$\vee \wedge \neg$} istnieje równoważna formuła zbudowana ze zmiennych zdaniowych oraz spójników {$\vee \neg$}
1. Zdefiniujmy zbiór formuł F
Zbiór formuł F jest najmniejszym zbiorem, takim że:
* dowolna zmienna zdaniowa p $\in$ F
* dla dowolnych $\phi, \phi_1, \phi_2 \in$ F zachodzi ($\neg \phi$) $\in$ F, ($\phi_1 \vee \phi_2$) $\in$ F, ($\phi_1 \wedge \phi_2$) $\in$ F
2. Zasada indukcji
Niech X będzie takim zbiorem, że:
* dowolna zmienna zdaniowa p $\in$ F
* dla dowolnych $\phi, \phi_1, \phi_2$ jeżeli $\phi \in$ X, $\phi_1 \in$ X, $\phi_2 \in$ X, to ($\neg \phi$) $\in$ X, ($\phi_1 \vee \phi_2$) $\in$ X, ($\phi_1 \wedge \phi_2$) $\in$ X
Wtedy X = F, co oznacza, że X zawiera wszystkie formuły ze zbioru F
3. Definicja zbioru X
Niech X = $\{$$\phi \in$ X | istnieje równoważna formule $\phi$ formuła $\phi'$ zbudowana ze zmiennych zdaniowych oraz spójników {$\vee \neg$}$\}$
4. Wprowadzamy definicję pomocniczą:
Niech formuła $\phi$ nazywa się "dobra" jeśli jest zbudowana wyłącznie ze zmiennych zdaniowych oraz spójników {$\vee \neg$}
5. Podstawa indukcji
Niech $\phi$ = p dla pewnego p $\in$ F. Wtedy $\phi'$ = p
$p \equiv p$
$\phi \equiv \phi'$. $\phi'$ jest formułą "dobra", więc $\phi \in$ X
6. Krok indukcyjny
Weźmy dowolne $\phi, \phi_1, \phi_2$ i załóżmy że są one w zbiorze X. Z założenia mamy, że istnieją "dobre" $\phi', \phi_1', \phi_2'$. Zatem $\phi \equiv \phi'$, $\phi_1 \equiv \phi_1'$, $\phi_2 \equiv \phi_2'$
6.1 Pokażmy, że $(\neg \phi \in)$ X
Skoro $\phi \equiv \phi'$, to $\neg \phi \equiv \neg \phi'$. Formuła $\neg \phi'$ jest "dobra", więc $\phi \in$ X
6.2 Pokażmy, że ($\phi_1 \vee \phi_2$) $\in$ X
$\phi_1 \vee \phi_2 \equiv \phi_1' \vee \phi_2'$,
$\phi_1' \vee \phi_2'$ jest formułą "dobrą", więc ($\phi_1 \vee \phi_2$) $\in$ X
6.3 Pokażmy, że ($\phi_1 \wedge \phi_2$) $\in$ X
Zauważmy, że ($\phi_1 \wedge \phi_2$) $\equiv$ $\neg(\neg \phi_1 \vee \neg \phi_2)$
Z założenia wynika, że ($\phi_1 \wedge \phi_2$) $\equiv$ $\neg(\neg \phi_1 \vee \neg \phi_2)$ $\equiv$ $\neg(\neg \phi_1' \vee \neg \phi_2')$ , a ta formuła jest "dobra"
7. Na mocy twierdzenia o indukcji strukturalnej X = F, więc dla każdej formuły $\phi \in$ X istnieje równoważna formuła "dobra". Ponieważ zbiór spójników {$\vee \wedge \neg$} jest zupełny, to zbiór {$\vee \neg$} również jest zupełny