Page 99 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 6: Formalized Symbolic Logics

Reverse Evaluation Notes

Reverse evaluation is the opposite of evaluation. We begin with one or more compound sentences
and try to figure out which interpretations satisfy those sentences. One way to do this is using a
truth table for the language. A truth table for a propositional language is a table showing all of
the possible interpretations for the propositional constants in the language. The following
figure shows a truth table for a propositional language with just three propositional constants.
Each row corresponds to a single interpretation. The interpretations i and j correspond to the
third and seventh rows of this table, respectively.
p q r
true true true
true true false
true false true
true false false
false true true
false true false
false false true
false false false

Note that, for a propositional language with n logical constants, there are n columns in the truth
tables and 2 rows. In doing reverse evaluation, we process input sentences in turn, for each
n
sentence crossing out interpretations in the truth table that do not satisfy the sentence. The
interpretations remaining at the end of this process are all possible interpretations of the input
sentences.

Validity, Satisfiability and Unsatisfiability

Evaluation and reverse evaluation are processes that involve specific sentences and specific
interpretations. In computational logic, we are rarely concerned with specific interpretations;
we are more interested in the properties of sentences that hold across interpretations. In particular,
the notion of satisfaction imposes a classification of sentences in a language based on whether
there are interpretations that satisfy that sentence. A sentence is valid if and only if it is satisfied
by every interpretation. The following sentence is valid.
p ∨ ¬p

A sentence is satisfiable if and only if it is satisfied by at least one interpretation. A sentence is
falsifiable if and only if there is at least one interpretation that makes it false. We have already
seen several examples of satisfiable and falsifiable sentences. A sentence is unsatisfiable if and
only if it is not satisfied by any interpretation. The following sentence is unsatisfiable. No
matter what interpretation we take, the sentence is always false.
p ⇔ ¬p
A sentence is contingent if and only if it is both satisfiable and falsifiable, i.e. it is neither valid
nor unsatisfiable. In one sense, valid sentences and unsatisfiable sentences are useless. Valid
sentences do not rule out any possible interpretations; unsatisfiable sentences rule out all
interpretations; thus they say nothing about the world. On the other hand, from a logical
perspective, they are extremely useful in that, as we shall see, they serve as the basis for legal
transformations that we can perform on other logical sentences.

LOVELY PROFESSIONAL UNIVERSITY 93