Logic Review and Exercises for CS2209 Tutorial
Dive into the world of propositional logic, logical operations, laws of logic, and rules of inference with this comprehensive review. Practice filling out truth tables and proving tautologies or contradictions in this tutorial for CS2209 students.
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
CS2209 Tutorial 3 Sep. 28th , 2020 Xindi Wang xwang842@uwo.ca Department of Computer Science
Reminder Assignment 2 is due on Oct 5th in zyBook (which means that you are required to buy zyBook to finish the assignment) Presentation Title Here
Todays Agenda Review of Propositional Logic Predicates and Quantifiers Agenda
Reviewof Propositional Logic Review of Propositional Logic
Logical Operations Basics: ? ? ? ? ? ? ? ? ? ? ? p q T T T T F F T T T F F F T F F F F T T F F T T T T F F T T F F T Logical Operations
Logical Operations Compound Propositions: Tautology: a compound proposition is a tautology if the proposition is always true (i.e. all rows in the true table are true) (e.g. ? ? ?) Contradiction: a compound proposition is a contradiction if the proposition is always false (i.e. all rows end with false) (e.g. ? ?) Satisfaction: some rows in the truth table end with true (e.g. ? ?) Logical Operations
Logical Laws ? ? Double Negation (? ?) ( ? ?) (? ?) ( ? ?) De Morgan s Laws ? ? q p ? ? q p Commutative Laws ? (? r) (? ?) r ? (? r) (? ?) r Associative Laws ? (? r) (? ?) (? r) ? (? r) (? ?) (? r) Distributive Laws ? T p ? F p Identity Laws ? F F ? T T Domination Laws ? p p ? p p Idempotent Laws ? (p q) p ? (p q) ? Absorption Laws ? ? (? ?) (? ?) ? ? ? ? Conditional Identities Logical Laws
Rules of Inference Rules of Inference
Exercises Filling out the truth table for a compound proposition (use basic logical connectives) (? ? ? ) ? ? (? ?) ? (? ?) (? (? ?)) p q s T T T T F F T T T F F T T F T F T F T T F T F F F T T F F T T T F F T F T F F T F T F F T F T F T F F F F T F T Exercises
Exercises Proving tautologies or contradictions using truth table (? ?) (? ?) Exercises
Exercises Using laws of logic to prove logical equivalence ? (? ?) ? (? ?) Exercises
Exercises Proving arguments are valid using rules of inference Exercises
Predicates and Quantifiers Predicates and Quantifiers
Predicates Definition: A logical statement whose truth value is a function of one or more variables is called a predicate. (propositions with parameters) P(x) is a predicate that P(x) is true for some values of ? ?, and false for the rest Example: ? < ? is a predicate, when ? = 1,y = 2 is true and ? = 3,y = 2 is false Predicates
Qualifiers: universal Universal qualifier: , for all The statement ? ?,?(?) (for every x in domain S, P(x)) is called a universally quantified statement ? ?,?(?) is true if and only if ?(?) is true for every ? ? If ?1,?2, ,?? is a list of elements in S, then ? ?,?(?) is true if and only if ? ?1 ? ?2 ?(??) is true Qualifiers
Qualifiers: existential Existential qualifier: , there exists The statement ? ?,?(?) (there exist some x in domain S, P(x)) is called a existentially quantified statement ? ?,?(?) is true if and only if there exist some true ? ? such that ?(?) is true If ?1,?2, ,?? is a list of elements in S, then ? ?,?(?) is true if and only if ? ?1 ? ?2 ?(??) is true Qualifiers
