Intro to Discrete Structures Lecture 1 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 1 p 1 28 1 The Foundations Logic and Proof 1 1 Propositional Logic 1 2 Propositional Equivalances 1 3 Predicates and Quantifiers 1 4 Nested Quantifiers 1 5 Rules of Inference 1 6 Introduction to Proofs 1 7 Proof Methods and Strategy Intro to Discrete StructuresLecture 1 p 2 28 1 1 Propositional Logic The rules of logic give precise meaning to mathematical statements and are used to distinguish between valid and invalid mathematical arguments A major goal is to teach you how to understand and construct correct mathematical arguments Intro to Discrete StructuresLecture 1 p 3 28 1 1 Propositional Logic In addition to its importance in understanding mathematical reasoning logic has numerous applications in computer science For instance these rules are used in the design of computer circuits the construction of computer programs and the verification of the correctness of programs Intro to Discrete StructuresLecture 1 p 4 28 Propositions We begin with the basic building blocks of logic propositions A proposition is a declarative sentence that is a sentence that declares a fact that is either true of false but not both Example 1 All the following declarative sentences are propositions 1 Washington D C is the capital of the Unites States of America True 2 Toronto is the capital of Canada True 3 1 1 2 True 4 2 2 3 False Intro to Discrete StructuresLecture 1 p 5 28 Propositions Some sentences that are not propositions are given below Example 2 Consider the following sentences 1 What time is it 2 Read this carefully 3 x 1 2 4 x y z 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 we can turn them into propositions if we assign values to the variables x and y Intro to Discrete StructuresLecture 1 p 6 28 Notation in Propositional Calculus The area of logic that deals with propositions is called propositional calculus or propositional logic We use letters to denote propositional variables or statement 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 false denoted by F if it is a false proposition Intro to Discrete StructuresLecture 1 p 7 28 Compound Propositions We now turn our attention to methods for producing new propositions from those that we already have New propositions called compound propostions are formed from existing propositions using logical operators Intro to Discrete StructuresLecture 1 p 8 28 Negation Definition 1 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 p is the opposite of the truth value of p The truth table for the negation of a proposition p T F p F T Intro to Discrete StructuresLecture 1 p 9 28 Connectives The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition The negation operator constructs a new proposition from a single existing proposition We will now introduce the logical operators that are used to form new propositions from two or more existing propositions These logical operators are also called connectives Intro to Discrete StructuresLecture 1 p 10 28 Conjuction Definition 2 The conjuction of p and q denoted by p q is the proposition p and q The conjuction p q is true when both p and q are true and is false otherwise The truth table for the conjuction of two propositions p T T F F q p q T T F F T F F F Intro to Discrete StructuresLecture 1 p 11 28 Disjuction Definition 3 The disjuction of p and q denoted by p q is the proposition p or q The disjuction p q is false when both p and q are false and is true otherwise The truth table for the disjuction of two propositions p T T F F q p q T T F T T T F F Intro to Discrete StructuresLecture 1 p 12 28 Exclusive or Definition 4 The exclusive or of p and q denoted by p q is the proposition that is true when exactly one of p and q is true and is false otherwise The truth table for the exclusive or of two propositions p T T F F q p q T F F T T T F F Intro to Discrete StructuresLecture 1 p 13 28 Conditional Statement Definition 5 The conditional statement of p q is the proposition if p then q The conditional statement p q is false when p is true and q is false true otherwise p is called the hypothesis or antecedent or premise and q is called the conclusion or consequence p T T F F q p q T T F F T T F T Intro to Discrete StructuresLecture 1 p 14 28 Biconditional Statement Definition 6 The biconditional statement of p q is the proposition p if and only if q The biconditional statement p q is true when p have the same truth value and is false otherwise Biconditional statements are also called bi implications p T T F F q p q T T F F T F F T Intro to Discrete StructuresLecture 1 p 15 28 Summary of all Connectives p T T F F q p T F F F T T F T p q T F F F p q T T T F p q F T T F p q T F T T p q T F F T Intro to Discrete StructuresLecture 1 p 16 28 Truth Tables of Compound Propositions Example 11 Construct the truth table of the compound proposition p q p q Intro to Discrete StructuresLecture 1 p 17 28 Truth Tables of Compound Propositions Build the truth table according to the decomposition p q p q p q p p q q p q q There are four rows in the truth table since the compound proposition involves two propositional variables p and q Intro to Discrete StructuresLecture 1 p 18 28 Truth Tables of Compound Propositions p q p q p q p p q q p q q p T T F F q T F T F q p q p q p q p q Intro to Discrete StructuresLecture 1 p 19 28 Truth Tables of Compound Propositions p q p q p q p p q q p q q p T T F F q T F T F q F T F T p q p q p q p q Intro to Discrete StructuresLecture 1 …
View Full Document
Unlocking...