I'm revising counterexamples for my logic exam next term, and one of them has me absolutely stumped. I have to provide a counterexample to refute the following claim:

∀x∃yPxyy v ∃x¬∃y∃zPxyz is logically true

The solutions say that the answer is:

Domain of discourse: {0, 1}
|P| in the L2-structure: {<0, 0, 1>, <1, 0, 1>}

Now, I can see that to refute the claim you have to show that there is a structure where both sides of the disjunction are false, and I can see how the first half of it is made false, but the negation of the existential in the second half is confusing me a lot - I can't wrap my head around the concept of it. Why is <1, 0, 1> impossible for the second half to yield in this domain of discourse?

Any help would be greatly appreciated.


2 Answers 2


Consider Px01; it is clearly true for both cases : x=0 and x=1, i.e. for all elements of the domain.

Thus, ∀x∃y∃zPxyz is true. But this is equivalent to : ¬∃x¬∃y∃zPxyz which is the negation of the right disjunct.

  • Why are the two equivalent?
    – user18883
    Jan 8, 2016 at 22:02
  • @user18883 because : "all crows are black" means "does not exist a crow that is not black". Jan 8, 2016 at 22:05
  • Ahhh yes I see. So how would I deduce from just the original question that it was <1, 0, 1> specifically that would disprove the right disjunct?
    – user18883
    Jan 8, 2016 at 22:17
  • Ah, no, don't worry, I get it. Thank you for your help!
    – user18883
    Jan 8, 2016 at 22:31

The second half is saying that for some object x, the relation P is never instantiated with x as the first term (there are no y and z such that Pxyz). To refute the claim just make sure that P applies to all possible objects as first terms. Here P is instantiated for both 0 and 1 as first terms so the model indeed refutes the claim.

You can view the negation as applying to both existentials combined (it's not true that there exists a y and a z such that...).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .