Results 1 to 6 of 6
Like Tree3Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Predicate logic problem

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    NY
    Posts
    3

    Predicate logic problem

    ∀x:X.(P^Q) ∃x:X. (P v Q)

    I want to prove that the left hand side entails () the right hand side using propositional and predicate logic. Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Predicate logic problem

    Do P and Q depend on x? Also, see this sticky thread.
    Thanks from hmat
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    NY
    Posts
    3

    Re: Predicate logic problem

    p and q are of type x and i can use natural deduction and axioms
    Last edited by hmat; November 17th 2012 at 03:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Predicate logic problem

    Hmm, I am not sure I understand "p and q are of type x." In terms of types, I would say, "P and Q are of type X -> Prop" where Prop is the type of propositions. But I understand that P and Q are unary predicates that accept arguments of type X.

    A derivation depends on the axioms you have. For example, if you have an axiom (∃x. Ax) <-> ∀x. Ax, then you can immediately use it to derive ∃x:X. (Px ^ Qx). Similarly, if you have an axiom A ^ B <-> (A v B), then you can derive ∃x:X. (Px v Qx). Otherwise, it is significantly more tricky.

    Also, do you use Fitch-style natural deduction (also called flag notation) or tree-like natural deduction?
    Thanks from hmat
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2012
    From
    NY
    Posts
    3

    Re: Predicate logic problem

    i can use the following axioms:

    P v P
    P ^ P (Proof by contradiction)

    So what you re saying is that i can use double negation to remove negation, correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Predicate logic problem

    Quote Originally Posted by hmat View Post
    P v P
    P ^ P (Proof by contradiction)
    P ^ P is not an axiom since it is contradictory.

    I'll describe the derivation in words. Assume \exists x\,\neg(\neg Px\lor\neg Qx). We need to derive a contradiction. Apply existential elimination to get an x and \neg(\neg Px\lor\neg Qx). Use universal elimination with that x on \forall x\,\neg(Px\land Qx) to get \neg(Px\land Qx). We are going to make two assumptions and show that they are contradictory.

    Assume Px and assume Qx. Then Px\land Qx, which contradicts \neg(Px\land Qx). Therefore, we close Px and derive \neg Px. Using disjunction introduction, this implies \neg Px\lor \neg Qx, which contradicts \neg(\neg Px\lor\neg Qx). Therefore, we close Qx and derive \neg Qx. As before, this implies \neg Px\lor \neg Qx, which contradicts \neg(\neg Px\lor\neg Qx). Thus we closed both Px and Qx and derived a contradiction.

    Note that I have not used the law of excluded middle A\lor\neg A. Using it, it may be possible to make the derivation a little clearer. Basically, once you have \neg(\neg Px\lor\neg Qx) and \neg(Px\land Qx), you consider (using disjunction elimination) four cases where either Px or \neg Px and either Qx or \neg Qx hold. In each case, it is possible to derive a contradiction using the two premises above. This is similar to constructing a truth table.
    Thanks from hmat
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: October 4th 2011, 06:34 AM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2011, 12:05 PM
  3. set theory / predicate logic math language problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2010, 12:21 AM
  4. Predicate Logic HELP.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 16th 2010, 08:54 AM
  5. Predicate logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2010, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum