Jak udowodnić równoważność dowolnej formuły z formułą w postaci alternatywno-koniunkcyjnej

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
ehogarth
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 16 lut 2021, o 15:57
Płeć: Kobieta
wiek: 22
Podziękował: 3 razy

Jak udowodnić równoważność dowolnej formuły z formułą w postaci alternatywno-koniunkcyjnej

Post autor: ehogarth »

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ę
matmatmm
Użytkownik
Użytkownik
Posty: 2280
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Re: Jak udowodnić równoważność dowolnej formuły z formułą w postaci alternatywno-koniunkcyjnej

Post autor: matmatmm »

Proponuję wzmocnić tezę indukcyjną do następującej: Każda formuła jest równoważna pewnej formule w koniunkcyjnej postaci normalnej oraz pewnej formule w dysjunkcyjnej postaci normalnej. Wtedy przypadek 2 idzie dość łatwo z praw de Morgana. Gdy dowodzimy w kroku indukcyjnym równoważności z formułą CNF, to z założenia indukcyjnego "bierzemy" formułę w DNF i odwrotnie.
ehogarth pisze: 27 lip 2021, o 18:17 \(\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) }\)
Po pierwsze ten zapis z dwukropkiem jest niepoprawny. Po drugie lepiej wprowadzić takie indeksy
\(\displaystyle{ \Phi_{1}=\left( \Psi_{1,1}\wedge\dots\wedge\Psi_{1,i_1}\right)\vee\dots\vee\left( \Psi_{j,1}\wedge\dots\wedge\Psi_{j,i_j}\right) }\)
Po trzecie warto wspomnieć, że są to literały.
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ć.
Znów zapis z dwukropkiem jest niepoprawny. Wypadałoby napisać, że \(\displaystyle{ \neg \Phi_{1}}\) jest formułą równoważną (ale nie równą) formule
\(\displaystyle{ \left( \neg\Psi_{1,1}\vee\dots\vee\neg\Psi_{1,i_1}\right)\wedge\dots\wedge\left( \neg\Psi_{j,1}\vee\dots\vee\neg\Psi_{j,i_j}\right) }\)
ODPOWIEDZ