Discrete Structures Module Preliminary Exam PDF

DISCRETE STRUCTURE 1 IT 1201 – MODULE PRELIM DISCRETE STRUCTURES i  Table of Contents Module 1: Propositional Logic Introduction 1 Learning Outcomes 1 Lesson 1. Proposition...

DISCRETE STRUCTURE 1 IT 1201 – MODULE PRELIM DISCRETE STRUCTURES i  Table of Contents Module 1: Propositional Logic Introduction 1 Learning Outcomes 1 Lesson 1. Proposition 1 Lesson 2. Model Theory 7 Lesson 3. Proof Theory 13 Assessment Task 14 References 16 Module 2: Sets Introduction 17 Learning Outcomes 17 Lesson 1. Sets 17 Lesson 2. Sets and Elements 18 Lesson 3. Venn Diagram 22 Lesson 4. Set Operations 25 Assessment Task 31 References 34 Module 3: Relations Introduction 35 Learning Outcomes 35 Lesson 1. Product Sets 35 Lesson 2. Relations 38 Lesson 3. Composition of Relations 39 Lesson 4. Types of Relations 41 Lesson 5. Closure Properties 44 Lesson 6. Equivalence Relation 46 Assessment Task 48 References 50 Module 4: Set Functions Introduction 52 Learning Outcomes 52 Lesson 1. Functions 52 Lesson 2. One to One Functions 55 Lesson 3. Mathematical Functions 57 Lesson 4. Sequence 60 Lesson 5. Recursive Defined Functions 61 Assessment Task 65 References 69 ii Course Code: IT 1201 Course Description: This course covered the mathematical topics most directly related to computer science. Topics included: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics, discrete probability, recursion, recurrence relations, and number theory. Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Course Intended Learning Outcomes (CILO): At the end of this program, graduates will have the ability to: 1. Define the Discrete Structures and its concepts. 2. Demonstrate the five (5) Discrete Structures Course. 3. Explain foundations of logic proofs and conditions. 4. Acquire a mastery of discrete structures and methods basic to further work in computer science. 5. Integrate Algorithm functions to the different Discrete Structures procedures. 6. Exhibit the values of love, respect and humility as an individual in his workplace and community. iii  MODULE 1 PROPOSITIONAL LOGIC Introduction One of the basic notions in mathematics, whether we are talking of geometry, ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪ ƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ arithmetic or any other area, is that of truth and falsity. Reasoning is what mathematics ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ is all about, and even if we are discussing a topic such as geometry, we need a ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ mathematical infrastructure to reason about the way the truth of a statement follows ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ from other known truths. One area of mathematics dealing with these concepts is ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ propositional logic (Pace, 2012, p. 9). ƪƣ Learning Outcomes At the end of this module, students should be able to: 1. Identify what is proposition in discrete mathematics. 2. Recognize the rules and definition of different operators for proposition. 3. Apply the different logical operations. 4. Use conditional statements with proposition. Lesson 1. Proposition According to Lipschutz & Lipson (2009), A proposition is a statement which is ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪƣ either true or false. We may not know whether or not it is true, but it must have a ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ definite value. Consider, for example, the following six sentences: ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ (i) Ice floats in water. (iii) 2 + 2 = 4 (v) Where are you going? (ii) China is in Europe. (iv) 2 + 2 = 5 (vi) Do your homework. The first four are propositions, the last two are not. Also, (i) and (iii) are true, but (ii) and (iv) are false. 1 Exercise: Which of the following are propositions? (a) If I am wrong, then I am an idiot. (b) Choose a number between 5 and 10. (c) Have I already arrived at the town of True? (d) 7 is the largest number. (e) Numbers are odd. Compound Proposition According to Lipschutz & Lipson (2009), many propositions are composite, that is, ƪƣ ƪƣ ƪƣ ƪƣ composed of subpropositions and various connectives discussed subsequently. Such ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ composite propositions are called compound propositions. A proposition is said to be ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ primitive if it cannot be broken down into simpler propositions, that is, if it is not ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ composite. For example, the above propositions (i) through (iv) are primitive propositions. ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ On the other hand, the following two propositions are composite: ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ “Roses are red and violets are blue.” and “John is smart or he studies every ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ night.” The fundamental property of a compound proposition is that its truth value is ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ completely determined by the truth values of its subpropositions together with the way ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ in which they are connected to form the compound propositions (Lipschutz & Lipson, ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ 2009, p. 70). We use letters to denote propositional variables (or sentential variables), that is, ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ variables that represent propositions, just as letters are used to denote numerical ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ variables. The conventional letters used for propositional variables are p,q,r,s,…. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ The truth value of a proposition is true, denoted by T, if it is a true proposition, ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ and the truth value of a proposition is false, denoted by F, if it is a false proposition. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Propositions that cannot be expressed in terms of simpler propositions are called ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ atomic propositions (Lipschutz & Lipson, 2009, p. 70). ƪƣ 2 Basic Logical Operations The three basic logical operations are conjunction, disjunction, and negation ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ which correspond, respectively, to the English words “and,” “or,” and “not.” ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Conjunction, p ∧ q: Any two propositions can be combined by the word “and” to ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ form a compound proposition called the conjunction of the original propositions. ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ Symbolically, ƪƣ p∧q ƪƣ ƪƣ read “p and q,” denotes the conjunction of p and q. Since p ∧q is a proposition it ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ has a truth value, and this truth value depends only on the truth values of p and q. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Specifically: Definition: If p and q are true, then p ∧ q is true; otherwise p ∧ q is false. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Definition 2: Let p and q be propositions. The conjunction of p and q, denoted by p ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ q are true and is false otherwise. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ The truth value of p ∧q may be defined equivalently by the table in Figure ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ 1. Here, the first line is a short way of saying that if p is true and q is true, then p ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ∧ q is true. The second line says that if p is true and q is false, then p ∧ q is false. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ And so on. Observe that there are four lines corresponding to the four possible ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ combinations of T and F for the two subpropositions p and q. Note that p ∧ q is ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ true only when both p and q are true. (Lipschutz & Lipson, 2009, p. 71) ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Figure 1. Truth Table 3  Example: Find the conjunction of the propositions p and q where p is the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Solution: The conjunction of these propositions, p ∧ q, is the proposition ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ Rebecca’s PC runs faster than 1 GHz.” This conjunction can be expressed more ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ processor runs faster than 1 GHz.” For this conjunction to be true, both conditions ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ given must be true. It is false when one or both of these conditions are false. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Disjunction, p ∨ q: Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically, p∨q read “p or q,” denotes the disjunction of p and q. The truth value of p ∨ q depends only on the truth values of p and q as follows. Definition: If p and q are false, then p ∨ q is false; otherwise p ∨ q is true. Definition 2: Let p and q be propositions. The disjunction of p and q, denoted y p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. The truth value of p ∨ q may be defined equivalently by the table in Figure ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ 1(b). Observe that p ∨ q is false only in the fourth case when both p and q are ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪ ƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪ ƣ false. The use of the connective or in a disjunction corresponds to one of the two ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ways the word or is used in English, namely, as an inclusive or. A disjunction is true ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ when at least one of the two propositions is true. That is, p ∨ q is true when both ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ p and q are true or when exactly one of p and q is true. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: Translate the statement “Students who have taken calculus or ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ introductory computer science can take this class” in a statement in propositional ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ logic using the propositions p: “A student who has taken calculus can take this ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ 4  class” and q: “A student who has taken introductory computer science can take this ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ class.” Solution: We assume that this statement means that students who have taken both ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ calculus and introductory computer science can take the class, as well as the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ students who have taken only one of the two subjects. Hence, this statement can ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ be expressed as p ∨ q, the inclusive or, or disjunction, of p and q. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Negation, ¬p: Given any proposition p, another proposition, called the negation of ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ p, can be formed by writing “It is not true that...” or “It is false that...” before p or, ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ p,” is denoted by ƪƣ ƪƣ ƪƣ ¬p The truth value of ¬p depends on the truth value of p as follows: ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Definition: If p is true, then ¬p is false; and if p is false, then ¬p is true. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Definition 2: Let p be a proposition. The negation of p, denoted by ¬p (also denoted ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ by p), is the statement “It is not the case that p.” The proposition ¬p is read “not ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: Consider the following six statements: (a1) Ice floats in water. (b1) 2 + 2 = 5 (a2) It is false that ice floats in water. (b2) It is false that 2 + 2 = 5. (a3) Ice does not float in water. (b3) 2 + 2 ≠ 5 Then (a2) and (a3) are each the negation of (a1); and (b2) and (b3) are each the negation of (b1). Since (a1) is true, (a2) and (a3) are false; and since (b1) is false, (b2) and (b3) are true. More Example Consider the propositions ‘I am carrying an umbrella’, ‘It is raining’ and ‘I am ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ drenched’. From these propositions we can construct more complex propositions such ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ as ‘I am carrying an umbrella and it is raining’, ‘if it is raining and I am carrying an ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ umbrella, then I am drenched’ and ‘I am carrying an umbrella unless it is raining.’ We ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ will now define a number of operators which will allow us to combine propositions ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ 5 together. Why should we bother doing this? Consider the compound proposition ‘It is ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪƣ ƪƣ raining and I am drenched’. Whatever the state of the weather and my clothes, I might ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ as well have said ‘I am drenched and it is raining’. Similarly, had I said ‘I am carrying an ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ umbrella and it is raining’, I might as well have said ‘it is raining and I am carrying an ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ umbrella’. Obviously, I can generalize: for any propositions P and Q, we would like to ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ show mathematically that saying ‘P and Q’ is the same as saying ‘Q and P’. To reason ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ mathematically, we should have a clear notion of what operators we will be using and their exact mathematical meaning. (Pace, 2012, p. 10) Definition: ƪƣ Given two propositions P and Q, the conjunction of P and Q is written as P ∧ Q. We ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ read this as ‘P and Q’, and it is considered to be true whenever both P and Q are true. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: We can write ‘it is raining and I am carrying an umbrella’ as ‘it is raining’ ∧ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ‘I am carrying an umbrella’. If it is raining, and I am carrying a closed umbrella, this ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ compound proposition is true, whereas if it is not raining, but I am carrying an open ƪ ƣ ƪ ƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪ ƣ ƪƣ umbrella, it would be false. ƪƣ ƪƣ ƪƣ Definition: Given two propositions P and Q, the disjunction of P and Q is written as P ∨ Q. We ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ read this as ‘P or Q’, and it is considered to be true whenever either P is true, or Q is ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ true, or both ƪƣ Example: We can write ‘I am carrying an umbrella or I am drenched’ as ‘I am carrying ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ an umbrella’ ∨ ‘I am drenched’. If I am carrying a closed umbrella in the rain, this is ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ true. If I am under the shower, carrying an open umbrella, this is still true. It would be ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ false if I am dry and carrying no umbrella. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Definition: Given two propositions P and Q, we write P → Q to mean ‘If P is true, then ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ so is Q’, or ‘P implies Q’. P → Q is considered to be true unless P is true and Q is false ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: We can write ‘If it is raining then I am drenched’ as ‘It is raining’ → ‘I am ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ ƪƣ ƪƣ ƪƣ ƪƣ drenched’. If it is raining, but I am inside and thus not wet, this proposition is false. If it ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ is raining and I am having a shower, then it is true. If it is not raining, then it is true ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ whether or not I am wet ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ 6 Definition: Given two propositions P and Q, we take their bi-implication, written P ⇔ Q, ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ to mean ‘P if and only if Q’. This is considered to be true whenever P and Q are ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ equivalent: either P and Q are both true, or P and Q are both false. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: ‘You will pass the exam if and only if you study and you work out the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ exercises’ can be written formally as ‘You will pass the exam’ ⇔ (‘you study’ ∧ ‘you ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ work the exercises’). If this is a true proposition, not only does it mean that if you do ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ not study or if you do not work out the exercises you will not pass the exams, but also ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ that if you do study and work the exercises, you will pass the exam ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Definition: Given a proposition P, the negation of P is written as ¬P. We read this as ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ‘not P’, and it is considered to be true whenever P is not true (P is false). ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Example: ‘If it is raining and I am not carrying an umbrella, then I will get wet or I will ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ run quickly home’ can be written as: ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ (‘it is raining’ ∧¬ ‘I am carrying an umbrella’) → (‘I will get wet’ ∨ ‘I will run quickly ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ home’) Lesson 2. Model Theory According to Pace (2012), to build a series of mathematical tools to reason about these formulae. For instance, some statement can be shown to be true no matter what—if the weather report were to predict “Tomorrow, either it will rain or it will not,” we can ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ immediately conclude that the forecast is correct. We may also want to use the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ mathematical tools we will develop to show that two sentences are equivalent (“It is ƪƣ ƪ ƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ cold and it is raining” is intuitively equivalent to “It is raining and it is cold”) or that one ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ sentence follows from another (“A lion escaped from the zoo” follows from “No tiger ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ escaped, and either a lion or a tiger, or both ,escaped from the zoo”). ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ 7 Truth Table Since basic propositions can only be either true or false, we can list all possible ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ values and use rules to generate the value of a compound formula. This approach ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ would not work in another field of mathematics, such as numbers, where the number of ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ values a basic variable can take ranges over an infinite collection. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Negation: Consider negation. We would like to draw up a table which precisely ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ describes the value of ¬P for any possible value of proposition P. The following table ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ should satisfy our needs: ƪƣ ƪƣ ƪƣ The double vertical line indicates that what comes to the right is the answer. Before the double line, we list all possible values of the propositional variables. In this case, since we have one variable, we have two possibilities. Truth tables used to define the meaning of the propositional operators are basic truth tables. They are to be considered different from the truth tables of compound formulae which are derived from basic truth tables. We call such tables derived truth tables. Using the basic truth table for negation, we can now draw up the derived truth table for the compound formula ¬(¬P): Conjunction: Let us now turn our attention to conjunction. Constructing the basic truth table for P ∧ Q is straightforward: 8 Example Let us start by drawing the truth table for ¬Q∧P. First we observe that, using ƪƣ the precedence rules, we can add brackets to get (¬Q)∧P. We will have two columns ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ before the first double line (one for P, one for Q). The last column will obviously have ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ¬Q∧P. Finally, we need to add a column ¬Q (the only sub formula we need). Consider filling one of the entries. The last entry in the rightmost column is to be filled ƪƣ by the value of ¬Q ∧P when we know (from the previous columns) that the value of ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ¬Q is true and that of P is false. Consulting the second row of the basic truth table for ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ conjunction we know that this last entry has to take the value false. ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ Disjunction By now the pattern of how to draw up truth tables should be quite clear. It is sufficient to be given the basic truth table of a new operator, and we can derive truth tables of formulae using that operator. Let us look at the basic truth table of disjunction. Example Let us draw the truth table for P∨(Q∨R): 9 Bi-implication: Note that the statement p ↔ q is true when both the conditional statements p → q and q → p are true and is false otherwise. That is why we use the ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ words “if and only if” to express this logical connective and why it is symbolically ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ written by combining the symbols → and ←. There are some other common ways to ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ express p ↔ q “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q.” “p exactly when q.” The last way of expressing the biconditional statement p ↔ q uses the abbreviation “iff” for “if and only if.” Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). Definition: Let p and q be propositions. The biconditional statement p ↔ q is the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ proposition “p if and only if q”. The biconditional statement p ↔ q is true when p and q ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ have the same truth values, and is false otherwise. Biconditional statements are also ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ called bi-implications. Example Let us draw the truth table of P ∧Q ⇔ Q∧P: 10 Implication: Many statements, particularly in mathematics, are of the form “If p then q.” Such statements are called conditional statements and are denoted by p→q The conditional p → q is frequently read “p implies q” or “p only if q.” Definition: Let p and q be propositions. The conditional statement p → q is the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ proposition “if p, then q.” The conditional statement p → q is false when p is true and ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ q is false, and true otherwise. In the conditional statement p → q, p is called the ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). ƪƣ ƪƣ ƪƣ ƪƣ Example Let us look at one final example to illustrate implication: (P → Q) → R: Propositions satisfy various laws which are listed in Table 4-1. (In this table, T and F are restricted to the truth values “True” and “False,” respectively.) We state this result formally. 11  An argument is an assertion that a given set of propositions P1 ,P2 ,...,Pn , called premises, yields (has a consequence) another proposition Q, called the conclusion. Such an argument is denoted by P1 , P2 ,..., Pn ⊦ Q The notion of a “logical argument” or “valid argument” is formalized as follows: Definition: An argument P1 , P2 ,..., Pn ⊦ Q is said to be valid if Q is true whenever all the premises P1 ,P2 ,...,Pn are true. An argument which is not valid is called fallacy Example: A fundamental principle of logical reasoning states: “If p implies q and q implies r, then p implies r”. That is, the following argument is valid: p → q, q → r ⊦ p → r (Law of Syllogism) 12 This fact is verified by the truth table in Fig. 4-8 which shows that the following ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ proposition is a tautology. Equivalently, the argument is valid since the premises p → q ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪ ƣ and q → r are true simultaneously only in Cases (rows) 1, 5, 7, and 8, and in these ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪƣ ƪƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪƣ ƪƣ cases the conclusion p → r is also true. (Observe that the truth table required 2 3 = 8 ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ lines since there are three variables p, q, and r.) (Lipschutz & Lipson, 2009). ƪƣ ƪƣ We now apply the above theory to arguments involving specific statements. We ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ emphasize that the validity of an argument does not depend upon the truth values nor ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ the content of the statements appearing in the argument, but upon the particular form ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ of the argument (Lipschutz & Lipson, 2009). Lesson 3. Proof Theory According to Pace, 2012, p. 29, Propositional model theory is just one way of ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ reasoning about propositions. In model theory, we explicitly build every possible model ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ ƪƣ of the system (using truth tables or similar techniques) and painstakingly verify our ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ ƪ ƣ claims for every case. ƪƣ ƪƣ ƪƣ The concept of proof is possibly the most fundamental notion in mathematics.