Semantic Consequence and Equivalence

SUMMARY
In this class, we will study Semantic Consequence and Equivalence in propositional logic, which is a natural continuation of what we have previously covered. We will learn how to derive the notion of semantic consequence from truth value assignments and how this idea relates to the deduction theorem. Additionally, we will see practical examples of using truth tables to obtain useful properties such as Conjunction Elimination and Disjunction Introduction. We will also explore the notion of Semantic Equivalence and see how it relates to properties we already know. Finally, we will show how using models and deduction techniques can simplify the study of problems of consequence and semantic equivalence.

LEARNING OBJECTIVES:
By the end of this class, the student will be able to:

Understand the notion of semantic consequence.
Understand the different interpretations of the symbol ⊨.
Understand the proof of the deduction theorem in its semantic version and its use in the study of consequence and semantic equivalence.
Understand the definition of semantic equivalence and its relation to truth values.
Apply the deduction theorem in its semantic version to transform consequence problems into validity problems.
Apply useful properties in the use of truth tables to demonstrate semantic equivalences.
Apply the laws of absorption, distribution, and DeMorgan in the simplification of complex expressions.
Analyze the relationship between models and deductions in the study of propositional logic.

INDEX
ASSIGNMENTS AND MODELS
THE DEDUCTION THEOREM (SEMANTIC VERSION)
USING THE DEDUCTION THEOREM IN THE STUDY OF CONSEQUENCE AND SEMANTIC EQUIVALENCE
SEMANTIC EQUIVALENCE AND PROPERTIES
SYNTHESIS

The study of Semantic Consequence and Equivalence is a natural continuation of what we have done when reviewing the semantics of propositional logic. Now we will review how the notion of semantic consequence is derived from truth value assignments, and how a semantic version of the deduction theorem naturally emerges from this. Practical examples of using truth tables to obtain some useful properties will be shown. You can also see all of this on the YouTube channel.

Assignments and Models

First, let’s start with a definition that is crucial for the developments we will see in this post, that of semantic consequence.

DEFINITION: An expression

G

is a (semantic) consequence of another expression

F

if for every assignment

\mathcal{A}

it holds that

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

This is represented by writing $F\models G$ and is read as “the expression $F$ models the expression $G$ ” or “ $G$ is a (semantic) consequence of $F$ .”

With this definition in hand, we must note that the symbol $\models$ actually has several different readings depending on the context:

$\mathcal{A} \models F$ means that $\mathcal{A}(F) = 1$ ; that is, that “ $\mathcal{A}$ models $F$ .”
$G \models F$ means that if any assignment models $G$ , then it models $F$ , and we read this as “ $F$ is a consequence of $G$ .”
$\models F$ means that $F$ holds under any assignment; that is, that $F$ is a tautology.

Thus, although the symbol $\models$ can have many interpretations, the context is not ambiguous.

The notion of (semantic) consequence is close to the notion of “implication” that we have previously reviewed, in the sense that if $F\models G$ holds, then $\models (F\rightarrow G)$ . In fact, this is very similar to the deduction theorem we saw several classes ago.

The Deduction Theorem (Semantic Version)

[see]

THEOREM: If

F

and

G

are any expressions, then it holds that

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Proof:

The proof of this theorem is easily obtained by observing the truth tables

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

If we focus on the meaning of $F\models G$ , we will see that this is equivalent to saying that $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , which in turn is the same as saying that $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Now, if we notice that also $\mathcal{A}\not\models F$ is exactly the same as $\mathcal{A}\models \neg F$ , then $F\models G$ is equivalent to saying that $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Now, if we make a truth table for $F \rightarrow G$ and mark in green the region where $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ holds, we will see the following:

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

From this, we have that when $F\models G$ , it always happens that $\models (F \rightarrow G)$ and vice versa, which is nothing more than the deduction theorem and its converse in the semantic version.

Let’s suppose we want to know if an expression $G$ is a consequence of another expression $F$ . We will refer to this as the consequence problem. Using the previous theorem, this problem can be transformed into a validity problem, because “ $G$ is a consequence of $F$ if and only if $(F\rightarrow G)$ is a theorem”.

Using the Deduction Theorem in the Study of Consequence and Semantic Equivalence

From the truth tables, some properties can be inferred that resemble some seen in the past.

EXAMPLE: Show using truth tables that the following properties hold

Conjunction Elimination:

(F\wedge G)\models F

Disjunction Introduction:

F\models (F\vee G)

Contradiction:

(F\wedge\neg F)\models G

Solution: Using the deduction theorem that we just reviewed, we can transform the consequence problem into a validity problem.

To solve Conjunction Elimination, we can make the following truth table

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

With this, we demonstrate that $((F\wedge G)\rightarrow F)$ is a tautology and, therefore, following the converse of the deduction theorem, we obtain that $(F\wedge G) \models F$ .

Disjunction Introduction is solved similarly by constructing an appropriate truth table

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Here we observe that $(F\rightarrow (F\vee G))$ is a tautology and, therefore, by the converse of the deduction theorem, we have that $F\models (F\vee G)$

And finally, the property of Contradiction is demonstrated using the same method

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

With this truth table, we have demonstrated that $((F\wedge \neg F)\rightarrow G)$ is a tautology and, therefore, by the converse of the deduction theorem, we have that $(F\wedge \neg F)\models G$ .

Semantic Equivalence and Properties

[see]

DEFINITION: If both

F\models G

and

G\models F

occur at the same time, then

F

and

G

are said to be semantically equivalent to each other. This is represented by writing

F\equiv G

As a consequence of this definition, two expressions are semantically equivalent if and only if they have the same truth values.

EXAMPLE: It can be shown using truth tables that the following symmetry semantic equivalences hold.

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

EXAMPLE: If

F

is any expression,

\top

a tautology, and

\bot

a contradiction, then the following semantic equivalences can be proven using truth tables

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

These equivalences are known as absorption laws.

EXAMPLE: In the semantics of propositional logic, the distribution equivalences of conjunction and disjunction also hold.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

EXAMPLE: In the semantics of propositional logic, DeMorgan’s Laws also hold.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

EXERCISE: A good exercise is to prove using truth tables that the semantic equivalences of the Absorption, Distributive, and DeMorgan’s Laws do indeed hold.

EXAMPLE: Demonstrate using semantic equivalences that the following equivalence occurs:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Solution: We can prove this equivalence using truth tables, but if we do this, we will have to deal with an expression with 5 propositional variables, and this implies making a truth table with

2^5 = 32

rows, which would be ideal to avoid. To achieve this, we will use the equivalences we have already shown.

First, note that $(E\vee \neg E)$ is a tautology. Let’s denote this tautology by $\top$ . Then, using the absorption laws, we have

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

Using the distribution laws, we obtain

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Finally, by symmetry

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Therefore, following these equivalences, we have the equivalence

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

which is what we wanted to prove.

Synthesis

If we observe the development of this last example, we will see that, as the number of variables increases, the complexity of studying problems of consequence and semantic equivalence grows exponentially if we rely on truth tables. However, we have seen that from the development of the idea of a model, something analogous to the deduction techniques we have already studied in considerable detail emerges. This relationship between models and deductions is what we will see soon, and the combination of both will finally save us countless headaches in the study of logic.