Logika intuicjonistyczna

Niektórzy logicy mają wątpliwości co do tego, czy powinniśmy przyjmować schemat dowodu niewprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające związki z teorią obliczeń (patrz izomorfizm Curryego-Howarda).

Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez $I_\Rightarrow$ to zbiór tych formuł, które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.

Definicja 7.1

Aksjomaty $I_\Rightarrow$

$(\phi \Rightarrow (\psi \Rightarrow \phi))$ (formuła ta jest nazywana aksjomatem K),
$(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow ((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) )$ (formuła ta jest nazywana aksjomatem S).

W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników $\wedge, \vee$ oraz $\neg$ . Dla uproszczenia zajmiemy się jedynie formułami, w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej, w którym jedynymi spójnikami są $\Rightarrow$ , da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca, za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.

Twierdzenie 7.2

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

Dowód

Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem twierdzenia klasycznego rachunku zdań.

Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy $\Rightarrow$ , które nie należą do $I_\Rightarrow$ , pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:

$((p \Rightarrow q) \Rightarrow p ) \Rightarrow p.$

W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.
W poniższych zadaniach udowodnimy poniższe twierdzenie

Twierdzenie 7.3

Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.

Zauważmy, że oznacza to również, że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika $\neg$ .
Aby udowodnić twierdzenie 7.3, zdefiniujemy jeszcze jedną logikę którą nazwiemy $I_3$ . Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.

Definicja 7.4

Matrycą $\mathbb{M}_3$ będziemy nazywać zbiór trójelementowy $M_3=\{0,1,2\}$ , w którym 2 jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje $\Rightarrow$ zdefiniowaną następująco

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

W przypadku rozważanej matrycy $\mathbb{M}_3$ wartościowanie będzie funkcją przypisującą zmiennym zdaniowym elementy zbioru $M_3$ . Podobnie jak dla logiki klasycznej wartościowanie zmiennych rozszzerzamy na wartościowanie formuł zgodnie z tabelą 7.4.

Przykład 7.5

Dla wartościowania $v$ takiego, że $v(p)=2, v(q)=1, v(r)=0$ formuła

$(p \Rightarrow q) \Rightarrow r$

przyjmuje wartość 0.

Definicja 7.6

Tautologią logiki $I_3$ będziemy nazywać każdą formułę implikacyjną, która przy każdym wartościowaniu zmiennych w $M_3$ przyjmuje wartość 2.

Ćwiczenie 7.1

Udowodnij, że aksjomaty S i K są tautologiami $I_3$ .

Rozwiązanie

Ćwiczenie jest elementarne, wystarczy sprawdzić wszystkie możliwości.

Ćwiczenie 7.2

Udowodnij, że jeśli formuła postaci $\phi \Rightarrow \psi$ oraz formuła ${\phi}$ są tautologiami $I_3$ , to formuła ${\psi}$ jest tautologią $I_3$ .

Rozwiązanie

Weżmy dowolne wartościowanie

$\displaystyle v$ w

$\displaystyle \mathbb{M}_3$ . Ponieważ formuły

$\displaystyle \phi \Rightarrow \psi$ oraz

$\displaystyle \phi$ są tautologiami

$\displaystyle I_3$ , to

$\displaystyle v(\phi \Rightarrow \psi) = v(\phi) = 2$ . Zobaczmy teraz jak może być wartościowana formuła

$\displaystyle \psi$ . Przypadek

$\displaystyle v(\psi)=0$ możemy wykluczyć, gdyż wtedy zgodnie z tabelą interpretacji 7.4 otrzymalibyśmy

$\displaystyle v(\phi \Rightarrow \psi) = 0$ . Podobnie, w przypadku

$\displaystyle v(\psi)=1$ otrzymalibyśmy

$\displaystyle v(\phi \Rightarrow \psi) = 1$ . Wobec tego pozostała jedynie możliwość

$\displaystyle v(\psi)=2$ i wtedy rzeczywiście

$\displaystyle v(\phi \Rightarrow \psi) = 2$ . Z dowolności wyboru

$\displaystyle v$ wynika, że

$\displaystyle v(\psi)=2$ dla dowolnego wartościowania, a więc

$\displaystyle \psi$ jest tautologią

$\displaystyle I_3$ .

Ćwiczenie 7.3

Udowodnij, że każde twierdzenie logiki $I_\Rightarrow$ jest tautologią $I_3$ .

Podpowiedź

Przeprowadź rozumowanie indukcyjne, ze względu na długość dowodu. Pomocne będą poprzednie zadania.

Rozwiązanie

Rozwiązanie jest analogiczne do rozwiązania ćwiczenia 4.1.

Ćwiczenie 7.4

Sprawdź, czy prawo Pierce'a jest tautologią $I_3$ .

Podpowiedź

Nie jest.

Rozwiązanie

Dla wartościowania

$v$ takiego, że

$v(p)=1$ i

$v(q)=0$ kolejne formuły przyjmują następujace wartości

$v(p\Rightarrow q) =0$

$v((p\Rightarrow q)\Rightarrow p) =2$

$v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1$

Wobec tego prawo Pierce'a nie jest tautologią

$I_3$ , gdyż wyróżnioną wartością prawdy

$I_3$ w jest 2.

Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę $I_3$ taką, że każda twierdzenie intuicjonizmu jest tautologią $I_3$ . Skoro prawo Pierce'a nie jest tautologią $I_3$ , to nie jest też twierdzeniem $I_\Rightarrow$ .

UWAGA! W dalszej części będziemy się posługiwać wyłącznie logiką klasyczną.