Chapter 3

Propositional Logic
True/false questions present a statement, and prompt the student to choose whether the statement is truthful. Students typically have a great deal of experience with this type of question. . . . True/false questions are among the easiest to write, and can be scored electronically. University of Wisconsin, Teaching Academy There are no real boolean values in Perl. Still every value in Perl is either true or false.

Contents
3.1 3.2 3.3 3.4 3.5 3.6 3.7 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Satisability, Validity, and Equivalence . . . . . . . . . . . . . . . . . . . . . Subformula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evaluating a Formula in an Interpretation . . . . . . . . . . . . . . . . . . . Evaluating Formulas Using Simplication Rules . . . . . . . . . . . . . . . . Propositional Formulas and Boolean Circuits . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 31 33 35 36 37 39 39

This chapter deals with propositional logic. We describe its syntax and semantics, and introduce the key notions of satisability, validity, and equivalence. A more detailed exposition of propositional logic may be found in standard textbooks on mathematical logic, e.g. Kleene [1952], Smullyan [1968], Lee and Chang [1973], Gallier [1986], and Fitting [1996]. As any other logic, propositional logic can express properties. They are expressed using a language; expressions in this language are called (propositional) formulas. These formulas formalize a mathematical analogue of the notion of proposition (assertion, statement,
Time 14:06 draft October 1, 2010

30

3.1 Syntax

Connective

Name verum falsum negation conjunction disjunction implication equivalence

Priority

4 3 3 2 1

Figure 3.1: Connectives sentence). Intuitively, a proposition is anything that can be either true or false. When we manipulate with formulas of propositional logic, we abstract away from the concrete meaning, or content of propositions. That is, we consider them only from an abstract viewpoint, so that the meaning of complex propositions is dened in terms of the meanings of simpler ones.

3.1 Syntax
Propositional formulas are written in a propositional language. To x a propositional language, we x a countable set P , whose elements will be called boolean variables and denoted by p, q, r . D EFINITION 3.1 (Formula) Propositional formulas are dened inductively as follows: (1) Every boolean variable is a formula, also called atomic formula, or simply atom. (2) and are formulas. (3) If A1 , . . . , An are formulas, where n 2, then (A1 . . . An ) and (A1 . . . An ) are formulas. (4) If A is a formula, then A is a formula. (5) If A and B are formulas, then (A B ) and (A B ) are formulas. The symbols , , , , , , and used to build formulas are called connectives. J

Note that we gave an inductive denition of propositional formulas in the sense of Section 2.7. The connectives are simply the constructors of this inductive denition. The connectives and are varyadic, that is, they do not have a xed number of arguments. The names of all connectives are summarized in Figure 3.1. We will sometimes call formulas by the names of their main (outermost) connective. For example, we will say that
October 1, 2010 draft Time 14:06

CHAPTER 3. PROPOSITIONAL LOGIC

31

a formula A1 . . . An is a disjunction (of formulas A1 , . . . , An ). To make formulas shorter, we will omit parentheses in them according to the standard conventions given in Figure 3.1 on the preceding page. Connectives with higher priorities bind stronger: for example, A1 A2 A3 A4 means (A1 (A2 A3 )) A4 . We will always use parentheses to distinguish connectives of the same priority. For example, we will never write p q r , since this formula can denote both (p q ) r and p (q r ). Likewise, we will never write p q r or p q r .

3.2 Semantics
So far we have only dened the syntax of propositional logic, without giving any meaning to formulas. In real life, the meaning of propositions expressed in natural language depends on the current situation, or the state of the world. For example, the proposition this book is written in a foreign language (3.1)

may be true under some circumstances and false under other. The situation is similar for other simple (atomic) propositions, for example this book has a red cover. (3.2)

For more complex propositions, their meaning may also depend on the current state of the world, but in a slightly different way. For example the proposition this book is written in a foreign language and has a red cover is true for some books and false for others, but it is true for every book for which propositions (3.1) and (3.2) are both true. This can be summarized as follows. (1) The meaning of simple, atomic propositions depends on their interpretation in the current world. (2) The meaning of more complex propositions depends on the meaning of their components. The semantics of propositional logic is based on these two assumptions. Formally, the semantics is dened through the notion of interpretation. An interpretation assigns values to boolean variables.1 These values are used to dene the values of arbitrarily complex formulas, based on the values of these components. D EFINITION 3.2 (Boolean Value, Interpretation, Truth) A boolean value, also called a truth value, is either 1 or 0. A interpretation for a set of boolean variables P is a mapping from
Remember that boolean variables in propositional logic are intended to be formal analogues of simple, atomic propositions.
1

Time 14:06

draft

October 1, 2010

32

3.2 Semantics

1 0

1 1 0

0 0 0

1 0

1 1 1

0 1 0

1 0

0 1

1 0

1 1 1

0 0 1

1 0

1 1 0

0 0 1

Figure 3.2: Operation tables for connectives P to the set of boolean values {1, 0}. We can say that boolean variables are interpreted as boolean values. Interpretations will also be called truth assignments. We will now extend interpretations to arbitrary propositional formulas. The denition is by induction. (1) I () = 1 and I () = 0. (2) I (A1 . . . An ) = 1 if and only if I (Ai ) = 1 for all i. (3) I (A1 . . . An ) = 1 if and only if I (Ai ) = 1 for some i. (4) I (A) = 1 if and only if I (A) = 0. (5) I (A B ) = 1 if and only if I (A) = 0 or I (B ) = 1. (6) I (A B ) = 1 if and only if I (A) = I (B ). If, for a formula A and interpretation I , we have I (A) = 1 (respectively, I (A) = 0), we say that A is true (respectively, false) in I , denoted by I A (respectively, I A). J Essentially, an interpretation I evaluates each formula A to a truth value, so we can speak about the value of A in I , that is I (A). Note that the truth value of a compound formula is uniquely determined by the truth values of its components. Therefore, logical connectives can be alternatively considered as functions on truth values. The notion of truth can then be illustrated by so-called operation tables for all connectives which dene the truth value of a compound formula using the truth values of its components. The operation tables for all connectives are given in Figure 3.2. For convenience, we only consider conjunctions and disjunctions of two formulas. Natural language sentences, even the simplest ones, may be ambiguous, so it may be difcult to say whether they are true or false. For example sentence (3.2) is not necessarily true or false. What if the cover is mainly red, but also has other colors? What if the color is between red and orange, but very close to red? There is a whole range of logics studied in philosophical logic in which there are more than two truth values,2 or even an innite number of truth values, but we will not consider these logics in this book. It will sometimes be convenient for us to use empty conjunctions and disjunctions. The empty conjunction is true in every interpretation, while the empty disjunction is always false.
2

For example true, false, and unknown.

October 1, 2010

draft

Time 14:06

CHAPTER 3. PROPOSITIONAL LOGIC

33

3.3 Satisability, Validity, and Equivalence

In this section we introduce the key notion of satisability of formulas and sets of formulas and some related notions. D EFINITION 3.3 (Model, Satisability, Validity, Equivalence) If a formula A is true in an interpretation I we say that I satises A. We also say that I is a model of A. A formula A is satisable (respectively, valid) if it is true in some (respectively, in every) interpretation. Valid formulas are also called tautologies. Two formulas A and B are called equivalent, denoted A B if every model of A is a model of B , and vice versa, every model of B is a model of A. J We generalize the notions of satisability and model to sets of formulas as follows. We say that an interpretation I satises a set of formulas S , denoted by I S , if it satises every formula in S . If I S , we also say that I is a model of S . A set of formulas is called satisable if there exists an interpretation which satises every formula in this set. Consider examples. Let p be a boolean variable. Then the formula p p is unsatisable. Each of the formulas p and p is satisable but not valid. The formula p p is valid. For propositional formulas, the notions of satisability, validity, and truth in an interpretation coincide. This will not be the case for more general classes of formulas introduced later in this book. The notions of satisability and validity are central in logic. Automated reasoning is a branch of computer science that deals with mechanized methods of establishing satisability or unsatisability of sets of formulas and related questions. It is not hard to argue that two formulas A and B are equivalent if in every interpretation their values coincide, that is, for every interpretation I we have I (A) = I (B ). E XAMPLE 3.4 For all formulas A and B , the following equivalences hold. A A; A A; A B (A B ); A B (A B ); A B A B.

(3.3) (3.4) (3.5) (3.6) (3.7)

Consider, for example, the rst pair of formulas, A and A, and let us show that they are equivalent. Take any interpretation I . If I A, then I (A ) = 0 = I (A). If I A, then I (A ) = 1 = I (A). In both cases we have I (A ) = I (A), so A A. We will show later how to verify such equivalences in general. J Let us note the following trivial, but useful, fact showing that the problems of checking equivalence, validity, and satisability can be regarded as instances of each other, in a sense.
Time 14:06 draft October 1, 2010

34

3.3 Satisability, Validity, and Equivalence

L EMMA 3.5 (i) A formula A is valid if and only if A is unsatisable. (ii) A formula A is satisable if and only if A is not valid. (iii) A formula A is valid if and only if A is equivalent to . (iv) Formulas A and B are equivalent if and only if the formula A B is valid. P ROOF. We will only prove property (iv). To prove the only if direction, suppose that A and B are equivalent. Take any interpretation I . If I A, then by the equivalence I B , and hence I A B . If I A, then again by the equivalence I B , and hence I A B . In both cases we have I A B , so A B is valid. To prove the if direction suppose that A B is valid. Take any interpretation I . We have I A B . By inspection of the operation table for (see Figure 3.2 on page 32) one can see that I A if and only if I B , so A and B are equivalent. J Although complexity-related questions are beyond the scope of this book, we would like to note that this lemma also shows that the problems of checking validity and equivalence are polynomial-time equivalent. In fact, validity and equivalence checking are coNP-complete problems, while satisability checking is NP-complete. This implies a subtle difference between checking satisability and checking unsatisability of a formula. To establish satisability of a formula A, it is enough to nd some interpretation that satises A. To establish unsatisability, one has to check that A is false in all interpretations. Strangely enough, this observation may be used to build algorithms which can sometimes establish satisability of a formula but can never establish unsatisability. For example, consider the following algorithm. Given a propositional formula A with variables p1 , . . . , pn , do the following. Select randomly boolean values b1 , . . . , bn for p1 , . . . , pn , for example, by tossing a coin. This gives us a random interpretation I = {p1 b1 , . . . , pn bn }. If I A, then a model of A is found, so terminate and return satisable. Repeat this procedure some number of times and no model was found, return I dont know. Even if we repeat this procedure a large number of times, there is no guarantee that A is unsatisable. We can claim that A is unsatisable only with some probability. Consider now satisability checking of sets of formulas. For nite sets one can reduces satisability checking to satisability checking for formulas using the following lemma. L EMMA 3.6 Let S = {A1 , . . . , An } be a set of formulas. Then S is satisable if and only if the formula A1 . . . An is satisable. J The relations between satisability and validity for innite sets of formulas are not that straightforward and will be investigated later. Though in practice we do not deal with innite sets of formulas, they will still be useful when we discuss satisability and validity for rst-order formulas. In many cases the semantics of nite sets of rst-order formulas can be conveniently characterized by the semantics of innite sets of propositional formulas. Obviously, if an interpretation I satises an innite set of formulas S , it also satises every subset of S . It is interesting that satisability of innite sets of formulas can be characterized in terms of satisability of nite sets as follows: a set S of formulas is satisable
October 1, 2010 draft Time 14:06

CHAPTER 3. PROPOSITIONAL LOGIC

35

if and only if every nite subset of S is satisable too. This property is called compactness and proved in Theorem 7.28. Note that compactness has an interesting corollary: if an innite set S of formulas is unsatisable, then it contains a nite unsatisable subset.

3.4 Subformula
The value of a compound formula is uniquely determined, using the operation tables, by the value of its components, or its immediate subformulas. D EFINITION 3.7 (Subformula) The notion of subformula and immediate subformula of a formula is dened inductively as follows. (1) The formulas A1 , . . . , An are the immediate subformulas of the formulas A1 . . . An and A1 . . . An . (2) The formulas A is the immediate subformula of the formula A. (3) The formulas A1 , A2 are the immediate subformulas of the formulas A1 A2 and A1 A2 . (4) Every formula A is a subformula of itself. (5) If A1 is a subformula of A2 and A2 is an immediate subformula of A3 , then A1 is a subformula of A3 . A subformula A of B is called proper if A = B . J

For example, the formula p1 p2 p3 p1 has the following subformulas: p1 , p2 , p3 , p1 , p2 p3 p1 , and the formula p1 p2 p3 p1 itself. Its immediate subformulas are p1 and p2 p3 p1 . It is not hard to argue that the subformula relation is a reexive and transitive closure of the notion of immediate subformula. The notions of subformula and immediate subformula can be obtained by specializing the general notions of expression and subexpression, see Section 2.7.1, to formulas. Let us now prove several properties of truth, satisability, and validity. These properties will be used, explicitly or implicitly, in justifying satisability-checking algorithms. One of the most important properties for us is that the semantics of formulas is preserved under equivalence. Since the truth value of a formula in an interpretation is uniquely determined by the truth values of its immediate subformulas, we have the following result. L EMMA 3.8 (Equivalent Replacement) Let I be an interpretation, a formula A1 be a subformula of a formula B1 and I A1 A2 . Let the formula B2 be obtained from B1 by replacement of one or more occurrences of A1 by A2 . Then I B1 B2 . J
Time 14:06 draft October 1, 2010

36

3.5 Evaluating a Formula in an Interpretation

Note that using the notation introduced in Section 2.7.3 we can reformulate this lemma as follows: if I A1 A2 , then I B [A1 ] B [A2 ]. This lemma immediately implies the following theorem. T HEOREM 3.9 (Equivalent Replacement) Let A1 be a subformula of a formula B1 and A1 A2 . Let the formula B2 be obtained from B1 by replacement of one or more occurrences of A1 by A2 . Then B1 B2 . J

3.5 Evaluating a Formula in an Interpretation

In this section we consider how to evaluate a formula in an interpretation. This can be formalized as the following decision problem. D EFINITION 3.10 (Formula Evaluation) Formula Evaluation is the following decision problem. An instance is a pair (A, I ), where A is formula and I is an interpretation. The answer is yes if I A. J This decision problem has a close relation to the so-called circuit value problem discussed below. We can evaluate formulas in interpretations by a straightforward use of the denition of the value of a formula. To this end, we can rst evaluate its immediate subformulas, and then evaluate the formula itself using the operation tables of Figure 3.2 on page 32. Let us try to evaluate some formulas. E XAMPLE 3.11 Consider the formula A = (p q ) (p q r ) (p r ) and consider the interpretation I = {p 1, q 0, r 1}. Put all the subformulas of this formula in a table in such a way that every formula is above all of its proper subformulas, see Figure 3.3.3 Then evaluate all the subformulas starting from the smallest ones (in the bottom of the table). For example, the formula (p q ) (p q r ) on line 3 is the conjunction of the formulas p q and p q r situated on lines 5 and 4, respectively. Since the formula on line 5 has the value 0 and the formula on line 4 has the value 1, their conjunction evaluates to 0. J Observe that it is not necessary to evaluate all the subformulas of a formula A in order to obtain the value of A. Consider, for example, the formula of Example 3.11. Since we know that r is true in I , we can immediately obtain that p r is true in I , too (see the operation table for the implication). Likewise, p r implies that the whole formula (p q ) (p q r ) (p r ) is true. Therefore, instead of evaluating all the subformulas of A it was enough to evaluate only three subformulas, including A itself. Moreover, it even was not necessary to know the values of p and q : the formula is true in every interpretation in which r is true.
3

For a better illustration, we repeat subformulas p, q and r having multiple occurrences in the formula.

October 1, 2010

draft

Time 14:06

CHAPTER 3. PROPOSITIONAL LOGIC

37

1 2 3 4 5 6 7 8 9

subformula (p q ) (p q r ) (p r ) pr (p q ) (p q r ) pq r pq pq p p p q q r r

value 1 1 0 1 0 0 1 0 1

Figure 3.3: Evaluation of formula using truth tables

3.6 Evaluating Formulas Using Simplication Rules

In this section we will show that evaluation of a formula can be done in a purely syntactic way. We will introduce a rewrite rule system which can be used to evaluate formulas in interpretations. To this end, we make the following observation. Suppose that we evaluate A in I and a subformula B of A is true in I . In this case B and have the same truth value in I , so can replace B by without affecting the truth value of A. Likewise, we can replace any subformula having the value 0 by . Using this observation, we can evaluate propositional formulas in an interpretation I as follows: (1) For every atom p true in I replace p by ; for every atom q false in I replace q by . (2) Use the rewrite rules corresponding to the operation tables of Figure 3.2 on page 32 to simplify the resulting formula. For example, the rewrite rules for have the following form4 ; ; ; . (3.8)

Note that every rewrite rule replaces a subformula by an equivalent one, so the value of the formula will not change. (3) If the formula nally rewrites into , then it is true; if it rewrites into , then it is false. We can use a stronger form of rewrite rules for formula evaluation. The idea can be illustrated by rewrite rules (3.8) for the implication. Note that A is equivalent to
We do not give here the complete list of all the rewrite rules, since later we will introduce their simplied version.
4

Time 14:06

draft

October 1, 2010

38

3.6 Evaluating Formulas Using Simplication Rules

... A1 . . . An

A1 . . . An ...

A A

Figure 3.4: Rewrite rules for formula evaluation independently of the A. Likewise, A is equivalent to independently of A. Therefore, we can replace the four rewrite rules of (3.8) by the following three rewrite rules: A ; A ; .

These rewrite rules use the variable A ranging over arbitrary propositional formulas. The rewrite rules for evaluating a formula are given in Figure 3.4. They are dened modulo permutation of arguments of and . That is, we do not distinguish A1 . . . An from any formula Ai1 . . . Ain , where the sequence i1 , . . . , in is a permutation of the sequence 1, . . . , n. For example, we treat A1 A2 A3 and A3 A1 A2 as the same formula. The algorithm for evaluating formulas is given in Figure 3.5 on the next page. E XAMPLE 3.12 (See Example 3.11 on page 36.) Consider again the formula A = (p q ) (p q r ) (p r ) and the interpretation I = {p 1, q 0, r 1}. Let us evaluate A in I using the Formula Evaluation Algorithm. According to the algorithm, we rst replace the true atoms by , and the false ones by . We obtain the formula ( ) ( ) ( ). Then we apply the rewrite rules to obtain its normal form. One possible sequence of rewritings is as follows: ( ) ( ) ( ) ( ) ( ) .
October 1, 2010 draft Time 14:06

CHAPTER 3. PROPOSITIONAL LOGIC

39

procedure evaluate (G, I ) input: formula G, interpretation I output: a boolean value begin forall atoms p occurring in G if I (p) = 1 then replace all occurrences of p in G by else replace all occurrences of p in G by rewrite G into a normal form using the rewrite rules of Figure 3.4 if G = then return 1 else return 0 end

Figure 3.5: Formula Evaluation Algorithm Another possible sequence of rewritings is as follows: ( ) ( ) ( ) ( ) ( ) ( ) . Note that both sequences yield the same answer (see Exercise 3.7). J

3.7 Propositional Formulas and Boolean Circuits

There exists a close resemblance between propositional formulas and boolean circuits. Correspondence between circuits and formulas. Boolean functions. Can all boolean functions be represented by circuits/formulas? Traditional questions related to boolean circuits: given two boolean circuits, are they equivalent? Given a circuit, does there exist an equivalent circuit of a smaller size?

Exercises
Formalize some sentences. E XERCISE 3.1 Some of the parentheses in following formulas were removed according to the priorities given in Figure 3.1 on page 30. Restore the parentheses. p1 p2 p3 p4 . p1 (p2 p3 p1 ) p2 p1 E XERCISE 3.2 Find all positions in the formula of Exercise 3.1. Time 14:06 draft J J October 1, 2010

40

3.7 Propositional Formulas and Boolean Circuits E XERCISE 3.3 Which formulas have no immediate subformulas? E XERCISE 3.4 For each of the following formulas, write down all of their subformulas. p1 p2 p3 p4 ; p r q p q r. J J

E XERCISE 3.5 Evaluate each of the formulas p (q r) and (p q ) r p q in the interpretation {p 0, q 1, r 0} using (i) the table-based method of Example 3.11; (ii) the rewriting-based algorithm of Figure 3.5. J E XERCISE 3.6 Represent as a formula the boolean function f of three arguments p1 , p2 , p3 with the following operation table: p1 0 0 0 0 1 1 1 1 p2 0 0 1 1 0 0 1 1 p3 0 1 0 1 0 1 0 1 f (p1 , p2 , p3 ) 0 0 0 0 1 1 0 1 J

Can you nd a formula with this property that contains only three occurrences of connectives?

E XERCISE 3.7 Prove that the Formula Evaluation Algorithm of Figure 3.5 on the preceding page returns the same answer independently of the order of rewriting. In other words, prove that the rewrite rule system of Figure 3.4 is conuent. J E XERCISE 3.8 A propositional formula A(p1 , . . . , pn ) of atoms p1 , . . . , pn is called a parity check formula if its models are exactly those that satisfy an even number of atoms among p1 , . . . , pn . Find parity check formulas which contain exactly one occurrence of each atom. J E XERCISE 3.9 Show that the formulas p (q r) and (p q ) r are not equivalent by nding an interpretation in which they have different truth values. J

October 1, 2010

draft

Time 14:06