COSC 50A - Lecture 1 - Logic and Proofs PDF

Foundation: Logic and Proofs Lourielene Baldomero College of Engineering and Information Technology Instructor/Professor  What is Discrete Mathematics? Discrete Mathemat...

Foundation: Logic and Proofs Lourielene Baldomero College of Engineering and Information Technology Instructor/Professor  What is Discrete Mathematics? Discrete Mathematics A study of mathematical structures that are countable or otherwise distinct and separable. It encompasses a wide array of topics that can be used to answer many tangible questions that arise in everyday life: Logic: Is a given argument logically sound, or does it contain a fallacy? Number Theory: If a leap year happens every 4 years, and PH presidents are elected every 6 years , how frequently is a presidential election held in a leap year? Counting: How many different outfits can you make from clothes in your closet? College of Engineering and Information Technology  What is Discrete Mathematics? Probability: What are your chances of winning the lottery? Recurrences: How much will you pay over the lifetime of mortgage if interest is compounded monthly? Graph Theory: What is the fastest way to get from your home to your workplace? College of Engineering and Information Technology  What is Logic? Logic By definition: Study of the laws of thought or correct reasoning, and is usually understood in terms of inferences or arguments. Basis of all mathematical reasoning, and of all automated reasoning. Example: “For every positive integer n, the sum of the positive integers not exceeding n is n(n+1)/2” College of Engineering and Information Technology  Importance of logic to Computer Science These rules are used in the design of computer circuits, the construction of computer programs, the verification of the correctness of programs, and in many other ways. College of Engineering and Information Technology  Propositions Proposition The basic building block of logic. It is a declarative sentence that declares a fact, that is either true or false, but not both. Example: 1. 1+1 = 2 2. 2+2 = 3 3. Lourielene is the not the first name of one of the instructors in COSC 50A. 4. Manila is the capital of the Philippines. College of Engineering and Information Technology  Propositions 1. What time is it? 2. Our topic today is logic. 3. COSC 50A is an easy subject.. 4. Read the document carefully. 5. x+1 = 2 6. x+y = z College of Engineering and Information Technology  Propositions Propositional Variables (statement variables) 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 is false, denoted by F, if it is a false proposition. True proposition = T False proposition = F College of Engineering and Information Technology  Propositions Propositional calculus (propositional logic) It was first developed by the Greek philosopher Aristotle more than 2300 years ago. studies the ways statements can interact with each other. College of Engineering and Information Technology  Compound Propositions Compound Propositions are new propositions formed from existing propositions using logical operators. Many mathematical statements are constructed by combining one or more propositions. College of Engineering and Information Technology  Logical Connectives Connectives are logical operators that are used to form new propositions from two or more existing propositions. List of Logical Connectives: 1. Negation 2. Conjunction 3. Disjunction 4. Conditional 5. Bi-conditional College of Engineering and Information Technology  Negation Operator Negation operator constructs a new proposition from a single existing proposition. The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. By definition: 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. College of Engineering and Information Technology  Negation Operator p ¬p T F F T Table 1. The Truth Table for the Negation of a Proposition. College of Engineering and Information Technology  Conjunction Operator Conjunction operator Indicated by the symbol ⋀. If the propositions, p and q, then the conjunction of p and q will also be a proposition, which contains the following properties: When p and q are true, then the conjunction of them will be true. When p and q are false, then the conjunction of them will be false. By definition: Let p and q be propositions. The conjunction of p and q, denoted by p ⋀ q is true when both p and q are true and is false otherwise. College of Engineering and Information Technology  Conjunction Operator p Q p⋀q T T T T F F F T F F F F Table 2. The Truth Table for the Conjunction of Two Propositions. College of Engineering and Information Technology  Disjunction Operator Disjunction operator Indicated by the symbol v. If there are two propositions p and q will also be a proposition, which contains the following properties: When p and q are false, then the disjunction of them will be false. When either p and q are true, then the disjunction of them will be true. By definition: Let p and q be propositions. The disjunction of p and q, denoted by p v q is false when both p and q are false and is true otherwise. College of Engineering and Information Technology  Disjunction Operator p Q pvq T T T T F T F T T F F F Table 3. The Truth Table for the Disjunction of Two Propositions. College of Engineering and Information Technology  Disjunction Operator The use of the connective or in a disjunction corresponds to one of the two ways the word or used in English: Inclusive or – a disjunction is true when at least one of the two propositions is true. Exclusive or – a disjunction is false when both are truth or both are false. By definition: Let p and q be propositions. The exclusive or of p and q, denoted by p⨁q, is the proposition that is true when exactly one of 𝑝 and 𝑞 is true and is false otherwise. College of Engineering and Information Technology  Disjunction Operator p Q p⨁q T T F T F T F T T F F F Table 3. The Truth Table for the Exclusive Or of Two Propositions. College of Engineering and Information Technology  Conditional Statements Conditional Statement Indicated by the symbol →. If there are two propositions, p and q, then the conditional of p and q will also be a proposition, which contains the following properties: If there is a proposition that has the form of 𝑖𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞, then that type of proposition will be known as the implication or conditional proposition. When 𝑝 is false, or 𝑝 and 𝑞 are true, then the implication of them will be true. When 𝑝 is true, and 𝑞 is false, then the implication of them will be false. College of Engineering and Information Technology  Conditional Statements Conditional Statement By definition: Let 𝑝 and 𝑞 be propositions. The conditional statements 𝑝 → 𝑞 is the proposition "𝑖𝑓 𝑝,𝑡ℎ𝑒𝑛 𝑞.“ The conditional statement 𝑝 → 𝑞 is false when 𝑝 is true and 𝑞 is false, and true otherwise. In the conditional statement 𝑝 → 𝑞, 𝑝 is called the hypothesis (or antecedent or premise) and 𝑞 is called the conclusion (or consequence). A conditional statement is also called an implication. The statement 𝑝 → 𝑞 is called a conditional statement because 𝑝 𝑞 asserts →Engineering College of andthat 𝑞 is true on the condition that 𝑝 holds Information Technology  Disjunction Operator p Q p→q T T T T F F F T T F F T Table 4. The Truth Table for the Conditional Statement of Two Propositions. College of Engineering and Information Technology  Bi-conditional operator Bi-conditional or Double Implication – It is indicated by the symbol ↔. If there are two propositions, 𝑝 and 𝑞, then the bi-conditional of 𝑝 and 𝑞 will also be a proposition, which contains the following properties: If there is a proposition that has the form "𝑝 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑞“, then that type of proposition will be known as bi-implication or bi- conditional proposition. When 𝑝 and 𝑞 are true, or 𝑝 and 𝑞 both are false, then bi-implication will be true otherwise false. College of Engineering and Information Technology  Bi-conditional operator Example #8: Let 𝑝 be the statement “you can take the flight,” and let 𝑞 be the statement “You buy a ticket.” Assessment: 𝑝 ↔ 𝑞 is the statement “You can take the flight if and only if you buy a ticket.” This statement is true if 𝑝 and 𝑞 are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight. College of Engineering and Information Technology  Bi-conditional operator Truth Table displays the truth table of 𝑝 → 𝑞. This table has a row for each of the four possible combinations of truth values of 𝑝 and 𝑞. 𝒑 𝒒 𝒑↔𝒒 𝑇 𝑇 𝑇 𝑇 𝐹 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹 𝑇 Table 5. The Truth Table for the bi-conditional statement of Two Propositions. College of Engineering and Information Technology  Precedence of Logical Operators Precedence of operators helps to decide which operator will get evaluated first in a complicated looking compound proposition. Operators Names Precedence ¬ Negation 1 ⋀ Conjunction 2 ∨ Disjunction 3 → Implication 4 ↔ Bi-conditional 5 College of Engineering and Information Technology  Precedence of Logical Operators Example: 𝑝 → 𝑞⋀¬𝑝 where 𝑝 = 𝑡𝑟𝑢𝑒 𝑇 ; 𝑞 = 𝑓𝑎𝑙𝑠𝑒 𝐹 ; Then: 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 ¬𝑝 = 𝐹; 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 (𝑞⋀ ¬𝑝 ) = 𝐹 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 𝑝 → 𝑞⋀ ¬𝑝 =𝐹 College of Engineering and Information Technology  Precedence of Logical Operators Example: 𝑝 → 𝑞⋀¬𝑝 where 𝑝 = 𝑡𝑟𝑢𝑒 𝑇 ; 𝑞 = 𝑓𝑎𝑙𝑠𝑒 𝐹 ; Then using a Truth Table: 𝒑 𝒒 ¬𝒑 (𝒒⋀¬𝒑) (𝒑 → (𝒒⋀¬𝒑) 𝑇 𝐹 𝐹 𝐹 𝐹 College of Engineering and Information Technology  Complex Compound Propositions Construct the truth table of the compound proposition (𝑝 ∨ ¬𝑞) → (𝑝 ∧ 𝑞) 𝒑 𝒒 ¬𝒒 𝒑 ∨ ¬𝒒 𝒑∧𝒒 (𝒑 ∨ ¬𝒒) → (𝒑 ∧ 𝒒) 𝑇 𝑇 𝑇 𝐹 𝐹 𝑇 𝐹 𝐹 College of Engineering and Information Technology