1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Predicate logic - true or false formulae

  1. Dec 28, 2013 #1
    Hello everyone, I can't seem to understand how to do this question.

    Determine whether the formula F: ∃x∀y(P(x) → x = y) is true or false under each of the following interpretations over the domain D = {a, b}.

    (i) both P(a) and P(b) are true;

    (ii) both P(a) and P(b) are false;

    (iii) P(a) is true and P(b) is false.

    Before I post my solution, please let me know if you think I'm not understanding the question. I think we are asked to write out all the interpretations for the 3 different cases and determine whether they make the formula true or false. If there are no false cases then the formula is true under the given interpretations - otherwise false. Here is my solution:

    i) we can immediately see two cases which would make the formula false so it is false under interpretation i) :
    P(a) → a=b and P(b) → b=a

    ii) No need to check here because the premises would be false so the formula is true in every case.

    iii) there are four cases, one of which is false so F is false under interpretation iii) :

    1) P(a) → a=a [true] 2) P(a)→ a=b [false] 3) P(b)→ b=b [true] 4) P(b)→ b=a [true]

    So my final answers would be i) false ii) true iii) false

    My answers for i) and ii) are matching with the answers sheet but our lecturer has provided me with the following solution for iii): "Then the formula is true. Indeed, both P(b) → b = a and P(b) → b = b are true."

    Can somebody please explain to me where I am wrong?
  2. jcsd
  3. Dec 28, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your error is in understanding the significance of the ∃x element. It means that you only have to find some x for which ∀y(P(x) → x = y) is true for the whole to be true.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted