reshown by
14,880 views
68 votes
68 votes

Which of the following first order formulae is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ is a first order formula with no free variable.

  1. $[\beta \rightarrow (\exists x, \alpha(x))] \rightarrow [\forall x, \beta \rightarrow \alpha(x)]$
  2. $[\exists x, \beta \rightarrow \alpha(x)] \rightarrow [\beta \rightarrow (\forall x, \alpha(x))]$
  3. $[(\exists x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
  4. $[(\forall x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
reshown by

9 Answers

Best answer
62 votes
62 votes
  1.  $[\beta \to (\exists x, \alpha(x))] \to [\forall x, \beta \to \alpha(x)]$
    LHS: If $\beta$ (some condition) is true, then there exists an $x$ for which $\alpha(x)$ is true.  
    RHS: For all $x$, if $\beta$ is true then $\alpha(x)$ is true. This is same as saying if $\beta$ is true then for all $x$,
    $\alpha(x)$ is true. $(\beta \implies \forall x, \alpha(x))$.
    So, $$\text{RHS} \implies \text {LHS} \text{ and } \text{LHS} \not\Longrightarrow  \text{RHS}.$$
  2. $[\exists x, \beta \to \alpha(x)] \to [\beta \to (\forall x, \alpha(x))]$
    LHS: There exists an $x$ such that if $\beta$ is true then $\alpha(x)$ is true. 
    RHS: If $\beta$ is true then for all $x, \alpha(x)$ is true.  
    So, $$\text{RHS} \implies \text {LHS} \text{ and }  \text{LHS} \not\Longrightarrow  \text{RHS}.$$
  3. $[(\exists x, \alpha(x)) \to \beta] \to [\forall x, \alpha(x) \to \beta]$
    LHS: If there is an $x$ such that $\alpha(x)$ is true, then $\beta$ is true. 
    RHS: For all $x$, if $\alpha(x)$ is true, then $\beta$ is true. 
    Here, both LHS and RHS are in fact same as $\beta$ is a formula which is independent of $x$. (if $\beta$ is true for one $x$, it is true for every $x$ and vice versa). 
    So, $$\text{RHS} \implies \text {LHS} \text{ and }  \text{LHS} \implies  \text{RHS}.$$
  4. $[(\forall x, \alpha(x)) \to \beta] \to [\forall x, \alpha(x) \to \beta]$
    LHS: If $\alpha(x)$ is true for every $x$, then $\beta$ is true.
    RHS: For every $x$, if $\alpha(x)$ is true then $\beta$ is true. 
    So, $$\text{RHS} \implies \text {LHS}  \text{ and }  \text{LHS} \not\Longrightarrow  \text{RHS}.$$

So, answer here is option C.

Any of options $A$, $B$, or $D$ could be valid if their implication is reversed. For option C, LHS, and RHS being equivalent, even if the implication is reversed (or changed to double implies) it remains valid. 

edited by
83 votes
83 votes

Usually operator , (comma) is used to replace braces in logical expressions

Let s consider the domain of x as {1,2}.

We will invalidate options one by one by invalidating the given conditional.

(A) $\{  \beta \rightarrow (\exists x , \alpha(x) ) \}  \rightarrow \{ \forall x , \beta \rightarrow \alpha(x) \}$

  The above expression can be re-written as :

  $\{  \beta \rightarrow (\exists x ( \alpha(x) ) ) \}  \rightarrow \{ \forall x ( \beta \rightarrow \alpha(x) ) \}$

Notice comma has been replaced by ()

Now we don't know what variable input does $\beta$ take so let us assume it  to be a simple propositional variable.

The L.H.S. can be re-written considering domain of x as {1,2} as

$\beta \rightarrow (\alpha_{1}+ \alpha_{2})$

This can be further written as : $\sim\beta + (\alpha_{1}+ \alpha_{2})$

R.H.S. can be re-written as : $(\beta \rightarrow \alpha_{1}) \land (\beta \rightarrow \alpha_{2})$

which evaluates as $\sim\beta + \alpha_{1}.\alpha_{2}$

Now we can clearly see that L.H.S $\rightarrow$ R.H.S. will be false if $\beta$ is true, $\alpha_{1}$ is true and $\alpha_{2}$ is false. Implication became invalid so we eliminate this option.

(B) $\{ \exists x , \beta \rightarrow \alpha(x) \} \rightarrow \{ \beta \rightarrow (\forall x, \alpha(x)) \}$

  after replacing comma it becomes

 $\{ \exists x ( \beta \rightarrow \alpha(x) ) \} \rightarrow \{ \beta \rightarrow (\forall x (\alpha(x))) \}$

Now re-writing L.H.S. and R.H.S. considering domain of x

L.H.S.  : $(\beta \rightarrow \alpha_{1})+(\beta \rightarrow \alpha_{2})$ and this evaluates to

$\sim\beta + \alpha_{1} + \alpha_{2}$

R.H.S. : $\beta \rightarrow (\alpha_{1}.\alpha_{2})$

and this evaluates to $\sim \beta + \alpha_{1}.\alpha_{2}$

This implication can also become false, following same reasoning from option (A).

(C) $\{ (\exists x , \alpha(x) ) \rightarrow \beta \} \rightarrow \{ \forall x, \alpha(x) \rightarrow \beta \}$

After replacing comma it becomes

$\{ (\exists x ( \alpha(x)) ) \rightarrow \beta \} \rightarrow \{ \forall x  (\alpha(x) \rightarrow \beta) \}$

L.H.S. : $(\alpha_{1} + \alpha_{2}) \rightarrow \beta$

which evaluates to

$\sim\alpha_{1}.\sim\alpha_{2} + \beta$

R.H.S. : $(\alpha_{1}\rightarrow\beta).(\alpha_{2}\rightarrow\beta)$

which evaluates to $\sim\alpha_{1}.\sim\alpha_{2} + \beta$

which is same as L.H.S. and hence this implication is valid.

(D) $\{ (\forall x, \alpha(x)) \rightarrow \beta \} \rightarrow \{ \forall x, \alpha(x) \rightarrow  \beta \}$

after replacing comma it becomes

$\{ (\forall x (\alpha(x))) \rightarrow \beta \} \rightarrow \{ \forall x (\alpha(x) \rightarrow  \beta )\}$

Considering domain of x to be {1,2} we re-write L.H.S. and R.H.S.

L.H.S. : $(\alpha_{1}.\alpha_{2})\rightarrow \beta$

and this evaluates to

$\sim \alpha_{1} + \sim \alpha_{2} + \beta$

R.H.S. : $(\alpha_{1}\rightarrow \beta)(\alpha_{2}\rightarrow\beta)$

Which evaluates to $\sim\alpha_{1}.\sim\alpha_{2}+\beta$

Now this implication can be set false, when $\sim\alpha_{1} $ is true , $\beta$ is false and $\sim\alpha_{2}$ is false.

Hence, this implication is invalid.

Answer (c)

38 votes
38 votes

[(∃x,α(x))→β]→[∀x,α(x)→β]

LHS => (∃x,α(x))→β ))

              (~∃x,α(x)) V β -> (∀x, ~α(x)) V β  )  -> (∀x, (~α(x) V β)) (I can change scope of  ∀x as B do not have x as  free variable in it.

(∀x, (α(x) -> β)) Proved !

C is correct

7 votes
7 votes

Additional details added to Arjun's answer.

 

Option A: $[β→(∃x,α(x))]→[∀x,β→α(x)]$

$LHS$: If $\beta$ then there exists an x, such that $\alpha(x)$ is true.
(If exam is held, then there exists a student, such that the student takes the exam)

$RHS$: For all x, if $\beta$ then $\alpha(x)$ is true.
(For all students, if exam is held, then they take the exam)

You can see the RHS is kinda like the superset of LHS. LHS clearly doesn't imply RHS, hence this option is incorrect.


Option B: $[∃x,β→α(x)]→[β→(∀x,α(x))]$

$LHS$: There exists an x such that if $\beta$, then $\alpha(x)$ is true.
(There exists a student, such that if exam is held, then the student takes the exam)

$RHS$: If $\beta$ then for all x, $\alpha(x)$ is true
(If exam is held, then for all students it is true that they take the exam)

For the same reason as above, this option is also incorrect.


Option C: $[(∃x,α(x))→β]→[∀x,α(x)→β]$

$LHS$: If there exists an x, such that $\alpha(x)$ is true, then  $\beta$.
(If there exists a student, such that it is true they take the exam, then the exam is held)

$RHS$: For all x, if $\alpha(x)$ is true the $\beta$.
(For all students, if they take the exam, then the exam is held)

Correct!


Option D: $[(∀x,α(x))→β]→[∀x,α(x)→β]$

$LHS$: If for all x, $\alpha(x)$ is true, then $\beta$.
(If for all students, they take the exam, then the exam is held.)

$RHS$: For all x, if $\alpha(x)$ is true, then $\beta$.
(For all students, if they take the exam then the exam is held)

The LHS does NOT imply RHS. In LHS if a student takes the exam it is held for him/her personally. But in RHS is all the students take the exam, only then it is considered held.

This option is incorrect!


 

 

Now, some background knowledge:

1

The comma i.e. "," operator after a quantifier means that the quantifier applies to the rest of the statement. Hence, in essence:

$[∀x,α(x)→β ]$ is equivalent to  $[∀x(α(x)→β)]$

This means you can replace the comma by parentheses.

Also, full stop/dot/period i.e. "." can be used in place of comma.

 

2

Notice the difference between the interpretations:

$[∀x,β→α(x)]$ => For all x... // Here only $\beta$ will be in range of "if"

$[(∀x,β)→α(x)]$ => If for all x... //Here the quantifier is also in the range of "if"

Answer:

Related questions

54 votes
54 votes
8 answers
3
Ishrat Jahan asked Oct 29, 2014
11,794 views
Host $X$ has IP address $192.168.1.97$ and is connected through two routers $R1$ and $R2$ to an­other host $Y$ with IP address $192.168.1.80$. Router $R1$ has IP address...