Formal LogicLogic: The foundation of reasoningStatementStatements and LogicStatements and Logical ConnectivesDefinitions for Logical ConnectivesSlide 7Another form of implicationSlide 9Slide 10Truth TablesWell Formed Formula (wff)Truth Tables for some wffsWff with n statement lettersTautology and ContradictionTautological EquivalencesSome Common EquivalencesDe Morgan’s LawsAlgorithmPseudocode exampleTautology Test AlgorithmFormal LogicMathematical Structures for Computer ScienceChapter 1Copyright © 2006 W.H. Freeman & Co. MSCS SlidesFormal LogicSection 1.1 Statements, Symbolic Representations and Tautologies2Logic: The foundation of reasoningWhat is formal logic? Multiple definitionsFoundation for organized and careful method of thinking that characterizes reasoned activityThe study of reasoning : specifically concerned with whether something is correct or falseFormal logic focuses on the relationship between statements as opposed to the content of any particular statement. Applications of formal logic in computer science:Prolog: programming languages based on logic.Circuit Logic: logic governing computer circuitry.Section 1.1 Statements, Symbolic Representations and Tautologies3StatementDefinition of a statement:A statement, also called a proposition, is a sentence that is either true or false, but not both.Hence the truth value of a statement is T (1) or F (0)Examples: Which ones are statements?All mathematicians wear sandals.5 is greater than –2.Where do you live?You are a cool person.Anyone who wears sandals is an algebraist.Section 1.1 Statements, Symbolic Representations and Tautologies4Statements and LogicAn example to illustrate how logic really helps us (3 statements written below): All mathematicians wear sandals.Anyone who wears sandals is an algebraist.Therefore, all mathematicians are algebraists.Logic is of no help in determining the individual truth of these statements.However, if the first two statements are true, logic assures the truth of the third statement.Logical methods are used in mathematics to prove theorems and in computer science to prove that programs do what they are supposed to do.Section 1.1 Statements, Symbolic Representations and Tautologies5Statements and Logical ConnectivesUsually, letters like A, B, C, D, etc. are used to represent statements.Logical connectives are symbols such as Λ, V, , Λ represents and represents implicationA statement form or propositional form is an expression made up of statement variables (such as A, B, and C) and logical connectives (such as Λ, V, , ) that becomes a statement when actual statements are substituted for the component statement variables. Example: (A V A)  (B Λ B)Section 1.1 Statements, Symbolic Representations and Tautologies6Definitions for Logical ConnectivesConnective # 1: Conjunction (symbol Λ)If A and B are statement variables, the conjunction of A and B is A Λ B, which is read “A and B”.A Λ B is true when both A and B are true. A Λ B is false when at least one of A or B is false. A and B are called the conjuncts of A Λ B.Connective # 2: Disjunction (symbol V)If A and B are statement variables, the disjunction of A and B is A V B, which is read “A or B”.A V B is true when at least one of A or B is true. A V B is false when both A and B are false.Section 1.1 Statements, Symbolic Representations and Tautologies7Definitions for Logical ConnectivesConnective # 3: Implication (symbol  )If A and B are statement variables, the symbolic form of “if A then B” is A  B. This may also be read “A implies B” or “A only if B.”Here A is called the hypothesis/antecedent statement and B is called the conclusion/consequent statement.“If A then B” is false when A is true and B is false, and it is true otherwise. Note: A  B is true if A is false, regardless of the truth of BExample: If Ms. X passes the exam, then she will get the jobHere A is She will get the job and B is Ms. X passes the exam.The statement states that Ms. X will get the job if a certain condition (passing the exam) is met; it says nothing about what will happen if the condition is not met. If the condition is not met, the truth of the conclusion cannot be determined; the conditional statement is therefore considered to be vacuously true, or true by default.Section 1.1 Statements, Symbolic Representations and Tautologies8Another form of implicationRepresentation of If-Then as OrLet A be “You do your homework” and B be “You will flunk.” The given statement is “Either you do your homework or you will flunk,” which is A V B.In if-then form, A  B means that “If you do not do your homework, then you will flunk,” where A (which is equivalent to A  ) is “You do not do your homework.” Hence, A  B  A V BA B ABT T TT F FF T TF F TA AB A V BT F T TT F F FF T T TF T F TSection 1.1 Statements, Symbolic Representations and Tautologies9Definitions for Logical ConnectivesConnective # 4: Equivalence (symbol )If A and B are statement variables, the symbolic form of “A if, and only if, B” and is denoted A  B. It is true if both A and B have the same truth values.It is false if A and B have opposite truth values. The truth table is as follows:Note: A  B is a short form for (A  B) Λ (B  A)A B AB BA (A  B) Λ (B  A)T T T T TT F F T FF T T F FF F T T TSection 1.1 Statements, Symbolic Representations and Tautologies10Definitions for Logical ConnectivesConnective #5: Negation (symbol )If A is a statement variable, the negation of A is “not A” and is denoted A.It has the opposite truth value from A: if A is true, then A is false; if A is false, then A is true. Example of a negation:A: 5 is greater than –2 A : 5 is less than –2B: She likes butter B : She dislikes butter / She hates butterA: She hates butter but likes cream / She hates butter and likes creamA : She likes butter or hates creamHence, in a negation, and becomes or and vice versaSection 1.1 Statements, Symbolic Representations and Tautologies11Truth TablesA truth table is a table that displays the truth values of a statement form which correspond to the different combinations of truth values for the variables.A AT