1

Which of the following predicate calculus statements is/are valid?

  1. $$\forall x, P(x)\lor \forall x,Q(x) \Rightarrow \forall x, (P(x)\lor Q(x))$$

  2. $$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \exists x, (P(x)\land Q(x)) $$

  3. $$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \forall x, P(x)\lor \forall x,Q(x)$$

  4. $$\exists x, (P(x)\lor Q(x)) \Rightarrow \forall x, P(x)\lor \exists x,Q(x)$$

What is the approach to solve these questions? I have learned that one way to solve these questions is to consider a $P(x)$ say "all numbers are odd" and $Q(x)$ say "all numbers are even", and then reason out with each option to see which one is true.
Being a CS freshman I have had a hard time understanding these,so can anyone explain to me in a straightforward fashion.
Also is there any mechanical(algebraic) way to solve these using propositional logic rules?

Mauro ALLEGRANZA
  • 94,169
bandit_king28
  • 403
  • Have you tried writing out the truth tables for the statements? Try that first. http://www.millersville.edu/~bikenaga/math-proof/truth-tables/truth-tables.html – Danny Lara Sep 24 '15 at 16:24
  • Can truth tables be drawn for statements involving quantifiers?Like I said i am a beginner,so how do I do that? – bandit_king28 Sep 24 '15 at 16:31
  • You have to "feel" which are false (like 2) and try to falsify them with a counterexample : for 2, the odd/even works : in plain English : it is true that "(there are odd numbers) and (there are even numbers)", but it is not true that "there are numbers which are (odd and even)". – Mauro ALLEGRANZA Sep 26 '15 at 08:44

1 Answers1

0

The approach to solving problems like these is to either formulate a proof to prove them true or to find a counter-example. Note that for falsehood, a counter-example is enough but for truthhood, an example says nothing.

The first statement is valid. To consider why, let's say P(x) stands for "x is red" and Q(x) for "x is yellow." $\forall xP(x) \lor \forall xQ(x)$ would translated to English state that "all objects are red or all objects are yellow." $\forall x(P(x) \lor Q(x))$ would state that "all objects are either red or yellow." It is obvious that the latter follows from the former.

A proof constructed using natural deduction would look like the following:

  1. $\forall xP(x) \lor \forall xQ(x)\quad\mathrm{Premise}$
  2. $a\quad\mathrm{Variable}$
  3. $\forall xP(x)\quad\mathrm{Assumption}$
  4. $P(a)\quad\forall x e3$
  5. $P(a) \lor Q(a)\quad\lor i_1 4$
  6. $\forall xQ(x)\quad\mathrm{Assumption}$
  7. $Q(a)\quad\forall x e6$
  8. $P(a) \lor Q(a)\quad\lor i_2 7$
  9. $P(a) \lor Q(a)\quad\lor e 1,3-5,6-8$
  10. $\forall x(P(x) \lor Q(x))\quad\forall x i 2-9$

Since we can transform the statement from the premise to the desired conclusion it is valid.

The second statement is invalid. Consider $P(x): x = 1$ and $Q(x): x = 2$ then $\exists P(x) \land \exists Q(x)$ is true because you can insert the values $P(1) \land Q(2)$. But $\exists x(P(x) \land Q(x))$ is false because no single $x$ can be both equal to 1 and 2 at the same time. Therefore the whole statement is invalid.

You can use the same definitions for $P(x)$ and $Q(x)$ to show that the third statement is invalid. If the domain are all the natural numbers, then it is so that $\exists P(x) \land \exists Q(x)$ is true, but neither $\forall x P(x)$ nor $\forall x Q(x)$ are true, therefore $\forall x P(x) \lor \forall x Q(x)$ is false and the statement is invalid.

For the fourth statement, set $P(x): x = 1$ and $Q(x): false$ so that it is false for every value of $x$. Then $\exists x(P(x) \lor Q(x))$ is true for $x = 1$ but $\forall x P(x) \lor \exists x Q(x)$ is not true for any value for $x$. It follows that the statement is invalid

Stand with Gaza
  • 617