in Mathematical Logic edited by
16,570 views
59 votes
59 votes

Which of the following is a valid first order formula? (Here \(\alpha\) and \(\beta\) are first order formulae with $x$ as their only free variable)

  1. $((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$
  2. $(∀x)[α] ⇒ (∃x)[α ∧ β]$
  3. $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$
  4. $(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$
in Mathematical Logic edited by
16.6k views

3 Comments

Brackets are not matching in (D) . pls fix
1
1
i  got the answer. but the thing is that how to come up with such example within 3 minutes in Exam ?? Is there any other method to check it ? If i am not able to come with some example ????
0
0
for 3)

in RHS Assume α is not true for all x, then in LHS first part become false making 2nd part of the RHS as true hence overall LHS become true

T->F

hence false

kindly check this??
1
1

7 Answers

68 votes
68 votes
Best answer

(D) is the answer.

  1. Let $X = \{3,6,9,8\}$. Let $α$ denote multiple of $3$ and $β$ denote multiple of $4. (∀x)[α]$ becomes false as $8$ is not a multiple of $3$, and so $(∀x)[α] ⇒ (∀x)[β]$ becomes TRUE. Now, this won't imply $(∀x)[α ⇒ β]$ as multiple of $3$ doesn't imply multiple of $4$ for $3, 6$ or $9$.
     
  2. Let $X = \{3,6,9\}$. Let $α$ denote multiple of $3$ and $β$ denote multiple of $4$. Now LHS is TRUE but RHS is false as none of the $x$ in $X$, is a multiple of $4$.
     
  3. Let $X = \{3,6,9,7\}$.  Let $α$ denote multiple of $3$ and $β$ denote multiple of $4$. Now  $(∀x)[α ∨ β]$ becomes false and hence LHS $= ((∀x)[α ∨ β] ⇒ (∃x)[α])$ becomes true. But RHS is false as $7$ is not a multiple of $3$.
     
  4. This is valid. LHS is saying that if $α$ is holding for any $x$, then $β$ also holds for that $x$. RHS is saying if $α$ is holding for all $x$, then $β$ also holds for all $x$. Clearly LHS $\implies$ RHS (but RHS does not imply LHS).
    For example, let $X = \{4, 8, 12\}, α$ denote multiple of $2$ and $β$ denote multiple of $4$. LHS $= (∀x)[α ⇒ β],$ is TRUE. RHS is also true. If we add '$3$' to $X$, then LHS is true, first part of RHS becomes false and thus RHS also becomes TRUE. There is no way we can make LHS true and RHS false here. But if we add $2$ and $3$ to $X$, RHS will be true and LHS will be false. So, we can't say RHS implies LHS.
edited by
by

4 Comments

Option B and C can be eliminated easily.But doubt comes in A and D..

For B  $\forall x( \alpha)\rightarrow \exists x(\alpha\wedge\beta)$

it is not valid because if $\alpha$  is true for all values of x and $\beta$  is false for all values of x then rhs is always false and LHS is true. So $TRUE \rightarrow FALSE$  is false. So option B is invalid.. Similarly we can prove that C is also invalid..
2
2
what does x as their onlu free variable mean here?
0
0
it means that only x can take any random value in the domain .
0
0
81 votes
81 votes

@Arjun sir already provided the best answer for this but this is another way of solving this. Strategy behind these question is assume L.H.S as true and make R.H.S as false by some values for which L.H.S is true-

 

1)((∀x)[α]⇒(∀x)[β])⇒(∀x)[α⇒β]

Assume some values of x for α and β which makes LHS as true-

x α β
x1 T F
x2 F T

 

In LHS  (∀x)[α] is false for the assumed domain and same as (∀x)[β] is false for the assumed domain. Now we know that              F-> F = T makes LHS true.

In RHS [α⇒β] is false for x1 and true for x2. So for all x RHS will become false.

$\therefore$ T -> F = F (Not Valid)

 

2)(∀x)[α]⇒(∃x)[α∧β]

Assume some values of x for α and β which makes LHS as true-

x α β
x1 T F
x2 T F

 

In LHS  (∀x)[α] is true for the assumed domain which makes the whole LHS true.

In RHS [α$\wedge$β] is false for x1 as well as for x2. So in RHS there is no true value, which makes whole RHS as false.

$\therefore$ T -> F = F (Not Valid)

 

3)((∀x)[α∨β]⇒(∃x)[α])⇒(∀x)[α]

Assume some values of x for α and β which makes LHS as true-

x α β
x1 T F
x2 F T

 

In LHS  [α∨β] is true for the x1 as well as for x2 which makes (∀x)[α∨β] as true and (∃x)[α] is true for the assumed domain because of x1. Now we know that  T-> T = T makes LHS true.

In RHS  (∀x)[α] is false for the assumed domain which makes the whole RHS false.

$\therefore$ T -> F = F (Not Valid)

 

4)(∀x)[α⇒β]⇒(((∀x)[α])⇒(∀x)[β])

Assume some values of x for α and β which makes LHS as true-

x α β
x1 T T
x2 F T
x3 F F

 

In LHS [α⇒β] is true for x1,x2 and x3. So for all x LHS will become true.

In RHS  (∀x)[α] is false for the assumed domain and same as (∀x)[β] is false for the assumed domain. Now we know that              F-> F = T makes RHS true.

$\therefore$ T-> T = T (Valid)

 

So correct answer is option D.

edited by

4 Comments

mza sa aa gya
1
1

@Shubhgupta How did you decide for the fourth option that till what part will be LHS and RHS??

0
0

@abir_banerjee

with brackets. 

                                   $\color{cyan} \downarrow$             $\color{cyan} \downarrow$
$(\forall x)[\alpha \rightarrow \beta] \rightarrow(((\forall x)[\alpha]) \rightarrow (\forall x)\beta)$
                                $\color{red} \uparrow$                                      $\color{red} \uparrow$

 

0
0
3 votes
3 votes

A)  $(∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$ 

For A the above sentence means that for all x if α is true then for all x  β should also be true. Here both α and β are bounded by different values of x. But on RHS α and β are bounded by the same value of X. so if even 1 value of α becomes false on the LHS side, the whole of expression $(∀x)[α]$ becomes false so regardless of the value of $(∀x)[β])$ the value of LHS is $TRUE$. So we can encounter a situation where α is True and β is false.  Here on LHS we are actually comparing the whole set. So, A is false

B) $(∀x)[α] ⇒ (∃x)[α ∧ β]$

Though whole of α may be true but that does not mean β will also be true so LHS does not imply RHS. so, B is false

C) $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$

This one is clearly invalid because for every x if $α ∨ β$ is true so either α is true or β s true. It may so happen that there exists some values of α which are true but that does not mean all of α will be true because there can also be value of β which can be true.

D)$(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$

This one is $VALID$ because both α and β bound same value of x. On RHS α and β can bound same or different values of x .So we can say that $LHS\subseteq RHS $

edited by
2 votes
2 votes

D. (∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])

(∀x)[~α $\vee$ β] ⇒ (~(∀x[α])) $\vee$  (∀x)[β])

(∀x)[~α $\vee$ β] ⇒  x(~α) V (∀x)[β]) which is TRUE.

 

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true