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 ∨ Q)  P ∧ (P ∨ Q) 



 tt  ﬀ  tt  tt 



 
 State in the truth table corresponds to the ﬁrst 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 Var^{b} to
the set of Boolean values Bool ≜{tt,ﬀ}.
State : Var^{b} ↦ Bool
We will use σ_{0},σ_{1},σ_{2},… 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) = ﬀ 

