edited by
20,560 views
88 votes
88 votes

Which one of the following  well-formed formulae is a tautology?
 

  1. $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
  2. $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
  3. $[ \forall x \, \exists y \, \left( P(x,y) \, \rightarrow \, R(x, y) \right)] \, \leftrightarrow [ \forall x \, \exists y \left(\neg P(x, y) \, \lor R(x, y) \right)]$
  4. $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
edited by

5 Answers

Best answer
67 votes
67 votes

NOTE: “Tautology" & “Valid" are Different Concepts in First Order Logic. Tautology & Valid are Same Concepts in Propositional Logic.

Watch the following Detailed Lecture on  “Tautology Vs Valid” in First Order Logic:

$\color{red}{\text{Tautology Vs Valid in First Order Logic:}}$ "Tautology" in Predicate Logic(Click Here)

Note 1 :

When no information is given about Domain of variables for a First Order Logic (FOL) formula, then consider that domain for all variables in the given FOL formula is same. Unless otherwise explicitly stated, domain should be taken same for all variables of a given FOL formula.

Note 2 :

For propositional logic(PL) / Sentential logic, “Tautology” of an expression means same thing as “Validity” of that expression. But this is Not true in FOL.


Tautology/Validity in Propositional Logic :

Tautologies are a key concept in propositional logic, where a tautology is defined as a propositional formula that is true under any possible Boolean valuation of its propositional variables.

Given propositional logic expression (PLE) $G$ is said to be Valid or Tautology iff $G$ is ALWAYS True, regardless of which valuation is used for the propositional variables. 

Some examples of Tautologies in PL :

$A \vee \neg A$

$(A \vee B) \rightarrow (A \vee B)$

$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A) $

In propositional logic, there is no distinction between a tautology and a logically valid formula. So, 

In Propositional logic $: \text{Valid} \equiv \text{Tautology} \equiv \text{True}$


Tautology/Validity in First Order Logic(FOL) :

From Wikipedia :

The definition of tautology can be extended to sentences in predicate logic, which may contain quantifiers—a feature absent from sentences of propositional logic. Indeed, in propositional logic, there is no distinction between a tautology and a logically valid formula. In the context of predicate logic, many authors define a tautology to be a sentence that can be obtained by taking a tautology of propositional logic, and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). The set of such formulas is a proper subset of the set of logically valid sentences of predicate logic (i.e., sentences that are true in every model).

The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in first-order logic. These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies, which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.

A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). (Note that Propositional logic manipulations can be done on the given formula, but No FOL manipulation should be done.)

For example, because $A \vee \neg A$ is a tautology of propositional logic,  $( \forall x (x=x)  ) \vee  \neg ( \forall x (x=x)  ) $ is a tautology in first order logic. 

Example $2 :$

$[(\forall y \neg Py \rightarrow \neg Px) \rightarrow (Px \rightarrow \neg \forall y \neg Py)]$ is a FOL Tautology.

because it can be obtained from a contraposition tautology  $(A \rightarrow \neg B) \rightarrow (B \rightarrow \neg A) $ by replacing $A$ by $\forall y \neg Py$ and $B$ by $Px$.

Example $3 :$

$ \forall x \forall y P(x,y) \rightarrow \forall x \forall y P(x,y) $ is a FOL tautology because it can be obtained from a PL Tautology $A \rightarrow A $ by replacing $A$ with $\forall x \forall y P(x,y).$

Not all logical validities are tautologies in first-order logic.

For example, the sentence $ {\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx} $
is true/valid in any first-order interpretation BUT it is Not a FOL Tautology, because it corresponds to the propositional sentence ${\displaystyle A\to B} $  which is not a tautology of propositional logic.

Example $2 :$

$\forall x(Px \rightarrow Px)$  is NOT a FOL Tautology because it corresponds to the propositional sentence $A$  which is not a tautology of propositional logic. Note that $\forall x(Px \rightarrow Px)$ is FOL Valid formula But Not Tautology.

Example $3 :$

$ (\forall x Px) \rightarrow Pc $   is NOT a FOL Tautology because it corresponds to the propositional sentence $A \rightarrow B$ (By replacing $ (\forall x Px)$ with $A$ and $Pc$ with $B$)  which is not a tautology of propositional logic. NOTE that $ (\forall x Px) \rightarrow Pc $ is FOL Valid formula But Not Tautology.

Example $4:$

The following is an example of a logical truth that is not a tautology:  $ \exists x \text{Cube}(x) \vee \exists x \neg \text{Cube}(x) $. Because the validity of the argument depends on the meaning of the existential quantifier $\exists $ , and not just on the meaning of the connective $\vee$.

A sentence containing quantifiers that is a tautology is this: $ \forall x \text{Cube}(x) \vee \neg \forall x \text{Cube}(x) $ which is just an instance of the tautologous form $ A \vee \neg A $.

So that's that. 

NOTE : Every FOL Tautology is FOL validity BUT Not vice versa.

So, If a given FOL formula is Not valid, then it is Not a FOL Tautology. 


Now coming back to the given question :

Option A :

Option A is NOT at all valid in FOL. 

$ \forall x \exists yR(x,y) \leftarrow  \exists y \forall xR(x,y) $ is FOL Validity. But it is Not FOL Tautology.

$ \forall x \exists y R(x,y) \rightarrow   \exists y \forall x R(x,y) $ is NOT FOL Validity. So, it is Not FOL Tautology as well.

Option B :

$ (\forall x[ \exists yR(x,y)\rightarrow S(x,y)])\rightarrow \forall x  \exists y S(x,y) $ is NOT at all valid. 

For example, Let $A$ be a set $\{a,b \}$ and let relation $R$ on $A$ be $  \{ (a,a) \}$  and let relation $S$ on $A$ be $  \{ (a,a) \}$  then clearly  $\forall x \exists y S(x,y) $ is false. Also $ (\forall x[ \exists y R(x,y)\rightarrow S(x,y)]) $ is true. So, we can say that option B is NOT Valid. So, it is Not a Tautology.

Option C :

$ [\forall x \exists y(P(x,y)\rightarrow R(x,y))]\leftrightarrow [\forall x \exists  y(\neg P(x,y)\vee R(x,y))] $  is a FOL Tautology. 

Note that we can do Propositional logic manipulations, so, $A \rightarrow B $ can be written $A' \vee B.$

So, 

$ [\forall x \exists y(P(x,y)\rightarrow R(x,y))] \leftrightarrow [\forall x  \exists y(\neg P(x,y)\vee R(x,y))] $ is same as $ [\forall x \exists y( \neg P(x,y) \vee R(x,y))]\leftrightarrow[\forall x  \exists y(\neg P(x,y)\vee R(x,y))] $

under only propositional logic manipulation.  

Now, we can take $A = [\forall x \exists y( \neg P(x,y) \vee  R(x,y))]$ and so $A  \leftrightarrow A$ is tautology in PL.

Option D :

$ \forall x \forall yP(x,y) \rightarrow  \forall x \forall y P(y,x)$ is FOL Valid But Not FOL Tautology. NOTE that if we replace $\forall x  \forall y P(x,y)$ by $A$ then  $ \forall x  \forall y P(y,x)$ is some B. But $A \rightarrow B$ is Not tautology in PL. 

References :

Page number $115$ in the below book :

Watch the following Detailed Lecture on  “Tautology Vs Valid” in First Order Logic:

$\color{red}{\text{Tautology Vs Valid in First Order Logic:}}$ "Tautology" in Predicate Logic (Click HERE)

edited by
72 votes
72 votes

A) lets take R(x,y) means x is divisible by y.
X= {6,8,9}
Y={2,3}

For all x, there exists any y such that x is divisible by y.   It is true in our example. 
but here take y individually, no single y is capable of dividing all x.  So it neither implies nor double implies the second one.
So FALSE.

B)  lets take ...
R(x,y)  means  x is divisible by y ,   
S(x,y) means  means   x/y =2 or 3
X={4,6,11}  Y={2,3}
(∀x[∃yR(x,y)→S(x,y)])→∀x∃yS(x,y)

(Always, make the LHS intentionally true, If we can make RHS false, then it is not tautology)

Here for all X, there exists a y such that ..."if x is divisible by y then x/y=2 or 3".... 11 is not divisible by any y...so no problem.
So LHS is true.
Go to RHS.   For all x, there exists a y such that x/y=2 or 3. Which is false. 11/2 and 11/3 are neither 2 nor 3
Here  T-> F  so False. Not tautology.

 D) 
X= 8,12,16
Y= 2,4
For all X and for all Y, Y divides X.......  It does not imply X divides Y.  So FALSE.



We are only left with option C.  So it is the ans. The method I follow is to disprove it. Not to prove it. So here also you can try something by taking any example. You cant disprove it. C is the ans.

edited by
45 votes
45 votes

Ans (C).

$\left(P \rightarrow Q\right) \leftrightarrow \left(\neg P \vee Q\right)$

edited by
0 votes
0 votes

option a :   lhs side means  “for all x there is a y which satisfy r(x,y)”.  and rhs means ”there is a particular y for every x”.  as bi directional implication given this means both LHS and RHS should be equivalent which is false. hence option a is wrong

option b and option d are just random thoughts written in fol .

option c : as we KNOW ,   P(X,Y) →R(X,Y)  ==  ~P(X,Y)  + R(X,Y)  both these are interchangeable and equivalent so option c is right

hence ans c  not so deep explanation  ..but enough for breaking this question and similar ones .this is the way i got ans

 

Answer:

Related questions

69 votes
69 votes
6 answers
2
38 votes
38 votes
5 answers
3
36 votes
36 votes
6 answers
4
go_editor asked Feb 13, 2015
15,515 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.