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.

$\endgroup$
1
  • $\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, 2016 at 7:26

1 Answer 1

Reset to default
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.)

$\endgroup$
8
  • $\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, 2016 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, 2016 at 5:58
  • $\begingroup$ Ah okay thank you I understand $\endgroup$
    – Ovi
    Jul 11, 2016 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, 2016 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, 2016 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.