Logic and Proofs: Understanding Tautologies, Equivalences, and Proof Techniques
Explore the fundamentals of logic and proofs, including tautologies, equivalences, proof techniques, and various logical concepts like Modus Ponens. Learn how to simplify logical expressions, apply De Morgan's Law, and understand the implications of deducing statements. Dive into the world of predicates, quantifiers, and logic games to enhance your understanding of mathematical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Tautologies, Equivalences, & Proofs Or Conclude: From: Separating And Proof Techniques/Lemmas And Using: Proving: From: Eval/Build Conclude: Simplify And : & ( ) & iff Eval/Build Simplify Selecting Or Or : ( ) & iff & Cases Excluded Middle , , & Modus Ponens & ( ) Deduction Implies : & Assume , prove Eval/Build Simplify Cases ( ) iff iff , , & & Equivalence Contrapositive & iff iff iff De Morgan's Law Transitivity & ( ) iff By Contradiction: From ( & ), conclude . Inconsistent: From and , conclude anything. Double Negation: iff Commutative: iff and iff Distributive: ( ) iff ( ) ( ) and ( ) iff ( ) ( )
What Our Logic Is and Is Not T T T T F F F T T In which is true? F F T , = T,T T,F F,T F,F If is true, then so is can be confusing because people think of causality.
What Our Logic Is and Is Not T T T T F F F T T Suppose I tell you . F F T , = T,T T,F F,T F,F Instead, use the operation s table. It is not true that is true is not. T T F = T
What Our Logic Is and Is Not T T T T F F F T T F F T Telling you is true, eliminates other possibilities. , = T,T T,F F,T F,F T T F = T
What Our Logic Is and Is Not T T T T F F F T T F F T In all the worlds remaining possible, is true. , = T,T T,F F,T F,F T T F = T
What Our Logic Is and Is Not From and , conclude . Modus Ponens: If is true, then so is Hey we still do use this! T T T T F F F T T F F T From this we can conclude . , = T,T T,F F,T F,F T T F = T
Predicates and Quantifiers boys b, Loves(b) Logic and Proofs Math 1019 Math 1090 Free and Bound Variables Truth Game A Game Tree Negations Restricted Domain Empty Set Sets of Tuples Skolem/Auxiliary Functions Objects, Predicates, & Relations & Order of Quantifiers: vs Negations Quantifiers and Games Humans are Mortal Understanding from the Inside Playing the Game Proof by Contradiction Formal Proofs Systems Oracles: Help from an Oracle Proof Game with Oracle Order of Quantifiers Example from Exercises Follow the Parse Tree 2 3 Diagonal Function f Distributive Laws for and Finding vs Verifing Model Tutorials Euclidian Geometry Overview of Topics Jeff Edmonds York University Math/EECS 1019/1090 Lecture 2
vs There is a girl for all boys to love. There is a inverse (eg 1/3) for all reals. Sam Mary T Bob Beth T Marilyn Monroe John T T Fred Ann One girl Sam Mary Not clear. Bob Beth T T T T Marilyn Monroe John T T T T T Fred Ann Could be a separate girl. Sam Mary For each boy, there is a girl. For each person, there is God. T Bob Beth T Marilyn Monroe John T T Fred Ann His special woman.
Proof Game with Oracle Prove: b, g, dayLoves(b, g, day) b, g, Loves(b, g, day) U,Loves,day M I must insist that you prove this using the following game. Three players: Prover: Works to prove the statement is true provides good objects asks for help from oracle makes conclusion Works to disprove the statement provides worst case objects defines the universe M Assures and manifests any assumptions about A when proving A B maybe defines the universe M valid Adversary: Oracle:
Proof Game with Oracle Three players: Adversary: If there is an implied M, I go first providing worst case U, functions, relations and free vars. I prove formula is true with the Adversary s choices and the Oracle s help. If x, If y, If or, If , get new oracle to assure LHS. prover: provides worst x. constructs best y. chooses which side to prove. Oracle: I assure A from A B. If x, If y, If or, If , assures LHS, then assures the RHS. or use modus ponens. queries about his favorite x. provides best y. chooses which side to prove.
Quantifiers and Games x, y, y>x Let s understand this deeply For All integer x, there Exists a y that is bigger. No matter how many people are in the hot tub, you can always fit one more. x? 0? 1? 2? 3? The integers go on forever. y is bigger. 1 is bigger. 2 is bigger. 3 is bigger. 4 is bigger.
Quantifiers and Games Say, I have a game for you. We will each choose an integer. You win if yours is bigger. I am so nice. I will even let you go first. Easy. I choose a trillion trillion. Well done. That is big! But I choose a trillion trillion and one so I win. Good game. Let me try again. I will win this time!
vs This creates a function p=p (v). Sam Fred Beth Ann p b, g, Loves(b, g) Sam Mary T Bob Beth T Marilyn Monroe John T T Fred Ann His special woman.
Example Build the Parse Tree. [( x (x) y (y)) y (y) ] ( y (y)) Prove: ( x (x) y (y)) y (y) y (y) x (x) y (y) y (y) 1 2 x (x) y (y) y (y) y (y) If someone assures me of y (y), I will assure that y (y). Done Done
Our Formal Proof Systems Lemmas/Theorems: Starting with all propositional tautologies (See slides). Prove new lemmas with quantifiers. Use lemmas via substitutions. Deduction : Assume (x ), prove (x ), conclude (x) (x). Within the assumption block we are only assuming that (x ) is true for some object x . Hence, from (x ) you can conclude x (x ), but the on the x prevents you from concluding x (x ). Similarly, add to any free variable in your axioms. After the assumption block, we conclude x [ (x) (x)], because we did this for an arbitrary object x .
Our Formal Proof Systems Rules (Adding/Removing / ) These help define and to work with quantifiers. Removing From line x (x), include line (term(x)) (eg (x)). Adding From line (x), include line x (x). Cannot be done for fixed x or x . Removing From line y (y), include line (y ). From line y (x,y), include line (x,y (x)). Note y is a fixed object while y (x) depends on x. If needed use y1 , y2 , to make sure they are not reused. Adding From line (term), include line y (y). Cannot be done if term depends on x bounded with x. Negating x (x) iff x (x)
Diagonal Build the Parse Tree. 1. y, x, (x,y)] [ d, (d,d)] y, x, (x,y) d, (d,d) I assure you by giving and receiving . I prove by constructing and receiving .
Diagonal Build intuition. y x 1. y, x, (x,y)] [ d, (d,d)] y y This means there is some row that is all true. T T T T There is a spot on the diagonal that is true. Yes (y ,y ).
Diagonal x U, , 1. y, x, (x,y)] [ d, (d,d)] ? y I get to get to provide the worse case universe ie. set of objects U, relations . My goal is to prove A C.
Diagonal y x U, , 1. y, x, (x,y)] [ d, (d,d)] Assume y, x, (x,y). I can help you! My goal is to prove d, (d,d). I need to construct a value d . y y T T T T T ? T Hey, I have a value of y that you can have. My goal is to prove (y ,y ). My x is this same y . I am going to give this value y to x to my oracle. Knowing x, (x,y ) is true for every x, I can assure you that it is true for yours. Hence valid. Hence (y ,y ).
Diagonal 1. y, x, (x,y)] [ d, (d,d)] Formal Proof: 1. Goal y, x, (x,y) d, (d,d) 2. y, x, (x,y) 3. x, (x,y ) 4. (y ,y ) Assume for Remove Remove with t=y have need 5. 6. d, (d,d) y, x, (x,y) d, (d,d) Add Conclude
Free Variable Fail U, ,c, (x) x (x) (c) x (x)same Prove: U, ,c,, (x) x (x) I must prove (x) x (x). Assume (c). x (x) (c) Knowing it, I can help you! I need to prove x (x). (x) I give you an arbitrary value x for x. I need to prove (x). I know (c) is true, but not (x). Ooops. The statement is not valid.
