

Introduction to Logic

Tools for Thought


Evaluation is the process of determining the truth values of compound sentences given a truth assignment for the truth values of proposition constants.
As it turns out, there is a simple technique for evaluating complex sentences. We substitute true and false values for the proposition constants in our sentence, forming an expression with 1s and 0s and logical operators. We use our operator semantics to evaluate subexpressions with these truth values as arguments. We then repeat, working from the inside out, until we have a truth value for the sentence as a whole.

As an example, consider the truth assignment i shown below.
p^{i} = 1
q^{i} = 0
r^{i} = 1
Using our evaluation method, we can see that i satisfies (p ∨ q) ∧ (¬q ∨ r).
(p ∨ q) ∧ (¬ q ∨ r)
(1 ∨ 0) ∧ (¬ 0 ∨ 1)
1 ∧ (¬ 0 ∨ 1)
1 ∧ (1 ∨ 1)
1 ∧ 1
1

Now consider truth assignment j defined as follows.
p^{j} = 0
q^{j} = 1
r^{j} = 0
In this case, j does not satisfy (p ∨ q) ∧ (¬q ∨ r).
(p ∨ q) ∧ (¬q ∨ r)
(0 ∨ 1) ∧ (¬1 ∨ 0)
1 ∧ (¬1 ∨ 0)
1 ∧ (0 ∨ 0)
1 ∧ 0
0

Using this technique, we can evaluate the truth of arbitrary sentences in our language. The cost is proportional to the size of the sentence. Of course, in some cases, it is possible to economize and do even better. For example, when evaluating a conjunction, if we discover that the first conjunct is false, then there is no need to evaluate the second conjunct since the sentence as a whole must be false.

Use the arrow keys to navigate.
Press the escape key to toggle all / one.

