8.4 Kiel pruvi nevalidecon

Natura dedukto aldonas procedon por pruvi ke rezonado estas korekta, sed, kial oni pruvas ke rezonado estas malkorekta? Natura dedukto tion ne ebligas.

Jen la nuna okazo: oni havas derivon $\Gamma\vdash A$, kaj kredas ke ekzistas modelo (aro da valoroj) kiu certigas $\Gamma$ -gamma- sed ne al $A$. Nu, oni nur devas trovi ĝin por pruvi ke tiu derivo estas nevalida. Al tiu modelo oni nomas kontraŭmodelo, kaj estas trovebla per pluraj rimedoj. Mi kredas ke la plej facila estas intuicie: provadi kelkajn valorojn kiuj ŝajnas kontraŭmodelon, ĝis oni trovu unu.

Ekzemple, $\neg P\Rightarrow\neg Q,\ \neg Q\vdash\neg P\vee Q$ estas nevalida ($\nvDash$), ĉar kiam $P$ certas kaj $Q$ falsas, tio el maldekstre (premisoj) estas certa, sed tio el dekstre (konkludo) estas falsa, do $\neg P\vee Q$ ne estas sekvo de tio el maldekstre.