Transcript PPT
Expressions (Propositional formulas or forms) • Instructor: Hayk Melikya Introduction to Abstract Mathematics [email protected] 1 Worm_UP Definition:The disjunction of the statements P and Q is the statement "P or Q" and is denoted by P Q: P Q is true if of P and Q true; otherwise, P Q is false. . P1 : the integer 2 is even. P2 : the integer 34 is prime. P1 P2 : is ---------- Introduction to Abstract Mathematics 2 Worm_Up Definition: The conjunction of the statements P and Q is the statement "P and Q" and is denoted by P ^ Q: P ^ Q is true if of P and Q true; otherwise, P ^ Q is false. P^Q: is ------------------ Introduction to Abstract Mathematics 3 Exercise 1 How would you write each of these statement using combinations of P: (meaning "Sue is an English major") and Q: (meaning "Sue is a junior") with the operations , , ~. 1. Sue is a junior English major. 2. Sue is either an English major or she is a junior. 3. Sue is a junior, but she is not an English major. 4. Sue is neither an English major nor a junior. 5. Sue is exactly one of the following: an English major or a junior. Introduction to Abstract Mathematics 4 Implication There are several ways of expressing P Q : 1. If P, then Q 2. Q if P 3. P implies Q 4. P only if Q (P is true only under the condition that Q is true) i.e., it cannot be the case that P is true and Q is false. Thus, if P is true, then necessarily Q must be true. 5. Q is necessary for P 6. P is sufficient for Q (the truth of P is sufficient for the truth of Q) Introduction to Abstract Mathematics 5 Exercise 2 Rewrite each of the following sentences in "if, then" form: (a) You will pass the test only if you study for at least four hours. (b) Attending class regularly is a necessary condition for passing the course. (c) In order to be a square, it is sufficient that the quadrilateral have four equal angles. (d) In order to be a square, it is necessary that the quadrilateral have four equal angles. (e) An integer is an odd prime only if it is greater than 22 Introduction to Abstract Mathematics 6 Propositional Expressions (Forms) • • Alphabet: variables (propositional variables) (letters X, Y, Z, … A, B, C ) symbols , , ~, and parentheses ( , ) also we add two more , Expressions are formed using these elements of alphabet as follows: 1. Each variable is expression 2. IF X and Y are expressions then ~ X, XY, XY, XY, XY and (X) all are expressions 3. Any expression is obtained by applying repeatedly, steps 1 or 2. Introduction to Abstract Mathematics 7 Examples: (XY)Z , (D), ((XY)(~ X Z)) X, are propositional expressions. (( X Y ((Y)() , PP, QR - are not propositiona expressions. At this point all these expressions have no meaning whatsoever. But if one replaces all the variables in expression (XY)Z by the propositions one will obtain a proposition and as any other proposition it can be evaluated either true or false. Introduction to Abstract Mathematics 8 Order of Operations To interpret a propositional expression, read from left to right and use the following order ( precedence): 1. propositional expressions within parentheses ( innermost first) 2. negations, 3. conjunctions, 4. disjunctions, 5. conditionals, 6. biconditionals. Introduction to Abstract Mathematics 9 Tautology and contradiction Definition: A compound proposition is a proposition composed of one or more given propositions (called the component propositions in this context) and at least one logical connective. Definition: A compound proposition P is called a tautology if it is true for all possible combinations of truth values of the component propositions that compose P Definition: A compound Proposition S is called a contradiction if it is false for all possible combinations of truth values of the component propositions that compose S Introduction to Abstract Mathematics 10 Very Important Tautologies: , , ~, , , 1. Commutative Law [Com] PQ QP , PQ QP 3. Distributive Law [Dist] P(Q R) (PQ)(P R) P (Q R) (PQ) (P R) 5. DeMorgan Law [DeM] ~( PQ) (~P~Q ) ~( PQ) (~P~Q ) 7. Implication Law [Impl] (PQ)(~P Q) 9. Exportation [Exp] (PQ)RP(QR) Introduction to Abstract Mathematics 2. Associative Law [Assoc] (PQ ) R P(Q R) (P Q ) R P (Q R) 4. Contrapositive Law [Contr] (PQ) (~Q~P) 6. Double Negation [DN] ~~(P) P 8. Equivalence Law [Equiv] PQ (PQ) (QP) PQ (PQ) (~Q ~P) 10. Tautology [Taut] PP P PP P 11 Inference Rules (Valid arguments) Let P1, P2, ..Pk are propositional expressions (PE) . If PE Q is true when all P1, P2, ..Pk are true then we say that Q logically follows from hypotheses P1, P2, ..Pk P1, P2, …,Pk ├ Q (├ is called turnstile) That what is called Inference rule or Valid argument Example: P, PQ ├ Q P, Q ├ PQ Introduction to Abstract Mathematics 12 Two Methods of Inference rules First: P1, P2, …,Pk ├ Q if and only if P1 P2 … Pk Q tautology Example: PQ , P├ Q ( MP) What about PQ , P├ P ?????? Introduction to Abstract Mathematics 13 Second Method To prove that P1, P2, …,Pk ├ Q enough to construct sequence of PE Q1, Q2, …, Qn Such that Qn= Q every Qi is either one of Pi ( i = 1, 2, . . . , k) or it follows by the rule of logic Introduction to Abstract Mathematics 14 Inference Rules , , ~, Let P, Q, R, S are the PE then 1. Modus Ponens [MP] PQ , P├ P 3. Constructive Dilemma [CD] (PQ) (RS), P R ├ Q S 2. Modus Tolens [MT] PQ , ~Q├ ~P 4. Simplification [Simp] PQ P 5. Conjunction [Conj] P, Q ├ PQ 6. Disjunctive Syllogism [DS] P Q , ~P ├ Q 7. Destructive Dilemma [DD] (PQ) (RS), ~Q ~S ├ ~P ~R 8. Transitivity PQ , QR├ PR Introduction to Abstract Mathematics 15 Definitions Two expressions are called (logically) equivalent if they have same truth table for all possible (True or False) values for all variables appearing in either expression. We use the following notation XY to indicate that expressions X and Y are equivalent. Do not be confused to use symbol (biconditional) instead of logical equivalence . We already know that X Y and , ~ X Y have same truth table so they are logically equivalent therefore (X Y)(~ XY) What about X Y and X Z (are they equivalent?) Introduction to Abstract Mathematics 16 Tautology and Contradiction Definition: A propositional expression is called tautology if it yields a true proposition regardless of what propositions replace its variables. Definition: A propositional expression is called a contradiction if it yields a False proposition regardless of what propositions replace its variables. As you know (P Q) ( ~Q ~P) therefore (P Q) (~Q ~P) is tautology Introduction to Abstract Mathematics 17 Proposition Each of the following propositional expressions is a tautology. a. (P Q) ( ~P Q) b. ~(P Q) (P ~Q ) c. ~(P Q) ( ~P ~Q) d. ~(P Q) ( ~P ~ Q) e. ~( ~P) P Proof: Some comments about proposition1.1 Introduction to Abstract Mathematics 18 Introduction to Abstract Mathematics 19