L1_Propositional_Logic_I_Pre_Lecture.pdf

COM1002 Foundations of Computer Science: Aumtumn Semester 2023 Introduce key mathematical concepts that underpin: computer science, software engineering, artificial intelligence. Dr Paul Watton [email protected] Motivation Lecture 1: Propositional Logic Puzzle 1. Babies are illogical. 2....

COM1002 Foundations of Computer Science: Aumtumn Semester 2023 Introduce key mathematical concepts that underpin: computer science, software engineering, artificial intelligence. Dr Paul Watton [email protected] Motivation Lecture 1: Propositional Logic Puzzle 1. Babies are illogical. 2. Nobody is despised who can manage a crocodile. 3. Illogical people are despised. What does this tell us about Babies and Crocodiles? Can we express the above statements using propositional logic and derive a deduction ? 2 COM1002 Logistics COM1002 Structure Autumn Semester Dr Paul Watton Dr Maksim Zhukovskii Spring Semester Prof Mark Stevenson Weeks 7-12 Weeks 1-6 COM1002 ASSESSMENT 50% 2 Online MOLE Quizzes Weeks 6 and January Examinations. 50% Exam paper on Spring Semester Material Resits • To pass COM1002, your overall mark for the Autumn & Spring Semester exams must be at least 40%. • If you score less than 40% overall (weighted average of both Semesters), you will need to do the summer resit. • The Summer resit exam is a written exam that covers material from BOTH semesters!!! 5 COM1002: TIMETABLE 2023 – Weeks 1-6 WEEK 1 2 3 4 5 Tuesday 9am-10am Lecture I (Prop Logic) Lecture 3 (Prop Logic) Lecture 5 (Sets) Lecture 7 (Predicate Logic) Lecture 9 (Boolean Algebra) Tuesday 10am-11am Lecture 2 (Prop Logic) Lecture 4 (Sets) Lecture 6 (Predicate Logic) Lecture 8 (Predicate Logic) Lecture 10 (Revision ) Friday 0900-1000 (x4 ) No Tutorial Tutorial: (ex 1) Tutorial: (ex 2) Tutorial: (ex 3) Revision Tutorial 6 blackboard exam on weeks 1-5 (50% of Autumn Semester) There will be a 10-15 minute gap in the middle of 2 hour lecture! Teaching and Assessment 1 Lectures and tutorial sessions: The lectures will: • explain the concepts, • show how to solve problems However: • You need to do some independent work! • Exercises are provided for you to develop & apply your understanding of the material. The tutorials will start from Friday 6th October (WEEK 2) • run by 3rd / 4th year UG teaching assistants. • allow you to get help if stuck on the exercises. • please attempt exercises before the tutorials so that you can identify where (or if) you need help. COM1002 Motivation: Why is maths relevant for Computer Science ? 8 Computers do not work correctly (or as intended) all of the time. 9 2018: Catastrophic Computer Failures… Source: https://www.designboom.com/technology/uber-self-driving-car-kills-pedestrian-arizona-03-19-2018/ March 18, 2018: first incident of a pedestrian death caused by a self-driving vehicle. the object-detection system misclassified Herzberg when its sensors first detected her “as an unknown object, as a vehicle, and then as a bicycle with varying expectations of future travel path (6.5 seconds before crash). Image Analysis and A screenshot from an Uber's self-driving car log Artificial Intelligence NATIONAL TRANSPORTATION SAFETY BOARD It wasn't until 1.3 seconds before the crash that the software onboard realized an emergency braking maneuver was needed to avoid a collision. But it did not brake - Why? Uber’s software prevented its system from hitting the brakes if that action was expected to cause a deceleration of faster than 6.5 m/s2. That is to say, in an Propositional Logic emergency, the computer could not brake. emergency braking maneuvers were not enabled while the vehicle is under computer control, to reduce the potential for erratic vehicle behavior. The system relied on the driver to take control in an emergency, but the system 11 was not designed to alert the operator” Software Verification and Testing Hundreds of Post Office workers ‘vindicated’ by High Court ruling over faulty IT system that left them bankrupt and in prison • Horizon computer system was found to contain software defects which caused shortfalls in the subpostmasters' branch accounts over a number of years. • It led to hundreds of subpostmasters being accused of false accounting and theft, resulting in some being made bankrupt, while others were prosecuted and jailed. • A former post office worker committed suicide after he was wrongly accused of stealing £60,000. • In 2019, the Post Office paid a £57.75 million settlement after more than 550 claimants brought group legal action over its Horizon computer system. https://www.independent.co.uk/news/business/news/post-office-it-scandal-horizon-subpostmasters-judge-inquiry-a9391146.html https://www.independent.co.uk/news/business/news/post-office-high-court-case-it-horizon-postmaster-prison-latest-a9249431.html https://www.standard.co.uk/news/uk/post-office-scandal-worker-suicide-wrongly-accused-stealing-b931504.html Costly software errors… https://raygun.com/blog/costly-software-errors-history/ https://www.one-beyond.com/most-expensive-software-mistakes/ 1991: Patriot software problem led to an inaccurate tracking calculation of Missile Error incoming missile; the attack killed 28 American soldiers. 1996: Ariane 5 Flight 501 36s into its launch the engineers hit the self destruct button following multiple computer failures. ($8Bn to develop, and was carrying a $500M satellite payload) 1998: NASA’s Mars Climate Orbiter engineering team failed to make a simple conversion from imperial units to metric. $125M craft crashed into Mars. 2004: EDS Child Support System 2008: Heathrow Terminal 5 Opening software were completely incompatible, and irreversible errors (£1Bn to UK taxpayers) over 10 days some 42,000 bags failed to travel with their owners, and over 500 flights were cancelled. Faulty software (bugs or poorly designed) can have devasting implications Programs and software systems are mathematical structures. Mathematics is the foundations to software. Implementation must match Specification Mathematics can help identify errors in systems. THIS COURSE: Introduces mathematical foundations to achieve this COM1002: Develops your critical thinking skills Critical Thinking: Your Survival Weapon In The IT World Source: https://digimantralabs.com/blog/critical-thinking-your-survival-weapon-in-the-it-world/ 15 Propositional Logic 16 Motivation To understand why things happen: • How consequences follow from situations: • Hence, how situations should be designed: • in order to produce particular consequences. • To analyse causes of failures. What is Logic ? In science, logic means "the study of valid reasoning.“ COM1002: Foundations of mathematics I am in a maths lecture IMPLIES  I am sleeping Suppose the above propositional statement is TRUE, is the following proposition TRUE? I am sleeping IMPLIES  I am in a maths lecture I am in a IMPLIES maths lecture  I am sleeping Note, suppose the above propositional statement is TRUE, is the following proposition TRUE? I am sleeping IMPLIES  NO, Not necessarily True! …there are lots of other places I could be sleeping! I am in a maths lecture Languages: Natural and Formal natural language: language that is used for normal everyday communication in a human society, e.g. Chinese, English and French. In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols that may be constrained by rules that are specific to it. programming language: a formal constructed language designed to communicate instructions to a machine to control its behaviour. Logical Reasoning Reasoning about situations involves complex sentences with the ‘logical connectives’ of natural language, such as ‘not’, ‘and’, ‘or’ and ‘if ... then ...’ These are not the only expressions that drive logical reasoning, but they do form the most basic level. Propositional logic: working with well-chosen notation improves understanding, facilitates computation and is easier to manipulate. Propositions and Deductions 1 Atomic propositions: Statements that can only be either ‘true’ or ‘false’ - my watch is ticking, - my parrot is dead; Compound propositions: State relationships between propositions, e.g ‘my parrot is dead or my watch has stopped’ ‘my parrot is dead and my watch has stopped’ Propositional statement: sentence or expression that can be either TRUE or FALSE Exercise 1.1 Which of the following are propositional statements ? ▪ ▪ ▪ ▪ ▪ Yes 2+3 = 5 Yes 2+3 = 6 Do your homework, Joel! No Joel didn’t do his homework Yes Is there life on Mars ? No Logical Language 1 Defining Languages: ▪ Involves at least two languages: ▪ the object language – the one being defined, ▪ a meta-language – the one used for defining it; ▪ An object language has two aspects: ▪ its syntax – the rules for writing it ▪ its semantics – deciding what constructions written in it mean. Logical Language 2 Defining Syntax: Involves two steps: ▪ define the symbols, and then ▪ define larger constructions: ▪ e.g. words, sentences, etc for natural languages, ▪ the formulae for propositional logic. Propositional Variables: ▪ used to stand for propositions, ▪ names often abbreviate the propositions, e.g. D for the proposition “this man is dead”. ‘DEAD’ for the statement “this man is dead”. Logical Language 3 Propositional Connectives:     ▪ The “operations” of propositional logic; ▪ Similar role to +, -, /,* etc in arithmetic; ▪ Form compound propositions: ▪ from one or two simpler ones; Each connective has a specific meaning, i.e its ‘semantics’ The Propositional Connectives 1 Negation: For a proposition p: • negation is written  p, • usually pronounced “not p”, • meaning of  p is “proposition p is false”. Laws for negation: •  true = false, and  false = true; • for any p:   p = p (law of double negation). The Propositional Connectives 2 Disjunction: For propositions p, q: • written p  q, • usually pronounced “p or q”, • is true if ‘either p is true, or q is true, or both, • p and q are often called disjuncts. Law for disjunction: p   p = true ‘the law of the excluded middle.’ Exercise Are the following disjunctions true or false ? 1. (3 < 2) ˅ (3 < 5) True 2. (5 < 4) ˅ (7 < 5) False 3. (5 < 6) ˅ (6 < 8) True The Propositional Connectives 3 Conjunction: • For propositions p and q: • written p  q, • usually pronounced “p and q”, • is true if ‘both p is true and q is true’ • p and q are often called conjuncts. Law for conjunction: p   p = false. Exercise Are the following conjunctions true or false ? 1. (3 < 2) ˄ (3 < 5) False 2. (5 < 4) ˄ (7 < 5) False 3. (5 < 6) ˄ (6 < 8) TRUE The Propositional Connectives 4 Implication: For propositions p and q: • written p  q, • usually pronounced “p implies q”, or “if p then q”, • p is the premise and q is the conclusion. • Means: ‘if p is true, then q must be true’. Law for implication: (Contrapositive) (p  q) is equivalent to ( q   p). If (p  q) is a TRUE statement then ( q   p) is TRUE. If ( q   p) is a TRUE statement then (p  q) is TRUE. Propositions and Deductions ▪ Deduction is a process with three steps: ▪ Start from premises – true propositions; ▪ Construct an inference from these; ▪ This gives a conclusion, as a truth value. The Propositional Connectives 4 Rules for Inference: For propositions p and q: If p , p  q are both TRUE then we can infer q is TRUE. If (a  b) & (b  c) then we can infer (a  c) If (a  b) & (b  c) & (c  d) then we can infer (a  d) A note on Implication (and English language) p  q may be expressed in English in several ways: p implies q if p then q q if p q whenever p p only if q Useful for some of the questions on Examples sheet 1. 36 Logic Puzzle 1. Babies are illogical. 2. Nobody is despised who can manage a crocodile. 3. Illogical people are despised. What does this tell us about Babies and Crocodiles? Can we express the above statements using propositional logic and derive a deduction ? 37 Solving strategy… 1. Identify the propositions and represent with a variable (recall a proposition can be TRUE or FALSE) 2. Try to rephrase the implication statements in the form: If * * * then * * * 3. Express statements with propositional logic variables. 4. Use the rules for inference to derive a deduction Logic Puzzle Solution 1. Babies are illogical. B – it is a baby Identify I - it is illogical propositional variables 2. Nobody is despised who can manage a crocodile. M – it can manage a crocodile D – it is despised 3. Illogical people are despised. I – it is illogical D – it is despised Where ‘it’ in this context refers to a general person. Logic Puzzle Solution 1. Babies are illogical. If it is a baby then it is illogical BI 2. Nobody is despised who can manage a crocodile. If it can manage a crocodile then it is not despised. 3. Illogical people are despised. If it is illogicial then it is despised ID M  ¬D Logic Puzzle Solution 1. Babies are illogical. (B  I) 2. Nobody is despised who can manage a crocodile. (M  ¬D) 3. Illogical people are despised. (I  D) Recall that (M  ¬D) If (B  I) & is equivalent to (I  D) & B  ¬M (D  ¬M) (D  ¬M) we can infer (B  ¬M) Babies cannot manage crocodiles