Discrete Mathematics for Computer Science

Introduction to Propositional Logic 91

Solution.

(a) (p A -q) -- r. Since and and but usually both get translated as A, the difference be-

tween the two English words is usually an issue not of what is the case but, rather, of

what we would have expected to be the case.

(b) (p v q) A -(p A q).

This proposition is "logically equivalent to" the proposition in Example 1 (f), meaning

that p <-+ (-q) is an equally good answer. We shall discuss logical equivalence in the next

section. 0

Definition 1. Let p, q, and r be propositions. The proposition -p is the negation of
p. The proposition p A q is the conjunction of p and q, and p and q are called its con-
juncts. The proposition p V q is the disjunction of p and q, and p and q are called its
disjuncts. The proposition p -+ q is a conditional, or an implication, with hypothesis p
and conclusion q. The proposition p +-* q is an equivalence or a biconditional.

Since the English language is often ambiguous, and the meanings of words can vary

from context to context, the English translations of the symbols we have just introduced

(--, A, v, -+, and ++) do not define the meanings of the symbols precisely. A precise def-

inition of each symbol is given by a truth table, which provides the truth value for the

result of applying the operation on each possible set of truth values for the operands. As

mentioned, we shall use the symbols T and F to denote the truth values TRUE and FALSE

as well as to denote propositional constants. Table 2.2 shows the truth table for negation.

Truth Table for

p

Table 2.2 Truth Table for Negation T F

F T

Table 2.2 is read as follows: For any proposition p, if p is T, then -'p is F, and if p

is F, then -p is T. This assignment of truth values agrees with the common usage of the
word not. Truth tables for the other propositional connectives are shown in Table 2.3.

Truth Table for A Truth Table for v

p q pAq p q pVq

T T T T T T

T F F T F T

F T F F T T

Table 2.3 Truth Tables for Logical F F F F F F

Connectives Truth Table for -* Truth Table for +

p q p--q p q p*- q

T T T T T T

T F F T F F

F T T F T F

F F T F F T