# Predicate logic problem

Printable View

• Nov 17th 2012, 01:41 AM
hmat
Predicate logic problem
∀x:X.¬(P^Q) http://upload.wikimedia.org/math/f/5...840a63edd5.png ¬∃x:X. ¬(¬P v ¬Q)

I want to prove that the left hand side entails (http://upload.wikimedia.org/math/f/5...840a63edd5.png) the right hand side using propositional and predicate logic. Thank you
• Nov 17th 2012, 03:47 AM
emakarov
Re: Predicate logic problem
Do P and Q depend on x? Also, see this sticky thread.
• Nov 17th 2012, 03:51 AM
hmat
Re: Predicate logic problem
p and q are of type x and i can use natural deduction and axioms
• Nov 17th 2012, 06:23 AM
emakarov
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?
• Nov 17th 2012, 06:42 AM
hmat
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?
• Nov 17th 2012, 09:54 AM
emakarov
Re: Predicate logic problem
Quote:

Originally Posted by hmat
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.