The Law of Excluded Middle tells us that if a string of a formal language $s\in L$ is a proposition, then the valuation function can take only two values - either the proposition is true or false: $[[s]]_I\in \mathbb B$ for all interpretations. This can also be expressed using the satisfaction relation: either we have $\models s$ or $\not{\models}s$.

However, we still do not know, how the satisfaction relation changes when we use the syntactical rules for building propositions. The following definition closes the gaps by defining the semantics of the propositional logic.

Definition: Semantics of PL0

Let $L$ be a formal language with the syntax of propositional logic $PL0$ and let $L'\subset L$ be the subset of $L$ which consists of propositions (i.e. Boolean constants, Boolean variables, and Boolean terms). The semantics of $PL0$* is defined recursively as its syntax was. We provide two equivalent definitions - one using interpretations "$I$" with the corresponding valuation functions $[[]]_I$, another using the satisfaction relation "$\models$" of $PL0$:

Definition I

For all interpretations of $PL0$ "$I$" of propositions, the corresponding valuation functions "$[[]]_I$" are defined as follows: * Boolean constants: * $[[ 1 ]]_I=1.$ * $[[ 0 ]]_I=0.$ * Boolean variables $x$: * $[[ x ]]_I=1$ if and only if $x=1.$ * Boolean terms $\phi,\psi$ under special symbols "$\neg\phi,$” “$\phi\vee\psi,$” “$\phi\wedge\psi,$” “$\phi\Rightarrow\psi,$” “$\phi\Leftrightarrow \psi$”: * Negation: $[[ \neg\phi ]]_I=1$ if and only if $[[\phi ]]_I=0.$ * Disjunction: $[[\phi \vee \psi]]_I=1$ if and only if $[[\phi ]]_I=1$ or $[[\psi ]]_I=1.$ * Conjunction: $[[\phi \wedge\psi]]_I=1$ if and only if $[[\phi ]]_I=1$ and $[[\psi ]]_I=1.$ * Implication: $[[\phi \Rightarrow\psi]]_I=1$ if and only if $[[\phi ]]_I=0$ or $[[\psi ]]_I=1.$ * Equivalence: $[[\phi \Leftrightarrow \psi]]_I=1$ if and only if $[[\phi \Rightarrow\psi]]_I=1$ and $[[\psi \Rightarrow\phi]]_I=1.$

Equivalent Definition II

The satisfaction relation of $PL0$ "$\models$" is given by: * Boolean Constants: * $\;\models 1.$ * $\not{\models}\; 0.$ * Boolean variables $x$: * $\models x$ if and only if $x=1.$ * Boolean terms $\phi,\psi$ under special symbols "$\neg\phi,$” “$\phi\vee\psi,$” “$\phi\wedge\psi,$” “$\phi\Rightarrow\psi,$” “$\phi\Longleftrightarrow \psi$”: * Negation: $\models \neg(\phi)$ if and only if $\not{\models}(\phi).$ * Disjunction: $\models (\phi \vee \psi)$ if and only if $\models (\phi)$ or $\models (\psi).$ * Conjunction: $\models (\phi \wedge\psi)$ if and only if $\models (\phi)$ and $\models (\psi).$ * Implication: $\models (\phi \Rightarrow\psi)$ if and only if $\not{\models} (\phi)$ or $\models (\psi).$ * Equivalence: $\models (\phi \Leftrightarrow \psi)$ if and only if $\models (\phi \Rightarrow\psi)$ and $\models (\psi \Rightarrow\phi).$

  1. Definition: $k$-nary Connectives, Prime and Compound Propositions
  2. Lemma: Boolean Function
  3. Definition: Truth Table
  4. Definition: Negation
  5. Definition: Conjunction
  6. Definition: Disjunction
  7. Definition: Implication
  8. Definition: Equivalence

Branches: 1
Chapters: 2
Definitions: 3
Lemmas: 4
Proofs: 5 6 7 8 9 10 11 12
Sections: 13


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs