Discrete Mathematics for Computer Science

Introduction to Propositional Logic 97

Solution. The subtrees Tp and T(-(pvq)) are as shown:

0 (-~(p vq))

TP vq)q(p

p q

T(-•(p v q))

The term syntax refers to the rules for forming grammatically correct strings of sym-
bols of a language. The rules specified here in the definition of the terms formula and
subformula are examples of rules for forming correct strings of symbols for propositional
logic. In the next section, we will discuss the semantics of propositional logic-that is,
what the strings of symbols mean-though we have already begun discussing semantics
by giving the truth tables.

2.1.3 Abbreviated Notation for Formulas

A formula such as

((((-(-p)) A (-'q)) A r) V (((--(-,q)) A (-.r)) A s)) *+ (s - p)

has so many parentheses that the reader can easily get confused. Just as in ordinary arith-
metic, however, formulas in informal usage are abbreviated by dropping some of the paren-
theses or by using different styles of parentheses, such as brackets. Some widely accepted
conventions are summarized in Table 2.4.

Table 2.4 Common Abbreviations and Other Informal Usage

1. Drop the outermost set of parentheses, simplifying (-p) to -p and (p v q) to
   pvq.

2. In a series of conjunctions nested to the left, such as (p A q) A r, drop the paren-

theses, writing p A q A r. Similarly, with disjunctions, abbreviate (p V q) v r to

p V q V r.

3. A -, symbol always applies to as little as possible. That is, - is the highest priority

operation, and -a v b means (-a) v b.

4. The remaining operations are often given priorities as follows, from highest to
   lowest: A, v, -->, and *-. Thus:

(a) -a A b V c A d abbreviates (((-a) A b) v (c A d)).

(b) a- b v b A c abbreviates (a -*(b (bv(b A c))).

(c) a + b-+-C cd abbreviates (a *+ (b -* (c A d))).

(Caution: Use this rule sparingly to omit parentheses. Overuse of the rule creates

almost-unreadable formulas. When in doubt, leave the parentheses in.)

5. In formulas with nested parentheses, it is common to replace some of the paren-
   theses with other symbols, usually brackets that is, ([ and 1). So, the formula in
   Section 2.1.3 might be written as
   [(--p A -q A r) V (--q A -r A s)] +-> [s -+ p]