Discrete Mathematics I for SE PDF

EMATH 1105 DISCRETE MATHEMATICS I for SE Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department THE FOUNDATIONS Logic Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGIC ❖Proposition – basic building blocks of logic – a d...

EMATH 1105 DISCRETE MATHEMATICS I for SE Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department THE FOUNDATIONS Logic Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGIC ❖Proposition – basic building blocks of logic – a declarative sentence that is either TRUE or FALSE, but not both. ❖Example: 1. Manila is the capital of the Philippines. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGIC Example: Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. 𝑥 + 1 = 2. 4. 𝑥 + 𝑦 = 𝑧. ❖ Sentences 1 and 2 are not propositions because they are not declarative sentences. ❖ Sentences 3 and 4 are not propositions because they are neither true nor false. ❖ Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the variables. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGIC ❖Letters are used to denote propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. p, q, r, s - conventional letters used for propositional variables ❖The truth value of a proposition is TRUE, denoted by T, if it is a true proposition. ❖The truth value of a proposition is FALSE, denoted by F, if it is a false proposition. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGIC: SAMPLE PROBLEM Which of these sentences are propositions? What are the truth values of those that are propositions? a) Manila is the capital of the Philippines. T b) Osaka is the capital of Japan. F c) 2 + 3 = 5. T d) 5 + 7 = 10. F e) x + 2 = 11. Not a Proposition f) Answer this question. Not a Proposition Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGIC ❖The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago. ❖New propositions, called compound propositions, are formed from existing propositions using logical operators or connectives. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS Operators or connectives are used to create a compound proposition from two or more propositions. 1. Negation (denote  or !) 2. “And” or logical conjunction (denoted ) 3. “Or” or logical disjunction (denoted ) 4. “XOR” or exclusive or (denoted ) 5. Conditional/Implication (denoted  or →) 6. Biconditional (denoted  or ) We define the meaning (semantics) of the logical operators using truth tables. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGICAL OPERATORS NEGATION Definition. Let 𝒑 be a proposition. The negation of 𝒑, denoted by ¬𝒑 (also denoted by 𝒑 ഥ ), is the statement “It is not the case that 𝒑.” The proposition ¬𝒑 is read “not p”. The truth value of the negation of 𝒑, ¬𝒑, is the opposite of the truth value of 𝒑. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS Example: Find the negation of the proposition and express this in simple English. 1. “Michael’s PC runs Linux.” Negation➔ “Michael’s PC does not run Linux” 2. “Julienne’s smartphone has at least 32GB of memory.” Negation ➔ “Julienne’s smartphone does not have at least 32GB of memory” ➔ “Julienne’s smartphone has less than 32GB of memory” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department LOGICAL OPERATORS EXERCISES: What is the negation of each propositions? 1. Leo has a girlfriend. Ans: Leo does not have a girlfriend. 2. There is no pollution in Iloilo. Ans: There is pollution in Iloilo. 3. 2+1=3 Ans: 2 + 1 ≠ 3 4. The summer in Boracay is hot and sunny. Ans: The summer in Boracay is not hot and it is not sunny. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS TRUTH TABLE FOR CONJUNCTION THE CONJUNCTION OF TWO Definition. Let 𝑝 and 𝑞 be propositions. PROPOSITIONS The 𝑐𝑜𝑛𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑝 and 𝑞, 𝒑 𝒒 𝒑 ∧ 𝒒 denoted by 𝑝 ∧ 𝑞, is the proposition "𝑝 𝑎𝑛𝑑 𝑞". The 𝑐𝑜𝑛𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑝 ∧ T T T 𝑞 is true when both 𝑝 and 𝑞 are T F F true and is false otherwise. F T F F F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Conjunction Construct a truth table for each conjunction below: 1. 𝑥 ∧ 𝑦 2. ~𝑥 ∧ 𝑦 3. ~𝑦 ∧ 𝑥 Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Conjunction 1. 𝑥 ∧ 𝑦 1. 𝑥 ∧ 𝑦 𝒙 𝒚 𝒙 ∧𝒚 𝒙 𝒚 𝒙 ∧𝒚 T T T T T T F T F F F T F T F F F F F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Conjunction 2. ~𝑥 ∧ 𝑦 2. ~𝑥 ∧ 𝑦 𝒙 𝒚 ~𝒙 ~𝒙 ∧ 𝒚 𝒙 𝒚 ~𝒙 ~𝒙 ∧ 𝒚 T T T T F F T F T F F F F T F T T T F F F F T F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Conjunction 3. ~𝑦 ∧ 𝑥 3. ~𝑦 ∧ 𝑥 𝒙 𝒚 ~𝒚 ~𝒚 ∧ 𝒙 𝒙 𝒚 ~𝒚 ~𝒚 ∧ 𝒙 T T T T F F T F T F T T F T F T F F F F F F T F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS DISJUNCTION TRUTH TABLE FOR THE DISJUNCTION OF Definition. Let 𝑝and 𝑞 be propositions. TWO PROPOSITIONS The 𝑑𝑖𝑠𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑝 and 𝑞, denoted by 𝑝 ∨ 𝑞, is the proposition 𝒑 𝒒 𝒑∨𝒒 "𝑝 𝑜𝑟 𝑞". The T T T 𝑑𝑖𝑠𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑝 ∨ 𝑞 is false when both 𝑝 and 𝑞 are false and is true T F T otherwise. F T T F F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Disjunction Construct a truth table for each disjunction below: 1. 𝑎 ∨ 𝑏 2. 𝑎 ∨ ~𝑏 3. ~𝑎 ∨ 𝑏 Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Disjunction 1. 𝑎 ∨ 𝑏 2. 𝑎 ∨ ~𝑏 𝒂 𝒃 𝒂∨𝒃 𝒂 𝒃 ~𝒃 𝒂 ∨ ~𝒃 T T T T T F T F F T F T F F F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: Disjunction 3. ~𝑎 ∨ 𝑏 𝒂 𝒃 ~𝒂 ~𝒂 ∨ 𝒃 T T T F F T F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS EXCLUSIVE OR TRUTH TABLE FOR THE EXCLUSIVE OR Definition. Let 𝑝and 𝑞 be propositions. OF TWO PROPOSITIONS The 𝑒𝑥𝑐𝑙𝑢𝑠𝑖𝑣𝑒 𝑜𝑟 of 𝑝 and 𝑞, denoted by "𝑝 ⊕ 𝑞", is the 𝒑 𝒒 𝒑⊕𝒒 proposition that is true when exactly T T F one of 𝑝 and 𝑞 is true and is false otherwise. T F T F T T F F F Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: XOR Example 1. The circuit is either ON or OFF but not both 2. Let ab < 0, then either a < 0 or b < 0 but not both 3. You may have cake or ice cream, but not both Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS CONDITIONAL STATEMENT TRUTH TABLE FOR Definition. Let 𝑝and 𝑞 be propositions. THE CONDITIONAL STATEMENT The 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡, denoted by "𝑝 → 𝑞", is the 𝒑 𝒒 𝒑→𝒒 proposition “ if 𝑝, then 𝑞.” The T T T conditional statement 𝑝 → 𝑞 is false when 𝑝 is true and 𝑞 is false, and T F F true otherwise. F T T F F T Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: CONDITIONAL STATEMENT PRACTICE: Let 𝑝 be the statement “Maria learns discrete mathematics” and 𝑞 the statement “Maria will find a good job”. Express the statement 𝑝 → 𝑞 as a statement in English. Answers: “If Maria learns discrete mathematics, then she will find a good job.” “Maria will find a good job when she learns discrete mathematics.” “For Maria to get a good job, it is sufficient for her to learn discrete mathematics. “Maria will find a good job unless she does not learn discrete mathematics.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: CONDITIONAL STATEMENT ❖The if-then construction used in many programming languages is different from that used in logic. ❖Most programming languages contain statements such as if p then S, where p is a proposition and S is a program segment (one or more statements to be executed). Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: CONDITIONAL STATEMENT The implication of 𝑝 → 𝑞 can be also read as: ▪ If p then q ▪ p implies q ▪ If p, q ▪ p only if q ▪ q if p ▪ q when p ▪ q whenever p ▪ q follows from p ▪ p is a sufficient condition for q (p is sufficient for q) ▪ q is a necessary condition for p (q is necessary for p) Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: CONDITIONAL STATEMENT Exercise: Which of the following conditional statement is true? 1. If -1 is a positive number, then 2 + 2 = 5. True. The premise is obviously false, thus no matter what the conclusion is, the implication holds. 2. If -1 is a positive number, then 2+2=4 True. Same as above. 3. If sin x = 0, then x = 0. False. x can be a multiple of . If we let x=2, then sin x=0 but x 0. The implication “if sin x = 0, then x = k, for some k” is true. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS BICONDITIONAL STATEMENT TRUTH TABLE FOR THE Definition. Let 𝑝and 𝑞 be propositions. BICONDITIONAL STATEMENT The 𝑏𝑖𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡, denoted by "𝑝 𝑞", is the 𝒑 𝒒 𝒑 𝒒 proposition “ 𝑝, if and only if 𝑞.” The T T T conditional statement 𝑝 𝑞 is true when 𝑝 and 𝑞 have the same truth T F F values, and is false otherwise. F T F F F T Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: BICONDITIONAL STATEMENT EXAMPLE: LET 𝑝 BE THE STATEMENT “YOU CAN TAKE THE FLIGHT,” AND LET 𝑞 BE THE STATEMENT “YOU BUY A TICKET.” THEN 𝑝 𝑞 Answer: “You can take the flight if and only if you buy a ticket.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: BICONDITIONAL STATEMENT EXERCISE: WHICH OF THE FOLLOWING BICONDITIONALS IS TRUE? 1. 𝑥2 + 𝑦2 = 0 IF AND ONLY IF 𝑥 = 0 𝑎𝑛𝑑 𝑦 = 0. True. Both implications holds true. 2. X 2  0 IF AND ONLY IF X  0. False. The implication “if x2  0 then x  0” is false. Consider x=-1. The hypothesis (-1)2=1  0 but the conclusion fails. 3. 2 + 2 = 4 IF AND ONLY IF 2 < 2 True. Both implications holds true. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL OPERATORS: TRUTH TABLE REVIEW: COMPLETE THE TRUTH TABLE. 𝒑 𝒒 𝒑  𝒒 𝒑𝒒 𝒑𝒒 𝒑𝒒 𝒑𝒒 F F F T T F T T Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE The inverse is formed by negating the hypothesis and negating the conclusion Example: 𝑝 → 𝑞: If you have a Sprite, then you have a root beer. ¬𝑝 → ¬𝑞: If you do not have Sprite, then you do not have a root beer. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE The converse is formed by interchanging the hypothesis and the conclusion. Example: 𝑝 → 𝑞: If it rains, then the ground gets wet. 𝑞 → 𝑝: If the ground gets wet, then it rained. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE The contrapositive is formed by negating both the hypothesis and the conclusion, and then interchanging the resulting negations. Example: 𝑝 → 𝑞: If 15 is an odd number, then15 is a prime number. ¬𝑞 → ¬𝑝: If 15 is not a prime number, then 15 is not an odd number. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE ❖ The proposition ¬𝒑 → ¬𝒒 is called the inverse of 𝑝 → 𝑞. ❖ The proposition 𝒒 → 𝒑 is called the converse of 𝑝 → 𝑞. ❖ The proposition ¬𝒒 → ¬𝒑 is called the contrapositive of 𝑝 → 𝑞. Note: Of these three conditional statements formed from 𝑝 → 𝑞, only the contrapositive always has the same truth value as 𝑝 → 𝑞. When two compound propositions always have the same truth value we call them equivalent, so that a conditional statement and its contrapositive are equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE SAMPLE PROBLEMS. Find the converse, inverse and the contrapositive of the implication: “If today is Friday, then I have a test today.” Converse: “If I have a test today, then today is Friday.” Inverse: “If today isn’t Friday, then I don’t have a test today.” Contrapositive: “If I don’t have a test today, then today isn’t Friday.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  INVERSE, CONVERSE, CONTRAPOSITIVE SAMPLE PROBLEMS. Find the converse, inverse and the contrapositive of the implication: “The home team wins whenever it is raining.” Converse: “If the home team wins, then it is raining.” Inverse: “If it is not raining, then the home team does not win.” Contrapositive: “If the home team does not win, then it is not raining.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC Truth Tables of Compound Propositions Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC Precedence of Logical Operators Logic and Bit Operations ❖ A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one). ❖ The well-known statistician John Tukey introduced this terminology in 1946. ❖ 1 represents T (true), 0 represents F (false). ❖ A variable is called a Boolean variable if its value is either true or false. ❖ Consequently, a Boolean variable can be represented using a bit. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC EXERCISE: Construct a truth table for each of these compound propositions. a) (p∨q)→(p⊕q) b) (p⊕q)→(p∧q) c) (p∨q)⊕(p∧q) d) (p q)⊕(¬p q) e) (p q)⊕(¬p ¬r) f) (p⊕q)→(p⊕¬q) Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC ANSWER TO EXERCISE: For questions a, b, c, d and f q Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC ANSWER TO EXERCISE: For question e, q Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC Truth table for the bit operators OR, AND, XOR. ❖ Information is often represented using bit strings, which are lists of zeros and ones. ❖ When this is done, operations on the bit strings can be used to manipulate this information. Definition: A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string. Example: 101010011 is a bit string of length nine. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC ❖ We define the bitwise OR, bitwise AND, and bitwise XOR of two strings of the same length to be the strings that have as their bits the OR, AND, and XOR of the corresponding bits in the two strings, respectively. ❖ We use the symbols ∨, ∧, and ⊕ to represent the bitwise OR, bitwise AND, and bitwise XOR operations, respectively. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL LOGIC PRACTICE: Find the bitwise OR, bitwise AND, and bitwise XOR of each of these pairs of bit strings. a) 101 1110, 010 0001 b) 1111 0000, 1010 1010 c) 00 0111 0001, 10 0100 1000 d) 11 1111 1111, 00 0000 0000 Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department APPLICATIONS OF PROPOSITIONAL LOGIC Logic has many important applications to mathematics, computer science, and numerous other disciplines. Logic is used in the specification of software and hardware, because these specifications need to be precise before development begins. Propositional logic and its rules can be used to design computer circuits, to construct computer programs, to verify the correctness of programs, and to build expert systems. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  APPLICATIONS OF PROPOSITIONAL LOGIC ❖ System specifications should be consistent, that is, they should not contain conflicting requirements that could be used to derive a contradiction. ❖ When specifications are not consistent, there would be no way to develop a system that satisfies all specifications. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  APPLICATIONS OF PROPOSITIONAL LOGIC LOGIC PUZZLES ❖ Puzzles that can be solved using logical reasoning. ❖ Solving logic puzzles is an excellent way to practice working with the rules of logic. Also, computer programs designed to carry out logical reasoning often use well- known logic puzzles to illustrate their capabilities. LOGIC CIRCUITS ❖ Propositional logic can be applied to the design of computer hardware. ❖ A logic circuit (or digital circuit) receives input signals p1,p2,...,pn, each a bit [either 0 (off) or 1 (on)], and produces output signals s1,s2,...,sn, each a bit. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  APPLICATIONS OF PROPOSITIONAL LOGIC LOGIC CIRCUITS ❖ The inverter, or NOT gate, takes an input bit p, and produces as output ¬𝑝. ❖ The OR gate takes two input signals p and q, each a bit, and produces as output the signal 𝑝 ∨ 𝑞. ❖ The AND gate takes two input signals p and q , each a bit, and produces as output the signal 𝑝 ∧ 𝑞. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  APPLICATIONS OF PROPOSITIONAL LOGIC LOGIC CIRCUITS ❖ Complicated digital circuits can be constructed from three basic circuits, called gates. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  APPLICATIONS OF PROPOSITIONAL LOGIC Example: A digital circuit that produces the output (𝑝 ∨ ¬𝑟) ∧ (¬𝑝 ∨ (𝑞 ∨ ¬𝑟)) when given input bits p, q, and r. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES An important type of step used in a mathematical argument is the replacement of a statement with another statement with the same truth value. Because of this, methods that produce propositions with the same truth value as a given compound proposition are used extensively in the construction of mathematical arguments. Note that we will use the term “compound proposition” to refer to an expression formed from propositional variables using logical operators, such as p ∧ q. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Classification of compound propositions according to their possible truth values: TAUTOLOGY – a compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it CONTRADICTION – a compound proposition that is always false CONTINGENCY – a compound proposition that is neither a tautology nor a contradiction Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Example of a Tautology and a Contradiction Logical Equivalences: Compound propositions that have the same truth values in all possible cases are called logically equivalent. One way to determine whether two compound propositions are equivalent is to use a truth table. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES The compound propositions 𝑝 and 𝑞 are called logically equivalent if 𝑝 𝑞 is a tautology. The notation 𝑝 ≡ 𝑞 denotes that 𝑝 and 𝑞 are logically equivalent *Remark: The symbol ≡ is not a logical connective, and 𝑝 ≡ 𝑞 is not a compound proposition but rather is the statement that 𝑝 𝑞 is a tautology. The symbol ⟺ is sometimes used instead ≡ to denote logical equivalence. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Example below illustrates this method to establish an extremely important and useful logical equivalence, namely, that of ¬(𝑝 ∨ 𝑞) with ¬𝑝 ∧ ¬𝑞. This logical equivalence is the De Morgan laws, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Example: Show that ¬(𝑝 ∨ 𝑞) and (¬𝑝 ∧ ¬𝑞) are logically equivalent. Because the truth values of the compound propositions ¬(𝑝 ∨ 𝑞) and ¬𝑝 ∧ ¬𝑞 agree for all possible combinations of the truth values of p and q, it follows that (𝑝 ∨ 𝑞) (¬𝑝 ∧ ¬𝑞) is a tautology and that these compound propositions are logically equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Exercise: Show that 𝑝 → 𝑞 and ¬𝑝 ∨ 𝑞 are logically equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Seatwork: Show that 𝑝 ∨ ( 𝑞 ∧ 𝑟) and( 𝑝 ∨ 𝑞 ) ∧ (𝑝 ∨ 𝑟) are logically equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Logical Equivalences: Table shown contains some important equivalences. In these equivalences, T denotes the compound proposition that is always true F denotes the compound proposition that is always false. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Logical Equivalences Involving Conditional Statements Logical Equivalences Involving Biconditional Statements Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES Furthermore, note that De Morgan’s laws extend to and Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES EXAMPLE : Use De Morgan’s laws to express the negations of “Von has a cellphone and he has a laptop computer” Solution: Let p: “Von has a cellphone” q: “Von has a laptop computer.” “Von has a cellphone and he has a laptop computer” → 𝑝 ∧ 𝑞 By the first of De Morgan’s laws, ¬( 𝑝 ∧ 𝑞 ) is equivalent to ¬𝑝 ∨ ¬𝑞. Consequently, we can express the negation of our original statement as “Von does not have a cellphone or he does not have a laptop computer.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  LOGICAL EQUIVALENCES EXAMPLE : Use De Morgan’s laws to express the negations of “James will go to the concert or Wilfred will go to the concert.” Solution: Let r: “James will go to the concert.” s: “Wilfred will go to the concert.” “James will go to the concert or Wilfred will go to the concert”→ 𝑟 ∨ 𝑠. By the second of De Morgan’s laws, ¬ ( 𝑟 ∨ 𝑠) is equivalent to ¬𝑟 ∧ ¬𝑠. Consequently, we can express the negation of our original statement as: “James will not go to the concert and Wilfred will not go to the concert.” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  CONSTRUCTING NEW LOGICAL EQUIVALENCES EXAMPLE : Show that ¬(𝑝 ∨ (¬ 𝑝 ∧ 𝑞)) and ¬𝑝 ∧ ¬𝑞 are logically equivalent by developing a series of logical equivalences. We could use a truth table to show that these compound propositions are equivalent. Indeed, it would not be hard to do so. However, we want to illustrate how to use logical identities that we already know to establish new logical identities, something that is of practical importance for establishing equivalences of compound propositions with a large number of variables. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  CONSTRUCTING NEW LOGICAL EQUIVALENCES EXAMPLE : Show that ¬( 𝑝 ∨ (¬ 𝑝 ∧ 𝑞 )) and ¬𝑝 ∧ ¬𝑞 are logically equivalent by developing a series of logical equivalences. ¬ 𝑝 ∨ ¬𝑝 ∧ 𝑞 ≡ ¬𝑝 ∧ ¬( ¬ 𝑝 ∧ 𝑞) by the second De Morgan law ≡ ¬𝑝 ∧ [¬(¬𝑝) ∨ ¬𝑞] by the first De Morgan law ≡ ¬𝑝 ∧ (𝑝 ∨ ¬𝑞) by the double negation law ≡ (¬𝑝 ∧ 𝑝) ∨ (¬𝑝 ∧ ¬𝑞) by the second distributive law ≡ 𝐹 ∨ (¬𝑝 ∧ ¬𝑞) because ¬𝑝 ∧ 𝑝 ≡ 𝐹 ≡ (¬𝑝 ∧ ¬𝑞) ∨ 𝐹 by the commutative law for disjunction ≡ ¬𝑝 ∧ ¬𝑞 by the identity law for F Consequently, ¬(𝑝 ∨ (¬𝑝 ∧ 𝑞)) and ¬𝑝 ∧ ¬𝑞 are logically equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  CONSTRUCTING NEW LOGICAL EQUIVALENCES EXAMPLE : Show that ¬ ¬𝑝 ∧ 𝑞 ∧ (𝑝 ∨ 𝑞 ) ≡ 𝑝 are logically equivalent by developing a series of logical equivalences. ¬ ¬𝑝 ∧ 𝑞 ∧ 𝑝 ∨ 𝑞 ≡ ¬ ¬𝑝 ∨ ¬𝑞 ∧ (𝑝 ∨ 𝑞) (De Morgan law) ≡ 𝑝 ∨ ¬𝑞 ∧ (𝑝 ∨ 𝑞) (Double negation) ≡ 𝑝 ∨ (¬𝑞 ∧ 𝑞) (Distributive) ≡ 𝑝 ∨ (𝑞 ∧ ¬𝑞) (Commutative) ≡𝑝∨𝐹 (Negation) ≡𝑝 by the identity law for F Consequently,¬ ¬𝑝 ∧ 𝑞 ∧ (𝑝 ∨ 𝑞 ) ≡ 𝑝 are logically equivalent. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL SATISFIABILITY A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. Note that a compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, that is, if and only if its negation is a tautology. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  PROPOSITIONAL SATISFIABILITY When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem. However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department END OF DISCUSSION Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  EMath 1105 - Discrete Mathematics I for SE EMath 1105 DISCRETE MATHEMATICS I for SE ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  Quantifiers Proof of Techniques  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS QUANTIFIERS AND FIRST – ORDER LOGIC - quantifier is a symbol that quantifies the variables. If we use a quantifier before a predicate, then the predicate becomes a proposition. Quantifications: all some many none few ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS TWO TYPES OF QUANTIFICATION: 1. Universal Quantification ∀ tells us that a predicate is true for every element under consideration 2. Existential Quantification (∃) tells us that there is one or more element under consideration for which the predicate is true. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS Universal Quantification of 𝑷(𝒙) is the statement “P(x) for all values of x in the domain.” The notation ∀𝑥 𝑃(𝑥) denotes the universal quantification of 𝑃(𝑥). ∀ 𝑥 𝑃(𝑥) as “𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥𝑃(𝑥)”, “𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑥𝑃(𝑥)” An element for which 𝑃(𝑥) is false is called a counterexample of ∀ 𝑥 𝑃(𝑥). ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS EXAMPLE 1: Let 𝑃(𝑥): 𝑥 is even number and the universe of discourse for 𝑥 is the set {1, 2, 3, 4}. Find the truth value of ∀ 𝑥 𝑃(𝑥 ). EXAMPLE 2: Let 𝑃(𝑥): 𝑥 ≠ 5 and the universe of discourse for 𝑥 is the set {1, 2, 3, 4}. Find the truth value of ∀ 𝑥 𝑃 (𝑥). ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS Existential quantification of 𝑷(𝒙) is the statement “There exists some 𝑥 in the universe of discourse such that P(x)” denoted by the symbol ∃ 𝒙 𝑷( 𝒙 ) EXAMPLE 1: Let 𝑃(𝑥): 𝑥 is even number and the universe of discourse for 𝑥 is the set {1, 2, 3, 4}. Find the truth value of ∃ 𝑥 𝑃(𝑥). EXAMPLE 2: Let 𝑃(𝑥): 𝑥 > 5 and the universe of discourse for 𝑥 is the set {1, 2, 3, 4}. Find the truth value of ∃ 𝑥 𝑃(𝑥). ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS Free and Bound Variables A variable in a predicate is said to be bound if a quantifier is used before it. A variable is free if it is not bounded. The variable 𝑥 is a bound variable in both ∀ 𝑥 𝑃 (𝑥, 𝑦) and ∃ 𝑥 𝑃 (𝑥, 𝑦) whereas 𝑦 is a free variable. The scope of a quantifier is the formula immediately following the quantifier. 𝑃(𝑥, 𝑦) is the scope of the quantifier in both the cases. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS AND FIRST – ORDER LOGIC Symbolize the following by using quantifiers, predicates, and logical connectives: Example 1: The square of any real number is greater than or equal to zero. let: 𝑃(𝑥): 𝑥 is a real number 𝑄 𝑥 : 𝑥2 ≥ 0 Then in symbols, the given sentence takes the form ∀𝑥 𝑃 𝑥 𝑄 𝑥 ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS AND FIRST – ORDER LOGIC Symbolize the following by using quantifiers, predicates, and logical connectives: Example 2: Some integers are multiples of 7. let: 𝑃(𝑥): 𝑥 is an integer 𝑄(𝑥): 𝑥 is multiple of 7. Then in symbols, the given sentence takes the form ∃ 𝑥 𝑃(𝑥) 𝑄(𝑥) ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS AND FIRST –ORDER LOGIC Symbolize the following by using quantifiers, predicates, and logical connectives: Example 3: There is an integer 𝒙 such that 𝒙𝟐 = 𝟏𝟔. let: 𝑄(𝑥): 𝑥 2 = 16 Then in symbols, the given sentence takes the form ∃𝑥𝑄 𝑥 ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE QUANTIFIERS AND FIRST – ORDER LOGIC In the following, use 𝑃(𝑥) ∶ 𝑥 is an odd integer 𝑄(𝑥) ∶ 𝑥 is a prime integer 𝑅(𝑥) ∶ 𝑥 2 is an odd integer Write a statement in English corresponding to each symbolic statement. (a) ∀𝑥 𝑃 𝑥 𝑅 𝑥 Sol’n: The squares of all odd integers are odd. (b) ∀𝑥 𝑃 𝑥 ∧ 𝑄 𝑥 Sol’n: All integers are odd and prime. (c) ∃ 𝑥 (𝑃 𝑥 ∧ 𝑄(𝑥)) Sol’n: Some odd integer are prime. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  Quantifiers Proof of Techniques  EMath 1105 - Discrete Mathematics I for SE PROOF TECHNIQUES In the previous topics, we presented various ways of using logical arguments and delivering conclusions. In mathematics and computer science, mathematical logic is used to prove theorems and the correctness of programs. After formally defining the term theorem, we describe some general techniques that are used in proving theorems ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE PROOF TECHNIQUES Recall: Theorem – is a statement that can be shown to be true (under certain conditions) For example, If 𝑥 is an integer and 𝑥 is odd, then 𝑥 2 is odd, or, equivalently, For all integers 𝑥, if 𝑥 is odd, then 𝑥 2 is odd. This statement can be shown to be true. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE PROOF TECHNIQUES Theorem are typically stated as follows: 1) As facts ▪ 6 is an even integer. ▪ The equation 𝑥 2 + 1 = 0 has no solutions in real numbers. 2) As Implications/conditional statement ▪ For all integers x, if x is even, then x + 1 is odd. 3) As bi-implications/biconditional statement ▪ For all integers x, x is even if and only if x is divisible by 2. ❖ As proof may consists of previously known facts, proved results, or previous statements of proof. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE 1. DIRECT PROOF The most straight forward type of proof; the conclusion is established by logically the axioms, definitions, and earlier theorems Example: Prove that, for all integers 𝒙, if 𝒙 is odd, then 𝒙𝟐 is odd. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE DIRECT PROOF Example: Prove that, for all integers 𝒂, if 𝒙 is odd, then 𝒂𝟐 is odd. Solution: Let “𝑎” be an integer such that “𝑎2 ” is odd. Then, 𝑎 = 2𝑛 + 1 for some integer n 𝑎2 = 2𝑛 + 1 2 𝒂𝟐 = 𝟒𝒏𝟐 + 𝟒𝒏 + 𝟏 𝒂𝟐 = 𝟐(𝟐𝒏𝟐 + 𝟐𝒏) + 𝟏 𝒂𝟐 = 𝟐𝒎 + 𝟏 where 𝒎 = 𝟐𝒏𝟐 + 𝟐𝒏 𝒊𝒔 𝒂𝒏 𝒊𝒏𝒕𝒆𝒈𝒆𝒓 ∴ 𝒂𝟐 is an odd integer. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE PROOF TECHNIQUES 2. INDIRECT PROOF Indirect proof infers the conclusion “if p then q” from the premise “if not q then not p” For example, this proof can be used to established that, given an integer 𝑥, if 𝑥² is even, thus 𝑥 is even. Suppose 𝑥 is not even. Then 𝑥 is odd. The product of two odd numbers is odd, hence 𝑥² = 𝑥 ∙ 𝑥 is odd. Thus 𝑥² is not even. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE PROOF TECHNIQUES 3. PROOF BY CONTRADICTION It is shown that if some statement were true, a logical contradiction occurs, hence the statement must be false. Example: Prove that 2 is irrational by giving a proof of contradiction. Solution: Let: p = 2 is irrational. So by definition 2 = a/b where a and b are non-zero integers with no common factor ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Thus, 𝑏 2 = 𝑎 Squaring both sides: 2𝑏² = 𝑎² So 𝑎² is even, which implies that a must also be even So we can write a = 2c, where c is also an integer Substitution into the original equation: 2𝑏2 = 2𝑐 2 = 4𝑐2 Dividing both sides by 2 yields 𝑏2 = 2𝑐2 ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE 4. PROOF BY MATHEMATHICAL INDUCTION ▪In proof by mathematical induction, a single “base case” is proved, and an ”induction rule” is proved, which establishes that a certain case implies the next case. ▪Applying the induction rule repeatedly, starting from the independently proved base case, proves many, often infinitely many other cases. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE 5. Proof by construction/Proof by example Is the construction of a concrete example with a property to show that something having that property exists. It can also be used to construct a counter example to disprove a proposition that all elements have a certain property. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Proof by construction/Proof by example Example: Show that the statement: “Every positive integer is the sum of the squares of two integers” is false. Solution: To show that this statement is false, we look for a counterexample, which is a particular integer that is not the sum of the squares of two integers 3 – cannot be written as the sum of the squares of two integers Therefore, we have shown that “ Every positive integer is the sum of the squares of two integers.” is false. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE 6. Proof by equivalence/Bi-conditional Proof A statement of the form p q, we show that p → q and q → p are both true The validity of this approach is based on the tautology. (p q) (p → q) Λ (q → p) Example: (1) Prove that the product of even integers is an even integer. Solution: Suppose: x & y are even integers Then: x = 2m & y = 2n for some integers m & n ▪Therefore, xy = (2m)(2n) = 4mn = 2(2mn) = 2t where t = 2mn ▪Because, m & n are integers, t is an integer Hence, xy is an even integer. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic In the previous topics, we defined and discussed basic properties of statements (also called propositions). There, we were interested only in the truth and falsity of the statement. The structure of the statement was not taken into account. The logic that we discussed before is categorized as the statement logic, or propositional logic. There are many justified arguments whose validity cannot be tested within the framework of propositional logic. For example, Every integer is a rational number. 3 is an integer. Therefore, 3 is a rational number. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic Every integer is a rational number. 3 is an integer. Therefore, 3 is a rational number. In mathematics, this is a justified argument. In propositional logic, to check the validity of this argument we symbolize it using statement letters. Let p denote: Every integer is a rational number. q denote: 3 is an integer. r denote: 3 is a rational number. The above argument takes the form p q ∴𝑟 ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic Now, this argument is valid if the statement formula (𝑝 ∧ 𝑞) → 𝑟 is a tautology. For if (𝑝 ∧ 𝑞) → 𝑟 is a tautology, then for any assignment of truth values to p, q and r, the truth value of (𝑝 ∧ 𝑞) → 𝑟 must be T. However, if we assign T to p, T to q, and F to r then the truth value is F. Hence, according to the propositional logic, the argument is not valid. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic If we introduce logical notions called predicates and quantifiers, then most of the everyday arguments (most of the arguments in mathematics and computer science) can be symbolized in such a way that we can verify the validity of the arguments. For example, x is an integer. Let us denote this sentence by P(x): P(x): x is an integer. Then P(5): 5 is an integer, is true. P(2.5): 2.5 is an integer, is false. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic To study the properties of such sentence, we need to extend the framework of propositional logic. The discussion of logic that follows is categorized as first-order logic. Once again consider the sentence x is an integer. Two parts of the sentence x – the variable is an integer – relation We call the relation “ is an integer” – the predicate, denoted by P. Moreover, P(x) is called a predicate or propositional function. Notice that there is a set of values, (in this case, say real numbers), associated with P(x), called the domain. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic Definition: Let x be a variable and D be a set; P(x) is a sentence. Then P(x) is called a predicate or propositional function with respect to the set D if for each value of x in D, P(x) is a statement [P(x) is true or false]. Moreover, D is called the domain of the discourse and x is called the free variable. Example: P(x): x is an even integer, where the domain of the discourse is the set of integers. Then P(4): 4 is an even integer, is T. P(3): 3 is an even integer, is F. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic The predicates that we considered until now involved only one variable. We can also have predicates involving two or more variables. Example: P(x,y): x equals y + 1. Hence, the predicate P(x,y) involves two variables and represents the relation “equal”. Let the domain be set of integers. x = 2 and y = 1 : x=2=1+1=y+1 P(2,1) is T. x = 5 and y = 4 : x=5=4+1=y+1 P(5,4) is T. x = 6 and y = 4 : x=6≠4+1=y+1 P(6,4) is F. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE Quantifiers and First-Order Logic Example: Let Q(x,y) denote the sentence Q(x,y): 𝑥 2 is greater than or equal to y. Let the domain be the set of integers. Here the predicate Q(x,y) involves two variables. Consider Q(2,3), 𝑥 2 = 4 > 3, it follows that Q(2,3) is true. However, Q(2,5) is false… 22 = 4 is neither greater than 5 or equal to 5. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE ALGORITHM An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem. The term algorithm is a corruption of the name al-Khowarizmi, a mathematician of the ninth century, whose book on Hindu numerals is the basis of modern decimal notation. Originally, the word algorism was used for the rules for performing arithmetic using decimal notation. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE ALGORITHM PROPERTIES OF ALGORITHMS There are several properties that algorithms generally share. They are useful to keep in mind when algorithms are described. These properties are: 1. Input. An algorithm has input values from a specified set. 2. Output. From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem. 3.Definiteness. The steps of an algorithm must be defined precisely. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE ALGORITHM 4. Correctness. An algorithm should produce the correct output values for each set of input values. 5. Finiteness. An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set. 6. Effectiveness. It must be possible to perform each step of an algorithm exactly and in a finite amount of time. 7. Generality. The procedure should be applicable for all problems of the desired form, not just for a particular set of input values. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE GREEDY ALGORITHM One of the simplest approaches often leads to a solution of an optimization problem. This approach selects the best choice at each step, instead of considering all sequences of steps that may lead to an optimal solution. Algorithms that make what seems to be the “best” choice at each step are called greedy algorithms. Once we know that a greedy algorithm finds a feasible solution, we need to determine whether it has found an optimal solution. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE GREEDY ALGORITHM Note that we call the algorithm “greedy” whether or not it finds an optimal solution. To do this, we either prove that the solution is optimal or we show that there is a counterexample where the algorithm yields a non-optimal solution. Greedy algorithm is also called the shortest path algorithm. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 - Discrete Mathematics I for SE REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO FACULTY – ECE DEPARTMENT  EMath 1105 Discrete Mathematics I for SE Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Growth of a Function Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Growth of a Function Rate of Growth = Asymptotic Analysis Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. If f(x) is faster growing than g(x), then f(x) always eventually becomes larger than g(x) in the limit (for large enough values of x). Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Growth of a Function Example: Suppose you are designing a website to process user data (financial records and the like). Program A takes fA(n)=30n+8 microseconds to process any n records, while Program B takes fB(n)=𝑛2 + 1 microseconds to process the n records. Which program would you choose, knowing you will want to support millions of users? Answer: Program A Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation  Big-O notation is used to express the time complexity of an algorithm  Using Big-O notation, we can compare two algorithms to determine which is more efficient as the size of the input grows.  We can assume that any operation requires the same amount of time.  The time complexity of an algorithm can be described independently of the software and hardware used to implement the algorithm. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation For example, if we have two algorithms for solving a problem, One using 100𝑛2 + 17𝑛 + 4 operations Other using 𝑛3 operations Big-omega and big-theta will be discussed also under this topic. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Def.: Let f , g be functions with domain R0 or N and codomain R. f(x) is O(g(x)) if there are constants C and k such that  x > k, |f (x )|  C  |g (x )| This is read as “ f(x) is big-O of g(x).” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation  x > k, |f (x )|  C  |g (x )| f (x ) is asymptotically dominated by g (x ) C|g(x)| is an upper bound of f(x). C and k are called witnesses to C|g(x)| the relationship between f & g. |f(x)| Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department k  Big-O Notation  To establish that f(x) is O(g(x)) we need only one pair of witnesses to this relationship.  We need the values of constants C and k.  Note that when there is one pair of witnesses to the relationship f(x) is O (g(x)), there are infinitely many pairs of witnesses.  Paul Bachman – first introduced the big-O notation in 1892 in an important book on number theory.  Landau’s symbol – another name for big-O symbol Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation To prove that a function f(x) is O(g(x)) A useful approach for finding a pair of witnesses is to first select a value of k for which the size of |f(x)| can be readily estimated when x > k. Next we need to see whether we can use this estimate to find for C. Then we can say that |f (x )|  C  |g (x )| for x > k. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Show that f(x) = x 2 + 2x + 1 is O(x2). Steps: 1. Know that x is the variable or argument of the function. 2. Then, think for a value of k (to be substituted to x > k). 3. Say x > 1. Multiply both sides by x to attain x ≤ x2. 4. Since the function contains also a constant 1 we can say 1 ≤ x2. (x2 since that is the argument of the big- O) 5. Replace x and 1 in the function by x 2. 6.Then x2 + 2x + 1 ≤ x2 + 2x2 + x2 = 4x2 so, let C = 4 and k = 1 as witnesses, f(x) = x2 + 2x + 1 < 4x2 when x > 1 Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Show that f(x) = x2 + 2x + 1 is O(x2). Could try x > 2. Then we have 2x ≤ x2 & 1 ≤ x2 then x2 + 2x + 1 ≤ x2 + x2 + x2 = 3x2 so, C = 3 and k = 2 are also witnesses to f(x) being O(x2). Note that f(x) is also O(x3), etc. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Show that f(x) = 7x2 is O(x3). When x > 7 we know that 7x2 < x3 (multiply x > 7 by x2) so, let C = 1 and k = 7 as witnesses. Could try x > 1. Then we have 7x2 < 7x3 so, C = 7 and k = 1 are also witnesses to f(x) being O(x3). Note that f(x) is also O(x4), etc. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Show that f(n) = n2 is not O(n). Show that no pair of C and k exists such that n2 ≤ Cn whenever n > k. When n > 0, divide both sides of n2 ≤ Cn by n to get n ≤ C. No matter what C and k are, n ≤ C will not hold for all n with n > k. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-O Notation Example: Prove that f(n) = n! is O(nn) Proof (easy): n! = 1 · 2 · 3 · 4 · 5 · · · n ≤n·n·n·n·n···n = nn where our witnesses are C = 1 and k = 1 Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Omega Notation Def.: Let f, g be functions with domain R0 or N and codomain R. f(x) is  (g(x)) if there are positive constants C and k such that x > k, C  |g (x )|  |f (x )|  This reads as “ f(x) is big-omega of g(x).” Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Omega Notation x > k, C  |g (x )|  |f (x )| ❖ C |g(x)| is a lower bound for |f(x)| |f(x)| C|g(x)| k Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Omega Property Example: Prove that f(x) = 3x2 + 2x + 3 is (g(x)) where g(x) = x2. Still need to find C and k. Proof: First note that 3x2 + 2x + 3 ≥ 3x2 for all x ≥ 0. Therefore, C = 3 and k = 0. That’s the same as saying that g(x) = x2 is O(3x2 + 2x + 3) Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Theta Notation Def.:Let f , g be functions with domain R0 or N and codomain R. f(x) is (g(x)) Read as: “f(x) is big-theta of g(x).” Conditions: if f(x) is O(g(x)) and f(x) is (g(x)). In symbol, 𝑪𝟏 𝒈(𝒙) ≤ 𝒇(𝒙) ≤ 𝑪𝟐 𝒈(𝒙) Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Theta Notation The graph of big-theta: C2|g(x)| |f(x)| C1|g(x)| Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Theta Example Let f(n) = 4n + 6, 𝒏 ≥ 𝟎. Show that 𝐟 𝐧 = 𝚯(𝐠(𝐧)) We need to attain this relationship: 𝑪𝟏 𝒈(𝒏) ≤ 𝒇(𝒏) ≤ 𝑪𝟐 𝒈(𝒏) What we need to solve? C1, C2 and k. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Theta Example f(n) = 4n + 6, 𝒏 ≥ 𝟎. Solving for Big-O: (We need to have g(n) as small as possible.) Let 𝑛 ≥ 3: 4𝑛 + 6 ≤ 𝑛 ? Hmmm... 4𝑛 + 6 ≤ 2𝑛 ? Another hmmm... 4𝑛 + 6 ≤ 4𝑛 ? Hmmm (3 times) 4𝑛 + 6 ≤ 6𝑛 ? Gotcha!!! So C2 = 6, with k = 3. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big-Theta Example f(n) = 4n + 6, 𝒏 ≥ 𝟎. Solving for Big-Ω: Let 𝑛 ≥ 3: By inspection, 4𝑛 + 6 ≥ 4𝑛 So C1 = 4, with k = 3. Therefore, 𝟒𝒏 ≤ 𝟒𝒏 + 𝟔 ≤ 𝟔𝒏 𝒇𝒐𝒓 𝒂𝒍𝒍 𝒏 ≥ 𝟑. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  Big Summary Upper Bound – Use Big-O Lower Bound – Use Big-Omega Upper and Lower (or Order of Growth) – Use Big-Theta Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department  References:  Cabero, J.B, Lopez, R., Salamat, L. G., Sta. Maria, A. C. (2012). Discrete Mathematics, National Bookstore  http://cglab.ca/~discmath/growth-of- functions.html#:~:text=The%20growth%20of%20a%20fu nction,2%2C%20or%20x%2B1. Prepared by: Engr. Alimo-ot & Engr. Sacramento, ECE Department