Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Chapter 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 doDefinition. 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)Let p, q, r, … be propositions. Compound statements can be formed using binary connectives (operators):• (and)• (inclusive or)• (implication)• (biconditional)and unary operator• (negation) Logic is the algebra of propositions (Boolean algebra)Conjunction s = pq (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 oatsWhen p, q are two true statements, (p q) is true.If p is true and q is false, (p q) is falseIf both p and q are false, (p q) is falsep q s = p q1 1 11 0 00 1 00 0 0Disjunction pq (p or q) is true when either p or q or both are true ( inclusive or ) and false otherwise.p q s = p q1 1 11 0 10 1 10 0 0Implication p qTerminology: 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 pNote: 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 walkdoes not imply that I go for a walk the weather is goodor that the weather is bad I will not go for a walkName the antecedent p and consequent q, p q, in each of the following statements.• If Peter gets scholarship he will go to college. • A sufficient condition for using 6 storage locations is that a 23 array is to be stored.• Susan will pass her physics class only if she studies hard.• Good combustion is a necessary condition for high gasoline mileage. pqppqqqpp q s = p q1 1 11 0 00 1 10 0 1vacuously true 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.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 11 0 0 10 1 1 00 0 1 1Definition A compound statement s(p, q, r,…) that is alwaystrue, 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 contradictionDefinition 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) p q r1 1 1 1 1 1 11 0 0 1 0 0 10 1 1 0 0 0 10 0 1 1 1 1 1(p q) ( q p) p q, or r: (p q) ( q p) p q is a tautology.Negation p (not p ) p p 1 00
View Full Document
Unlocking...