Hoofdstuk 8 Logica

8.1 Propositielogica

8.1.1 Uitspraken

Axioma’s

• • Een uitspraak is ofwel waar ofwel vals.

Verklaring symbolen

• • \(p, q\) : uitspraken

• • \(\neg p\) : niet \(p\) (negatie)

• • \(p \wedge q\) : \(p\) en \(q\) (conjunctie)

• • \(p \vee q\) : \(p\) of \(q\) (disjunctie)

• • \(p \rightarrow q\) : als \(p\) dan \(q\) (implicatie)

• • \(p \leftrightarrow q\) : \(p\) als en slechts als \(q\) (equivalentie)

Definities

• • \(p\) tautologie als \(p\) altijd waar

• • \(p\) contradictie als \(p\) altijd vals

• • \(p \Leftrightarrow q\) zijn equivalente uitspraken als \(p \leftrightarrow q\) is een tautologie

8.1.2 Stellingen

• • \(\neg (\neg p)\:\Leftrightarrow \: p\)

• • \((p\:\rightarrow \: q) \:\Leftrightarrow \: (\neg p \vee q)\)

• • \(((p \:\rightarrow \: q)\wedge p)\:\rightarrow \: q\)

• • \(((p \:\rightarrow \: q)\wedge \neg q)\:\rightarrow \: \neg p\)

• • \((\neg (p \:\wedge \: q)\wedge p)\:\rightarrow \: \neg q\)

• • \((p \vee q)\wedge \neg q)\:\rightarrow \:p\)

Contrapositie van de implicatie

\[(p\:\rightarrow \: q) \:\Leftrightarrow \: (\neg q \:\rightarrow \: \neg p)\]

Wetten van De Morgan

\begin{align*} \neg (p\wedge q)\: & \Leftrightarrow \:\neg p \vee \neg q \\ \neg (p \vee q)\: & \Leftrightarrow \:\neg p \wedge \neg q \end{align*}

Commutativiteiten

\begin{align*} p \wedge q & \Leftrightarrow q \wedge p \\ p \vee q & \Leftrightarrow q \vee p \\ (p \:\Leftrightarrow \: q) & \Leftrightarrow (q \:\Leftrightarrow \: p) \end{align*}

Associativiteiten

\begin{align*} (p \wedge q)\wedge r & \Leftrightarrow p \wedge (q \wedge r) \\ (p \vee q) \vee r & \Leftrightarrow p \vee (q \vee r) \\ ((p \:\Leftrightarrow \: q)\: \Leftrightarrow \: r) & \Leftrightarrow (p\:\Leftrightarrow \: (q \:\Leftrightarrow \: r)) \end{align*}

Distributiviteiten

\begin{align*} p \wedge (q\vee r) & \Leftrightarrow (p \wedge q) \vee (p\wedge r) \\ p \vee (q\wedge r) & \Leftrightarrow (p \vee q) \wedge (p\vee r) \end{align*}

Transitiviteiten

\begin{align*} ((p \:\rightarrow \: q) \wedge (q\:\rightarrow \: r)) & \rightarrow (p \:\rightarrow \: r) \\ ((p \:\Leftrightarrow \: q)\wedge (q\:\Leftrightarrow \: r)) & \rightarrow (p \:\Leftrightarrow \: r) \\ \end{align*}

8.1.3 Uitspraken met kwantoren

\begin{align*} \neg (\forall x \in A:p(x)) &\Leftrightarrow \exists \: x \in A: \neg p(x)\\ \neg (\exists x \in A:p(x)) &\Leftrightarrow \forall \: x \in A: \neg p(x) \end{align*}