Section 1.1 Statements, Symbolic Representation, and Tautologies
13
The algorithm first assigns the truth values “true” to P and “false” to Q, consistent with the assumption that P S Q is not a tautology. The algorithm then
enters a loop, where a sequence of steps is repeated until some condition is met.
Within the loop, truth assignments continue to be made to smaller and smaller
components of the original P and Q until all occurrences of individual statement
letters have truth values. Then the algorithm tests whether a contradiction has
occurred, and writes out the information about whether P S Q is a tautology.
ALgoRItHM TAuTologyTesT
TautologyTest (wff P; wff Q)
//Given wffs P and Q, decides whether the wff P S Q is a tautology.
//Assume P S Q is not a tautology
P = true
//assign T to P
Q = false
//assign F to Q
repeat
for each compound wff already assigned a truth value,
assign the truth values determined for its components
until all occurrences of statements letters have truth values
if some letter has two truth values
then //contradiction, assumption false
write (“P S Q is a tautology.”)
else //found a way to make P S Q false
write (“P S Q is not a tautology.”)
end if
end TautologyTest
eXAMPLe 8
Consider the wff (A S B) S (B′ S A′). This matches the pattern needed in order to use algorithm TautologyTest, namely P S Q, where P is A S B and Q is
B′ S A′. Following the algorithm, we first assign truth values
A S B true and B′ S A′ false
Moving on to the loop, the assignment of false to the compound statement B′ S A′ 
determines the further assignments
B′ true and A′ false
or
B false and A true
Now working with P, A true and A S B true determines the assignment
B true