2.7k 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)[β])
Brackets are not matching in (D) . pls fix
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 ????
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??

(A) 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.

(B) 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.

(C)  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.

(D) 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.
selected by
Sir, please mention some example for option d
sir ,for (d) option take set as {2,5,7,13} where [ alpha : prime numbers] [beta : odd numbers] (∀x)[α ⇒ β] ⇒ ((∀x)[α]) ⇒ (∀x)[β]) now left side of implication we have for all x alpha implies beta which is false means false------> RHS now solving RHS, RHS says for all x if alpha than for all x beta also there.. which is false means now RHS is false.. therefore false --------> false (i.e) true +false which is always true.. so (d) option correct plz check is that correct/?????
What you told is correct. But what we want to prove is "validity". That is our formula must be TRUE for all instances. So, taking an example won't help. Example helps only for proving satisfiability.
@arjun sir,how to solve these type of question which involve quantifiers in them and ask us to rove tautology??..pls help
You need to know the De-Morgan's law for first order logic. Then with a good English, basics of set theory and a bit of practice you can solve any such question easily. The weblinks here are good: http://gatecse.in/mathematical-logic/
@Arjun if we take universal domain as persons

α =males

β=females

For this B. option becomes true ?

i had checked other options im getting B. plz verify with my domain
you are taking domain person dont include person which is man and women.

if you are seeing like that then Arjun sir ans also wrong take 12 in set . so the logic is B is not true for any possible domain.

If we prove it is wrong for any domain then it is invalid .
@Gabbar For that domain, option B becomes TRUE if there exist a person who is both male as well as female.

Anyway, important thing here is not to make the formula TRUE or FALSE. A formula is VALID if no instance of it is FALSE. So, it is enough to give any instance which gives FALSE and prove that our formula is not valid. But now how to prove that a given formula is VALID? - Here we cannot take any example as we are not going to get instance which is false. And getting one or two instances which are TRUE does not prove anything.
Nice discussion on such confusing question.Thanks, everyone.

How A) and D) differs?

A)Say α=Number divisible by 3, β=Number divisible by 4

((∀x)[α] ⇒ (∀x)[β]) = (( ∃x )[~α] + (∀x)[β])

i.e. Some number not divisible by 3 or all number divisible by 4

So, LHS could be {7,5}

RHS= (∀x)[α ⇒ β] = (∀x)[~α + β]

i.e. all number of set x either not divisible by 3 or divisible by 4

So, RHS could contain {4,8,7,5}

So, LHS doesnot implies RHS.

D)just opposite to A). So, it is valid :)

(A) 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.

For Each X={3,6,9,8}

LHS= (T^T^T^F)=>(F^F^F^T)
F=>F
TRUE

RHS= [(T=>F)^(T=>F)^(T=>F)^(F=>T)]
FALSE

TRUE=>FALSE
Make Implication False.

Sir , Won't the answer keep on changing if we take different values of X
I am unable to understand the approach for this question at all. Kindly explain how is this being done?
@arjun, will there be a difference if in place of free variable, x is a bounded variable?

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)

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

So,(D) is ans.