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: Find a counter example/predicate logic

  1. Aug 13, 2012 #1
    1. The problem statement, all variables and given/known data
    Find a counter example to show that the following is invalid:

    ∃xP(x) ∧ ∃x(P(x) → Q(x)) → ∃xQ(x)

    2. Relevant equations


    3. The attempt at a solution

    Well, I have tried to find something related to properties of numbers but found nothing... Then I tried to mess around with some nonsense sentences like:

    Let x be a creature, P(x) = "x is human being", Q(x) = "x is male".


    Some creature is human being - true
    For some creature if it is human being then it is male. - true
    Some creature it is a male - true

    (true and true) = true

    (true → true) = true

    So no counter example here. Any hint for me? I'm pretty much stuck..
  2. jcsd
  3. Aug 13, 2012 #2
    a counter example is where the premises are true and conclusion is false leading to a invalid argument form.

    Take this example

    For some person x1 and if some person x2 hits person x1 then x2 will hurt x1 only if x2 was sleeping.

    so your counterexample to this would be
    x2 hits person x1
    x2 does not hurt person x1
    x2 was sleeping

    statement is also invalid since you have an existential quantifier being used which is usually coupled with an and operator and not with a conditional operator since the premises can all be false yet yield a true conclusion.
  4. Aug 13, 2012 #3

    Thanks for reply. I do know what I'm supposed to do i.e found something that ∃xP(x) and ∃x(P(x) → Q(x)) are true but ∃xQ(x) is false. I think that I'm confuced about two points:

    1) Is x same in every premise and in conclusion?
    2) I think I interpret the premises incorrectly. So if there is x that has property P and the same x has the property that if it has property P then it has property Q. It seems so obvious that there then must be x that has property Q. But I know this kind of reasoning is wrong..

    Any more help for me?
  5. Aug 13, 2012 #4
    Hmm.. I came up with this:

    Let x be human being.
    P(x) = "x curses"
    Q(x) = "x insults"

    So I thought this as follows:
    There is a person who curses and the same person by cursing does insult someone. (These are the premises) i.e ∃xP(x) ∧ ∃x(P(x) → Q(x))

    So it doesn't follow that x insults because he/she hasn't intention to do so. He/She is just cursing.

    Does this disprove this:

    ∃xP(x) ∧ ∃x(P(x) → Q(x)) → ∃xQ(x) ?
  6. Aug 13, 2012 #5
    hmm I believe I was mistaken with my example. What is going on here is that there are three quantifiers with the same predicate variable x. But they are three separate predicate variables. Are you sure they use x throughout the formula? I think what your statement says is this "For some x1 and for some other x2, If x2... then x2... is sufficient for some other x3."
  7. Aug 13, 2012 #6


    User Avatar
    Science Advisor

    Why not do piece-by-piece:

    You need the antecedent to be true and the consequent must be false:

    so (sorry, I don't know how to Tex logic formulas )

    i) ~∃xQ(x) , or, for all x, ~Q(x)



    So, say you have S={a,b} as your universe, with:

    ~Q(a), ~Q(b)

    P(a) , ~P(b)


    i)From P(a) , you have ∃xP(x)

    ii) Since ~P(b) , then ~P(b)\/ Q(b) , so P(b)→Q(b), so ∃x(P(x)→Q(x) ) is satisfied by b

    iii) Clearly, ~∃xQ(x)

    I think this does it.

    The method is using a truth-tree.


    Sorry, it is difficult for me to tell if yours is a counterexample: I don't know what your universe of domain is

    let alone an assignment of the satisfaction values , i.e., which elements of

    your universe satisfy Q(x) or not, and which satisfy P(x) or not.
    Last edited: Aug 13, 2012
  8. Aug 13, 2012 #7
    Observe that implication holds even if its left-hand argument does not.
  9. Aug 13, 2012 #8
    Bacle is right...

    The point is, the x's DON'T have to be the same throughout the whole argument. The x's only have to be the same inside the 'scope' of the quantifier, and the scope is the scentence between cases right after the quantifier.

    So, like Bacle said, if you have a set S= {a,b} as your universe:

    It is possible that P(a) is true, but P(b), Q(a) and Q(b) are all false. Then both premises are true, but the consequent is false:

    P is true for a, so Ex(P(x)); (P(b) -> Q(b)) is true; but there is no x so Q(x) is true!
  10. Aug 13, 2012 #9
    Thank you for your replies!

    I think I got it now.

    So let x [itex]\in[/itex] {a,b}

    Let's assume that for a P(a) is true, and P(b) is not, and both Q(a) and Q(b) are false.


    1) a satisfies P therefore [itex]\exists[/itex]P(x)
    2) P(b) and Q(b) satisfy ∃x(P(x) → Q(x)) (because (false -> false ) = true

    So they are both true.

    3) But there is no x that satisfies ∃x(Q(x)) (Because for a and b Q(x) doesn't hold!)

    So there is the counterexample!

    Thank you very much Bacle2 (and others) !

    I think my mistake was that I was assuming that x must be the same troughout the argument.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook