Chapter 2 Fundamentals of Logic The rules of logic give precise meaning to mathematical statements We need to study logic to learn how to construct valid reasoning Logic focuses on the relationship between propositions not the content of any particular proposition Logical methods are used in mathematics to prove theorems and in computer science to prove that programs do what they supposed to do Definition A proposition or a statement is a sentence that is either true or false but not both Boolean variables Which of the following are propositions Two is a prime number How are you x 1 2 There is life on Saturn n2 n 41 is a prime number for all natural numbers n N like any statement this one relies upon some definitions terminology and notations Logic is the algebra of propositions Boolean algebra Let p q r be propositions Compound statements can be formed using binary connectives operators and inclusive or implication biconditional and unary operator negation Conjunction s p q p and q is true when both p and q are true and false otherwise p grass is green q horses like oats s p q grass is green and horses like oats When p q are two true statements p q is true If p is true and q is false p q is false If both p and q are false p q is false s p q p q 1 1 1 1 0 0 0 1 0 0 0 0 Disjunction p q p or q is true when either p or q or both are true inclusive or and false otherwise s p q p q 1 1 1 1 0 1 0 1 1 0 0 0 Implication p q Terminology p antecedent hypothesis premises q consequent conclusion p implies q if p then q p is sufficient condition of q q whenever p p only if q q is necessary condition of p Note p q does NOT imply p q i e p is sufficient but not necessary condition of q If the weather is good I will go for a walk The weather is good I will go for a walk does not imply that I go for a walk the weather is good or that the weather is bad I will not go for a walk Name the antecedent p and consequent q p q in each of the following statements If Peter gets scholarship he will go to college q p A sufficient condition for using 6 storage locations is that a 2 3 array is to be stored q p Susan will pass her physics class only if she studies hard p Good combustion is a necessary condition for q high gasoline mileage p q Implication p q has a truth value It is defined to be true in all cases except when p is true and q is false s p q p q 1 1 1 1 0 0 0 1 1 0 0 1 vacuously true p q is NOT equivalent to q p converse of p q since not for all assignments of p q truth value of p q is the same as truth value of q p p q p q q p 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 Definition A compound statement s p q r that is always true no matter what the truth values of p q r is called a tautology A compound statement s p q r that is always false is called a contradiction Definition Two compound statements s1 p q r and s2 p q r are called equivalent if s1 s2 is a tautology The notations s1 s2 denotes that s1 and s2 are logically equivalent Biconditional p q or p q is true when p and q have the same truth value and false otherwise p is sufficient and necessary condition of q q if and only if iff p p and q are equivalent p q p q q p p q q p 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 p q q p p q or r p q q p p q is a tautology p q r Negation p not p p p 1 0 0 1
View Full Document
Unlocking...