Dowody na dowodach

[Jakub Gurak]

Wykażemy, że każde twierdzenie klasycznego rachunku zdań jest tautologią klasycznego rachunku zdań.

Podajemy najpierw aksjomatu klasycznego rachunku zdań.

Dla dowolnych formuł \(\displaystyle{ \alpha, \beta,\gamma}\) zakładamy aksjomaty:

1.\(\displaystyle{ \alpha \Rightarrow \left( \beta \Rightarrow \alpha \right).}\)

2.\(\displaystyle{ \left( \alpha \Rightarrow \left( \beta \Rightarrow \gamma \right) \right) \Rightarrow \left( \left( \alpha \Rightarrow \beta \right) \Rightarrow \left( \alpha \Rightarrow \gamma \right) \right).}\)

3.\(\displaystyle{ \left( \neg \alpha \Rightarrow \beta \right) \Rightarrow \left( \left( \neg \alpha \Rightarrow \neg \beta \right) \Rightarrow \alpha \right) .}\)

Aby przekonać się, że to są prawa pomocną jest tautologią \(\displaystyle{ \alpha \Rightarrow \left( \beta \Rightarrow \gamma \right) \Leftrightarrow \left( \alpha \wedge \beta \right) \Rightarrow \gamma.}\)

Wykażemy, że aksjomat 2 jest tautologią. Weźmy dowolne wartościowanie \(\displaystyle{ w}\) . Pokażemy, że przy tym wartościowanie cała formuła jest prawdziwa. Przypuśćmy dla dowodu nie wprost, że tak nie jest. Wtedy cała formuła jest wartościowanie na 0, czyli formuła \(\displaystyle{ \left( \alpha\Rightarrow \left( \beta \Rightarrow \gamma \right) \right)}\) przyjmuje wartość 1, a formuła \(\displaystyle{ \left( \alpha \Rightarrow \beta \right) \Rightarrow \left( \alpha \Rightarrow
\gamma \right) ,}\) jest wartościowana na 0, co oznacza, że \(\displaystyle{ w\left( \alpha \right)=1,w\left( \gamma \right)=0,}\) i ponieważ \(\displaystyle{ w\left( \alpha \Rightarrow \beta \right)=1,}\) więc musi być \(\displaystyle{ w\left( \beta \right)=1,}\), więc mając \(\displaystyle{ w\left( \alpha \right)=1=w\left( \beta \right),w\left( \gamma \right)=0,}\) otrzymujemy, że cały poprzednik implikacji przyjmuję wartość 0- sprzeczność. \(\displaystyle{ \square}\)

Dowodem formalnym formuły \(\displaystyle{ \alpha}\) nazywamy skończony ciąg formuł \(\displaystyle{ \alpha _{1}, \alpha _{2},\ldots, \alpha _{n}}\) taki, ze formuła \(\displaystyle{ \alpha}\) jest tym samym napisem co napis \(\displaystyle{ \alpha _{n},}\) a każda formuła \(\displaystyle{ \alpha _{i}}\) w tym ciągu jest aksjomatem klasycznego rachunku zdań lub powstaje z dwóch formuł występujących wcześniej w dowodzie po przez zastosowanie do nich reguły Modus Ponens.

Reguła Modus Ponens to formalne wnioskowanie, że jeżeli akceptujemy formułe \(\displaystyle{ \alpha}\) oraz formułę \(\displaystyle{ \alpha\Rightarrow\beta}\) to winniśmy również zaakceptować formułę \(\displaystyle{ \beta.}\)

Twierdzeniem klasycznego rachunku zdań nazywamy dowolną formułę, która ma dowód formalny z aksjomatów klasycznego rachunku zdań.

Możemy teraz udowodnić, że każde twierdzenie klasycznego rachunku zdań jest tautologią. Potrzebować będziemy dwa proste fakty.

Aksjomaty klasycznego rachunku zdań są tautologiami (pozostałe łatwe dowody nie wprost ).

Zastosowanie reguły Modus Ponens do tautologii daje tautologie.

Niech \(\displaystyle{ \alpha,\beta}\) będą formułami, tak, ze zarówno formuły \(\displaystyle{ \alpha , \alpha \Rightarrow \beta}\) są tautologiami. Pokażemy, że \(\displaystyle{ \beta}\) jest tautologią. Niech \(\displaystyle{ w}\) będzie dowolnym wartościowaniem. Przypuśćmy dla dowodu nie wprost, że \(\displaystyle{ w\left( \beta \right)=0}\) . Ponieważ \(\displaystyle{ \alpha}\) jest tautologią więc \(\displaystyle{ w\left( \alpha \right)=1.}\) Ponieważ \(\displaystyle{ w\left( \alpha \right)=1,}\) i \(\displaystyle{ w\left( \beta \right)=0,}\) więc z określenia implikacji \(\displaystyle{ w\left( \alpha\Rightarrow \beta \right)=0,}\) co jest sprzeczne z tym, że formuła \(\displaystyle{ \alpha \Rightarrow \beta}\) jest tautologią.

PIĘKNY DOWÓD:

Aby dowieść twierdzenie, rozważmy dowolną formułę \(\displaystyle{ \alpha}\) będącą twierdzeniem klasycznego rachunku zdań. Istnieje zatem jej dowód formalny. Niech \(\displaystyle{ \alpha _{1}, \alpha _{2},\ldots, \alpha _{n}}\) będzie dowodem formalnym formuły \(\displaystyle{ \alpha.}\) Wykażemy, indukcyjnie, że \(\displaystyle{ \alpha}\) jest tautologią. Indukcję poprowadzimy że względu na długość dowodu (czyli ilość formuł w ciągu będącym dowodem ).

Jeśli \(\displaystyle{ \alpha}\) ma długość \(\displaystyle{ 1}\), to \(\displaystyle{ \alpha _{1}= \alpha,}\) to \(\displaystyle{ \alpha _{1}}\) musi być jednym z aksjomatów( gdyż nie może powstać przez zastosowanie reguły Modus Ponens do formuł występujących wcześniej w dowodzie, gdyż to jest pierwsza formuła ). Ponieważ aksjomaty klasycznego rachunku zdań są tautologiami, więc \(\displaystyle{ \alpha}\) jest tautologią.

Krok indukcyjny:
Weźmy dowolne \(\displaystyle{ n}\) naturalne, \(\displaystyle{ n \ge 2}\), i przypuśćmy, że wszystkie formuły o dowodach silnie krótszych od \(\displaystyle{ n}\) są tautologiami. Pokażemy, że wszystkie formuły o dowodach długości \(\displaystyle{ n}\) są tautologiami. Weźmy dowolną formułę \(\displaystyle{ \alpha}\) mającą dowód formalny długości \(\displaystyle{ n}\). Niech \(\displaystyle{ \alpha _{1}, \alpha _{2},\ldots, \alpha _{n}= \alpha}\) będzie dowodem formuły \(\displaystyle{ \alpha.}\) Jeśli \(\displaystyle{ \alpha}\) jest aksjomatem, to jest tautologią. W przeciwnym wypadku powstaje z dwóch formuł \(\displaystyle{ \alpha _{m}, \alpha _{k}}\) występujących wcześniej w dowodzie po przez zastosowanie do nich reguły Modus Ponens. Ponieważ \(\displaystyle{ \alpha _{m}}\) występuje w dowodzie \(\displaystyle{ \alpha}\), więc ciąg formuł \(\displaystyle{ \alpha _{1}, \alpha _{2},\ldots, \alpha _{m}}\) jest dowodem formuły \(\displaystyle{ \alpha _{m}.}\) Ponieważ jest to dowód długości silnie krótszej od \(\displaystyle{ n}\), więc z założenia indukcyjnego \(\displaystyle{ \alpha _{m}}\) jest tautologią. Analogiczne rozumowanie dla \(\displaystyle{ \alpha _{k}}\) pokazuje, że \(\displaystyle{ \alpha _{k}}\) jest tautologią. Wobec czego z faktu dowiedzionego tuż przed tym dowodem wynika, że \(\displaystyle{ \alpha}\) jest tautologią jako formuła otrzymana po zastosowaniu reguły Modus Ponens do tautologii. Wobec dowolności wyboru formuły \(\displaystyle{ \alpha}\) wszystkie formuły o dowodach długości \(\displaystyle{ n}\) są tautologiami. Krok indukcyjny został dowiedziony.

Na zasadzie indukcji twierdzenie jest udowodnione.\(\displaystyle{ \square}\)

Zachodzi wynikanie w drugą stronę(ale dowodu nie znam), co oznacza, że w rachunku zdań tautologie są tym samym co twierdzenia.

Napiszę jeszcze parę słów o logice intuicjonistycznej( tak to się niestety nazywa). Tutaj aksjomatami są dokładnie pierwsze dwa aksjomaty klasycznego rachunku zdań. Twierdzeniami takiej teorii są formuły, które da się dowieść przy pomocy reguły Modus Ponens z przyjętych tutaj aksjomatów .

Twierdzenie:

Każde twierdzenie logiki intuicjonistycznej jest twierdzeniem klasycznego rachunku zdań.

Dowód:

Każdy dowód logiki intuicjonistycznej jest również dowodem klasycznego rachunku zdań

I to wymaga dowodu.

Pomyślę nad tym potem, trzeba będzie to udowodnić (pewnie indukcyjnie) .

[matmatmm]

Każdy dowód logiki intuicjonistycznej jest również dowodem klasycznego rachunku zdań

Co tu jest trudnego? Zbiór aksjomatów logiki intuicjonistycznej \(\displaystyle{ \Gamma}\) zawiera się w zbiorze aksjomatów klasycznego rachunku zdań \(\displaystyle{ \Delta}\). Jeśli ciąg \(\displaystyle{ \alpha_1,\ldots,\alpha_n}\) jest dowodem w logice intuicjonistycznej, to biorąc dowolne \(\displaystyle{ \alpha_i}\) mamy \(\displaystyle{ \alpha_i\in\Gamma\subseteq\Delta}\) lub \(\displaystyle{ \alpha_i}\) powstaje przez modus ponens. Koniec dowodu.

[Jakub Gurak]

Wygląda na to, że tak, dzięki. Nie wiedziałem do końca jak się za to zabrać, i pachniało mi to dowodem indukcyjnym, że krok po kroku budujemy dowody uboższej teorii( o jeden aksjomat) jako dowody bogatszej teorii. Dzięki, nie pomyślałbym, że można tak prosto, zabierałbym się za to pewnie indukcyjnie, ale chyba nie warto jednak.