Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Tutorial #3 Sample Solutions

    Uploaded by

    kuroshitsuji
    This document provides sample solutions to a tutorial on logic equivalences and interpretations. 1) It derives equivalences between logical statements, showing the steps, or provides counterexamples when equivalences do not hold. 2) It gives interpretations of logical statements that make them true or false by defining a domain and predicate meanings.

    Copyright:

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

    Tutorial #3 Sample Solutions

    Uploaded by

    kuroshitsuji
    15 views2 pages
    This document provides sample solutions to a tutorial on logic equivalences and interpretations. 1) It derives equivalences between logical statements, showing the steps, or provides counterexamples when equivalences do not hold. 2) It gives interpretations of logical statements that make them true or false by defining a domain and predicate meanings.

    Original Title

    Tutorial #3 sample solutions

    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 provides sample solutions to a tutorial on logic equivalences and interpretations. 1) It derives equivalences between logical statements, showing the steps, or provides counterexamples when equivalences do not hold. 2) It gives interpretations of logical statements that make them true or false by defining a domain and predicate meanings.

    Copyright:

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

    Tutorial #3 Sample Solutions

    Uploaded by

    kuroshitsuji
    This document provides sample solutions to a tutorial on logic equivalences and interpretations. 1) It derives equivalences between logical statements, showing the steps, or provides counterexamples when equivalences do not hold. 2) It gives interpretations of logical statements that make them true or false by defining a domain and predicate meanings.

    Copyright:

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

    CSC 165 H1S Tutorial # 3 — Sample Solutions Summer 2014

    1. For each equivalence below, either provide a derivation from one side of the equivalence to the other (justify
    each step of your derivation with a brief explanation — for example, by naming one of the equivalences (see
    over for a list), or show that the equivalence does not hold (warning: you cannot use a derivation to show
    non-equivalence — instead, think carefully about what an equivalence means, and how you can disprove it).

    (a) (P ⇒ R) ∧ (Q ⇒ R) ⇐⇒ (P ∨ Q) ⇒ R
    Sample Solution:

    (P ⇒ R) ∧ (Q ⇒ R) ⇐⇒ (¬P ∨ R) ∧ (¬Q ∨ R) (implication)


    ⇐⇒ (¬P ∧ ¬Q) ∨ R (distributivity)
    ⇐⇒ ¬(P ∨ Q) ∨ R (DeMorgan’s law)
    ⇐⇒ (P ∨ Q) ⇒ R (implication)

    (b) P ⇒ (Q ⇒ R) ⇐⇒ (P ⇒ Q) ⇒ R
    Sample Solution:
    The equivalence does not always hold:
    Let P = False, Q = True, R = False.
    Then [P ⇒ (Q ⇒ R)] = [False ⇒ (True ⇒ False)] = [False ⇒ False] = True and
    [(P ⇒ Q) ⇒ R] = [(False ⇒ True) ⇒ False] = [True ⇒ False] = False.

    (c) P ⇒ (Q ⇒ R) ⇐⇒ (P ⇒ Q) ⇒ (P ⇒ R)
    Sample Solution:

    (P ⇒ Q) ⇒ (P ⇒ R) ⇐⇒ ¬(P ⇒ Q) ∨ (¬P ∨ R) (implication)


    ⇐⇒ (P ∧ ¬Q) ∨ (¬P ∨ R) (implication negation)
    
    ⇐⇒ (P ∨ ¬P ) ∧ (¬Q ∨ ¬P ) ∨ R (distributivity)
    ⇐⇒ (¬P ∨ ¬Q) ∨ R (identity and commutativity)
    ⇐⇒ ¬P ∨ (¬Q ∨ R) (associativity)
    ⇐⇒ P ⇒ (Q ⇒ R) (implication)

    Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 2


    CSC 165 H1S Tutorial # 3 — Sample Solutions Summer 2014

    Standard Equivalences (where P , Q, P (x), Q(x), etc. are arbitrary sentences)

    • Commutativity P ∨ P ⇐⇒ P ∀x, P (x) ⇐⇒ ∀y, P (y)


    P ∧ Q ⇐⇒ Q ∧ P • Double Negation ∃x, P (x) ⇐⇒ ∃y, P (y)
    P ∨ Q ⇐⇒ Q ∨ P ¬¬P ⇐⇒ P • Quantifier Negation
    P ⇔ Q ⇐⇒ Q ⇔ P • DeMorgan’s Laws ¬∀x, P (x) ⇐⇒ ∃x, ¬P (x)
    • Associativity ¬(P ∧ Q) ⇐⇒ ¬P ∨ ¬Q ¬∃x, P (x) ⇐⇒ ∀x, ¬P (x)
    P ∧ (Q ∧ R) ⇐⇒ (P ∧ Q) ∧ R ¬(P ∨ Q) ⇐⇒ ¬P ∧ ¬Q • Quantifier Commutativity
    P ∨ (Q ∨ R) ⇐⇒ (P ∨ Q) ∨ R • Distributivity ∀x, ∀y, S(x, y) ⇐⇒ ∀y, ∀x, S(x, y)
    • Identity P ∧ (Q ∨ R) ⇐⇒ (P ∧ Q) ∨ (P ∧ R) ∃x, ∃y, S(x, y) ⇐⇒ ∃y, ∃x, S(x, y)
    P ∧ (Q ∨ ¬Q) ⇐⇒ P P ∨ (Q ∧ R) ⇐⇒ (P ∨ Q) ∧ (P ∨ R) • Quantifier Distributivity (where S
    P ∨ (Q ∧ ¬Q) ⇐⇒ P • Implication does not contain variable x)
    • Absorption P ⇒ Q ⇐⇒ ¬P ∨ Q S ∧ ∀x, Q(x) ⇐⇒ ∀x, S ∧ Q(x)
    P ∧ (Q ∧ ¬Q) ⇐⇒ Q ∧ ¬Q • Biconditional S ∨ ∀x, Q(x) ⇐⇒ ∀x, S ∨ Q(x)
    P ∨ (Q ∨ ¬Q) ⇐⇒ Q ∨ ¬Q P ⇔ Q ⇐⇒ (P ⇒ Q) ∧ (Q ⇒ P ) S ∧ ∃x, Q(x) ⇐⇒ ∃x, S ∧ Q(x)
    • Idempotency • Renaming (where P (x) does not S ∨ ∃x, Q(x) ⇐⇒ ∃x, S ∨ Q(x)
    P ∧ P ⇐⇒ P contain variable y)

    2. An “interpretation” for a logical statement consists of a domain D (any non-empty set of elements) and a
    meaning for each predicate symbol. For example, D = {1, 2} and P (x): “x > 0” is an interpretation for the
    statement ∀x ∈ D, P (x) (in this case, one that happens to make the statement True). For each statement
    below, provide one interpretation under which the statement is true and another interpretation under which
    the statement is false — if either case is not possible, explain why clearly and concisely.
    (a) ∀x ∈ D, ∀y ∈ D, P (x, y)
    Sample Solution: Let D = {1, 2} and P (x, y): “x < y.” Then, ∀x ∈ D, ∀y ∈ D, P (x, y) is
    False because P (2, 1) is False.
    Let D = {1} and P (x, y): “x = y.” Then ∀x ∈ D, ∀y ∈ D, P (x, y) is True because P (1, 1) is
    True.
    (b) (P ∧ Q) ⇒ (P ∨ Q)
    Sample Solution: Let P = False and Q = True. Then

    (P ∧ Q) ⇒ (P ∨ Q) = (False ∧ True) ⇒ (False ∨ True)


    = False ⇒ True
    = True

    It is impossible to make the statement False because this would require P ∧ Q to be True
    (meaning both P and Q are True) while at the same time P ∨ Q is False (meaning both P and
    Q are False).
    (c) (∀x ∈ D, ∃y ∈ D, P (x, y)) ⇒ (∃y ∈ D, ∀x ∈ D, P (x, y))
    Sample Solution: Let D = {1, 2} and P (x, y): “x is an integer multiple of y.” Then,
    ∀x ∈ D, ∃y ∈ D, P (x, y) is True because P (1, 1) and P (2, 2) are both True (i.e., we can always
    pick y = x for every x). Moreover, ∃y ∈ D, ∀x ∈ D, P (x, y) is True because P (1, 1) and P (2, 1)
    are both True (i.e., y = 1 works for every x). Hence, the entire statement is True.
    Let D = {1, 2} and P (x, y): “x 6= y.” Then, ∀x ∈ D, ∃y ∈ D, P (x, y) is True because
    P (1, 2) and P (2, 1) are both True (i.e., we can always pick y to be different from x). However,
    ∃y ∈ D, ∀x ∈ D, P (x, y) is False because there is no value of y ∈ D that is different from every
    other element of D. Hence, the entire statement is False.

    Dept. of Computer Science, University of Toronto, St. George Campus Page 2 of 2

    You might also like