0
$\begingroup$

This is a question from the Discrete Mathematics question from Kenneth Rosen book.

I didn't understand the question and thus I am confused how to begin with question. Below is the question from the book.

Establish these logical equivalences, where x does not occur as free variable in A. Assume that the domain is nonempty.

a) ( ∀x P(x)) ∨ A) ≡ ∀x (P(x) ∨ A)

Also what does "x does not occur as free variable in A" mean. Thank You.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: To get a better understanding of what is going on try to to show this equivalence for the following 2 particular cases: the case where $A$ is $\forall x R(x,y)$ and the case $\exists x R(x,y)$. In other words, start checking that $(\forall x P(x)) \lor ( \forall x R(x,y) ) \equiv \forall x (P(x) \lor \forall x R(x,y) )$ and that $(\forall x P(x)) \lor ( \exists x R(x,y) ) \equiv \forall x (P(x) \lor \exists x R(x,y) )$ $\endgroup$ – boumol Jul 13 '16 at 7:26
1
$\begingroup$

The question is asking you to use the rules of deduction you have been given to show that the two sides of the equivalence are exactly the same as each other - so in this case, show that "((for all x: P(x) is true) or (A is true))" is logically equivalent to "for all x: (P(x) is true or A is true)".

"x does not occur as a free variable in A" means that you can assume that A is not affected by the value of x, because if you were to write A out as a statement you wouldn't find x appearing as something whose value can be varied. (In P(x), x is a free variable, but in $\forall x P(x)$, x is "bound" by the $\forall$ qualifier.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I understand that your interpretation of "x does not occur as a free variable in x" makes sense; if x occured in A at all, the question would be unsolvable unless we were given A. However, the wording seems a bit off to me. "x does not occur as a free varibable" still leaves open the possibility that "x occurs as a bound variable", doesn't it? Shouldn't they say "x does not occur as a bound variable" instead? $\endgroup$ – Ovi Jul 11 '16 at 5:56
  • $\begingroup$ If x appears as a bound variable in A, then in the overall evaluation of A the x essentially "disappears", or at least it doesn't actually matter that it is x. Whereas if it's a free variable, it's quite troublesome that it also appears as a bound variable in the component involving P. $\endgroup$ – ConMan Jul 11 '16 at 5:58
  • $\begingroup$ Ah okay thank you I understand $\endgroup$ – Ovi Jul 11 '16 at 6:00
  • $\begingroup$ Can you clarify the difference between bound variable and free variable. As per my knowledge free variable is something that is not initialized or is in the scope of quantifiers. $\endgroup$ – Navneet Srivastava Jul 11 '16 at 6:10
  • $\begingroup$ That's exactly it. A free variable is one whose value is "free" to vary, and hence the truth of the overall proposition may depend on the value of the variable. A bound variable is one that is set to a particular value or is otherwise quantified, meaning that it's not able to vary, and hence its value is "bound". $\endgroup$ – ConMan Jul 11 '16 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.