Тексты на английском <<  Общение звук видео в интернете 8 класс Border Life: The Clash between Wildlife Conservation and Rural Poverty  >> Logic in computer science ES c233/CS F214/IS F214 Motivation Motivation Motivation Motivation Motivation Objective of the course Introduction to Logic History of Logic Fundamental of Logic Fundamental of Logic Fundamental of Logic Logic in CS Propositional Logic: Basics Propositional Logic: Basics Propositional Logic: Basics Propositional Logic: Basics Propositional Logic: Basics Propositional Logic: Basics Propositional Logic: Basics Propositional Logic Propositional Logic Propositional Logic Propositional Logic Natural Deduction Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction Rules of Natural Deduction

Презентация: «Logic in computer science ES c233CS F214IS F214». Автор: Prof. N Goyal. Файл: «Logic in computer science ES c233CS F214IS F214.ppt». Размер zip-архива: 235 КБ.

Logic in computer science ES c233CS F214IS F214

содержание презентации «Logic in computer science ES c233CS F214IS F214.ppt»
СлайдТекст
1 Logic in computer science ES c233/CS F214/IS F214

Prof. Navneet Goyal, CSIS Department, BITS-Pilani

2 Motivation

Logic 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 Motivation

Faults (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 First-order Logic!

4 Motivation

Questions 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 Motivation

Can 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 Motivation

Since the latter half of the twentieth century logic has been used in computer science for various purposes ranging from program specification and verification to theorem-proving.

7 Objective of the course

To prepare the student for using logic as a formal tool in computer science

8 Introduction to Logic

Logic 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 Logic

Symbolic 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 Logic

Two 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 Logic

We 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 Logic

5 basic connectives And Or If…then If and only if Not

13 Logic in CS

Logic 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: Basics

Declarative sentences Non-declarative sentences Go and attend classes Don’t take make-ups 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: Basics

It’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: Basics

Propositional 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: Basics

Every 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: Basics

Why 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: Basics

Assertions 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: Basics

This 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 Logic

Declarative 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 Logic

Atomic 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 Logic

p ^ 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 Logic

p 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 Deduction

Construct 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 Deduction

Constructing 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 Deduction

Rules 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 Deduction

Fundamental 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 Deduction

Example: 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 Deduction

Fundamental 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 Deduction

De 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 Deduction

Most 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 Deduction

Fallacies: 3 forms of faulty inferences! Fallacy of affirming the consequent Fallacy of denying the antecedent Non-sequitur 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 Deduction

Fallacy 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. Non-sequitur (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 Deduction

Examples 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 Deduction

Examples 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 Deduction

Examples 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 Deduction

Examples 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 Deduction

What 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 Deduction

Sequent Premises Conclusion

«Logic in computer science ES c233CS F214IS F214»
http://900igr.net/prezentacija/anglijskij-jazyk/logic-in-computer-science-es-c233cs-f214is-f214-81588.html
cсылка на страницу

Тексты на английском

46 презентаций о текстах на английском
Урок

29 тем
Слайды