Modele Kripkego

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Pokażemy, za pomocą modeli Kripkego, że następujące zdanie nie jest tautologią w logice intuicjonistycznej.

$$\phi=((p\rightarrow q)\rightarrow p)\rightarrow p).$$

W tym celu, wystarczy wskazać model Kripkego $K$ wraz ze stanem $a$, w którym powyższe zdanie nie jest wymuszone, tj. $a\not{\Vdash}\phi$.

Rozważmy model $K$ ze stanami: $a, b, c, d$, jak na obrazku poniżej.kripke

W tym modelu, $p$ jest wymuszone jedynie w stanach $b$ oraz $d$, a $q$ jest wymuszone jedynie w stanie $b$. Przez $\not p$ oznaczamy, że w tym stanie nie jest wymuszone $p$, i podobnie dla $q$. Warunek jaki powinien zachodzić w strukturze Kripkego jest taki, że jeżeli $p$ jest wymuszone w jakimś stanie, to także we wszystkich większych (ale może być tak że $p$ nie jest wymuszone w jakimś stanie, a jest wymuszone w większych). Na rysunku dowolnego modelu Kripkego, w każdym stanie powinno się pojawić $p$ lub $\not p$, tj. w każdym stanie albo jest wymuszone $p$, albo $p$ nie jest wymuszone.

W stanie $a$ wymuszone jest $((p\rightarrow q)\rightarrow p)$, tj. $$a\Vdash ((p\rightarrow q)\rightarrow p),$$ bo:

  1. $b\Vdash p\rightarrow q$ oraz $b\Vdash p$
  2. $d\not{\Vdash} p\rightarrow q$, bo $d\Vdash p$, a nie zachodzi $d\Vdash q$.
  3. Podobnie w stanach $a,c$: $a\not{\Vdash} p\rightarrow q$ oraz $c\not{\Vdash} p\rightarrow q$. Te własności wynikają z tzw. “monotoniczności”: gdyby $a\Vdash p\rightarrow q$, to też by było $d\Vdash p\rightarrow q$, bo $d\ge a$.

W szczególności, dla wszystkich $s\ge a$, jeżeli $s\Vdash p\rightarrow q$ to $s\Vdash p$. Tak więc, $a\Vdash ((p\rightarrow q)\rightarrow p),$ ale  $a\not\Vdash p$. Zatem

$$a\not\Vdash ((p\rightarrow q)\rightarrow p)\rightarrow p).$$

Tak więc, formuła $\phi$ nie jest tautologią intuicjonistycznej logiki zdaniowej.

Zadanie. Udowodnić, że formuła $\neg (p\land q)\rightarrow (\neg p\lor \neg q)$$ nie jest tautologią intuicjonistycznej logiki zdaniowej.

 

One thought on “Modele Kripkego”

  1. Dzień dobry,
    wszystko jest jasne aż do punktu 3 w podsumowaniu.
    Zupełnie nie rozumiem dlaczego skoro ‘a’ nie wymusza p -> q to z tego wynika, że ‘a’ nie wymusza (((p->q)->q)->q)

Leave a Reply

Your email address will not be published. Required fields are marked *