1Propositional calculus
II Logic and Set Theory
1.2 Semantic entailment
The idea of semantic entailment is to assign truth values to propositions, where
we declare each proposition to be “true” or “false”. This assignment is performed
by a valuation.
Definition (Valuation). A valuation on
L
is a function
v
:
L → {
0
,
1
}
such
that:
– v(⊥) = 0,
– v(p ⇒ q) =
(
0 if v(p) = 1, v(q) = 0,
1 otherwise
We interpret
v
(
p
) to be the truth value of
p
, with 0 denoting “false” and 1
denoting “true”.
Note that we do not impose any restriction of
v
(
p
) when
p
is a primitive
proposition.
For those people who like homomorphisms, we can first give the set
{
0
,
1
}
a
binary operation ⇒ by
a ⇒ b =
(
0 if a = 1, b = 0
1 otherwise
as well as a constant
⊥
= 0. Then a valuation can be defined as a homomorphism
between L and {0, 1} that preserves ⊥ and ⇒.
It should be clear that a valuation is uniquely determined by its values on
the primitive propositions, as the values on all other propositions follow from
the definition of a valuation. In particular, we have
Proposition.
(i) If v and v
′
are valuations with v(p) = v
′
(p) for all p ∈ P , then v = v
′
.
(ii)
For any function
w
:
P → {
0
,
1
}
, we can extend it to a valuation
v
such
that v(p) = w(p) for all p ∈ L.
Proof.
(i)
Recall that
L
is defined inductively. We are given that
v
(
p
) =
v
′
(
p
) on
L
0
. Then for all
p ∈ L
1
,
p
must be in the form
q ⇒ r
for
q, r ∈ L
0
. Then
v
(
q ⇒ r
) =
v
(
p ⇒ q
) since the value of
v
is uniquely determined by the
definition. So for all p ∈ L
1
, v(p) = v
′
(p).
Continue inductively to show that v(p) = v
′
(p) for all p ∈ L
n
for any n.
(ii)
Set
v
to agree with
w
for all
p ∈ P
, and set
v
(
⊥
) = 0. Then define
v
on
L
n
inductively according to the definition.
Example. Suppose v is a valuation with v(p) = v(q) = 1, v(r) = 0. Then
v((p ⇒ q) ⇒ r) = 0.
Often, we are interested in propositions that are always true, such as
p ⇒ p
.
These are known as tautologies.
Definition (Tautology).
t
is a tautology, written as
|
=
t
, if
v
(
t
) = 1 for all
valuations v.
To show that a statement is a tautology, we can use a truth table, where we
simply list out all possible valuations and find the value of v(t).
Example.
(i) |= p ⇒ (q ⇒ p) “A true statement is implied by anything”
v(p) v(q) v(q ⇒ p) v(p ⇒ (q ⇒ p))
1 1 1 1
1 0 1 1
0 1 0 1
0 0 1 1
(ii) |= (¬¬p) ⇒ p. Recall that ¬¬p is defined as ((p ⇒ ⊥) ⇒ ⊥).
v(p) v(p ⇒ ⊥) v((p ⇒ ⊥) ⇒ ⊥) v(((p ⇒ ⊥) ⇒ ⊥) ⇒ p)
1 0 1 1
0 1 0 1
(iii) |= [p ⇒ (q ⇒ r)] ⇒ [(p ⇒ q) ⇒ (p ⇒ r)].
Instead of creating a truth table, which would be horribly long, we show
this by reasoning: Suppose it is not a tautology. So there is a
v
such that
v
(
p ⇒
(
q ⇒ r
)) = 1 and
v
((
p ⇒ q
)
⇒
(
p ⇒ r
)) = 0. For the second
equality to hold, we must have
v
(
p ⇒ q
) = 1 and
v
(
p ⇒ r
) = 0. So
v(p) = 1, v(r) = 0, v(q) = 1. But then v(p ⇒ (q ⇒ r)) = 0.
Sometimes, we don’t want to make statements as strong as “
t
is always true”.
Instead, we might want to say “
t
is true whenever
S
is true”. This is known as
semantic entailment.
Definition (Semantic entailment). For
S ⊆ L
,
t ∈ L
, we say
S
entails
t
,
S
semantically implies t or
S |
=
t
if, for any
v
such that
v
(
s
) = 1 for all
s ∈ S
, we
have v(t) = 1.
Here we are using the symbol
|
= again. This is not an attempt to confuse
students. |= t is equivalent to the statement ∅ |= t.
Example. {p ⇒ q, q ⇒ r} |= (p ⇒ r).
We want to show that for any valuation
v
with
v
(
p ⇒ q
) =
v
(
q ⇒ r
) = 1, we
have v(p ⇒ r) = 1. We prove the contrapositive.
If
v
(
p ⇒ r
) = 0, then
v
(
p
) = 1 and
v
(
r
) = 0. If
v
(
q
) = 0, then
v
(
p ⇒ q
) = 0.
If
v
(
q
) = 1, then
v
(
q ⇒ r
) = 0. So
v
(
p ⇒ r
) = 0 only if one of
v
(
p ⇒ q
) or
v(q ⇒ r) is zero.
Note that
{p} |
=
q
and
p ⇒ q
both intuitively mean “if
p
is true, then
q
is
true”. However, these are very distinct notions.
p ⇒ q
is a proposition within
our theory. It is true (or false) in the sense that valuations take the value 0 (or
1).
On the other hand, when we say
{p} |
=
q
, this is a statement in the meta-
theory. It is true (or false) in the sense that we decided it is true (or false) based
on some arguments and (informal) proofs, performed in the real world instead
of inside propositional calculus.
The same distinction should be made when we define syntactic implication
later.
Before we dive into syntactic implication, we will define a few convenient
terms for later use.
Definition (Truth and model). If
v
(
t
) = 1, then we say that
t
is true in
v
, or
v
is a model of
t
. For
S ⊆ L
, a valuation
v
is a model of
S
if
v
(
s
) = 1 for all
s ∈ S
.