Semantics of propositional logic

• Preface
• Parsing input (SLR parser)
• Parser F# code
• Well-formed syntax
• Semantics of propositional logic
• Constructing tables
• The application

This is a bit abstract. But bear with it. The truth tables we obtain with this application actually models the semantics of propositional logic. But we might benefit from formally define the semantics.

We have what is called a model $$(S,\phi)$$ Here $S$ is a non-empty set of situations. $\phi$ is a function that maps atomic propositions to either true or false.

Propositional logic only contains one situation. Thus we omit the S, and we simply have $$p \mapsto \phi(p) \in \{T,F\}$$

Now we have a model. It contains a function that maps all atomic proposition to either true or false: $\mathbb{M} = (\phi)$. We define the following for this model

• $\mathbb{M} \vDash A$ : A is true in the model $\mathbb{M}$
• $\mathbb{M} \not\models A$ : A is false in the model $\mathbb{M}$

The symbol $\models$ simply reads "models". This we can expand to work for the connectives besides atoms. We get for a model $\mathbb{M}$

1. \( \mathbb{M} \models A \) if and only if \( \phi(A) = T \) for \( A \) an atomic proposition.
2. \( \mathbb{M} \models \neg A \) if and only if \( \mathbb{M} \not\models A \).
3. \( \mathbb{M} \models A \land B \) if and only if \( \mathbb{M} \models A \) and \( \mathbb{M} \models B \).
4. \( \mathbb{M} \models A \lor B \) if and only if \( \mathbb{M} \models A \) or \( \mathbb{M} \models B \).
5. \( \mathbb{M} \models A \Rightarrow B \) if and only if \( \mathbb{M} \not\models A \) or \( \mathbb{M} \models B \).
6. \( \mathbb{M} \models A \iff B \) if and only if \( \mathbb{M} \models A \) exactly when \( \mathbb{M} \models B \).

This can be written to truth tables as thus

Negation

A	¬
T	F
F	T

Conjunction

A	B	A ∧ B
T	T	T
F	T	F
T	F	F
F	F	F

Disjunction

A	B	A ∨ B
T	T	T
F	T	T
T	F	T
F	F	F

Implication

A	B	A ⇒ B
T	T	T
F	T	T
T	F	F
F	F	T

Biimplication

A	B	A ⇔ B
T	T	T
F	T	F
T	F	F
F	F	T

Thus on evaluating complex expressions we start with atomic propositions for which we consult our model. When these are evaluated, we evaluate more and more complex expressions until the whole proposition is evaluated.

Tautologies, contradictions and contingent propositions

For some truth table we have the following

• If every row in the right most column is true, we say that the proposition is a tautology.
• If ever row in the right most column is false, we say that the proposition is a contradiction or that it is absurd.
• If the last column is a mix, that is if the proposition is neither a tautology or absurd, we say that it is contingent.

Tautology example

The most simple example is the proposition $p \lor \neg p$. Just by saying it out loud it makes sense that you must have one of the two possibilities: either you have something or you don't. The truth table confirms

p	p ∨ ¬p
T	T
F	T

Contradiction example

The most obvious example is the proposition that we have something while we don't have it: $p \land \neg p$:

p	p ∧ ¬p
T	F
F	F

Contingent example

Most propositions fall into this category. As an example we can pick any of the tables for the five connectives. None of these are tautologies, and none of these are absurd.

Share