Logic and Proofs PDF

IT’S A PRANK INSTRUCTOR: MARK REY A. AMPUAN,  THE FOUNDATIONS: LOGIC AND INSTRUCTOR: MARK REY A. AMPUAN, LPT PROOFS INSTRUCTOR: MARK REY A. AMPUAN,  Problem Solving using inductive and deductive reasoning  Inductive reasoning Examples: 1. Use induct...

IT’S A PRANK INSTRUCTOR: MARK REY A. AMPUAN,  THE FOUNDATIONS: LOGIC AND INSTRUCTOR: MARK REY A. AMPUAN, LPT PROOFS INSTRUCTOR: MARK REY A. AMPUAN,  Problem Solving using inductive and deductive reasoning  Inductive reasoning Examples: 1. Use inductive reasoning to predict the next number in each of the following lists. a. 3, 6, 9, 12, 15, ? b. 1, 3, 6, 10, 15, ? 2. Pick a number. Multiply the number by 8, add 6 to the product, divide the sum by 2, and subtract 3. Use inductive reasoning to make a conjecture.  Deductive reasoning 2. Each of four neighbors, Sean, Maria, Sarah, and Brian, has a different occupation (editor, banker, chef, or dentist). From the ff. clues, determine the occupation of each neighbor. a. Maria gets home from work after the banker but before the dentist. b. Sarah, who is the last to get home from work, is not the editor. c. The dentist and Sarah leave for work at the same time. d. The banker lives next door to Brian. There are four students: Alice, Bob, Carol, and David. Each of them enjoys a different hobby (gardening, painting, cycling, or cooking). From the following clues, determine who enjoys which hobby: a) Alice does not enjoy gardening or cycling. b) The person who enjoys painting lives next to Bob. c) Carol enjoys cycling. d) The person who enjoys gardening lives next to both Alice and Carol. e) David does not live next to the person who enjoys cycling. In CMC there is a group of friends namely Tom, Lily, Max, and Sarah. each own a different pet: a dog, a cat, a bird, or a rabbit. From the following clues, determine which pet each friend owns: a) Tom does not own the rabbit or the bird. b) The person who owns the cat lives next to Sarah. c) Lily, who is allergic to fur, does not own the dog or the cat. d) Max's pet is not the bird. e) The person who owns the rabbit lives next door to Tom. Problem-solving strategies Polya’s Problem Solving Strategy Polya: “The Father of Problem Solving” George Pólya was a Hungarian mathematician. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory. He is also noted for his work in heuristics and mathematics education.  Polya's four-step Problem Solving strategy In 1945 George Polya published the book How To Solve It which quickly became his most prized publication. It sold over one million copies and has been translated into 17 languages. In this book he identifies four basic principles of problem solving. Four steps of problem solving strategies Polya’s Problem Solving Strategy 1. Understand the problem Do you understand all the words used in stating the problem? What are you asked to find or show? Can you restate the problem in your own words? Can you think of a picture or diagram that might help you understand the problem? Is there enough information to enable you to find a solution? 2. Devise a plan There are many reasonable ways to solve problems. The skill lies in choosing an appropriate strategy. This best learned by solving many problems. You will find choosing a strategy increasingly easy. 3. Carry out the plan This step is usually easier than devising the plan. In general, all you need is care and patience, given that you have the necessary skills. Persist with the plan that you have chosen. If it continues not to work discard it and choose another. Don't be misled, this is how mathematics is done, even by professionals. 4. Look back/review the solution Much can be gained by taking the time to reflect and look back at what you have done, what worked, and what didn't. Doing this will enable you to predict what strategy to use to solve future problems.  Problem Solving Strategies Guess and check Use a model Look for a pattern Consider special cases Make an orderly list Work backwards Draw a picture Use direct reasoning Eliminate possibilities Use a formula Solve a simpler Solve an equation problem Use symmetry  Discovery Learning 1. A baseball team won two out of their last four games. In how many different orders could they have two wins and two losses in four games? 2. The product of the ages, in years, of three teenagers is 4590. None of the teens are the same age. What are the ages of the teenagers? 3. Mang Tomas owns goats and ducks. Counting heads there are 39. Counting legs there are110. How many goats and how many ducks has Mang Tomas?  EXAMPLES 1. A baseball team won two out of their last four games. In how many different orders could they have two wins and two losses in four games? ❑Understand the problem. ❑Devise a plan. ❑Carry out the plan. ❑Review the solution. 1. Understand the problem There are many different orders. The team may have won two straight games and lost the last two (WWLL). Or, maybe they lost the first two games and won the last two (LLWW). Of course, there are other possibilities such as WLWL. 2. Devise a Plan We will make an organized list of all the possible orders. An organized list is a list that is produced using a system that ensures that each of the different orders will be listed once and only once. 3. Carry out the plan Each entry in our list must contain two Ws and two L’s. We will use a strategy that makes sure each order is considered with no duplication. One such strategy is always to write a W unless doing so will produce too many W’s or a duplicate of one of the previous orders. If it is not possible to write a W then and only then, do we write an L. This strategy produces the six different orders shown below: 1. WWLL (start with two wins) 2. WLWL (start with one win) 3. WLLW 4. LWWL (start with one loss) 5. LWLW 6. LLWW (start with two losses) 4. Review the solution We made an organized list. The list has no duplicates and the list considers all possibilities, so we are confident that there are 6 different orders in which the baseball team can win exactly two out of 4 games. 4. Each one – Ann, Enya, Alvin, and Johnny have different favorite color among red, blue, green, and orange. No person’s name contains the same number of letters as his/her favorite color. Alvin and the boy who likes blue live in different parts of town. Red is the favorite color of one of the girls. What is each person’s favorite color?  Get ½ sheet of paper 1. The product of the ages, in years, of three teenagers is 4590. None of the teens are the same age. What are the ages of the teenagers? 2. Mang Tomas owns goats and ducks. Counting heads there are 39. Counting legs there are110. How many goats and how many ducks has Mang Tomas?  Propositional Logic Propositional logic is the study of propositions (true or false statements) and The ways of combining them (logical operators) to get new propositions. It is effectively an algebra of propositions.  PROPOSITIONAL LOGIC In this algebra, ❑ the variables stand for unknown propositions (instead of unknown real numbers) and ❑ the operators are and, or, not, implies, and if and only if (rather than plus, minus, negative, times, and divided by). ❑Just as middle/high school students learn the notation of algebra and how to manipulate it properly, we want to learn the notation of propositional logic and how to manipulate it properly.  A proposition is a declarative statement that’s either true (T) or false (F), but not both Propositions ▪ Every cow has 4 legs ▪ Riyadh is the capital of Saudi Arabia ▪ 1+1=2 ▪ 2+2=3 Not Propositions ▪ What time is it? ▪ X+1=2 ▪ Answer this question 29  PROPOSITIONAL LOGIC New propositions, called compound propositions are formed from existing propositions using logical Operators 30  Propositional Logic negation Suppose p is a proposition The negation of p is written as ¬p and has meaning: “It is not the case that p.” The proposition ¬p is read “not P” Truth table for the p ¬p negation of proposition F T ¬p T F 31 “ today is Friday” “ it is not the case that today is Friday” or “today is not Friday” “it is not Friday today”  Propositional Logic conjunction Suppose p and q are propositions The conjunction of p and q is written as p∧q The proposition p∧q is read “p and q” p q p∧q Truth table for the F F F Conjunction of two propositions F T F p∧q T F F T T T 33  Propositional Logic conjunction p is the proposition “Today is Friday” q is the proposition “It is raining today” The conjunction of p and q is proposition “ Today is Friday and it is raining today” This proposition Is true on rainy Fridays Is false on any day that is not a Friday on Fridays when it does not rain 34  Propositional Logic disjunction ▪ Inclusive Or Suppose p and q are propositions The disjunction of p and q is written as p∨q The proposition p∨q is read “p or q” p q p∨q Truth table for the F F F Disjunction (Inclusive Or) of two propositions F T T p∨q T F T T T T 35  Propositional Logic disjunction p is the proposition “Today is Friday” q is the proposition “It is raining today” The disjunction of p and q is proposition “ Today is Friday or it is raining today” This proposition Is true on any day that is either a Friday or a rainy day(including rainy Fridays) Is false on days that are not Fridays when it also does not rain 36  Propositional Logic disjunction ▪ Exclusive Or Suppose p and q are propositions The Exclusive Or of p and q is written as p⊕q The proposition p⊕q is read “p or q but not both” p q p⊕q Truth table for the Exclusive Or of two propositions F F F p⊕q F T T T F T (¬p∧q) ∨ (p∧¬q) T T F 37  Propositional Logic disjunction ▪ Exclusive Or “Tonight I will stay home or go out to a movie.” 38  Propositional Logic implication Suppose p and q are propositions The conditional statement (implication) p→q The proposition p→q is read “ if p, then q” P hypothesis – antecedent – premise q conclusion -consequence p q p→q Truth table for the F F T Implication F T T p→q T F F ¬p ∨ q T T T 39  Propositional Logic implication Terminology used to express p→q “if p, then q” “p is sufficient for q” “q if p” “q when p” “a necessary condition for p is q” “q unless ¬p“ “p implies q” “p only if q” “a sufficient condition for q is p” “q whenever p” “q is necessary for p” “q follows from p” “if p, q” 40  Propositional Logic implication p is the proposition “Ahmed learns discrete mathematics” q is the proposition “Ahmed will find a good job” The p→q is proposition “ if Ahmed learns discrete mathematics, then he will find a good job” This proposition Is false when p is true and q is false Otherwise it is true 41  Propositional Logic implication p is the proposition “today is Friday” q is the proposition “2+3=5” The p→q is proposition “ if today is Friday, then 2+3=5” This proposition p q p→q Is true because its F F T Conclusion (q) is true “ F T T T F F T T T 42  Propositional Logic implication p is the proposition “today is Friday” q is the proposition “2+3=6” The p→q is proposition “ if today is Friday, then 2+3=6” This proposition Is true every day p q p→q except Friday F F T F T T T F F T T T 43  Propositional Logic implication The conditional statement (implication) p→q “if it is raining, then the home team wins” ¬q→ ¬p is called contrapositive of p→q “if the home team does not win, then it is not raining” The proposition q→p is called converse of p→q “if the home team wins, then it is raining” ¬p→ ¬q is called inverse of p→q “if it is not raining, then the home team does not win”  Propositional Logic bi-implication Suppose p and q are propositions The biconditional statement (bi-implication) p↔q The proposition p ↔ q is read “ p if and only if q” p ↔ q is true if both p→q ∧ q→p are true p→q ∧ p←q -------🡪 p↔q p q p↔q Truth table for the F F T Bi-implication F T F p↔q T F F (p ∧ q ) ∨ (¬ p ∧ ¬ q ) T T T 45  Propositional Logic bi-implication The proposition p ↔ q has the same truth value as p→q ∧ q→p p q p→q q→p p→q ∧ q→p p↔q F F T T T T F T T F F F T F F T F F T T T T T T 46  Propositional Logic bi-implication p is the proposition “You can take the flight” q is the proposition “You buy a ticket” The p ↔ q is proposition “You can take the flight if and only if You buy a ticket” This proposition Is true if p and q are either both true or both false” 47  Propositional Logic Truth table of compound propositions ▪ Precedence of logical operators ¬∧∨→↔ 48  Propositional Logic Truth table of compound propositions Construct the Truth table of compound propositions (p ∨ ¬ q) → (p ∧ q) p q ¬q p∨¬q p∧ q (p∨¬q) → (p∧ q) F F T T F F F T F F F T T F T T F F T T F T T T 49  Propositional Logic ▪ Translating English sentence into a logical expression “You can access the internet from campus only if you are a computer science major or you are not a freshman” a: “You can access the internet from campus” b: “you are a computer science major” c: “you are a freshman” Where a,b,c are propositional variables a → (b ∨ ¬c) 50  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) ✔ Translating sentences in natural language into logical expressions is an essential part of specifying both hardware and software systems. ✔ System and software engineers take requirements in natural language and produce precise and unambiguous specifications that can be used as the basis for system development. 51  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) ✔ Express the specification ”The automated reply cannot be sent when the file system is full“ using logical connectives. P: “The automated reply can be sent” q: “The file system is full” q → ¬p ✔ System specifications should be consistent They should not contain conflicting requirements that could be used to drive a contradiction 52  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) determine whether these system specifications are consistent : ✔ “The diagnostic message is stored in the buffer or it is retransmitted” ✔ “The diagnostic message is not stored in the buffer” ✔ “if the diagnostic message is stored in the buffer, then it is retransmitted” P: “The diagnostic message is stored in the buffer” q: “The diagnostic message is retransmitted” p ∨ q ¬p p→q 53  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) p ∨ q ¬p p→q p q ¬p p∨ q p → q F F T F T F T T T T T F F T F T T F T T system specifications are consistent 54  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) determine whether these system specification are consistent : ✔ “The diagnostic message is stored in the buffer or it is retransmitted” ✔ “The diagnostic message is not stored in the buffer” ✔ “if the diagnostic message is stored in the buffer, then it is retransmitted” ✔ “The diagnostic message is not retransmitted” P: “The diagnostic message is stored in the buffer” q: “The diagnostic message is retransmitted” p ∨ q ¬p p→q ¬q 55  Propositional Logic ▪ Translating English sentence into a logical expression (System specifications) p ∨ q ¬p p→q ¬q p q ¬p p∨ q p → q ¬q F F T F T T F T T T T F T F F T F T T T F T T F system specifications are inconsistent 56  Propositional Logic ▪ Boolean Searches Logical connectives are used extensively in searches of large collections of information: Indexes of Web pages, these searches employ techniques from propositional logic. The connective AND is used to match records that contain both of the two search items. OR is used to match one or both of two search items. NOT is used to exclude a particular search item (- is used in Google). 57  Propositional Logic ▪ Logic Puzzles puzzles that can be solved using logical reasoning are known as logic puzzles. Knight “always tell the truth” Knave “always lie” You encounter two people A and B,What are A and B if A says “B is a knight” B says “ the two of us are opposite” 58  Propositional Logic ▪ Logic Puzzles Let: p: “A is a knight“ q: “B is a knight“ ¬p : “ A is a knave” ¬q: “ B is a knave” A says “B is a knight” q B says “ the two of us are opposite” (p ∧ ¬q) ∨ (¬ p ∧ q) If A is a knight Then q is true and (p ∧ ¬q) ∨ (¬ p ∧ q) is true But (p ∧ ¬q) ∨ (¬ p ∧ q) is false We can conclude that A is a knave 59  Propositional Logic ▪ Logic Puzzles Let: p: “A is a knight“ q: “B is a knight“ ¬p : “ A is a knave” ¬q: “ B is a knave” A says “B is a knight” q B says “ the two of us are opposite” (p ∧ ¬q) ∨ (¬ p ∧ q) If B is a knight (q is true) Then (p ∧ ¬q) ∨ (¬ p ∧ q) is true and q is false We can conclude that B is a knave A and B are knaves 60  Propositional Logic ▪ Logic and Bit operations A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string. 101010011 is a bit string of length nine ▪ Bitwise OR(∨), Bitwise AND (∧), Bitwise XOR(⊕) 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 Bitwise OR 1 1 1 0 1 1 1 1 1 1 Bitwise AND 0 1 0 0 0 1 0 1 0 0 Bitwise XOR 1 0 1 0 1 0 1 0 1 1 61 Chapter 1 Exercises Pages (16-20) 1,3,6,7,9,10 12-14 (b,c) 15,17 20,22,24,25,26 27-33 (e) 36-38 48 50 62  Propositional Equivalences Classification of compound propositions ▪A compound proposition that is always true is called a tautology. (p ∨ ¬p) ▪A compound proposition that is always false is called a contradiction. (p ∧ ¬p) ▪A compound proposition that is neither a tautology nor a contradiction is called a contingency. 63  Propositional Equivalences Logical equivalences compound propositions that have the same truth values in all possible cases are called Logically equivalent Compound propositions p and q are Logically equivalent if p↔q is a tautology. logical equivalence ≡ ⇔ Note ≡ and ⇔ are not logical operators(connectives). Rather they indicate a kind of logical equality. 64  Propositional Equivalences Prove that ¬[r∨(q∧(¬r → ¬p ))] ≡ ¬r∧(p∨¬q) by using a truth table. 65  Propositional Equivalences Identity laws p∧T≡p p∨F≡p Domination laws p∧F≡F p∨T≡T Idempotent laws p∨p≡p p∧p≡p Double negation law ¬(¬p) ≡ p Negation laws p∨ ¬p ≡ T p ∧ ¬p ≡ F Absorption laws p∨(p∧q) ≡ p p∧(p ∨ q) ≡ p Commutative laws p ∨ q ≡ q ∨ p p∧q≡q∧p Associative laws (p∨q)∨r ≡ p∨(q∨r) (p∧q)∧r ≡ p∧(q∧r) De Morgan’s laws ¬(p∨q) ≡ ¬p∧¬q ¬(p∧q) ≡ ¬p∨¬q Distributive laws p∨(q∧r) ≡ (p∨q)∧(p∨r) p∧(q∨r) ≡ (p∧q)∨(p∧r) T denotes the compound proposition that is always true F denotes the compound proposition that is always false 66  Propositional Equivalences p → q ≡ ¬p ∨ q ¬(p →q) ≡ p ∧ ¬q p → q ≡ ¬q → ¬ p p ∨ q ≡ ¬p → q p ∧ q ≡ ¬(p → ¬ q) (p → q) ∧ (p → r) ≡ p → (q ∧ r ) (p → q) ∨ (p → r) ≡ p → (q ∨ r ) (p → r) ∧ (q → r) ≡ (p ∨ q ) → r (p → r) ∨ (q → r) ≡ (p ∧ q ) → r p ↔ q ≡ (p → q) ∧ (q → p) p↔q≡¬p↔¬q p ↔ q ≡ (p ∧ q ) ∨ (¬ p ∧ ¬ q ) ¬ (p ↔ q) ≡ p ↔ ¬ q 67  Propositional Equivalences Use De Morgan’s law to express the negation of “Ahmed has a mobile and he has a laptop” p: “Ahmed has a mobile” q: “Ahmed has a laptop” p∧q ¬(p∧q) ≡ ¬p ∨¬q ¬ p: “Ahmed has not a mobile” ¬ q: “Ahmed has not a laptop” “Ahmed has not a mobile or he has not a laptop” 68  Propositional Equivalences ¬∧∨→↔ Show that ¬(p → q) ≡ p ∧ ¬q Show that ¬(p ∨ (¬ p ∧ q)) ≡ ¬ p ∧ ¬q Show that (p ∧ q) → (p ∨ q) is a tautology 69  Predicates and Quantifiers Predicates “x is greater than 3” This statement is neither true nor false when the value of the variable is not specified. This statement has two pats The fist part (subject) is the variable x The second (predicate) is “is greater than 3” We can denote this statement by P(x) Where P denotes the predicate “is greater than 3” Once a value has been assigned to x, the statement P(x) becomes a proposition and has a truth value. P is called Proposition function. 70  Predicates and Quantifiers Predicates let P(x) denote “is greater than 3” What are the truth values of P(4) and P(2)? let Q(x,y) denote “x=y+3” What are the truth values of Q(1,2) and Q(3,0)? let R(x,y,z) denote “x+y=z” What are the truth values of R(1,2,3) and R(0,0,1)? P(x1,x2,x3,………,xn) P is called n-place(n-ary) predicate. 71  Predicates and Quantifiers Predicates let A(c,n) denote “computer c is connected to network n” Suppose that the computer MATH1 is connected to network CAMPUS2, but not to network CAMPUS1 What are the truth values of A(MATH1, CAMPUS1) and A(MATH1, CAMPUS2) ? 72  Predicates and Quantifiers Predicates Proposition functions(Predicates) occur in computer programs. If x>0 then x:=x+1 P(x) : “x>0” If P(x) is true the assignment is executed If P(x) is false the assignment is not executed 73  Predicates and Quantifiers Universal quantification Which tell us that a predicate is true for every element under consideration. existential quantification Which tell us that there is one or more element under consideration for which the predicate is true. The area of logic that deals with predicates and quantifiers is called predicate calculus. 74  Predicates and Quantifiers The universal quantification of P(x) is the statement “P(x) for all values of x in the domain” ∀x P(x) read as “for all x P(x)” “for every x P(x)” ∀ is called universal quantifier The existential quantification of P(x) is the statement “there exists an element x in the domain such that P(x)” ∃x P(x) read as “there is an x such that P(x)” “there is at least one x such that P(x)” “for some x P(x)” ∃ is called existential quantifier 75  Predicates and Quantifiers ∀x P(x) When true P(x) is true for every x. When false there is an x for which P(x) is false. ∃x P(x) When true there is an x for which P(x) is true. When false P(x) is false for every x. 76  Predicates and Quantifiers Let Q(x) “x0” What is the truth value of ∀x Q(x) when the domain consists of all integers? Q(x) is not true for every integer number x, for example Q(0) is false. x=0 is a counterexample for the statement ∀x Q(x) Thus ∀x Q(x) is false. 78  Predicates and Quantifiers What is the truth value of ∀x (x2≥ x) when the domain a) consists of all real number? b) consists of all integers? a) is false because (0.5)2 ≥ 0.5 x2≥ x is false for all real numbers in the range 0