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

Thread: 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,577
    Thanks
    790

    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; Nov 17th 2012 at 03:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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,577
    Thanks
    790

    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 $\displaystyle \exists x\,\neg(\neg Px\lor\neg Qx)$. We need to derive a contradiction. Apply existential elimination to get an x and $\displaystyle \neg(\neg Px\lor\neg Qx)$. Use universal elimination with that x on $\displaystyle \forall x\,\neg(Px\land Qx)$ to get $\displaystyle \neg(Px\land Qx)$. We are going to make two assumptions and show that they are contradictory.

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

    Note that I have not used the law of excluded middle $\displaystyle A\lor\neg A$. Using it, it may be possible to make the derivation a little clearer. Basically, once you have $\displaystyle \neg(\neg Px\lor\neg Qx)$ and $\displaystyle \neg(Px\land Qx)$, you consider (using disjunction elimination) four cases where either $\displaystyle Px$ or $\displaystyle \neg Px$ and either $\displaystyle Qx$ or $\displaystyle \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: Oct 4th 2011, 06:34 AM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Mar 23rd 2011, 12:05 PM
  3. set theory / predicate logic math language problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2010, 12:21 AM
  4. Predicate Logic HELP.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Feb 16th 2010, 08:54 AM
  5. Predicate logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 10th 2010, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum