Jak udowodnić równoważność dowolnej formuły z formułą w postaci alternatywno-koniunkcyjnej
: 27 lip 2021, o 18:17
Dzień dobry,
pytanie jak w tytule.
Moja propozycja jest następująca:
Definiujemy zbiór \(\displaystyle{ A }\) zawierający wszystkie formuły dające się utworzyć ze zmiennych zdaniowych z pewnego zbioru \(\displaystyle{ B}\).
\(\displaystyle{ A_{1}=B }\)
\(\displaystyle{ \vdots }\)
\(\displaystyle{ A_{n}=A_{n-1} \cup \left\{ \neg \Phi_{1} : \Phi_{1}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \vee \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \wedge\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \Rightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \Leftrightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\} }\)
I pokazujemy indukcyjnie, że \(\displaystyle{ \forall_{n\in\mathbb{N}} }\) dowolny element ze zbioru \(\displaystyle{ A_{n} }\) jest równoważny pewnej formule w postaci alternatywno-koniunkcyjnej. Zatem w drugim kroku dowodu indukcyjnego, w tezie musimy rozpatrzyć 6 przypadków:
\(\displaystyle{ 1.\quad \Phi\in A_{n} }\)
\(\displaystyle{ 2.\quad \Phi\in\left\{ \neg\Phi_{1} : \Phi_{1}\in A_{n}\right\} }\)
\(\displaystyle{ 3.\quad \Phi\in\left\{ \Phi_{1}\vee\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 4.\quad \Phi\in\left\{ \Phi_{1}\wedge\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 5.\quad \Phi\in\left\{ \Phi_{1} \Rightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 6.\quad \Phi\in\left\{ \Phi_{1} \Leftrightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
Pierwszy i trzeci są oczywiste. Mam problem z udowodnieniem przypadku drugiego, który wydaje się mieć kluczowe znaczenie przy dowodzie przypadków: 4, 5, 6, gdzie można skorzystać z pewnych tautologii.
Przypadek drugi zaczęłam rozpisywać tak:
\(\displaystyle{ \Phi_{1} }\) z założenia ma postać alternatywno-koniunkcyjną, więc przyjmijmy \(\displaystyle{ \Phi_{1} : \left( \Psi_{1,1}\wedge\dots\wedge\Psi_{1,i}\right)\vee\dots\vee\left( \Psi_{j,1}\wedge\dots\wedge\Psi_{j,k}\right) }\)
wtedy \(\displaystyle{ \neg \Phi_{1} : \left( \neg\Psi_{1,1}\vee\dots\vee\neg\Psi_{1,i}\right)\wedge\dots\wedge\left( \neg\Psi_{j,1}\vee\dots\vee\neg\Psi_{j,k}\right) }\) i nie wiem co z tym dalej zrobić.
Macie jakiś pomysł?
z góry dziękuję
pytanie jak w tytule.
Moja propozycja jest następująca:
Definiujemy zbiór \(\displaystyle{ A }\) zawierający wszystkie formuły dające się utworzyć ze zmiennych zdaniowych z pewnego zbioru \(\displaystyle{ B}\).
\(\displaystyle{ A_{1}=B }\)
\(\displaystyle{ \vdots }\)
\(\displaystyle{ A_{n}=A_{n-1} \cup \left\{ \neg \Phi_{1} : \Phi_{1}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \vee \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \wedge\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \Rightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\}\cup\left\{ \Phi_{1} \Leftrightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n-1}\right\} }\)
I pokazujemy indukcyjnie, że \(\displaystyle{ \forall_{n\in\mathbb{N}} }\) dowolny element ze zbioru \(\displaystyle{ A_{n} }\) jest równoważny pewnej formule w postaci alternatywno-koniunkcyjnej. Zatem w drugim kroku dowodu indukcyjnego, w tezie musimy rozpatrzyć 6 przypadków:
\(\displaystyle{ 1.\quad \Phi\in A_{n} }\)
\(\displaystyle{ 2.\quad \Phi\in\left\{ \neg\Phi_{1} : \Phi_{1}\in A_{n}\right\} }\)
\(\displaystyle{ 3.\quad \Phi\in\left\{ \Phi_{1}\vee\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 4.\quad \Phi\in\left\{ \Phi_{1}\wedge\Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 5.\quad \Phi\in\left\{ \Phi_{1} \Rightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
\(\displaystyle{ 6.\quad \Phi\in\left\{ \Phi_{1} \Leftrightarrow \Phi_{2} : \Phi_{1},\Phi_{2}\in A_{n}\right\} }\)
Pierwszy i trzeci są oczywiste. Mam problem z udowodnieniem przypadku drugiego, który wydaje się mieć kluczowe znaczenie przy dowodzie przypadków: 4, 5, 6, gdzie można skorzystać z pewnych tautologii.
Przypadek drugi zaczęłam rozpisywać tak:
\(\displaystyle{ \Phi_{1} }\) z założenia ma postać alternatywno-koniunkcyjną, więc przyjmijmy \(\displaystyle{ \Phi_{1} : \left( \Psi_{1,1}\wedge\dots\wedge\Psi_{1,i}\right)\vee\dots\vee\left( \Psi_{j,1}\wedge\dots\wedge\Psi_{j,k}\right) }\)
wtedy \(\displaystyle{ \neg \Phi_{1} : \left( \neg\Psi_{1,1}\vee\dots\vee\neg\Psi_{1,i}\right)\wedge\dots\wedge\left( \neg\Psi_{j,1}\vee\dots\vee\neg\Psi_{j,k}\right) }\) i nie wiem co z tym dalej zrobić.
Macie jakiś pomysł?
z góry dziękuję