1

a) ∀x F(x) ∧ ∀x G(x) ≡ ∀x (F(x) ∧ G(x))

b) ∀x F(x) ∨ ∀x G(x) ≡ ∀x (F(x) ∨ G(x))

c) ∃x F(x) ∧ ∃x G(x) ≡ ∃x (F(x) ∧ G(x))

d) ∃x F(x) ∨ ∃x G(x) ≡ ∃x (F(x) ∨ G(x))

This is Discrete Mathematics. the instructions are "Which of the following statements is right, and which is wrong". I am not sure, but I assume they are asking to show if it is equivalent? Like for example, the first one I assume is true because I would distribute the ∀x to the F(x) and G(x). Thank you for your help.

alex
  • 13

1 Answers1

0

a) and d) are true, b) and c) are not.

a) Left side says that all x are in F and all x are in G, so as long as there is one x that is not in F or not in G the left side is false. The right side says that all x are both in F and G, so as long as there is one x that is not in F or G it is false. As you can see both sides will be true only if every x is in both F and G, and are thus equivalent (I would say this is pretty obvious if you pronounce the expression with words instead of formula)

b) Left side says that either all x are in F or all x are in G, thus if there is one x that is only in G and a different x which is only in F, left side is false. (the first x makes the assertion about all x being in F false, and the second x makes the assertion about all x being in G false, thus the whole left side is false). The right side is still true though, it just says that all x are either in F or G, so both aforementioned x satisfy it (one being only in G, other being only in F, thus each of them being in either F or G). Thus left and right sides are not equivalent, since it is possible that one is true and other is false for same choice of x.

I'll leave c) and d) to you, I can edit the post tomorrow to cover them as well if you wish.

Also, I am sorry if F(x) doesn't mean 'x is in F', but I'm just used to saying it like that in expressions like these.

DoctorJAM
  • 108
  • Thank you very much. That was a really good explanation and it really helped in my understanding of question "b". You're awesome. – alex Sep 18 '14 at 04:49
  • 1
    @alex - we can add a very useful "mnemonic" rule : $\forall$ distribute over $\land$ but not (in general) over $\lor$, while $\exists$ distribute over $\lor$ but not (in general) over $\land$. This is due to the fact that $\exists$ "works like" an infinite disjunction and $\forall$ like an infinite conjunction. If we consider a finite universe with only $n$ objects $a_1,\dots, a_n$, to say $\forall xP(x)$ is the same as : $P(a_1) \land \ldots \land P(a_n)$, and to say $\exists xP(x)$ is the same as $P(a_1) \lor \ldots \lor P(a_n)$. – Mauro ALLEGRANZA Sep 18 '14 at 07:26