The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
4k views

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)[β])$
asked in Mathematical Logic by Veteran (59.7k points)
edited by | 4k views
0
Brackets are not matching in (D) . pls fix
0
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 ????
+1
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??

3 Answers

+35 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.
answered by Veteran (369k points)
edited by
0
Sir , Won't the answer keep on changing if we take different values of X
0
I am unable to understand the approach for this question at all. Kindly explain how is this being done?
0
@arjun, will there be a difference if in place of free variable, x is a bounded variable?
0

srestha you said LHS does not implies RHS 

there can be 2 cases for that T---->F and F---->T 

in the example you gave{7,5} proves T---->T 

and in example arjun sir gave {3,6,9,8} proves T-----> F (not valid)

0
@Arjun Sir I have some questions, rather i am asking for a suggestion to solve such kind of problems

1)Sir i have gone through  your several approaches that you follow for solving such problems where i have observed for various options (let say a,b,c,d) yu are taking different  set of domains and propositional fuctions respectively let say for option a )you take domain(x)={3,6,9,12} and p(x): x is a even number q(x): x is a odd number

let say for option b) domain(x)={3,6,8} p(x):x is a multiple of 3 q(x)=x is multiple of 2   

So my question is Is it right approach before solving a problem to predefine a fixed domain and fixed propositional functions for all options a,b,c,d

let say domain(x)={3,6,8} p(x):x is a multiple of 3 q(x)=x is multiple of 2   

now for this same set of domain as well as propositional functions can i solve all the options a,b,c,d

2).I sometimes fell in fear when i found a option True and it is valid .I fear that if someone came up with set of   domain and propositional functions which proves its false .So,in course of fear i think more about that problem which takes more time .

So my question is how to handle  such situation  ?
+1
The point is that to prove something correct you've make sure it is correct for each and every case(maybe infinite in number) but to prove something wrong we only need one case.

So, to check validity of implication try to prove it false, by trying to make LHS as True and RHS as false, if you'll able to do so then implication is not valid otherwise it is valid.

I think arjun sir also done the same he found out one case such that implication can be proved wrong and yes, you've thing that by yourself and don't worry it will come easy if you practice with right mindset as I mentioned above.
0
@Arjun Can we say that in option A) a weaker condition implies a stronger condition which makes it wrong. But in option D) a stronger condition implies a weaker condition which makes it correct.
0
What if we solve option d with set {3,6,9,8} then this option d will not be true or valid.

valid means for any set this option holds true but for {3,6,9,8} this is not true.
0
I'm not getting the trick actually.

Can anyone tell me what is the basic fanda to do this type of questions?
0
@halder just read @bhuv comment u will understand inshallah what is going on here
+12 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.

answered by Loyal (5.7k points)
edited by
0
for D option ,can you please prove ,RHS implies LHS as false using the same method.
0
@SubVer For D, RHS implies LHS is false and which is option A.
0
awesome explanation

thanks bro
0
Elegant explanation thanks
0
It looks quite easy,but on which basis you are assuming the values of Alpha & Beta??
0
D option:

X         α        β

X1      T         T

X2      T         F

LHS:  (∀x)[α⇒β]⇒(((∀x)[α]) will be true( F⇒T)

RHS: (∀x)[β]) : False

Doesn't this prove that D) option is invalid?
0

@MRINMOY_HALDER, just assume those values for which LHS become true.

 

@Sambhrant Maurya, LHS for D is (∀x)[α⇒β] and RHS is (((∀x)[α])⇒(∀x)[β])

–3 votes
Option (D) (∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β]) is valid.

So,(D) is ans.
answered by Loyal (7.1k points)
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

44,284 questions
49,774 answers
164,289 comments
65,856 users