© 1996-2018

II.4 Formal semantics of Propositional Logic

Formal Semantics [Slide 32]

Formal (denotational) semantics of Propositional Logic:

Propositions × State   Bool

  • Propositions: set of all possible propositions
  • Bool: set of semantic Boolean values {tt,}
  • State: a ‘snapshot’ of the semantic values of the propositional variables in a formula

Formal Semantics [Slide 33]

Example 3.

proposition: P (P Q)

state σ: semantic value of P is tt and of Q is

(P Q)
P (P Q)


  • State in the truth table corresponds to the first two elements in a row.
  • The semantic value of the proposition w.r.t. a state is the last element in a row of the truth table.

State [Slide 34]

A state is a mapping State from the set of propositional variables Varb to the set of Boolean values Bool {tt,}.

State : Varb   Bool

We will use σ012, to denote states and Σ to denote the set of all possible states.

Example 4.

Let σ0 be a state such that

σ0(P) = tt
σ0(Q) =

Contact | Home | ITL home | Course | Proofs | Algebra | FL