Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    03 Logic3

    Uploaded by

    Nisa Fatima
    This document discusses propositional logic and predicate logic. It defines propositional functions that can take variables as inputs and return propositions. Predicates are modeled as propositional functions that take subjects as inputs and return propositions. Quantifiers are needed to represent statements about all or some objects of a domain.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    03 Logic3

    Uploaded by

    Nisa Fatima
    19 views17 pages
    This document discusses propositional logic and predicate logic. It defines propositional functions that can take variables as inputs and return propositions. Predicates are modeled as propositional functions that take subjects as inputs and return propositions. Quantifiers are needed to represent statements about all or some objects of a domain.

    Original Title

    03-Logic3

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses propositional logic and predicate logic. It defines propositional functions that can take variables as inputs and return propositions. Predicates are modeled as propositional functions that take subjects as inputs and return propositions. Quantifiers are needed to represent statements about all or some objects of a domain.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    19 views17 pages

    03 Logic3

    Uploaded by

    Nisa Fatima
    This document discusses propositional logic and predicate logic. It defines propositional functions that can take variables as inputs and return propositions. Predicates are modeled as propositional functions that take subjects as inputs and return propositions. Quantifiers are needed to represent statements about all or some objects of a domain.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 17

    Discrete Structures

    Lecture 3: Propositional Logic


    based on slides by Jan Stelovsky
    based on slides by Dr. Baek and Dr. Still
    Originals by Dr. M. P. Frank and Dr. J.L. Gross
    Provided by McGraw-Hill

    Muhammad Adeel Zahid


    Department of Computer Science
    Government College University
    Faisalabad
    Types of Propositions

    • A Proposition can eb categorized into following three types


    • Tautology
    • Contradiction
    • Contingency
    • Tautology is a compound proposition that is always TRUE regardless of the truth
    value of its atomic propositions
    • ∨¬ , ∨
    • I will take this course or I will not take this course
    • Contradiction is a compound statement that is always FALSE regardless of the
    truth value of its atomic propositions
    • ∧¬ , ∧
    • I will take this course and I will not take this course
    • Contingency is a compound proposition that can either be TRUE or FALSE
    • Neither a tautology nor a contradiction
    • ∨ →

    2
    Logical Equivalence

    • Compound proposition p is logically equivalent to compound


    proposition q, written ≡ or ⇔ if the compound proposition
    ↔ is a tautology

    • Compound propositions p and q are logically equivalent to each other


    iff p and q contain the same truth values as each other in all
    corresponding rows of their truth tables

    3
    Logical Equivalence: Proof via Truth Table

    • Prove that ¬ ∧ ≡ ¬ ∨ ¬ (De Morgan’s Law)

    ¬ ¬ ¬( ∧ ) ¬ ∨¬

    • Prove the following equivalences using truth table


    • ¬ ∨ ≡ ¬ ∧ ¬ De Morgan’s Law
    • → ≡¬ ∨
    • ∨ ∧ ≡ ∨ ∧ ( ∨ ) Distributive Law

    4
    Equivalence Laws

    • They are like arithmetic identities but for propositional equivalences


    • In trigonometry you might have come across identity
    • sin 2 = 2 sin cos
    • Similarly you have in propositional logic
    • ¬ ∨ ≡ →
    • You can replace one with another to further simplify/solve propositional
    equations
    • Identity: ∧ ≡ and ∨ ≡
    • Domination: ∨ ≡ and ∧ ≡
    • Idempotent: ∨ ≡ and ∧ ≡
    • Double negation: ¬¬ ≡

    5
    Equivalence Laws

    • Commutative: ∨ ≡ ∨ and ∧ ≡ ∧
    • Associative:
    • ∨ ∨ ≡ ∨ ∨
    • ∧ ∧ ≡ ∧ ∧
    • Distributive
    • ∨ ∧ ≡ ∨ ∧ ∨
    • ∧ ∨ ≡ ∧ ∨ ∧
    • De Morgan’s: ¬ ∨ ≡ ¬ ∧ ¬ and ¬ ∧ ≡¬ ∨¬
    • Absorption: ∨ ∧ ≡ and ∧ ∨ ≡
    • Trivial tautology/contradiction: ∨ ¬ ≡ ∧¬ ≡

    6
    Operator Definitions via Equivalence

    • Using equivalence, we can define operators in terms of other


    operators
    • ⊕ ≡ ∧¬ ∨ ¬ ∧
    •≡ ∧ ¬ ∨ ¬ ∧ ( ∧ ¬ ∨ ) By distributive law
    • ≡ ¬ ∨ ∧¬ ∧ ∨ ∧¬ By commutative law
    • ≡ ¬ ∨ ∧ ¬ ∨¬ ∧ ∨ ∧ ∨¬ Distributive
    •≡ ∧ ¬ ∨¬ ∧ ∨ ∧ Trivial Tautology
    • ≡ ¬ ∨ ¬ ∧ ∨ Identity
    • ≡ ¬ ∧ ∧ ∨ De Morgan
    • ≡ ∨ ∧ ¬( ∧ ) Commutative

    7
    Defining Operators via Equivalences

    • Implication: → ≡ ¬ ∨
    • Biconditional implication: ↔ ≡ → ∧ →
    • Also, ↔ ≡ ¬ ⊕
    • The above three equivalences have already been proved using truth
    table
    • You can use any of the equivalence laws and the equivalences proved
    through truth table to simplify/solve your expressions

    8
    Example Problem

    • Prove that ¬ → ≡ ∧¬
    •¬ → ≡ ¬ ¬ ∨ By expanding implication
    • ≡ ¬ ¬ ∧ ¬ De Morgan’s Law
    • ≡ ∧ ¬ Double negation

    9
    Example Problem

    • Prove that ∧ ¬ → ⊕ ≡ ¬ ∨ ∨ ¬ using symbolic


    derivation (not by using truth table
    • ∧¬ → ⊕
    • ≡ ¬ ∧ ¬ ∨ ⊕ Expand implication
    •≡¬ ∧¬ ∨ ∨ ∧ ¬( ∧ ) Expand exclusive OR
    •≡ ¬ ∨ ∨ ∨ ∧¬ ∧ De Morgan
    •≡ ∨¬ ∨ ∨ ∧¬ ∧ Commutative
    •≡ ∨¬ ∨ ∨ ∧¬ ∧ Open brackets for disjunction
    •≡ ∨ ¬ ∨ ∨ ∧¬ ∧ associative over disjunction

    10
    Example Problem

    •≡ ∨ ¬ ∨ ∨ ∧¬ ∧ copy over
    •≡ ∨ ¬ ∨ ∨ ∧ (¬ ∨ ¬ ∧ Distributive
    •≡ ∨ ∨ ∧ (¬ ∨ ¬ ∨ ¬ Tautology and De Morgan
    •≡ ∨ ∧ ¬ ∨¬ Domination
    • ≡ ∨ ¬ ∨ ¬ Identity
    • ≡ ¬ ∨ ¬ ∨ Commutative
    • ≡ ¬ ∨ ∨ ¬ Open brackets and re-arrange for same operator (OR)

    11
    Predicate Logic

    • Consider the statement, “Every student of this class has visited Mexico”
    • How can we translate this statement into proposition(s)
    • Suppose, we have only three students in the class namely Ahmed, Ali and
    Yasir
    • We can make propositions like
    • = Ahmed has visited Mexico
    • = Ali has visited Mexico
    • = Yasir has visited Mexico
    • And the above statement would translate to
    • ∧ ∧
    • What if class has 50 students?
    • Do we make 50 propositions to translate a simple sentence?

    12
    Predicate Logic

    • Consider another sentence


    • “For every integer x, x>0”
    • Can we translate the above sentence into propositional logic?
    • Set of integers is infinite unlike number of students in the class
    • So, what do we need?
    • We need propositional functions that can return TRUE or FALSE given their
    input variables and we also need quantifiers
    • In a statement “Ali has visited Mexico”, Ali is subject, object or the
    entity and “has visited Mexico” is the predicate or the property about
    that entity

    13
    Predicate Logic

    • A predicate is modeled as propositional function P(.) from subjects to


    propositions
    • E.g: P(x) = x has visited Mexico
    • P(Ahmed) = Ahmed has visited Mexico
    • We use upper case letters P, Q, R… to represent predicates and lower-
    case letters to represent subjects or variables
    • Consequently, applying a predicate to a subject is a proposition but
    predicate itself is not a proposition
    • P(x) = x has visited Mexico (not a proposition)
    • P(Ali) = Ali has visited Mexico (This is a proposition)

    14
    Propositional Functions

    • The logic of predicate can be generalized to allow the propositional


    functions that take multiple inputs
    • E.g P(x,y,z) = x played cricket with y at z
    • P(Ali, Yasir, Iqbal Stadium) = Ali played cricket with Yasir at Iqbal
    Stadium
    • Let P(x): x > 5
    • P(4) means 4 > 5
    • P(5) means 5 > 5
    • P(9) means 9>5

    15
    Examples

    • Let C(x,y) : x is the capital of y


    • C(Islamabad, Pakistan): Islamabad is the capital of Pakistan
    • C(Lahore, Punjab): Lahore is the capital of Pakistan
    • C(Sakkhar, Sindh): Sakkher is the capital of Sindh
    • C(Washington DC, USA): Washington DC. is the capital of USA
    • C(London, Ireland): London is the capital of Ireland

    16
    What Next

    • But how can we represent statements like


    • Every student of this class has visited Mexico
    • Every integer has an additive inverse
    • Every integer has a multiplicative inverse
    • For every integer x, there exists and integer y such that x + y = x
    • We need quantifiers for this purpose

    17

    You might also like