Results 1 to 6 of 6

Math Help - Rules for quantifiers in Predicate Logic

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    Rules for quantifiers in Predicate Logic

    Hello everybody!

    There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc.

    First: how can I determine if the following implication is true or false?

    ( \forallx)[P(x) \rightarrowQ(x)] \rightarrow[ \forallP(x) \rightarrow \forallQ(x)]

    A book I have states that it is true, but it doesn't explain why. The exercise pretends the determination of its truth o falsity only using std logical identities like using the implication, the contrapositive, DeMorgan, etc. I also know that \forall only distributes over AND, and \exists only distributes over OR.

    Thank you and hope you help me to construct this proof.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by LightMath09 View Post
    Hello everybody!

    There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc.

    First: how can I determine if the following implication is true or false?

    ( \forallx)[P(x) \rightarrowQ(x)] \rightarrow[ \forallP(x) \rightarrow \forallQ(x)]

    A book I have states that it is true, but it doesn't explain why. The exercise pretends the determination of its truth o falsity only using std logical identities like using the implication, the contrapositive, DeMorgan, etc. I also know that \forall only distributes over AND, and \exists only distributes over OR.

    Thank you and hope you help me to construct this proof.
    It belongs to the axiom groups of FOL. See page 2 of the below link.
    http://www.london.ac.uk/fileadmin/do...logic_ba07.pdf

    It is a variant of "PRED-3" in the "quantifier axioms" section in the wiki.
    First-order logic - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2007
    From
    Moldova
    Posts
    15
    Quote Originally Posted by LightMath09 View Post
    ...There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc....
    I have posted a message on http://www.mathhelpforum.com/math-he...824-post2.html about so-called natural deduction, which does not use axioms.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by andrei View Post
    I have posted a message on http://www.mathhelpforum.com/math-he...824-post2.html about so-called natural deduction, which does not use axioms.
    I'll appreciate if you post a proof for the above using a natural deduction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2007
    From
    Moldova
    Posts
    15
    <br />
\begin{array}{rcl}<br />
\forall x(P(x)\to Q(x))&\vdash&\forall x(P(x)\to Q(x)).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xP(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x)\to Q(x)\text{ --- }\forall\text{-elimination, 1}.\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&Q(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xQ(x).\\<br />
\end{array}<br />

    (I cannot finish the proof because of latex restrictions.) Now by using twice \forall-introduction to the 6th deduction, we get above formula.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by andrei View Post
    <br />
\begin{array}{rcl}<br />
\forall x(P(x)\to Q(x))&\vdash&\forall x(P(x)\to Q(x)).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xP(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x)\to Q(x)\text{ --- }\forall\text{-elimination, 1}.\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&Q(x).\\<br />
\forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xQ(x).\\<br />
\end{array}<br />

    (I cannot finish the proof because of latex restrictions.) Now by using twice \forall-introduction to the 6th deduction, we get above formula.
    Thanks for your reply.

    I don't know much about the natural deduction, but it seems like the above proof is similar to that of the first order logic.

    If the above proof were the proof of the first order logic, I think the above proof involves a circular reasoning. It is because the last line uses a generalization theorem which in turn uses the above axiom.

    A Generalization theorem says that

    "If  \Gamma \vdash \phi and x does not occur free in any formula in \Gamma, then \Gamma \vdash \forall x\phi.

    The last line has the form,
    if \Gamma \vdash Q(x), then \Gamma \vdash \forall x Q(x).

    The above Q(x) has obtained by modus ponens from P(x) and P(x) \to Q(x). By the inductive hypothesis, we have  \Gamma \vdash \forall x P(x) and  \Gamma \vdash \forall x (P(x) \to Q(x)).

    We obtain \Gamma \vdash \forall x Q(x) by M.P

    1. \Gamma \vdash \forall x P(x)
    2. \Gamma \vdash \forall x P(x) \to \forall x Q(x) (implicitly invoking this line)

    Line 2 uses the above axiom. It is obtained by modus ponens of \forall x (P(x) \to Q(x)) and the axiom  \forall x (P(x) \to Q(x)) \to (\forall x P(x) \to \forall x Q(x)).

    Rather, the above axiom is obtained by proving
    \{\forall x(\alpha \to \beta), \forall x \alpha \} \models \forall x \beta.

    If any of you is interested in the above proof, I will post it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2011, 12:05 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 07:53 AM
  3. Predicate Logic with quantifiers
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: February 23rd 2010, 09:10 PM
  4. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 6th 2010, 06:23 AM
  5. More predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum