Täydellisyyslause
Todistus > Propositiologiikan täydellisyyslauseen todistus

Olkoot  A ja  B_{1},B_{2},\dots ,B_{m} propositiolauseita, ja olkoon propositiolausejoukko 
 {\mathcal {J}}=\{B_{1},B_{2},\dots ,B_{m}\}. Propositiologiikan täydellisyyslause: jos kaikilla totuusjakaumilla  v pätee  v(A)=1, kun  v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1; niin  {\mathcal {J}}\vdash A.
Tehdään vastaoletus: kaikilla totuusjakaumilla  v pätee  v(A)=1, kun  v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1; ja toisaalta  {\mathcal {J}}\nvdash A.
Väite 1:  {\mathcal {J}}\cup \{\lnot A\} on ristiriidaton lausejoukko.
Tehdään väitteen 1 vastaoletus:   {\mathcal {J}}\cup \{\lnot A\} on ristiriitainen. Tällöin jollakin propositiolauseella  C pätee  {\mathcal {J}}\cup \{\lnot A\}\vdash C\land \lnot C. Propositiologiikan tunnettuja päättelysääntöjä soveltamalla saadaan  {\mathcal {J}}\cup \{\lnot A\}\vdash \lnot \lnot A ja edelleen  {\mathcal {J}}\vdash A. Ollaan päädytty ristiriitaan. Täten väite 1 pätee.
Koska  {\mathcal {J}}\cup \{\lnot A\} on ristiriidaton, niin sillä on Lindenbaumin lauseen nojalla maksimaalisesti ristiriidaton laajennus  {\mathcal {K}}, jolla  {\mathcal {J}}\cup \{\lnot A\}\subset {\mathcal {K}}.
Olkoon  v totuusjakauma siten, että kaikille atomilauseille  p_{0},p_{1},\dots  pätee
Väite 2: propositiolauseella  D pätee  v(D)=1 jos ja vain jos  D\in {\mathcal {K}}. Todistetaan väite 2 induktiolla propositiolauseen  D rakenteen suhteen.
D=p_{n}. Totuusjakauman  v määritelmän nojalla  v(D)=v(p_{n})=1 jos ja vain jos  p_{n}=D\in {\mathcal {K}}.
D=\lnot E. Induktio-oletus on, että  v(E)=1 jos ja vain jos  E\in {\mathcal {K}}, mikä on loogisesti yhtäpitävää sen kanssa, että  v(E)=0 jos ja vain jos  E\not \in {\mathcal {K}}.  v(D)=v(\lnot E)=1 jos ja vain jos  v(E)=0 jos ja vain jos  E\not \in {\mathcal {K}}. Lemman 2 nojalla  E\not \in {\mathcal {K}} jos ja vain jos  \lnot E=D\in {\mathcal {K}}.
D=(E\land F). Induktio-oletus on, että  v(E)=1 jos ja vain jos  E\in {\mathcal {K}} ja että  v(F)=1 jos ja vain jos  F\in {\mathcal {K}}.  v(D)=v(E\land F)=1 jos ja vain jos  v(E)=v(F)=1. Induktio-oletuksen nojalla  v(E)=v(F)=1 jos ja vain jos  E\in {\mathcal {K}} ja  F\in {\mathcal {K}}. Lemman 3 nojalla  E\in {\mathcal {K}} ja  F\in {\mathcal {K}} jos ja vain jos  (E\land F)=D\in {\mathcal {K}}.
D=(E\lor F). Induktio-oletus on, että  v(E)=1 jos ja vain jos  E\in {\mathcal {K}} ja että  v(F)=1 jos ja vain jos  F\in {\mathcal {K}}.  v(D)=v(E\lor F)=1 jos ja vain jos  v(E)=1 tai  v(F)=1 jos ja vain jos  E\in {\mathcal {K}} tai  F\in {\mathcal {K}}. Lemman 4 nojalla  E\in {\mathcal {K}} tai  F\in {\mathcal {K}} jos ja vain jos  (E\lor F)=D\in {\mathcal {K}}.
D=(E\to F). Induktio-oletus on, että  v(E)=1 jos ja vain jos  E\in {\mathcal {K}} ja että  v(F)=1 jos ja vain jos  F\in {\mathcal {K}}.  v(D)=v(E\to F)=1 jos ja vain jos  v(E)=0 tai  v(F)=1 jos ja vain jos  E\not \in {\mathcal {K}} tai  F\in {\mathcal {K}}. Lemman 5 nojalla  E\not \in {\mathcal {K}} tai  F\in {\mathcal {K}} jos ja vain jos  (E\to F)=D\in {\mathcal {K}}.
D=(E\leftrightarrow F). Induktio-oletus on, että  v(E)=1 jos ja vain jos  E\in {\mathcal {K}} ja että  v(F)=1 jos ja vain jos  F\in {\mathcal {K}}.  v(D)=v(E\leftrightarrow F)=1 jos ja vain jos joko  v(E)=v(F)=1 tai  v(E)=v(F)=0 jos ja vain jos joko  E\in {\mathcal {K}} ja  F\in {\mathcal {K}} tai  E\not \in {\mathcal {K}} ja  F\not \in {\mathcal {K}}. Lemman 6 nojalla joko  E\in {\mathcal {K}} ja  F\in {\mathcal {K}} tai  E\not \in {\mathcal {K}} ja  F\not \in {\mathcal {K}} jos ja vain jos  (E\leftrightarrow F)=D\in {\mathcal {K}}.
Täten väite 2 todistettiin päteväksi.
Koska  \lnot A\in {\mathcal {K}} ja koska  \{B_{1},B_{2},\dots ,B_{m}\}\subset {\mathcal {K}}, niin väitteen 2 nojalla totuusjakaumalla  v pätee  v(\lnot A)=v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1 ja siis  v(A)=0. Ollaan saatu ristiriita. Siis alkuperäinen väite eli propositiologiikan täydellisyyslause pätee.  \square