A calculus of the absurd

21.2 Logics

21.2.1 Foundational things

These are the meta-definitions for any given logic (that is, they are kind of a “template” for defining a specific logic). Once we answer these questions, we have a logic!

  • Definition 21.2.1 An interpretation assigns a value to specified free symbols in a formula.

  • Definition 21.2.2 An interpretation is suitable for a formula if it binds all free variables.

  • Definition 21.2.3 Given a formula \(F\) (or a set of formulas), a model \(M\) is an interpretation for which \(F\) is true.

    In formulas, this is either

    \begin{align} & \mathcal {A}(F) = 1 \\ & \mathcal {A} \vDash F \end{align}

  • Definition 21.2.4 Logical consequence If for every interpretation whenever \(F\) is true, \(G\) is too, then we write

    \begin{align} F \vDash G \end{align}

  • Definition 21.2.5 Logical equivalence ???

    \begin{align} & F \vDash G \\ & M \vDash G \end{align}

  • Definition 21.2.6 Tautology notation If \(F\) is a tautology (informally it is always true) then we write

    \begin{equation} \vDash F \end{equation}

    That is, \(F\) cannot be derived

  • Definition 21.2.7 Unsatisfiability If \(F\) is unsatisfiable we write

    \begin{equation} F \vDash \bot \end{equation}

  • Theorem 21.2.1 Relation between tautology and unsatisfiability We can prove that

    \begin{equation} \big ( \vDash F \big ) \iff \big (\lnot F \vDash \bot \big ) \end{equation}

    This apparently follows from what this means.

  • Theorem 21.2.2 Normal forms The statements of the theorem is that we can always write any formula in a normal form.

    Consider some formula in propositional logic, for which we have a truth table. We then consider the \(1\) entries. For these rows, we might have something in the form

    \begin{equation} \begin{pmatrix} A & B & C & F \\ 0 & 1 & 0 & 1 \end {pmatrix} \end{equation}

    Then we add a term which is one if and only if \(A = 0, B = 1, C = 0\). For example, in this case we would have something that looks a bit like

    \begin{equation} (\lnot A \land B \land \lnot C) \lor .... \end{equation}

    For conjunctive normal form, this is a little more complex, but we could do something like

    \begin{equation} (A \lor B \lor C) \land (...) \land ... \land (...) \end{equation}

    then instead of making terms one when the conditions trigger, we make terms zero when the conditions are not triggered.