Number theory and Cryptography lecture notes

notes on number theory and cryptography, number theory and cryptography tutorial,number theory in cryptography and network security, pdf free download
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
Arithmetic, Logic and Numbers With and Introduction to Cryptography Unit Lo: Logic Edward A. Bender S. Gill Williamson c Edward A. Bender & S. Gill Williamson 2010. All rights reserved.Preface The material in this unit of study was, over several years, presented by the authors to lower division undergraduates in the Department of Mathematics and the Department of Computer Science and Engineering at the University of California, San Diego (UCSD). All material has been classroom tested by the authors and other faculty members at UCSD. The first course of a two quarter sequence was chosen from six units of study: Boolean Func- tions (Unit BF), Logic (Unit Lo), Number Theory and Cryptography (Unit NT), Sets and Functions (Unit SF), and Equivalence and Order (Unit EO), and Induction, Se- quences and Series (Unit IS). Thesecond course of the sequence was chosen from four units of study: Counting and Listing (Unit CL), Functions (Unit Fn), Decision Trees and Recursion (Unit DT), and Basic Concepts in Graph Theory (Unit GT). The order of presentation of units within the first six, as well as those within the second four, can be varied for students with a good high school background in mathematics. Discrete mathematics has become an essential tool in computer science, economics, biology, mathematics, chemistry, and engineering. Each area introduces its own special terms for shared concepts in discrete mathematics. The only way to keep from reinventing the wheel from area to area is to know the precise mathematical ideas behind the concepts being applied by these various fields. Our course material is dedicated to this task. At the end of each unit is a section of multiple choice questions: Multiple Choice Questions for Review. These questions should be read before reading the corresponding unit, and they should be referred to frequently as the units are read. We encouraged our students to be able to work these multiple choice questions and variations on them with ease and understanding. At the end of each section of the units are exercises that are suitable for written homework, exams, or class discussion. iiiivTable of Contents Unit Lo: Logic Section 1: Propositional Logic.......................................................................Lo-1 truth table, statement forms, tautology, contradiction, implication, conditional, contrapos- itive, double implication, biconditional, converse, inverse, if, only if, sufficient, necessary, unless Section 2: Predicate Logic...........................................................................Lo-12 predicate, truth set, prime, composite, Fermat number, Mersenne number, perfect numbers, Goldbachconjecture,Fermat’sLastTheorem,MarinMersenne(1588–1648), PierredeFermat (1601–1665), Christian Goldbach (1690–1764), Leonhard Euler (1707–1783), Karl Friedrich Gauss (1777–1855) Multiple Choice Questions for Review........................................................Lo-23 Notation Index....................................................................................Lo-Index 1 Subject Index......................................................................................Lo-Index 3 A star in the text () indicates more difficult and/or specialized material. vviUnit Lo Logic Logic is the tool for reasoning about the truth and falsity of statements. There are two main directions in which logic develops. • The first is the depth to which we explore the structure of statements. The study of the basic level of structure is called propositional logic. First order predicate logic, which is often called just predicate logic, studies structure on a deeper level. • The second direction is the nature of truth. For example, one may talk about state- ments that are usually true or true at certain times. We study only the simplest situation: a statement is either always true or it is considered false. “True” and “false” could be replaced by 1 and 0 (or any other two symbols) in our discus- sions. Using 1 and 0 relates logic to Boolean functions. In fact, propositional logic is the studyofBooleanfunctions,where1 plays therole of“true”and0 the roleof“false.” As we saw in Unit BF, Boolean functions can be thought of as computer circuits. Thus, proposi- tional logic, Boolean functions, and computercircuits are different ways of interpreting the same thing. Propositional logic is not sufficient for all our logic needs. Mathematics requires pred- icate logic. This and other logics are employed in the design of expert systems, robots and artificial intelligence. Section 1: Propositional Logic If it is not fresh in your mind, you should review the material in the first section of Unit BF (Boolean Functions). In that section we were wearing our “arithmetic hat.” Now we are wearing our “logic hat” and so refer to things differently: Arithmetic Hat Logic Hat 0 and 1, respectively false and true, respectively Boolean variable statement variable form of function statement form value of function truth value of statement (form) equality of function (forms) equivalence of statement forms We should explain some of these terms a bit more. • InEnglish,statementvariableshavestructure—verbs,subjects,prepositionalphrases, and so on. In propositional logic, we don’t see the structure. You’re used to that because variables in high school algebra don’t have any structure; they just stand for (unknown) numbers. Lo-1Logic • A function can be written in many ways. For example, xy+x, x+yx, x(y+1) and (x+z)y +x−yz are all ways of writing the same function. Logicians refer to the particular way a function is written as a statement form. You may wonder why we’re concernedwith statement forms since we’re not concerned with function forms in other areas of mathematics but just their values. That is a miscon- ception. We are concerned with function forms in algebra. It’s just that you’re so used to the equality of different forms that you’ve forgotten that. Knowing that certain forms represent the same function allow us to manipulate formulas. For example, the commu- tative (ab = ba and a+b = b+a) and distributive (a(b+c) = ab+ac) laws allow us to manipulate the function forms xy+x, x+yx and x(y+1) to show that they all have the same value; that is, they all represent the same function. As soon as the equality of the u v uv function forms is less familiar, you’re aware of their importance. For example (a ) =a , x x sin(2x)= 2sinxcosx and d(e )/dx=e . Since some of you may still be confused, let’s restate this. For our purposes, we shall say that two statement forms are different as statement forms, or simply different if they “lookdifferent.” Theyare thesame if they“lookthesame.” This is notvery precise,but is goodenough. Thus, forexample,p∨q andq∨plookdifferentandsoaredifferentstatement forms. We say that two statement forms are logically equivalent (or simply equivalent) if they have the same truth table. The statement forms p∨q and q∨p are equivalent (have same truth table). Likewise, (p∧q)∨r and (p∨r)∧(q∨r) are different statement forms that are equivalent, as may be seen by doing a truth table for each form and comparing them. We are familiar with these ideas from high school algebra. For example, x(y +z) and xy+xz look different but are equivalent functions. Sometimes we’ll let our logic hat slip and use Boolean function terminology. In par- ticular, we’ll often use 0 instead of “false” and 1 instead of “true.” The constant functions are particularly important and are given special names. Definition 1 (Tautology, contradiction) A statement form that represents the con- stant 1 function is called a tautology. In other words, the statement form is true for all truth values of the statement variables. A statement form that represents the constant 0 function is called a contradiction. In other words, the statement form is false for all truth values of the statement variables. Recall that some of the basic functions studied in Unit BF:not, and andor, denoted by ∼, ∧ and ∨, respectively. We defined these three functions by giving their values in tabular form, which is called a truth table just as it is for Boolean functions in Unit BF. In that unit, definitions were as follows, where we have replaced 0 and 1 by F and T to emphasize “false” and “true;” however, we’ll usually use 0 and 1. p q p∧q p q p∨q p q p “equals” q p ∼p F F F F F F F F T F T F T F F T T F T F T F T F F T F T T F F T T T T T T T T T We said therewere threefunctions, but thereis a fourth table. Besides,p “equals”q isn’t a function—is it? What happened? The statementp “equals”q is either true or false. Thus, Lo-2Section 1: Propositional Logic 2 we can think of “equals” as a function with domainF,T and rangeF,T. In symbols, 2 “equals”:F,T →F,T. In what follows, we’ll replace “equals” with the symbol “⇔” (equivalence) which is usually used in logic. We use the more familiar “=” for assigning meaning and values. Thus • q =“the sky is blue” assigns an English meaning to q. • q =p∨r says thatq “means”p∨r; that is, we should replaceq by the statement form p∨r. • p=1 means we are assigning the value 1 (true) to p. Since propositional logic can be viewed as the study of Boolean functions, the tech- niques we developed for proving results about Boolean functions (Venn diagrams, truth tables and algebraic)can also be used in propositionallogic. For convenience, we recall the theorem for manipulating Boolean statements: Theorem1(Algebraicrulesforstatementforms) Eachrulestatesthattwodifferent statement forms are equivalent. That is, they look different but have the same truth table. Associative Rules: (p∧q)∧r⇔p∧(q∧r) (p∨q)∨r⇔p∨(q∨r) Distributive Rules: p∧(q∨r)⇔ (p∧q)∨(p∧r) p∨(q∧r)⇔(p∨q)∧(p∨r) Idempotent Rules: p∧p⇔p p∨p⇔p Double Negation: ∼∼p⇔p DeMorgan’s Rules: ∼(p∧q)⇔∼p∨∼q ∼(p∨q)⇔∼p∧∼q Commutative Rules: p∧q⇔q∧p p∨q⇔q∨p Absorption Rules: p∨(p∧q)⇔p p∧(p∨q)⇔p Bound Rules: p∧0⇔0 p∧1⇔p p∨1⇔ 1 p∨0⇔p Negation Rules: p∧(∼p)⇔ 0 p∨(∼p)⇔ 1 Truth tables and algebraic rules are practically the same as the tabular method and algebraic rules for sets discussed in Section 1 of Unit SF. The next example explains why this is so. You may want to read the first four pages of Unit SF now. Example 1 (Logic and Sets) We’ve already pointed out that propositional logic and Boolean arithmetic can be viewed as different aspects of the same thing. In this example, we show that basic manipulation of sets are also related. Suppose we are studying some sets, say P,Q andR. Let the correspondinglower case letters p, q and r stand for the statement that x belongs to the set. For example p is the statement “x∈P”. Consider the distributive rule for sets: P ∩(Q∪R) =(P ∩Q)∪(P ∩R). It is equivalent to saying that x∈P ∩(Q∪R) if and only if x∈(P ∩Q)∪(P ∩R) Lo-3Logic for all x in the universal set. What does x ∈ P ∩(Q∪R) mean? It means x ∈ P and x ∈ (Q∪R). What does x ∈ (Q∪R) mean? It means x ∈ Q or x ∈ R. Putting this all together and using our logic notation, x ∈ P ∩(Q∪R) means p∧(q∨r). Similarly x∈(P∩Q)∪(P∩R) means (p∧q)∨(p∧r). Thus the set form of the distributive rule is the same as p∧(q∨r)⇔ (p∧q)∨(p∧r), the distributive rule for logic. It should beobvious how thingsare translatedbetweenset notationand logic notation and why we get the same algebraic rules. A practical consequence of this is that we can use Venn diagrams to prove logic statements just as we used them in Unit SF. Why is the tabular method for proving set identities like a truth table? The answer is simple, considerP, Q and R again. There are exactly eight possibilities for the location of x, corresponding to the eight regions of the Venn diagram. For example, if x∈ P, x6∈ Q andx∈R, then the correspondingrow in the tabular method for sets begins “Yes No Yes” and the truth table for p, q and r begins T F T. Thus the way to translate between the two methods is Yes↔T and No↔F. Implication “If it is raining, then the sidewalk is wet.” This is a simple example of an implication statement. Some other forms are “The sidewalk is wet whenever it is raining” and “If the sidewalk isn’t wet, then it isn’t raining.” We want to include implication in propositional logicsincestatementsoftheform“IfX,thenY”playanimportantpartinlogicalreasoning. To do so, we must face two problems: • It is not clear how we should view “If X, thenY” whenX is false. For example, what should we think if it isn’t raining? • Due to the variety and ambiguity of English, translation into Boolean statements may not be clear. In the remainder of this section, we investigate carefully the relationship between English language assertions and Boolean functions (Boolean statement forms) associated with im- plication. Let r = “it is raining” and let w = “the sidewalk is wet.” In symbolic notation, we use r⇒w to stand for the statement “If it is raining, then the sidewalk is wet.” Usually, when such a statement is made we are primarily concerned with the situation when r is true. For the study of logic, we must be concerned with all situations, so we need to know how to think aboutr⇒w when r is false. If it is not raining, the sidewalk may be wet (it rained earlier, the sprinklers are on, etc.) or the sidewalk may not be wet. Thus when r is false, we have no reason to disbelieve the statement r⇒w. Of course, we have no reason to believe it either, so we are free to choose whatever we want for the truth value in this case. We take the generous approach and call r⇒w true when r is false. (Actually we’re not being generous—this is the standard interpretation.) Lo-4Section 1: Propositional Logic Let’s put all this into a definition. Definition 2 (Implication) We define p⇒q to be the Boolean function, called impli- cation or p implies q or the “conditional of q by p.” As a Boolean function, p⇒q has the following truth table: p q p⇒q 0 0 1 0 1 1 1 0 0 1 1 1 The expression p⇒ q is a Boolean statement form. It is equivalent to the statement form∼p∨q, as can be seen by comparing truth tables: p q ∼p∨q 0 0 1 0 1 1 1 0 0 1 1 1 Note that the Boolean function f(p,q) defined by p⇒q has value 1 when p =0, indepen- dent of the value of q. We’ve been a bit sloppy: we’ve said r = “It is raining” and also, by the definition, r = 1. Clearly “It is raining” is not the same as “1.” What’s going on? Since we are studying the truth values of statements, we should have said r =the truth value of “It is raining.” We’ll continuewith the commonpracticeofabusing theterminologyby omitting thewords “the truth value of.” Example 2 (Implication, rain and Venn diagrams) Let R be the set of all times when it is raining and let W be the set of all times when the sidewalk is wet. What does our earlier example r ⇒ w say about the sets R and W? Suppose t is a time; that is, an element of our universal set of all times. • If t∈R, then it is raining at time t and so, by r⇒w, t∈W. Thus R⊆W. • If t6∈ R, then it is not raining at time t. In this case, r⇒w gives us no information aboutwhetheror nottis inW. Why isthat? Whenr is false,r⇒w is trueregardless of whether or not w is true; that is, whether or not t is in W. What happened to the 0 case of r⇒ w in the definition of implication? That is the case t∈R (becauser is true)andt6∈W (becausew is false). Since the definition of implication says this is false, it says that this cannot happen. This is a consequence of R⊆W. This is the way we represent p⇒q with Venn diagrams: There is a set P where p is true and another set Q where q is true and we insist that P ⊆Q. Lo-5Logic How can we show that p⇒ q is not true for specific p and q? (For example, “If it is raining, then my car won’t start.”) We must find an instance wherep is true and q is false because this is the only time p ⇒ q is false. (It’s raining, but my car starts.) You’ll see more of this later. Example 3 (Statement forms associated with implication) Here is a table that defines the basic statement forms associated with the conversational use of implication. p q p⇒q ∼q⇒∼p q⇒p ∼p⇒∼q p⇔q 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 Starting with the statement form p ⇒ q, the statement form ∼q ⇒ ∼p is called the contrapositive of p⇒q, the statement form q⇒p is called the converse of p⇒q, and the statementform∼p⇒∼q is called the inverse ofp⇒q. Note that, although the statement anditscontrapositivearedifferentstatementforms(theylookdifferent)theyareequivalent (i.e., the same as Booleanfunctions). Likewise, the converse and theinverse are equivalent. But, and this is important, the statement and its converse are not equivalent. The final statement form p⇔ q is called double implication or “biconditional” and is equivalent to (p⇒q)∧(q⇒p). Here, in tabular form, are some additional facts related to implication. p q p⇒q ∼p∨q ∼(p⇒q) p∧∼q 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 The statement forms p⇒q and∼p∨q are equivalent as are∼(p⇒q) and p∧∼q. Example 4 (Right triangles and the Pythagorean theorem) Throughout this ex- ample, suppose 0 a≤ b≤ c are some fixed numbers. Take R = “The triangle with side 2 2 2 lengths a,b,c is a right triangle” and P = “a +b =c .” We know from high school that “If R then P.” As a Boolean statement form we may write R⇒P. If you proved this fact 2 2 2 by starting with a right triangle and using a geometric argument to show thata +b =c , then the statement form R⇒ P represented the state of your knowledge at that point in 2 2 2 time. You then probably went on to learn the law of cosines: a +b −2ab cos(θ) = c . Using that, you can easily see that the converseP ⇒R is true. Now you can represent the state of your knowledge by R⇔P. The statement form R⇒ P is equivalent to ∼R∨P. Either a triangle is not a right 2 2 2 triangle or it satisfies a +b =c . Start with the statement, “If the triangle with side lengths a,b,c is a right triangle, 2 2 2 then a +b =c .” Lo-6Section 1: Propositional Logic 2 2 2 • The contrapositive of that statement is “If a +b = 6 c , then the triangle with side lengths a,b,c is not a right triangle.” 2 2 2 • The converse is, if a +b = c , then the triangle with side lengths a,b,c is a right triangle.” • The inverse is, “If the triangle with side lengths a,b,c is a not right triangle, then 2 2 2 a +b 6=c .” Example 5 (The many English forms for p⇒q) In this example we’ll discuss most of the ways implication is written in English. Pay careful attention to when we use the phrase “statement form” and when we use the phrase “Boolean function.” Be sure to read the last part of the example where we discuss the distinction between statement form and Boolean function further. • if ... then: The basic English form, “If p then q,” is understood to stand for the statement form p ⇒ q. Note that the “if” is associated with p. Alternatively to this, one sees “q if p.” Again, the “if” is associated with p, so this stands for the statement form p ⇒ q. Thus, “If it’s raining, then it’s cloudy” is interpreted as the samestatementformas“It’scloudyif it’sraining.” Bothstandfor thestatementform “raining”⇒ “cloudy.” • only if: Sometimes we say “p only if q,” as in “I’ll go to the party only if I finish studying.” Some people would paraphrase this as, “If I don’t finish studying, then I won’t go to the party.” In other words “p only if q” is translated into the statement form ∼q ⇒ ∼p. This statement form is equivalent, as a Boolean function, to the statement form p⇒q, because an implication form is equivalent to its contrapositive form. In other words, “p only if q”, however it is interpreted as a statement form, is equivalent as a Boolean function to “If I go to the party, then I finished studying.” Thus the phrase “p only if q” can be translated as a Boolean function into either one of the equivalent statement forms ∼q ⇒ ∼p or p ⇒ q, whichever is most convenient for the discussion at hand. • if and only if: The biconditional, p ⇔ q is sometimes stated as “p if and only if q” and written “p iff q”. • sufficient: The expression, “p is sufficient forq”(or “p is a sufficient condition for q”) is usually translated into the statement form p⇒ q. Some students find it helpful to (silently to themselves) expand this phrase to “p is sufficient to force q to happen.” Then it is easier to remember that this means p⇒q. Instead of saying “p is sufficient for q”, one sometimes says “a sufficient condition for q is p.” • necessary: Thestatement“pisnecessaryforq”usuallystandsforthestatementform ∼p⇒∼q. Somestudents(againsilentlytothemselves)expandthisto“pisanecessary consequenceofq.” They find this easier to associatewith the equivalent (as a Boolean function) form q ⇒ p. Instead of saying “p is necessary for q”, one says “a necessary condition for q is p.” • necessary and sufficient: Combining the two previous bulleted items, we see that “p is necessary and sufficient for q” is equivalent top⇔q, the biconditional. Notice that we simply combined “necessary” and “sufficient”, just as we combined “if” and “only if” earlier to get the biconditional. Lo-7Logic • unless: Another possible source of confusion is the term “unless.” To say “p unless q” is, formally, to specify the statement form ∼q ⇒ p. The most common usage of “unless” in English is something like, “The building is safe, unless the fire alarm is ringing.” Formally, this means, “If the fire alarm is not ringing, then the building is safe.” Think of a night watchman sitting in his office with the fire alarm on the wall. Since the alarm isn’t ringing he relaxes, maybe even takes a nap. His assumption is that “If the fire alarm is not ringing then all is well, the building is safe, I can relax.” Ifyou asked him, “Whyare you sleeping?” hemight reply, “Thebuilding is safe unless the fire alarm is ringing.” An equivalent Boolean function is ∼p ⇒ q, the contrapositive of ∼q ⇒ p. Thus we have “Ifthebuilding is notsafe, thenthefire alarmisringing.” Notethesymmetry in translating “p unless q” into either of the equivalent forms ∼p⇒ q or ∼q ⇒ p. In translating “p unless q” into a Boolean function, simply apply “∼” to one of p or q and have that imply the other without applying “∼”. Let’s review the role of the concepts of a “statement form” and a “Boolean function” in the above discussion. (a) Generally, when we are translating an English description of an implication into sym- bolic form, we are concerned most of all with obtaining the correct Boolean function. With a little practice you will find this easy to do. (b) In the rare case when we are being pedantic and want to know if some statement form is the contrapositive, converse, or inverse, of an implication described in English, then we need to associate a precise statement form with the English sentence. Our policy will be to always give you that statement form when you need to know it for the discussion or question. The one exception to this policy is the case of “if p then q” (or “q if p”) which we always associate with the statement form p⇒q. Thus, in most cases, as with other English usages, all you will need to be able to do is translate “if p then q” into an equivalent form as a Boolean function: p⇒ q, ∼q ⇒∼p, ∼p∨q, etc. Example 6 (A way of translating English implications) Of course, you can mem- orize the rules from the previous example (and that may be a good idea), but what if you forgetorifyou runintosomethingnew? Supposewe seeasentencethatrelatestwophrases A and B; for example, “If A then B” or “A requires B.” Suppose we also realize that an implication is involved. How can we determine whetherto writeA⇒B orB⇒A or some other implication? Here’s a trick: The truth table for p ⇒ q has only one row which is false and that occurswhenp is true andq is false. Take your sentence and figure out how to make it false and set things up so that it corresponds to (True)⇒(False). Let’s do some examples. What about “A requires B?” Consider “Fishes require water.” This is false if some- thing is a fish and does not require water. In general “A requires B” is false when A is true and B is false. Thus, we have A⇒B. What about “A is necessary for B?” Consider “Enrollment is necessary for credit.” ThisisfalseifIreceivecrediteventhoughIamnotenrolled. Inotherwords“Aisnecessary for B” is false when B is true and A is false. Thus we can write it as B⇒A. Lo-8Section 1: Propositional Logic What about “A unlessB?” Consider “I will flunk unless I study.” This is false when I don’t flunk and I don’t study. Thus, it is false whenA andB are both false. Since we need (True)⇒(False), we need to negate something. One possibility is ∼A ⇒ B and another is ∼B ⇒ A. Which is correct? They both are — one is the contrapositive of the other. However, they sound different in English. Compare “If I passed, then I studied” and “If I don’t study, then I won’t pass.” The first is celebration after the fact and the second is a warning about what I should do. What about “A or B?” Wait There’s no implication here. In logic all that matters is the truth table. Any statement form involving two variables that is false in only one of the four cases can be written as an implication. “A or B” is false only when both A and B are false. Thus ∼A⇒ B. You’ve actually seen this before: we learned that p⇒ q and ∼p∨q are equivalent, so set p =∼A and q =B. Exercises for Section 1 1.1. In Example 1 we noted that algebraic operations in propositional logic, set the- ory and Boolean functions can be viewed as different aspects of the same thing. What logic and set operationscorrespondto the exclusive or operationfor Boolean functions? 1.2. Let h = “he is happily married,” and w = “he is wealthy,” and s = “he is smart.” Write the following statements in symbolic form: (a) He is happily married and wealthy but not smart. (b) He is not wealthy, but he is happily married and smart. (c) He is neither happily married, nor wealthy, nor smart. 1.3. Let n = “Nancy will major in computer science” and k = “Karen will major in computer science.” Write the following statement in symbolic form: Either Nancy will major in computer science or Karen will major in computer science, but not both. 1.4. We have three flags: COM which indicates that the computer is out of memory, DEO which indicates that a disk error has occurred, ZIP which indicates that the ZIP disk does not have enough memory. Weuseptomean“theCOMflagisoff”,thatis, theflagiszero. Weduseq andr to mean the DEO and ZIP flags, respectively, are off. Write the following statements in symbolic form: (a) COM is off and DEO is off and ZIP is off. Lo-9Logic (b) COM is off but DEO is on. (c) There is enough memory in the computer; however, either a disk error has occurred or the ZIP disk is out of memory. (d) The computer is out of memory and no disk error has occurred, but the ZIP disk is out of memory. (e) Either the computer is out of memory or both COM == 0 and DEO == 0.  1.5. Is the statement form (p∧q)∨ ∼p∨(p∧∼q) ∨r a tautology, contradiction, or neither? 1.6. Is the statement form (p∧∼q)∧(∼p∨q)∧r a tautology, contradiction, or neither?  1.7. Is the statement form (∼p∧q)∧(q∨r) ∧∼q∧r a tautology, contradiction, or neither? 1.8. Construct a truth table for p∨(∼p∧q)⇒q. 1.9. Construct a truth table for p∨(∼p∧q)⇒∼q. 1.10. Construct a truth table for (p⇒q)⇒ (q⇒p). 1.11. Write negations of the following statements in English. Make them as easily understood as possible. (a) If P is a pentagon then P is a polygon. (b) If Tom is Ann’s father, then Jim is Ann’s uncle and Sue is her aunt and Mary is her cousin. 1.12. Write the converses and inverses for the statements in the previous exercise. 1.13. Why is the assertion, “There is some statement p ⇒ q that is not equivalent to its contrapositive,” equivalent to the statement, “There is some statement p ⇒ q whose converse is not equivalent to its inverse?” (Note: both statementsare false.) 1.14. Write the contrapositives for the statements in Exercise 1.11. 1.15. Write the contrapositive of the statement “Dennis won’t enter the America’s Cup unlessheis sure ofvictory.” Use the interpretationof“punlessq” asthestatement form∼p⇒q. 1.16. You were told by your high school principal that you will “graduate with honor” (call thatH) only if you either “make the honor roll each semester” (M) or “com- plete all language requirements” (C), and if, in addition, you “get straight A’s in Lo-10Section 2: Predicate Logic biology”(B)and“letterinatleastoneathleticactivity”(A). Youletteredintrack, got straight A’s in all your science classes (including biology), and completed all languagerequirements, but at graduationyou were not given any honors. Did your high school principal lie to you? 1.17. Write two different statement forms using “if” and “then” that are equivalent to the following: “Learning to program in C is a necessary condition for learning to program in C++. ” 1.18. Given (∼p∨q)⇒ (r∨∼q), rewrite it as a statement form using only∼ and∧.     1.19. Given p⇒ (q⇒ r) ⇔ (p∧q)⇒ r ∧∼p∧∼q∧∼r, rewrite it using only ∼ and∨. 1.20. Start with the statement form “Getting up when the alarm rings is a sufficient condition for me to get to work on time.” Rewrite it in an equivalent if- then form. 1.21. Start with the statement form, “Having sides of length 3, 4, and 5 is a sufficient condition for this triangle to be a right triangle.” Rewrite it in an equivalent if- then form. 1.22. Start with the statement form, “Doing all of the programming assignments is a necessary condition for Jane to pass her Java course.” Rewrite this statement in an equivalent if-then form. 1.23. “If the program is running then there is at least 250K of RAM.” Which of the following are equivalent to this statement? (a) If there is at least 250K of RAM then the program is running. (b) If there is less than 250K of RAM then the program is not running. (c) The program will run only if there is at least 250K of RAM. (d) If the program is not running then there is less than 250K of RAM. (e) A necessary condition for the program to run is that there are at least 250K of RAM. (f) A sufficient condition for the program to run is that there is at least 250K of RAM. Lo-11Logic Section 2: Predicate Logic Wehavebeenstudyingstatementsthatareeithertrueorfalse. But,considerthestatement 2 “x 1.” Inordertodecideifthisstatementistrueorfalse,weneedtoknowthenumerical 2 2 value of x. If x = 1.1, then “x 1” is true. If x = 0.9, then “x 1” is false. The best 2 2 way to think of this is to regard the statement “x 1” as a function S(x) =“x 1.” If we take this point of view, we need to specify the domain of S. First suppose the domain of S is R, the set of all real numbers. The codomain (or range) of S, by our description 2 just given, is a set of statements that are either true or false (e.g., S(0.9) = “0.9 1”, 2 S(2.3)= “2.3 1”). The function S is an example of a predicate. Definition 3 (Predicate and truth set) A predicate is any function whose codomain is statements that are either true or false. There are two things to be careful about: • The codomain is statementsnot the truth value of the statements. • The domain is arbitrary — different predicates can have different domains. The truth set of a predicate S with domain D is the set of those x∈ D for which S(x) is true. It is written x∈DS(x) is true or simply xS(x). 2 Note that S(0.9) = “0.9 1” is a correct statement consistent with the way we commonly use functional notation. But S(0.9) = FALSE or S(0.9) = 0 is not a correct 2 statement even though “0.9 1” is false. This is because the codomain of S is a set of statements,nottheset0,1. Insteadof“S(0.9)=0”weshouldsay“S(0.9)isfalse.” Like- wise, we say “S(1.1) is true.” These are sometimes shortened to “∼S(0.9)” and “S(1.1).” The expressionxS(x) may look strange, but it is consistent with the usual use of the notation. If the domain is known, there is no need to mention it and x ... means 2 the set of those x for which ... is true. The truth set of the predicate S(x) = “x 1” with domainR is the setxx 1∪xx−1. With some domains, it is more natural to think of a predicate as a function of more than one variable. For example, the domain may be R×R and the predicate may be   2 2 “P(x,y) = (x y 0) ⇒ (x y ) .” Notice that P(x,y) is true for all x,y ∈ R. In other words “For all x,y ∈R,S(x,y)” is true. This sort of statement is the essence of predicate logic, so we introduce some terminology. Definition 4 (Quantifiers) The phrase “for all” is called a universal quantifier and ◦ is written ∀ (“A” rotated 180 ). If S(x) is a predicate and the set D is contained in the domain of x, the statement “∀x∈ D, S(x)” is read “for all x∈ D, S(x) is true,” or just “for allx∈D,S(x).” The statement “∀x∈D, S(x)” is true if and only if S(x) is true for every x∈ D; otherwise the statement “∀x∈ D, S(x)” is false. If the value of D is clear, we may write simply∀xS(x). The phrase “for some” is called an existential quantifier and is written∃ (“E” rotated Lo-12Section 2: Predicate Logic ◦ 180 ). If S(x) is a predicate and the set D is contained in the domain of x, the statement “∃x∈D, S(x)” is read “for some x∈D, S(x) is true,” or just “for some x∈D,S(x).” It is also read “there exists x∈D such that S(x).” The statement “∃x∈D, S(x)” is true if and only if S(x) is true for at least one x∈D; otherwise the statement “∃x∈D, S(x)” is false. If the value of D is clear, we may write simply∃xS(x). In terms of truth sets: • “∀x∈D, S(x)” is equivalent to saying that the truth set of S(x) contains the set D. • “∃x∈D, S(x)” is equivalent to saying that the truth set ofS(x) contains at least one element of the set D One can view much of mathematics as an attempt to understand the truth sets of certain 2 predicates. Forexample,canyoudescribethetruthsetofthepredicateS(b,c) = “x +bx+c 2 has no real roots”? You can answer this if you know that “the roots of x +bx+c are √ √ 2 (−b± b −4c)/2” is true for all (b,c)∈R×R and that “( d∈R)⇔ (d≥ 0)” is true for 2 all d∈R. The answer is(b,c)b 4c. To work with the notation and also introduce ideas we will need later, we’ll look at some examples from elementary number theory. The word “elementary” here means easy to state, not, necessarily, easy to solve. To make it easier to specifydomains, we need some notation. Definition5(Notationforsetsofnumbers) RecallthatRdenotestherealnumbers,Z denotestheintegers,andQdenotestherationalnumbers(ratiosofintegers). Inaddition,N + denotes the nonnegative integers (the “natural numbers”),N denotes the nonzero natural numbers (positive integers), and P denotes the primes. A natural number n is prime if n ≥ 2 and the only divisors of n are n and 1. An integer n ≥ 2 that is not prime is composite. The number 2 is the smallest prime and the only even prime. The other primes less than 20 are 3,5,7,11,13,17,19. Example 7 (Goldbach’s conjecture) A mathematician named Christian Goldbach (1690–1764),noticedthat 4 =2+2, 6 = 3+3, 8 =3+5, 10 = 5+5, 12= 5+7, 14 =7+7, 16 =5+11, etc., making him think that every even number greater than or equal to 4 can be written as the sum of two primes. We can state this in our notation:     ∀n∈N, (n≥ 4)∧(n even) ⇒ ∃p,q∈P, n =p+q . Goldbach made this conjecture in 1742 in a letter to Euler (1701-1783). Of course, it can be written in various other ways; for example, ∀n≥ 2, ∃p,q∈P, 2n=p+q, where it is understood from the context that n must be an integer and not something like √ 5 or π. Lo-13Logic Sadly (for mathematicians, since few others are interested) it is unknown whether or not Goldbach’s conjecture is true. At least we have learned how to make the assertion, if not how to prove or disprove it. However, something is known for odd numbers: It is known that   ∃K∈N, ∀n≥K, (n odd)⇒∃p,q,r∈P, n=p+q+r is true. This can be stated as “every sufficiently large odd number is the sum of three primes.” (The“sufficientlylarge”isdueto“n≥K.”) ThiswasprovedbyIvanVinogradov (1891–1983) in 1937. Example 8 (Sets and logic again) In Example 1 we saw how set identities could be thought of in terms of propositionallogic. We can also phrase this in predicatelogic terms. Let U be the universal set. For every set A,B,C and so on that is being considered, introduce the predicates A(x),B(x),C(x) and so on. Define A(x) to be true if and only if 1 x∈A and do likewise for the other predicates. A statement about sets is now equivalent to the corresponding statement about predicates with a universal quantifier. For example, ∼(A∪B)= (∼A∩∼B) is true if and only if   ∀x∈U, ∼(A(x)∨B(x))⇔ (∼A(x)∧∼B(x)) . Why is that? The logic statement asserts thatx∈∼(A∪B) if and only if x∈(∼A∩∼B). This is essentially the element method of proof. Example 9 (Quantifiers and negation) Let R(x) = “x+2 is prime” be a predicate. The statement “∀n∈P, R(n)” is an example of the universal quantifier “for all” applied to this predicate. Another way to say the same thing is “∀(n∈P), (n+2∈P).” We have used parentheses to make it easier to see that the predicate is n+2 ∈ P and that n ∈ P belongs with the quantifier. You should practice inserting parentheses in what follows to make it easier to read. Using the normal English meanings of the statements, you should be able to see that the negation of these statements is “∃n∈P,∼R(n),” which can be written “∃ n∈P, n+2∈/ P.” Both negation statement forms mean the same thing. The symbol “∈/” is the negation of∈. Since∈ stands for “is in” or “is an element of,”∈/ stands for “is not in” or “is not an element of.” In this case, “∀ n∈P, R(n)” is false and “∃ n∈P, ∼R(n)” is true since 7∈P and 9 ∈/ P. When ∃ is read “there exists,” the symbol ∋ is sometimes used for “such that.” Thus we can write either “∃n∈P, n+2∈/P” or “∃n∈P∋ n+2∈/P.” Thenegationofa“forall”togeta“forsome”inthepreviousexampleisanapplication of the following theorem for moving negation through quantifiers. You should be able to 1 If you remember the definition of “characteristic function,” you should be able to see that A(x) is simply the characteristic function for the set A. Lo-14

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.