edited by
16,609 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)[β])$
edited by

7 Answers

Best answer
69 votes
69 votes

(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
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
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 $

2 votes
2 votes

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

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

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

 

Answer:

Related questions

4 votes
4 votes
0 answers
3
Syedarshadali asked Jun 29, 2017
978 views
Consider the following logic program P A(x) <- B(x, y), C(y) <- B(x,x) Which of the following first order sentences is equivalent to P?Can anyone explain how it can be s...