№  Слайд  Текст 
1 

Logic in computer science ES c233/CS F214/IS F214Prof. Navneet Goyal, CSIS Department, BITSPilani 
2 

MotivationLogic became popular in the early 20th century among philosophers and mathematicians What constitutes a correct proof in Mathematics? Some ‘correct’ proofs were later disproved by other mathematicians Concept of logic helps us to figure out what constitutes a correct argument and what constitutes a wrong argument Euclid’s parallel postulate & Fermat’s Last theorem are classic examples! 
3 

MotivationFaults (bugs) have been detected in proofs (programs) Bugs are hard to detect! Notion of correct argument Formal Logic as foundation to Mathematics? Mathematics does rest on one strong foundation – Set Theory! Set theory is based on Firstorder Logic! 
4 

MotivationQuestions related to automation or mechnizability of proofs needs to be answered These questions are relevant & important for present day computer science! They form the basis for automatic theorem proving David Hilbert asked the important question, as to whether all mathematics, if reduced to statements of symbolic logic, can be derived by a machine. 
5 

MotivationCan the act of constructing a proof be reduced to the manipulation of statements in symbolic logic? Logic enabled mathematicians to point out why an alleged proof is wrong, or where in the proof, the reasoning has been faulty. By symbolising arguments rather than writing them out in some natural language (which is fraught with ambiguity), checking the correctness of a proof becomes a much more viable task 
6 

MotivationSince the latter half of the twentieth century logic has been used in computer science for various purposes ranging from program specification and verification to theoremproving. 
7 

Objective of the courseTo prepare the student for using logic as a formal tool in computer science 
8 

Introduction to LogicLogic is called the CALCULUS of Computer Science! LOGIC: CS CALCULUS: Physical sciences & Engineering Disciplines CS areas where we use LOGIC Architecture (logic gates) Software Engineering (Specification & Verification) Programming Languages ( Semantics & Logic Programming) AI (automatic theorem proving) Algorithms (complexity) Databases (SQL) 
9 

History of LogicSymbolic Logic (500 BC – 19th century) Algebraic Logic (Mid to late 19th century) Mathematical Logic (19th century to 20th century) Logic in Computer Science 
10 

Fundamental of LogicTwo famous laws of classical logic Law of the excluded middle Law of contradiction Declarative statements Truth values – T or F Propositions For every proposition p, either p is T or p is F For every proposition p, it is not the case that p is both T and F 
11 

Fundamental of LogicWe are interested in precise declarative statements about computer systems and programs We not only want to specify such statements, but also want to check whether a given program or system fulfils specifications at hand Need to develop a calculus of reasoning which allows us to draw conclusions Derive new facts from given facts 
12 

Fundamental of Logic5 basic connectives And Or If…then If and only if Not 
13 

Logic in CSLogic underlies the reasoning in mathematical statements Objective is to develop languages to model the situations that we encounter in CS Reasoning about situations formally Constructing arguments about them Arguments should be valid and can be defended rigorously Can be executed on a machine 
14 

Propositional Logic: BasicsDeclarative sentences Nondeclarative sentences Go and attend classes Don’t take makeups Examples of declarative statements Goldbach’s conjecture All BITSIANs are intelligent A is older than B There is ice in the glass 
15 

Propositional Logic: BasicsIt’s a language! Propositional logic is based on propositions or declarative statements Propositions or declarative statements can be mapped onto Boolean values T or F Statements about computer systems or programs We also want to check whether a computer program or a system satisfies the specifications 
16 

Propositional Logic: BasicsPropositional logic describes ways to combine true statements by means of connectives to produce other true statements. If it is asserted that `Jack is taller than Jill' and `Jill can run faster than Jack' are T `Jack is taller than Jill and Jill can run faster than Jack'. However, if Jill is actually taller than Jack, then the 1st statement is F and the combined statement is false as well. Propositional logic allows us to formalize such statements In concise form: A ^ B 
17 

Propositional Logic: BasicsEvery logic comprises a (formal) language for making statements about objects and reasoning about properties of these objects. We will restrict our attention to mathematical objects, programs, and data structures in particular Statements in a logical language are constructed according to a predefined set of formation rules called ‘syntax rules’. 
18 

Propositional Logic: BasicsWhy English or any other natural language can’t be used? English is a rich language which cant be formally described Meaning of an English sentence can be ambiguous, subject to different interpretations depending on the context and implicit assumptions Another important factor is conciseness. Natural languages tend to be verbose, and even fairly simple mathematical statements become exceedingly long (and unclear) when expressed in them. The logical languages that we shall define contain special symbols used for abbreviating syntactical constructs. 
19 

Propositional Logic: BasicsAssertions and Proofs A precise language is required whose syntax can be completely described in a few simple rules semantics can be defined unambiguously A logical language can be used in different ways Deduction system or proof system 
20 

Propositional Logic: BasicsThis use of a logical language is called proof theory. A set of facts ‘called’ axioms and a set of deduction rules (inference rules) are given, and the object is to determine which facts follow from the axioms and the rules of inference. When using logic as a proof system, one is not concerned with the meaning of the statements that are manipulated, but with the arrangement of these statements, and specifically, whether proofs or refutations can be constructed. 
21 

Propositional LogicDeclarative sentences in English ? string of symbols Compressed but complete encoding of declarative statements Allows us to concentrate on the mere mechanics of our argumentation Specifications of systems or software are sequence of such declarative statements Automatic manipulation of such statements, something that machines love to do 
22 

Propositional LogicAtomic or indecomposable sentences The number 5 is even Composition of atomic sentences p: I won the lottery last week q: I purchased a lottery ticket r: I won the last week’s sweepstakes (horse race) ¬ p: I did not win the lottery last week p v r: atleast one of them is true. Disjunction. I won the lottery last week or I won the last week’s sweepstake (not to be confused with English OR) 
23 

Propositional Logicp ^ r: conjunction. Last week I won the lottery and the sweepstakes p q: implication. If I won the lottery last week, then I purchased a lottery ticket. p is called the assumption and q is called conclusion. 
24 

Propositional Logicp q: implication: Some interpretations p implies q If p then q p only if q p is a sufficient condition for q q is a necessary condition for p q if p q follows from p q provided p q is a consequence of p q whenever p 
25 

Natural DeductionConstruct a language of reasoning about propositions Set of rules which allow us to draw a conclusion given a set of premises PROOF RULES Allow us to infer formulas from other formulas Applying these rules is succession, we may infer a conclusion from a set of premises Be careful though!! 
26 

Natural DeductionConstructing a proof is much like a programming! It is not obvious which rules to apply and in what order to obtain the desired conclusion Careful choice of proof rules! 
27 

Rules of Natural DeductionRules of inference/natural deduction specify which conclusions may be inferred legitimately from assertions known, assumed, or previously established Fundamental rule 1 (modus ponens or rule of detachment) p p q . . . q Fundamental rule 2 (transitive rule) p q q r . . . p r 
28 

Rules of Natural DeductionFundamental rule 1 (modus ponens or rule of detachment) p p q . . . q The rule is a valid inference because [p ^ (p q)] q is a tautology! (use truth tables or abbreviated truth tables to show that a proposition is a tautology) 
29 

Rules of Natural DeductionExample: if it is 11:00 o’ clock in Tallahassee if it is 11:00 o’ clock in Tallahassee, then it is 11:00 o’ clock in New Orleans then by rule of detachment, we must conclude: it is 11:00 o’ clock in New Orleans Difference between implication and inference! the truth of an implication p q does not guarantee the truth of either p or q. But the truth of both p and p q does guarantee the truth of q. 
30 

Rules of Natural DeductionFundamental rule 2 (transitive rule) p q q r . . . p r This is a valid rule of inference because the implication (p q) ^ (q r) (p r) is a tautology! Generalization is possible De Morgan’s law: FR #3 Law of contraposition: FR #4 
31 

Rules of Natural DeductionDe Morgan’s law: FR #3 ~(p v q) = (~p) ^ (~q) ~(p ^ q) = (~p) v (~q) Law of contrapositive: FR #4 p q = (~q ~p) Double Negation ~(~p) =p Implication p q = (~p) v q 
32 

Rules of Natural DeductionMost arguments in Mathematics are based on FR#1 & FR#2, with occasional use of FR#3 & FR#4. Get comfortable with FRs! 
33 

Rules of Natural DeductionFallacies: 3 forms of faulty inferences! Fallacy of affirming the consequent Fallacy of denying the antecedent Nonsequitur fallacy Fallacy of affirming the consequent p q q . . . p If the prices of gold are rising, then inflation is surely coming. Inflation is surely coming. Therefore, the price of gold is rising. Check: [(p q) ^ q] p for tautology! 
34 

Rules of Natural DeductionFallacy of denying the antecedent (affirming the opp.) p q ~p . . . ~q Since the opp. of p q is ~p ~q, this fallacy is the same as affirming the opp. Nonsequitur (it does not follow) p If Socrates is a man, then Socrates is mortal . . . q Socrates is a man Therefore, Socrates is mortal Socrates is a man Therefore, Socrates is mortal 
35 

Rules of Natural DeductionExamples of Arguments If a baby is hungry, then the baby cries. If the baby is not mad, then he does not cry. If a baby is mad, then he has a red face. Therefore, if a baby is hungry, then he has a red face. Model this problem!! h: a baby is hungry c: a baby cries m: a baby is mad r: a baby has a red face 
36 

Rules of Natural DeductionExamples of Arguments If a baby is hungry, then the baby cries. If the baby is not mad, then he does not cry. If a baby is mad, then he has a red face. Therefore, if a baby is hungry, then he has a red face. Model this problem!! h: a baby is hungry c: a baby cries m: a baby is mad r: a baby has a red face 
37 

Rules of Natural DeductionExamples of Arguments If Nixon is not reelected, then Tulsa will lose its air base Nixon will be reelected iff Tulsa votes for him If Tulsa keeps its air base, Nixon will be reelected Therefore, Nixon will be relelected Model this problem!! R: Nixon will be reelected T: Tulsa votes for Nixon A: Tulsa keeps its air base 
38 

Rules of Natural DeductionExamples of Arguments If angles A & B are rt angles, then they are equal The angles A & B are equal Hence, the angles A & B must be rt angles R: A & B are at rt angles E: A & B are equal Fallacy: affirming the consequent! 
39 

Rules of Natural DeductionWhat remains when arguments are symbolized is the bare logical skeleton, the mere form of argument which many arguments may have in common regardless of the context of the sentences It is this form that enables us to analyze the inference, for deduction has more to do with forms of the propositions in an argument than with their meanings 
40 

Rules of Natural DeductionSequent Premises Conclusion 
«Logic in computer science ES c233CS F214IS F214» 