Utsagnslogikk og sannhetstabeller

Et utsagn er en setning som er enten sann (T) eller usann (F). Sammensatte utsagn bygges med konnektivene \(\neg\) (ikke), \(\land\) (og), \(\lor\) (eller), \(\rightarrow\) (impliserer) og \(\leftrightarrow\) (hvis og bare hvis). En sannhetstabell med \(n\) variabler har \(2^n\) rader. En tautologi er sann i alle rader, en motsigelse usann i alle rader, og en kontingens er verken.

Sentrale ekvivalenser:

Implikasjon: \(p \rightarrow q \equiv \neg p \lor q\)

Kontrapositiv: \(p \rightarrow q \equiv \neg q \rightarrow \neg p\)

De Morgan: \(\neg(p \land q) \equiv \neg p \lor \neg q\), \(\neg(p \lor q) \equiv \neg p \land \neg q\)

Distributiv: \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)

Bikondisjonal: \(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\)

To utsagn er logisk ekvivalente (\(P \equiv Q\)) når de har samme sannhetsverdi i alle rader, ekvivalent med at \(P \leftrightarrow Q\) er en tautologi. Husk at det omvendte \(q \rightarrow p\) IKKE er ekvivalent med \(p \rightarrow q\), men kontrapositivet \(\neg q \rightarrow \neg p\) er det.

Normalformer: CNF og DNF

En literal er en variabel eller dens negasjon. DNF (disjunktiv normalform) er en OR av AND-termer; CNF (konjunktiv normalform) er en AND av OR-klausuler. CNF er sentral i SAT-løsing fordi en formel er tilfredsstillbar nettopp når hver klausul har minst én sann literal.

Eksempel 1: Finn DNF og CNF for \(p \leftrightarrow q\) fra sannhetstabellen.

Sannhetstabell: \(p \leftrightarrow q\) er sann i radene (T,T) og (F,F), usann i (T,F) og (F,T).

DNF (les sann-radene som mintermer): (T,T) gir \((p \land q)\); (F,F) gir \((\neg p \land \neg q)\).

DNF: \((p \land q) \lor (\neg p \land \neg q)\).

CNF (les usann-radene som maxtermer): (T,F) gir \((\neg p \lor q)\); (F,T) gir \((p \lor \neg q)\).

CNF: \((\neg p \lor q) \land (p \lor \neg q)\).

Gyldige slutninger og feilslutninger

En slutning er gyldig hvis det er umulig at premissene er sanne og konklusjonen usann samtidig — ekvivalent med at \((P_1 \land \cdots \land P_n) \rightarrow Q\) er en tautologi.

Gyldige slutningsregler:

Modus ponens: \(p,\; p \rightarrow q \;\therefore\; q\)

Modus tollens: \(\neg q,\; p \rightarrow q \;\therefore\; \neg p\)

Hypotetisk syllogisme: \(p \rightarrow q,\; q \rightarrow r \;\therefore\; p \rightarrow r\)

Disjunktiv syllogisme: \(p \lor q,\; \neg p \;\therefore\; q\)

Feilslutninger (ugyldige): affirming the consequent (\(q, p\rightarrow q \therefore p\)) og denying the antecedent (\(\neg p, p\rightarrow q \therefore \neg q\)).

Bevismetoder

De fire kjernemetodene har hver sin eksplisitte struktur. Direkte: anta \(p\), utled \(q\). Kontrapositiv: bevis \(\neg q \rightarrow \neg p\). Motsigelse: anta \(\neg P\), utled en umulighet. Element-argument: for \(A \subseteq B\), ta vilkårlig \(x \in A\) og vis \(x \in B\).

Eksempel 2: Bevis ved kontrapositiv: «Hvis \(n^2\) er partall, så er \(n\) partall».

Kontrapositivet er: «Hvis \(n\) er oddetall, så er \(n^2\) oddetall».

Anta \(n\) er oddetall: \(n = 2k+1\) for et heltall \(k\).

\(n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\).

Dette har formen \(2m+1\), altså et oddetall. Kontrapositivet er bevist.

Siden kontrapositivet er ekvivalent med originalen, følger påstanden.

Eksempel 3: Element-argument for \(A \cap B \subseteq A \cup B\).

La \(x \in A \cap B\) være vilkårlig.

Per definisjon av snitt: \(x \in A\) og \(x \in B\).

Spesielt \(x \in A\), så per definisjon av union \(x \in A \cup B\).

Siden \(x\) var vilkårlig, gjelder \(A \cap B \subseteq A \cup B\).

Predikatlogikk og kvantorer

Predikater \(P(x)\) blir utsagn først når \(x\) bindes av en kvantor. \(\forall x\,P(x)\) («for alle») og \(\exists x\,P(x)\) («det finnes minst én»).

Kvantor-negasjon:

\(\neg \forall x\,P(x) \equiv \exists x\,\neg P(x)\)

\(\neg \exists x\,P(x) \equiv \forall x\,\neg P(x)\)

Oversettelse: \(\forall\) med implikasjon: \(\forall x\,(S(x) \rightarrow P(x))\). \(\exists\) med konjunksjon: \(\exists x\,(S(x) \land P(x))\).

Rekkefølge: \(\exists y \forall x\,P(x,y)\) er sterkere enn \(\forall x \exists y\,P(x,y)\) og er ikke ekvivalent.

Studieguide: Logikk og bevisteknikker

Studieguide: Logikk og bevisteknikker