Discrete Mathematics - Propositional Logic 1 PDF

Discrete Mathematics  Module 2 Subtopic 1 LOGIC PROPOSITIONAL LOGIC 1 OBJECTIVES Determine if a given sentence is a proposition. Construct truth tables. Determining the converse, inverse, and contrapositive of a given conditional. LOGIC Science of necessary inference or study of reasoni...

Discrete Mathematics  Module 2 Subtopic 1 LOGIC PROPOSITIONAL LOGIC 1 OBJECTIVES Determine if a given sentence is a proposition. Construct truth tables. Determining the converse, inverse, and contrapositive of a given conditional. LOGIC Science of necessary inference or study of reasoning Identifies valid mathematical argument STATEMENT/PROPOSITION A declarative sentence that is either true or false not both Examples: Which among the following examples are propositions? 1. Quezon City was once the capital of the Philippines. 2. 12  4 = 3 3.3 is an integer. 4. Who are you talking to? 5. Read this sentence carefully. 6. x + 4 = 7 7. u + v = w 8. 520  111 9. y > 5 10. Today is Friday. PROPOSITIONAL LOGIC It is the area of logic that deals with propositions. It is the logic of compound statements built from simpler statements using so- called Boolean connectives. APPLICATIONS OF PROPOSITIONAL LOGIC IN COMPUTER SCIENCE Design of digital electronic circuits Expressing conditions in programs Queries to databases & search engines COMPOUND PROPOSITION is a combination of one or more propositions. It is formed by using logical operators or connectives. COMPOUND PROPOSITION EXAMPLES p = “Cruise ships only go on big rivers.” q = “Cruise ships go on the Hudson.” r = “The Hudson is a big river.” ¬ r = “The Hudson is not a big river.” p ^ q = “Cruise ships only go on big rivers and go on the Hudson.” p ^ q → r = “If cruise ships only go on big rivers and go on the Hudson, then the Hudson is a big river.” FORMAL NAMES, NICKNAME AND SYMBOLS OF CONNECTIVES NEGATION OF PROPOSITION Let p be a proposition. The negation of p, 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. NEGATION OF PROPOSITION Let p: I like facebook very much. ¬ p= I don’t like facebook very much. NEGATION OF PROPOSITION TRUTH TABLE Logical matrix or truth table is an array of decision value (truth value). LOGICAL CONNECTIVE: AND The logical connective And is true only when both of the propositions are true. It is also called a conjunction. 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. LOGICAL CONNECTIVE: AND Example: It is raining and it is warm Let p: It is raining q: It is warm p^q LOGICAL AND TRUTH TABLE LOGICAL CONNECTIVE: OR The logical connective OR is true if one or both of the propositions are true. It is also called a disjunction. Let p and q be propositions. The disjunction of p and q, denoted by 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. LOGICAL CONNECTIVE: OR Example: You may have cake or you may have ice cream Let p: You may have cake q: you may have ice cream pνq LOGICAL OR TRUTH TABLE LOGICAL CONNECTIVE: EXCLUSIVE OR The exclusive OR, or XOR, of two propositions is true when exactly one of the propositions is true and the other one is false Example: The circuit is either ON or OFF but not both Let a or b ,