Scribd Logo
Upload

Welcome to Scribd!

  • 152 views

    The Foundations: Logic and Proofs Kenneth H. Rosen 7 Edition

    Uploaded by

    Mahir Sohan
    This document discusses propositional logic concepts including tautologies, contradictions, contingencies, logical equivalences, and propositional satisfiability. It provides examples and explanations of each concept. For logical equivalences, it lists important rules and provides examples of constructing new logical equivalences by applying multiple rules. For propositional satisfiability, it explains how to determine if a proposition is satisfiable or unsatisfiable using truth tables. Exercises are provided to have the reader practice these concepts.

    Copyright:

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

    The Foundations: Logic and Proofs Kenneth H. Rosen 7 Edition

    Uploaded by

    Mahir Sohan
    152 views17 pages
    This document discusses propositional logic concepts including tautologies, contradictions, contingencies, logical equivalences, and propositional satisfiability. It provides examples and explanations of each concept. For logical equivalences, it lists important rules and provides examples of constructing new logical equivalences by applying multiple rules. For propositional satisfiability, it explains how to determine if a proposition is satisfiable or unsatisfiable using truth tables. Exercises are provided to have the reader practice these concepts.

    Original Title

    Lecture 2.1 Pt2

    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 concepts including tautologies, contradictions, contingencies, logical equivalences, and propositional satisfiability. It provides examples and explanations of each concept. For logical equivalences, it lists important rules and provides examples of constructing new logical equivalences by applying multiple rules. For propositional satisfiability, it explains how to determine if a proposition is satisfiable or unsatisfiable using truth tables. Exercises are provided to have the reader practice these concepts.

    Copyright:

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

    The Foundations: Logic and Proofs Kenneth H. Rosen 7 Edition

    Uploaded by

    Mahir Sohan
    This document discusses propositional logic concepts including tautologies, contradictions, contingencies, logical equivalences, and propositional satisfiability. It provides examples and explanations of each concept. For logical equivalences, it lists important rules and provides examples of constructing new logical equivalences by applying multiple rules. For propositional satisfiability, it explains how to determine if a proposition is satisfiable or unsatisfiable using truth tables. Exercises are provided to have the reader practice these concepts.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 17

    Chapter 1

    The Foundations : Logic and Proofs


    Kenneth H. Rosen 7th edition
    Section 1.3 : Propositional Equivalences
    Tautology, Contradiction & Contingency
     Tautology:
     A compound proposition that is always true, no matter what
    the truth values of the propositional variables that occur in
    it.
     Contradiction:
     A compound proposition that is always false is called a
    contradiction.
     Contingency:
     A compound proposition that is neither a tautology nor a
    contradiction is called a contingency.
    Tautology, Contradiction &
    Contingency(Contd.)
    Example 1:
     Tautology:
     Consider the truth table of ∨ ¬ . Because ∨ ¬ is always
    true, it is a tautology.
     Contradiction:
     Consider the truth table of ∧ ¬ . Because ∧ ¬ is always
    false, it is a contradiction.

    ¬ ∨¬ ∧¬
    F T T F
    T F T F
    Logical Equivalences
     Compound propositions that have the same truth values
    in all possible cases are called logically equivalent.
     The compound propositions and are called logically
    equivalent if ↔ is a tautology.
     The notation ≡ denotes that and are logically
    equivalent.
    Logical Equivalences(Contd.)
     Example 1:
     Show that ¬( ∨ ) and ¬ ∧ ¬ are logically
    equivalent.
     Solution:
     We can verify from the following truth table that, ¬( ∨
    )≡¬ ∧¬ .
    ¬ ¬ ( ∨ ) ¬( ∨ ) ¬ ∧¬
    F F T T F T T
    F T T F T F F
    T F F T T F F
    T T F F T F F
    Logical Equivalences(Contd.)
     Exercises:
     Show that → and ¬ ∨ are logically equivalent.
     Show that ∨ ( ∧ ) and ( ∨ ) ∧ ( ∨ ) are
    logically equivalent.
    Logical Equivalence Rules
     Important rules

    ∧ ≡ Identity Laws ( ∨ ) ∨ ≡ ∨ ( ∨ ) Associative


    ∨ ≡ ( ∧ ) ∧ ≡ ∧ ( ∧ ) Laws

    ∨ ≡ Domination ∨ ∧ ≡ ∨ ∧ ∨ Distributive
    ∧ ≡ Laws ∧ ( ∨ ) ≡ ( ∧ ) ∨ ( ∧ ) Laws
    ∧ ≡ Idempotent ¬( ∧ ) ≡¬ ∨¬ De Morgan’s
    ∨ ≡ Laws ¬( ∨ ) ≡¬ ∧¬ Laws
    ¬(¬ ) ≡ Double ∨ ( ∧ ) ≡ Absorption
    Negation Law ∧ ( ∨ ) ≡ Laws
    ∨ ≡ ∨ Commutative ∨¬ ≡ Negation laws
    ∧ ≡ ∧ Laws ∧¬ ≡
    Logical Equivalence Rules(Contd.)
     Important Rules Regarding Conditionals

    • → ≡¬ ∨ • ↔ ≡ ( → ) ∧ ( → )
    • → ≡¬ →¬ • ↔ ≡¬ ↔¬
    • ∨ ≡¬ → • ↔ ≡ ( ∧ ) ∨ (¬ ∧ ¬ )
    • ∧ ≡ ¬( → ¬ ) • ¬( ↔ ) ≡ ↔¬
    • ¬( → ) ≡ ∧¬
    • ( → ) ∧ ( → ) ≡ → ( ∧ )
    • ( → ) ∧ ( → ) ≡ ( ∨ ) →
    • ( → ) ∨ ( → ) ≡ → ( ∨ )
    • ( → ) ∨ ( → ) ≡ ( ∧ ) →
    Constructing New Logical Equivalences
     Example 1:
     Show that ¬( → ) and ∧ ¬ are logically equivalent.

     Solution:
    ¬ → ≡ ¬(¬ ∨ ) by Rule
    ≡ ¬(¬ ) ∧ ¬ by the second De Morgan Law
    ≡ ∧¬ by the Double Negation Law
    Constructing New Logical
    Equivalences(Contd.)
     Example 2:
     Show that ¬( ∨ (¬ ∧ )) and ¬ ∧ ¬ are logically
    equivalent by developing a series of logical equivalences.

     Solution:
    ¬( ∨ (¬ ∧ )) ≡ ¬ ∧ ¬(¬ ∧ ) by the second De Morgan law
    ≡ ¬ ∧ [¬(¬ ) ∨ ¬ ] by the first De Morgan law
    ≡ ¬ ∧ ( ∨¬ ) by the double negation law
    ≡ (¬ ∧ ) ∨ (¬ ∧¬ ) by the second distributive law
    ≡ ∨ (¬ ∧¬ ) because ¬ ∧ ≡
    ≡ (¬ ∧¬ ) ∨ by the commutative law of disjunction
    ≡ ¬ ∧¬ by the identity law for
    Constructing New Logical
    Equivalences(Contd.)
     Example 3:
     Show that ( ∧ ) → ( ∨ ) is a tautology.

     Solution:
    ( ∧ ) → ( ∨ ) ≡ ¬( ∧ ) ∨ ( ∨ ) by law of conditional
    ≡ (¬ ∨¬ ) ∨ ( ∨ ) by the first De Morgan law
    ≡ (¬ ∨ ) ∨ (¬ ∨ ) by the associative and commutative
    laws of disjunction (or simply
    rearranging the terms)
    ≡ ∨ by negation law and the commutative
    law of disjunction
    ≡ by the domination law
    Propositional Satisfiability
     A compound proposition is if there is an
    assignment of truth values to its variables that makes it
    .
     When no such assignments exists, that is, when the
    compound proposition is for all assignments of
    truth values to its variables, the compound proposition is
    .
     To show that a compound proposition is ,
    we need to show that every assignment of truth values to
    its variables makes it .
     We can logically reason with the values of each variable.
    But in our case, we will use the truth table.
    Propositional Satisfiability(Contd.)
     Example 1:
     Determine the satisfiability of the compound proposition
     ∨¬ ∧ ∨¬ ∧ ∨¬
    Propositional Satisfiability(Contd.)
     Solution:
     Let = ∨¬ ∧ ∨¬ ∧ ∨¬

    ¬ ¬ ¬ ∨¬ ∨¬ ∨¬
    F F F T T T T T T T
    F F T T T F T F T F
    F T F T F T F T T F
    F T T T F F F T T F
    T F F F T T T T F F
    T F T F T F T F T F
    T T F F F T T T F F
    T T T F F F T T T T
    Propositional Satisfiability(Contd.)
    Since there is at least one combination of input for the variables , ,
    of the compound proposition, which gives a true value for the
    compound proposition , we can say that the is satisfiable.
    Propositional Satisfiability(Contd.)
     Exercises:
     Determine the satisfiability of each of the compound
    propositions

     ( ∨ ∨ ) ∧ (¬ ∨ ¬ ∨ ¬ )
     ( ∨¬ ) ∧ ( ∨¬ ) ∧ ( ∨¬ ) ∧( ∨ ∨ ) ∧ (¬ ∨¬ ∨
    ¬ )
    THE END

    You might also like