Logic and Propositional Calculus

propositional calculus and predicate calculus propositional calculus artificial intelligence and propositional calculus and logical quantifiers propositional calculus and quantification theory
Dr.NaveenBansal Profile Pic
Dr.NaveenBansal,India,Teacher
Published Date:25-10-2017
Your Website URL(Optional)
Comment
CHAPTER 4 Logic and Propositional Calculus 4.1 INTRODUCTION Many algorithms and proofs use logical expressions such as: “IF p THEN q”or “If p AND p , THEN q OR q ” 1 2 1 2 Therefore it is necessary to know the cases in which these expressions are TRUE or FALSE, that is, to know the “truth value” of such expressions. We discuss these issues in this chapter. We also investigate the truth value of quantified statements, which are statements which use the logical quantifiers “for every” and “there exist.” 4.2 PROPOSITIONS AND COMPOUND STATEMENTS A proposition (or statement) is a declarative statement which is true or false, but not both. Consider, for example, the following six sentences: (i) Ice floats in water. (iii) 2+ 2 = 4 (v) Where are you going? (ii) China is in Europe. (iv) 2+ 2 = 5 (vi) Do your homework. The first four are propositions, the last two are not. Also, (i) and (iii) are true, but (ii) and (iv) are false. Compound Propositions Many propositions are composite, that is, composed of subpropositions and various connectives discussed subsequently.Suchcompositepropositionsarecalled compound propositions.Apropositionissaidtobe primitive if it cannot be broken down into simpler propositions, that is, if it is not composite. For example, the above propositions (i) through (iv) are primitive propositions. On the other hand, the following two propositions are composite: “Roses are red and violets are blue.” and “John is smart or he studies every night.” 70 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use. CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 71 The fundamental property of a compound proposition is that its truth value is completely determined by the truth values of its subpropositions together with the way in which they are connected to form the compound propositions. The next section studies some of these connectives. 4.3 BASIC LOGICAL OPERATIONS This section discusses the three basic logical operations of conjunction, disjunction, and negation which correspond, respectively, to the English words “and,” “or,” and “not.” Conjunction, p ∧ q Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically, p∧ q read “p and q,” denotes the conjunction of p and q. Since p∧ q is a proposition it has a truth value, and this truth value depends only on the truth values of p and q. Specifically: Definition 4.1: If p and q are true, then p∧ q is true; otherwise p∧ q is false. The truth value of p∧ q may be defined equivalently by the table in Fig. 4-1(a). Here, the first line is a short way of saying that if p is true and q is true, then p∧ q is true. The second line says that if p is true and q is false, then p∧ q is false.And so on. Observe that there are four lines corresponding to the four possible combinations of T and F for the two subpropositions p and q. Note that p∧ q is true only when both p and q are true. Fig. 4-1 EXAMPLE 4.1 Consider the following four statements: (i) Ice floats in water and 2+ 2 = 4. (iii) China is in Europe and 2+ 2 = 4. (ii) Ice floats in water and 2+ 2 = 5. (iv) China is in Europe and 2+ 2 = 5. Only the first statement is true. Each of the others is false since at least one of its substatements is false. Disjunction, p ∨ q Anytwopropositionscanbecombinedbytheword“or”toformacompoundpropositioncalledthedisjunction of the original propositions. Symbolically, p∨ q read “p or q,” denotes the disjunction of p and q. The truth value of p∨ q depends only on the truth values of p and q as follows.72 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 Definition 4.2: If p and q are false, then p∨ q is false; otherwise p∨ q is true. The truth value of p∨ q may be defined equivalently by the table in Fig. 4-1(b). Observe that p∨ q is false only in the fourth case when both p and q are false. EXAMPLE 4.2 Consider the following four statements: (i) Ice floats in water or 2+ 2 = 4. (iii) China is in Europe or 2+ 2 = 4. (ii) Ice floats in water or 2+ 2 = 5. (iv) China is in Europe or 2+ 2 = 5. Only the last statement (iv) is false. Each of the others is true since at least one of its sub-statements is true. Remark: The English word “or” is commonly used in two distinct ways. Sometimes it is used in the sense of “p or q or both,” i.e., at least one of the two alternatives occurs, as above, and sometimes it is used in the sense of “p or q but not both,” i.e., exactly one of the two alternatives occurs. For example, the sentence “He will go to Harvard or to Yale” uses “or” in the latter sense, called the exclusive disjunction. Unless otherwise stated, “or” shall be used in the former sense. This discussion points out the precision we gain from our symbolic language: p∨ q is defined by its truth table and always means “p and/or q.” Negation, ¬p Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not true that ...” or “It is false that ...” before p or, if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not p,” is denoted by ¬p The truth value of¬p depends on the truth value of p as follows: Definition 4.3: If p is true, then¬p is false; and if p is false, then¬p is true. The truth value of ¬p may be defined equivalently by the table in Fig. 4-1(c). Thus the truth value of the negation of p is always the opposite of the truth value of p. EXAMPLE 4.3 Consider the following six statements: (a ) Ice floats in water. (a ) It is false that ice floats in water. (a ) Ice does not float in water. 1 2 3 (b )2+ 2=5(b ) It is false that 2+ 2 = 5. (b )2+ 2 = 5 1 2 3 Then (a ) and (a ) are each the negation of (a ); and (b ) and (b ) are each the negation of (b ). Since (a ) 2 3 1 2 3 1 1 is true, (a ) and (a ) are false; and since (b ) is false, (b ) and (b ) are true. 2 3 1 2 3 Remark: The logical notation for the connectives “and,” “or,” and “not” is not completely standardized. For example, some texts use: p & q, p· q or pq for p∧ q p+ q for p∨ q p , p¯ or ∼ p for ¬p 4.4 PROPOSITIONS AND TRUTH TABLES Let P(p,q,...) denote an expression constructed from logical variables p,q,..., which take on the value TRUE (T) or FALSE (F), and the logical connectives∧,∨, and¬ (and others discussed subsequently). Such an expression P(p,q,...) will be called a proposition.CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 73 The main property of a proposition P(p,q,...) is that its truth value depends exclusively upon the truth values of its variables, that is, the truth value of a proposition is known once the truth value of each of its variables is known. A simple concise way to show this relationship is through a truth table. We describe a way to obtain such a truth table below. Consider, for example, the proposition¬(p∧¬q). Figure 4-2(a) indicates how the truth table of¬(p∧¬q) is constructed. Observe that the first columns of the table are for the variablesp,q,... and that there are enough rows in the table, to allow for all possible combinations of T and F for these variables. (For 2 variables, as above, n 4 rows are necessary; for 3 variables, 8 rows are necessary; and, in general, for n variables, 2 rows are required.) There is then a column for each “elementary” stage of the construction of the proposition, the truth value at each step being determined from the previous stages by the definitions of the connectives∧,∨,¬. Finally we obtain the truth value of the proposition, which appears in the last column. Theactualtruthtableoftheproposition¬(p∧¬q)isshowninFig.4-2(b).Itconsistspreciselyofthecolumns in Fig. 4-2(a) which appear under the variables and under the proposition; the other columns were merely used in the construction of the truth table. Fig. 4-2 Remark: In order to avoid an excessive number of parentheses, we sometimes adopt an order of precedence for the logical connectives. Specifically, ¬has precedence over ∧ which has precedence over ∨ For example,¬p∧ q means (¬p)∧ q and not¬(p∧ q). Alternate Method for Constructing a Truth Table Another way to construct the truth table for¬(p∧¬q) follows: (a) First we construct the truth table shown in Fig. 4-3. That is, first we list all the variables and the com- binations of their truth values. Also there is a final row labeled “step.” Next the proposition is written on the top row to the right of its variables with sufficient space so there is a column under each variable and under each logical operation in the proposition. Lastly (Step 1), the truth values of the variables are entered in the table under the variables in the proposition. (b) Nowadditionaltruthvaluesareenteredintothetruthtablecolumnbycolumnundereachlogicaloperation asshowninFig.4-4.Wealsoindicatethestepinwhicheachcolumnoftruthvaluesisenteredinthetable. The truth table of the proposition then consists of the original columns under the variables and the last step, that is, the last column is entered into the table. Fig. 4-374 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 Fig. 4-4 4.5 TAUTOLOGIES AND CONTRADICTIONS Some propositionsP(p,q,...) contain only T in the last column of their truth tables or, in other words, they aretrueforanytruthvaluesoftheirvariables.Suchpropositionsarecalled tautologies.Analogously,aproposition P(p,q,...) is called a contradiction if it contains only F in the last column of its truth table or, in other words, if it is false for any truth values of its variables. For example, the proposition “p or not p,” that is, p∨¬p,isa tautology, and the proposition “p and not p,” that is, p∧¬p, is a contradiction. This is verified by looking at their truth tables in Fig. 4-5. (The truth tables have only two rows since each proposition has only the one variable p.) Fig. 4-5 Note that the negation of a tautology is a contradiction since it is always false, and the negation of a contradiction is a tautology since it is always true. Now let P(p,q,...) be a tautology, and let P (p,q,...), P (p,q,...),... be any propositions. Since 1 2 P(p,q,...) does not depend upon the particular truth values of its variables p,q,..., we can substitute P for 1 p,P for q,... in the tautology P(p,q,...) and still have a tautology. In other words: 2 Theorem 4.1 (Principle of Substitution): If P(p,q,...) is a tautology, then P(P ,P ,...) is a tautology for 1 2 any propositions P ,P ,.... 1 2 4.6 LOGICAL EQUIVALENCE Two propositions P(p,q,...) and Q(p,q,...) are said to be logically equivalent, or simply equivalent or equal, denoted by P(p, q, ...) ≡ Q(p, q, . . .) if they have identical truth tables. Consider, for example, the truth tables of¬(p∧q) and¬p∨¬q appearing in Fig. 4-6. Observe that both truth tables are the same, that is, both propositions are false in the first case and true in the other three cases. Accordingly, we can write ¬(p∧ q)≡¬p∨¬q In other words, the propositions are logically equivalent. Remark: Let p be “Roses are red” and q be “Violets are blue.” Let S be the statement: “It is not true that roses are red and violets are blue.” Then S can be written in the form ¬(p∧ q). However, as noted above, ¬(p∧ q)≡¬p∨¬q. Accordingly, S has the same meaning as the statement: “Roses are not red, or violets are not blue.”CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 75 Fig. 4-6 4.7 ALGEBRA OF PROPOSITIONS Propositions satisfy various laws which are listed in Table 4-1. (In this table, T and F are restricted to the truth values “True” and “False,” respectively.) We state this result formally. Theorem 4.2: Propositions satisfy the laws of Table 4-1. (Observe the similarity between this Table 4-1 and Table 1-1 on sets.) Table 4-1 Laws of the algebra of propositions Idempotent laws: (1a) p∨ p ≡ p (1b) p∧ p ≡ p Associative laws: (2a) (p∨ q)∨ r ≡ p∨ (q ∨ r) (2b) (p∧ q)∧ r ≡ p∧ (q ∧ r) Commutative laws: (3a) p∨ q ≡ q ∨ p (3b) p∧ q ≡ q ∧ p Distributive laws: (4a) p∨ (q ∧ r) ≡ (p∨ q)∧ (p∨ r) (4b) p∧ (q ∨ r)≡ (p∧ q)∨ (p∧ r) (5a) p∨ F ≡ p (5b) p∧ T ≡ p Identity laws: (6a) p∨ T ≡ T (6b) p∧ F ≡ F Involution law: (7)¬¬p ≡ p (8a) p∨¬p ≡ T (8b) p∧¬p ≡ T Complement laws: (9a)¬T ≡ F (9b)¬F ≡ T DeMorgan’s laws: (10a)¬(p∨ q)≡¬p∧¬q (10b)¬(p∧ q)≡¬p∨¬q 4.8 CONDITIONAL AND BICONDITIONAL STATEMENTS Many statements, particularly in mathematics, are of the form “If p then q.” Such statements are called conditional statements and are denoted by p → q The conditional p → q is frequently read “p implies q”or“p only if q.” Another common statement is of the form “p if and only if q.” Such statements are called biconditional statements and are denoted by p ↔ q The truth values of p → q and p ↔ q are defined by the tables in Fig. 4-7(a) and (b). Observe that: (a) Theconditional p → q isfalseonlywhenthefirstpart pistrueandthesecondpart qisfalse.Accordingly, when p is false, the conditional p → q is true regardless of the truth value of q. (b) The biconditional p ↔ q is true whenever p and q have the same truth values and false otherwise. The truth table of¬p∧q appears in Fig. 4-7(c). Note that the truth table of¬p∨q and p → q are identical, that is, they are both false only in the second case.Accordingly, p → q is logically equivalent to¬p∨ q; that is, p → q≡¬p∨ q76 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 In other words, the conditional statement “If p then q” is logically equivalent to the statement “Not p or q” which only involves the connectives∨ and¬ and thus was already a part of our language. We may regard p → q as an abbreviation for an oft-recurring statement. Fig. 4-7 4.9 ARGUMENTS An argument is an assertion that a given set of propositions P ,P ,...,P , called premises, yields (has a 1 2 n consequence) another proposition Q, called the conclusion. Such an argument is denoted by P ,P , ..., P Q 1 2 n The notion of a “logical argument” or “valid argument” is formalized as follows: Definition 4.4: An argument P ,P , ..., P Q is said to be valid if Q is true whenever all the premises 1 2 n P ,P ,...,P are true. 1 2 n An argument which is not valid is called fallacy. EXAMPLE 4.4 (a) The following argument is valid: p, p → q q(Law of Detachment) The proof of this rule follows from the truth table in Fig. 4-7(a). Specifically, p and p → q are true simultaneously only in Case (row) 1, and in this case q is true. (b) The following argument is a fallacy: p → q, q p For p → q and q are both true in Case (row) 3 in the truth table in Fig. 4-7(a), but in this case p is false. Now the propositions P ,P ,...,P are true simultaneously if and only if the proposition P ∧ P ∧...P 1 2 n 1 2 n is true. Thus the argument P ,P ,...,P Q is valid if and only if Q is true whenever P ∧ P ∧...∧ P is 1 2 n 1 2 n true or, equivalently, if the proposition (P ∧ P ∧...∧ P )→ Q is a tautology. We state this result formally. 1 2 n Theorem 4.3: The argument P ,P , ..., P Q is valid if and only if the proposition (P ∧P ...∧P )→ Q 1 2 n 1 2 n is a tautology. We apply this theorem in the next example. EXAMPLE 4.5 A fundamental principle of logical reasoning states: “If p implies q and q implies r, then p implies r”CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 77 Fig. 4-8 That is, the following argument is valid: p → q, q → r p →r(Law of Syllogism) This fact is verified by the truth table in Fig. 4-8 which shows that the following proposition is a tautology: (p → q)∧ (q → r)→ (p → r) Equivalently, the argument is valid since the premises p → q and q → r are true simultaneously only in Cases (rows) 1, 5, 7, and 8, and in these cases the conclusion p → r is also true. (Observe that the truth table required 3 2 = 8 lines since there are three variables p, q, and r.) We now apply the above theory to arguments involving specific statements. We emphasize that the validity of an argument does not depend upon the truth values nor the content of the statements appearing in the argument, but upon the particular form of the argument. This is illustrated in the following example. EXAMPLE 4.6 Consider the following argument: S : If a man is a bachelor, he is unhappy. 1 S : If a man is unhappy, he dies young. 2 ________________________________ S : Bachelors die young Here the statement S below the line denotes the conclusion of the argument, and the statements S and S above 1 2 the line denote the premises. We claim that the argument S ,S S is valid. For the argument is of the form 1 2 p → q, q → r p → r where p is “He is a bachelor,” q is “He is unhappy” and r is “He dies young;” and by Example 4.5 this argument (Law of Syllogism) is valid. 4.10 PROPOSITIONAL FUNCTIONS, QUANTIFIERS Let A be a given set. A propositional function (or an open sentence or condition) defined on A is an expression p(x) which has the property that p(a) is true or false for each a ∈ A. That is, p(x) becomes a statement (with a truth value) whenever any element a ∈ A is substituted for the variable x. The set A is called the domain of p(x), and the set T of all elements of A for which p(a) is true is called the truth set of p(x). In other words, p T =x x ∈ A, p(x) is true or T =xp(x) p p78 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 Frequently, when A is some set of numbers, the condition p(x) has the form of an equation or inequality involving the variable x. EXAMPLE 4.7 Find the truth set for each propositional function p(x) defined on the set N of positive integers. (a) Let p(x) be “x + 2 7.” Its truth set is6,7,8,... consisting of all integers greater than 5. (b) Let p(x) be “x + 5 3.” Its truth set is the empty set. That is, p(x) is not true for any integer in N. (c) Let p(x) be “x + 5 1.” Its truth set is N. That is, p(x) is true for every element in N. Remark: The above example shows that if p(x) is a propositional function defined on a set A then p(x) could be true for all x ∈ A, for some x ∈ A, or for no x ∈ A. The next two subsections discuss quantifiers related to such propositional functions. Universal Quantifier Let p(x) be a propositional function defined on a set A. Consider the expression (∀x ∈ A)p(x) or ∀x p(x) (4.1) which reads “For every x in A, p(x) is a true statement” or, simply, “For all x, p(x).” The symbol ∀ which reads “for all” or “for every” is called the universal quantifier. The statement (4.1) is equivalent to the statement T =x x ∈ A, p(x)= A (4.2) p that is, that the truth set of p(x) is the entire set A. The expression p(x) by itself is an open sentence or condition and therefore has no truth value. However, ∀x p(x), that is p(x) preceded by the quantifier∀, does have a truth value which follows from the equivalence of (4.1) and (4.2). Specifically: Q : If x x ∈ A, p(x)= Athen∀x p(x) istrue;otherwise, ∀x p(x) isfalse. 1 EXAMPLE 4.8 (a) The proposition (∀n∈ N)(n+ 4 3) is true sincen n+ 4 3=1, 2, 3, ...= N. (b) The proposition (∀n∈ N)(n+ 2 8) is false sincen n+ 2 8=7, 8, ...= N. (c) The symbol∀ can be used to define the intersection of an indexed collectionA i ∈ I of sets A as follows: i i ∩(A i ∈ I)=x∀ ∈ I, x ∈ A i i i Existential Quantifier Let p(x) be a propositional function defined on a set A. Consider the expression (∃x ∈ A)p(x) or ∃x, p(x) (4.3)CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 79 which reads “There exists an x in A such that p(x) is a true statement” or, simply, “For some x, p(x).”The symbol ∃ which reads “there exists” or “for some” or “for at least one” is called the existential quantifier. Statement (4.3) is equivalent to the statement T =x x ∈ A, p(x)= (4.4) p i.e., that the truth set of p(x) is not empty.Accordingly,∃x p(x), that is, p(x) preceded by the quantifier∃, does have a truth value. Specifically: Q : If xp(x) = then∃x p(x) is true; otherwise, ∃x p(x) is false. 2 EXAMPLE 4.9 (a) The proposition (∃n∈ N)(n+ 4 7) is true sincen n+ 4 7=1, 2=. (b) The proposition (∃n ∈ N)(n+ 6 4) is false sincen n+ 6 4=. (c) The symbol∃ can be used to define the union of an indexed collectionA i ∈ I of sets A as follows: i i ∪(A i ∈ I)=x∃ i ∈ I, x∈ A i i 4.11 NEGATION OF QUANTIFIED STATEMENTS Consider the statement: “All math majors are male.” Its negation reads: “It is not the case that all math majors are male” or, equivalently, “There exists at least one math major who is a female (not male)” Symbolically, using M to denote the set of math majors, the above can be written as ¬(∀x ∈ M)(x is male)≡ (∃ x ∈ M) (x is not male) or, when p(x) denotes “x is male,” ¬(∀x ∈ M)p(x)≡ (∃ x ∈ M)¬p(x) or ¬∀xp(x)≡∃x¬p(x) The above is true for any proposition p(x). That is: Theorem 4.4 (DeMorgan): ¬(∀x ∈ A)p(x) ≡ (∃ x ∈ A)¬p(x). In other words, the following two statements are equivalent: (1) It is not true that, for all a ∈ A, p(a) is true. (2) There exists an a ∈ A such that p(a) is false. There is an analogous theorem for the negation of a proposition which contains the existential quantifier. Theorem 4.5 (DeMorgan): ¬(∃x ∈ A)p(x)≡ (∀x ∈ A)¬p(x). That is, the following two statements are equivalent: (1) It is not true that for some a ∈ A, p(a) is true. (2) For all a ∈ A, p(a) is false.80 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 EXAMPLE 4.10 (a) The following statements are negatives of each other: “For all positive integers n we have n+ 2 8” “There exists a positive integer n such that n+ 2  8” (b) The following statements are also negatives of each other: “There exists a (living) person who is 150 years old” “Every living person is not 150 years old” Remark: The expression¬p(x) has the obvious meaning: “The statement¬p(a) is true when p(a) is false, and vice versa” Previously,¬ was used as an operation on statements; here¬ is used as an operation on propositional functions. Similarly, p(x)∧ q(x), read “p(x) and q(x),” is defined by: “The statement p(a)∧ q(a) is true when p(a) and q(a) are true” Similarly, p(x)∨ q(x), read “p(x) or q(x),” is defined by: “The statement p(a)∨ q(a) is true when p(a) or q(a) is true” Thus in terms of truth sets: (i) ¬p(x) is the complement of p(x). (ii) p(x)∧ q(x) is the intersection of p(x) and q(x). (iii) p(x)∨ q(x) is the union of p(x) and q(x). One can also show that the laws for propositions also hold for propositional functions. For example, we have DeMorgan’s laws: ¬(p(x)∧ q(x))≡¬p(x)∨¬q(x) and ¬(p(x)∨ q(x))≡¬p(x)∧¬q(x) Counterexample Theorem 4.6 tells us that to show that a statement∀x, p(x) is false, it is equivalent to show that∃ x¬p(x) is true or, in other words, that there is an element x with the property that p(x ) is false. Such an element x is 0 0 0 called a counterexample to the statement∀x, p(x). EXAMPLE 4.11 (a) Consider the statement∀x ∈ R,x = 0. The statement is false since 0 is a counterexample, that is,0 = 0 is not true. 1 2 (b) Consider the statement∀x ∈ R,x ≥ x.The statement is not true since, for example, is a counterexample. 2 1 1 1 1 2 2 Specifically, ( ) ≥ is not true, that is, ( ) . 2 2 2 2 2 (c) Consider the statement ∀x ∈ N,x ≥ x. This statement is true where N is the set of positive integers. 2 In other words, there does not exist a positive integer n for which n n.CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 81 Propositional Functions with more than One Variable A propositional function (of n variables) defined over a product set A= A ×···× A is an expression 1 n p(x ,x ,...,x ) 1 2 n which has the property that p(a ,a ,...,a ) is true or false for any n-tuple (a ,...a ) in A. For example, 1 2 n 1 n x + 2y + 3z 18 3 is a propositional function on N = N× N× N. Such a propositional function has no truth value. However, we do have the following: Basic Principle: A propositional function preceded by a quantifier for each variable, for example, ∀x∃y,p(x,y) or ∃x∀y∃z,p(x,y,z) denotes a statement and has a truth value. EXAMPLE 4.12 Let B=1,2,3,...,9 and let p(x,y) denote “x+y = 10.” Then p(x,y) is a propositional 2 function on A= B = B × B. (a) The following is a statement since there is a quantifier for each variable: ∀x∃y,p(x,y), that is, “For every x, there exists a y such that x + y = 10” This statement is true. For example, if x = 1, let y = 9; if x = 2, let y = 8, and so on. (b) The following is also a statement: ∃y∀x,p(x,y), that is, “There exists a y such that, for every x, we have x + y = 10” No such y exists; hence this statement is false. Note that the only difference between (a) and (b) is the order of the quantifiers. Thus a different ordering of the quantifiers may yield a different statement. We note that, when translating such quantified statements into English, the expression “such that” frequently follows “there exists.” Negating Quantified Statements with more than One Variable Quantified statements with more than one variable may be negated by successively applying Theorems 4.5 and 4.6. Thus each ∀ is changed to ∃ and each ∃ is changed to ∀ as the negation symbol ¬ passes through the statement from left to right. For example, ¬∀x∃y∃z,p(x,y,z)≡∃x¬∃y∃z,p(x,y,z)≡¬∃z∀y∃z,p(x,y,z) ≡∃x∀y∀z, ¬p(x,y,z) Naturally, we do not put in all the steps when negating such quantified statements. EXAMPLE 4.13 (a) Consider the quantified statement: “Every student has at least one course where the lecturer is a teaching assistant.” Its negation is the statement: “There is a student such that in every course the lecturer is not a teaching assistant.”82 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 (b) The formal definition that L is the limit of a sequence a ,a ,... follows: 1 2 ∀∈ 0,∃ n ∈ N, ∀nn we have a − L ∈ 0 0 n Thus L is not the limit of the sequence a ,a ,... when: 1 2 ∃∈ 0,∀n ∈ N, ∃nn such that a − L≥∈ 0 0 n Solved Problems PROPOSITIONS AND TRUTH TABLES 4.1. Let p be “It is cold” and let q be “It is raining”. Give a simple verbal sentence which describes each of the following statements: (a)¬p;(b) p∧ q;(c) p∨ q;(d) q∨¬p. In each case, translate∧,∨, and∼ to read “and,” “or,” and “It is false that” or “not,” respectively, and then simplify the English sentence. (a) It is not cold. (c) It is cold or it is raining. (b) It is cold and raining. (d) It is raining or it is not cold. 4.2. Find the truth table of¬p∧ q. Construct the truth table of¬p∧ q as in Fig. 4-9(a). Fig. 4-9 4.3. Verify that the proposition p∨¬(p∧ q) is a tautology. Construct the truth table of p∨¬(p∧ q) as shown in Fig. 4-9(b). Since the truth value of p∨¬(p∧ q) is T for all values of p and q, the proposition is a tautology. 4.4. Show that the propositions¬(p∧ q) and¬p∨¬q are logically equivalent. Construct the truth tables for ¬(p ∧ q) and ¬p∨¬q as in Fig. 4-10. Since the truth tables are the same (both propositions are false in the first case and true in the other three cases), the propositions ¬(p ∧ q) and ¬p∨¬q are logically equivalent and we can write ¬(p∧ q)≡¬p∨¬q. Fig. 4-10CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 83 4.5. Use the laws in Table 4-1 to show that¬(p∧ q)∨ (¬p∧ q)≡¬p. Statement Reason (1)¬(p∨ q)∨ (¬p∧ q)≡ (¬p∧¬q)∨ (¬p∧ q) DeMorgan’s law (2) ≡¬p∧ (¬q ∨ q) Distributive law (3) ≡¬p∧ T Complement law (4) ≡¬p Identity law CONDITIONAL STATEMENTS 4.6. Rewrite the following statements without using the conditional: (a) If it is cold, he wears a hat. (b) If productivity increases, then wages rise. Recall that “If p then q” is equivalent to “Not p or q;” that is, p → q≡¬p∨ q. Hence, (a) It is not cold or he wears a hat. (b) Productivity does not increase or wages rise. 4.7. Consider the conditional proposition p → q. The simple propositions q → p,¬p→¬q and¬q→¬p are called, respectively, the converse, inverse, and contrapositive of the conditional p → q. Which if any of these propositions are logically equivalent to p → q? Construct their truth tables as in Fig. 4-11. Only the contrapositive¬q→¬p is logically equivalent to the original conditional proposition p → q. Fig. 4-11 4.8. Determine the contrapositive of each statement: (a) If Erik is a poet, then he is poor. (b) Only if Marc studies will he pass the test. (a) The contrapositive of p → q is¬q→¬p. Hence the contrapositive follows: If Erik is not poor, then he is not a poet. (b) The statement is equivalent to: “If Marc passes the test, then he studied.” Thus its contrapositive is: If Marc does not study, then he will not pass the test. 4.9. Write the negation of each statement as simply as possible: (a) If she works, she will earn money. (b) He swims if and only if the water is warm. (c) If it snows, then they do not drive the car. (a) Note that¬(p → q)≡ p∧¬q; hence the negation of the statement is: She works or she will not earn money.84 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 (b) Note that¬(p ↔ q)≡ p↔¬q≡¬p ↔ q ; hence the negation of the statement is either of the following: He swims if and only if the water is not warm. He does not swim if and only if the water is warm. (c) Note that¬(p→¬q)≡ p∧¬¬q ≡ p∧ q. Hence the negation of the statement is: It snows and they drive the car. ARGUMENTS 4.10. Show that the following argument is a fallacy: p → q,¬ p ¬q. Constructthetruthtablefor(p → q)∧¬p→¬q asinFig.4-12.Sincetheproposition(p → q)∧¬p→¬q is not a tautology, the argument is a fallacy. Equivalently, the argument is a fallacy since in the third line of the truth table p → q and¬p are true but¬q is false. Fig. 4-12 4.11. Determine the validity of the following argument: p → q,¬ p ¬p. Constructthetruthtablefor(p → q)∧¬q→¬p asinFig.4-13.Sincetheproposition(p → q)∧¬q→¬p is a tautology, the argument is valid. Fig. 4-13 4.12. Prove the following argument is valid: p→¬q, r → q, r¬p. Construct the truth table of the premises and conclusions as in Fig. 4-14(a). Now, p→¬q, r → q, and r are true simultaneously only in the fifth row of the table, where¬p is also true. Hence the argument is valid. Fig. 4-14CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 85 4.13. Determine the validity of the following argument: If 7 is less than 4, then 7 is not a prime number. 7 is not less than 4. 7 is a prime number. First translate the argument into symbolic form. Let p be “7 is less than 4” and q be “7 is a prime number.” Then the argument is of the form p→¬q, ¬q q Now, we construct a truth table as shown in Fig. 4-14(b). The above argument is shown to be a fallacy since, in the fourth line of the truth table, the premises p→¬q and¬p are true, but the conclusion q is false. Remark: The fact that the conclusion of the argument happens to be a true statement is irrelevant to the fact that the argument presented is a fallacy. 4.14. Test the validity of the following argument: If two sides of a triangle are equal, then the opposite angles are equal. Two sides of a triangle are not equal. The opposite angles are not equal. First translate the argument into the symbolic form p → q, ¬p¬q, where p is “Two sides of a triangle are equal” and q is “The opposite angles are equal.” By Problem 4.10, this argument is a fallacy. Remark:Although the conclusion does follow from the second premise and axioms of Euclidean geometry, the above argument does not constitute such a proof since the argument is a fallacy. QUANTIFIERS AND PROPOSITIONAL FUNCTIONS 4.15. Let A=1,2,3,4,5. Determine the truth value of each of the following statements: (a) (∃x ∈ A)(x + 3 = 10) (c) (∃x ∈ A)(x + 3 5) (b) (∀x ∈ A)(x + 3 10) (d) (∀x ∈ A)(x + 3 ≤ 7) (a) False. For no number in A is a solution to x + 3= 10. (b) True. For every number in A satisfies x + 3 10. (c) True. For if x = 1, then x + 3 5, i.e., 1 is a solution. 0 0 (d) False. For if x = 5, then x + 3 is not less than or equal 7. In other words, 5 is not a solution to the given 0 0 condition. 4.16. Determine the truth value of each of the following statements where U=1,2,3 is the universal set: 2 2 2 2 2 (a)∃x∀y,x y + 1; (b)∀x∃y,x + y 12; (c)∀x∀y,x + y 12. (a) True. For if x = 1, then 1, 2, and 3 are all solutions to 1y + 1. 2 (b) True. For each x , let y = 1; then x + 1 12 is a true statement. 0 0 2 2 (c) False. For if x = 2 and y = 3, then x + y 12 is not a true statement. 0 0 0 0 4.17. Negate each of the following statements: (a)∃x ∀y, p(x,y); (b)∃x ∀y, p(x,y); (c)∃y ∃x ∀z, p(x,y,z). Use¬∀x p(x)≡∃x¬p(x) and ¬∃x p(x)≡∀x¬p(x): (a) ¬(∃x∀y, p(x,y))≡∀x∃y¬p(x,y) (b) ¬(∀x∀y, p(x,y))≡∃x∃y¬p(x,y) (c) ¬(∃y ∃x ∀z, p(x,y,z))≡∀y ∀x ∃z¬p(x,y,z)86 LOGIC AND PROPOSITIONAL CALCULUS CHAP. 4 4.18. Let p(x) denote the sentence “x + 2 5.” State whether or not p(x) is a propositional function on each of the following sets: (a) N, the set of positive integers; (b) M=−1,−2,−3,...; (c) C, the set of complex numbers. (a) Yes. (b) Although p(x) is false for every element in M, p(x) is still a propositional function on M. (c) No. Note that 2i + 2 5 does not have any meaning. In other words, inequalities are not defined for complex numbers. 4.19. Negate each of the following statements: (a) All students live in the dormitories. (b) All mathematics majors are males. (c) Some students are 25 years old or older. Use Theorem 4.4 to negate the quantifiers. (a) At least one student does not live in the dormitories. (Some students do not live in the dormitories.) (b) At least one mathematics major is female. (Some mathematics majors are female.) (c) None of the students is 25 years old or older. (All the students are under 25.) Supplementary Problems PROPOSITIONS AND TRUTH TABLES 4.20. Let p denote “He is rich” and let q denote “He is happy.” Write each statement in symbolic form using p and q. Note that “He is poor” and “He is unhappy” are equivalent to¬p and¬q, respectively. (a) If he is rich, then he is unhappy. (c) It is necessary to be poor in order to be happy. (b) He is neither rich nor happy. (d) To be poor is to be unhappy. 4.21. Find the truth tables for. (a) p∨¬q; (b)¬p∧¬q. 4.22. Verify that the proposition (p∧ q)∧¬(p∨ q) is a contradiction. ARGUMENTS 4.23. Test the validity of each argument: (a) If it rains, Erik will be sick. (b) If it rains, Erik will be sick. It did not rain. Erik was not sick. Erik was not sick. It did not rain. 4.24. Test the validity of the following argument: If I study, then I will not fail mathematics. If I do not play basketball, then I will study. But I failed mathematics. Therefore I must have played basketball. QUANTIFIERS 4.25. Let A=1,2,...,9,10. Consider each of the following sentences. If it is a statement, then determine its truth value. If it is a propositional function, determine its truth set. (a) (∀x ∈ A)(∃y ∈ A)(x +y 14) (c) (∀x ∈ A)(∀y ∈ A)(x +y 14) (b) (∀y ∈ A)(x +y 14) (d) (∃y ∈ A)(x +y 14)CHAP. 4 LOGIC AND PROPOSITIONAL CALCULUS 87 4.26. Negate each of the following statements: (a) If the teacher is absent, then some students do not complete their homework. (b) All the students completed their homework and the teacher is present. (c) Some of the students did not complete their homework or the teacher is absent. 4.27. Negate each statement in Problem 4.15. 4.28. Find a counterexample for each statement were U=3,5,7,9 is the universal set: (a)∀x,x + 3≥ 7, (b)∀x,x is odd, (c)∀x,x is prime, (d)∀x,x= x Answers to Supplementary Problems 4.25. (a) The open sentence in two variables is preceded by two quantifiers; hence it is a statement. Moreover, 4.20. (a) p→¬q; (b)¬p∧¬q; (c) q→¬p; the statement is true. (d)¬p→¬q. (b) The open sentence is preceded by one quantifier; 4.21. (a) T, T, F, T; (b) F, F, F, T. henceitisapropositionalfunctionoftheothervari- able. Note that for every y ∈ A, x +y 14 if 4.22. Construct its truth table. It is a contradiction since 0 and only if x = 1,2, or 3. Hence the truth set is its truth table is false for all values of p and q. 0 1,2,3. 4.23. First translate the arguments into symbolic form: (c) Itisastatementanditisfalse:if x = 8and y = 9, p for “It rains,” and q for “Erik is sick:” 0 0 then x + y 14 is not true. 0 0 (a)p → q, ¬p¬q(b)p → q, ¬q¬p (d) It is an open sentence in x. The truth set is A itself. 4.26. (a) Theteacherisabsentandallthestudentscompleted By Problem 4.10, (a) is a fallacy. By Problem 4.11, their homework. (b) is valid. (b) Some of the students did not complete their home- 4.24. Let p be “I study,” q be “I failed mathematics,” and work or the teacher is absent. rbe“Iplaybasketball.”Theargumenthastheform: (c) All the students completed their homework and the p→¬q, ¬r → p,q r teacher is present. 4.27. (a) (∀x ∈ A)(x+3 = 10) (c) (∀x ∈ A)(x+3 ≥ 5) Construct the truth tables as in Fig. 4-15, where the premises p→¬q,¬r → p, and q are true simul- (b) (∃x ∈ A)(x+3 ≥ 10) (d) (∃x ∈ A)(x+3 7) taneously only in the fifth line of the table, and in 4.28. (a) Here 3 is a counterexample. that case the conclusion r is also true. Hence the (b) The statement is true; hence no counterexample argument is valid. exists. (c) Here 9 is the only counterexample. (d) The statement is true; hence there is no counterexample. Fig. 4-15CHAPTER 5 Techniques of Counting 5.1 INTRODUCTION This chapter develops some techniques for determining, without direct enumeration, the number of possible outcomes of a particular event or the number of elements in a set. Such sophisticated counting is sometimes called combinatorial analysis. It includes the study of permutations and combinations. 5.2 BASIC COUNTING PRINCIPLES There are two basic counting principles used throughout this chapter. The first one involves addition and the second one multiplication. Sum Rule Principle: Suppose some event E can occur in m ways and a second event F can occur in n ways, and suppose both events cannot occur simultaneously. Then E or F can occur in m+ n ways. Product Rule Principle: Suppose there is an event E which can occur in m ways and, independent of this event, there is a second event F which can occur in n ways. Then combinations of E and F can occur in mn ways. The above principles can be extended to three or more events. That is, suppose an event E can occur in n 1 1 ways, a second event E can occur in n ways, and, following E ; a third event E can occur in n ways, and so 2 2 2 3 3 on. Then: Sum Rule: If no two events can occur at the same time, then one of the events can occur in: n + n + n +··· ways. 1 2 3 Product Rule: If the events occur one after the other, then all the events can occur in the order indicated in: n · n · n ·...ways. 1 2 3 88 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use. CHAP. 5 TECHNIQUES OF COUNTING 89 EXAMPLE 5.1 Suppose a college has 3 different history courses, 4 different literature courses, and 2 different sociology courses. (a) The numberm of waysa student can choose one of each kind of courses is: m= 3(4)(2)= 24 (b) The number n of ways a student can choose just one of the courses is: n= 3+ 4+ 2 = 9 There is a set theoretical interpretation of the above two principles. Specifically, suppose n(A) denotes the number of elements in a set A. Then: (1) Sum Rule Principle: Suppose A and B are disjoint sets. Then n(A∪ B) = n(A)+ n(B) (2) Product Rule Principle: Let A× B be the Cartesian product of sets A and B. Then n(A× B) = n(A)· n(B) 5.3 MATHEMATICAL FUNCTIONS We discuss two important mathematical functions frequently used in combinatorics. Factorial Function The product of the positive integers from 1 to n inclusive is denoted by n, read “n factorial.” Namely: n= 1· 2· 3·...· (n−2)(n−1)n = n(n−1)(n−2)·...· 3· 2· 1 Accordingly, 1= 1 and n= n(n− l). It is also convenient to define 0= 1. EXAMPLE 5.2 (a) 3=3·2·1= 6, 4=4·3·2·1= 24, 5=5· 4= 5(24)= 120. 12· 11· 10 12· 11· 10· 9 12 (b) = = and, more generally, 3·2· 1 3· 2· 1· 9 39 n(n− 1)··· (n− r + 1) n(n− 1)··· (n− r + 1)(n− r) n = = r(r − 1)···3· 2· 1 r(r − 1)···3· 2· 1· (n− r) r(n− r) (c) For large n, one uses Stirling’s approximation (wheree= 2.7128...): √ n −n n= 2πnn e