Page 98 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes interpretation of the ∨ operator and is differentiated from exclusive or in which a
disjunction is true if and only if an odd number of its disjuncts are false.
4. The truth value of an implication is false if and only if its antecedent is true and is consequent
is false; otherwise, the truth value is true. This is called material implication.
5. As with an implication, the truth value of a reduction is false if and only if its antecedent
is true and its consequent is false; otherwise, the truth value is true. Of course, it is important
to remember that in a reduction the antecedent and consequent are reversed.
6. An equivalence is true if and only if the truth values of its constituents agree, i.e. they are
either both true or both false.
We say that an interpretation i satisfies a sentence if and only if it is true under that interpretation.

Evaluation

Given the semantic definitions in the last section, we can easily determine for any given
interpretation whether or not any sentence is true or false under that interpretation. The technique
is simple. We substitute true and false values for the propositional constants and replace complex
expressions with the corresponding values, working from the inside out.
As an example, consider the interpretation i show below:
i
p = true
q = false
i
r = true
i
We can see that i satisfies (p ∨ q) ∧ (¬q ∨ r).
(p ∨ q) ‘“ (¬q ∨ r)
(true ∨ false) ∧ (¬false ∨ true)
true ∧ (¬false ∨ true)
true ∧ (true ∨ true)
true ∧ true
true
Now, consider interpretation j defined as follows:
i
p = true
i
q = false
i
r = true
In this case, j does not satisfy (p ∨ q) ∧ (¬q ∨ r).
(p ∨ q) ∧ (¬q ∨ r)
(true ∨ true) ∧ (¬true ∨ false)
true ∧ (¬true ∨ false)
true ∧ (false ∨ false)
true ∧ false
false
Using this technique, we can evaluate the truth of arbitrary sentences in our language. The cost
is proportional to the size of the sentence.

92 LOVELY PROFESSIONAL UNIVERSITY