GATE IT 2006 | Question: 21

Question

Consider the following first order logic formula in which $R$ is a binary relation symbol.

$∀x∀y (R(x, y) \implies R(y, x))$

The formula is

• A. satisfiable and valid
• B. satisfiable and so is its negation
• C. unsatisfiable but its negation is valid
• D. satisfiable but its negation is unsatisfiable

Comments

@Rajsukh Mohanty you are again wrong bro , Please refer to the definition of antisymmetric and asymmetric . 

Antisymmetric says ∀x∀y(xRy ^ x!=y ---> ~ R(y,x))

Asymmetric says ∀x∀y(xRy  ---> ~ R(y,x))

But you have given ex as (2,4) its true that 2 divides 4 and 4 doesn't divide 2 and 2!=4 but this must be true for all x and y . Consider this ex(2,-2) both the integers divide each other so its not antisymmetric nor assymetric. 

---

@Prashant_Dubey right, right. sorry bro, I really screwed up on the definition of anti-symmetric and asymmetric.

---

https://youtu.be/wzVFO4hyVfo?list=PLIPZ2_p3RNHidhFvyKH4U_VE1rFAyvG8U&t=5916

Answer 1

The given relation is nothing but symmetry. We have both symmetric relations possible as well as anti-symmetric but neither always holds for all sets. So they both are not valid but are satisfiable. (B) option.

Comments

@samarpita,

Your understanding is all correct Except the definition of Model that you wrote. 

A model of a formula is an interpretation in which it is true.

A model of a quantificational formula(First Order Logic Formula) is analogous to a satisfying truth assignment
of a propositional formula, so a satisfiable formula of quantificational logic is one that has a model.

A valid formula, also known as a theorem, is a formula that is true under every interpretation.

Valid formulas are the quantificational analogs of tautologies in propositional logic.

Model means an Interpretation which makes your formula True.

Interpretation means Domain + Predicate.

You are only considering Domain in the definition of Model, not the predicate. BUT you are applying it all correctly.

$\color{red}{\text{Detailed Video Solution} }$ with COMPLETE Analysis is here: Video Solution with Complete Analysis

---

Watch @GO Classes Discrete mathematics 2023 course, First order logic, Lectures 17, 18, 19, which cover Model concept in First order logic, as well as in propositional logic. Watch these 3 lectures. It will help you understand many concepts very clearly.

https://www.goclasses.in/s/store/courses/description/2023-Discrete-Mathematics

---

For people who didn’t get the anti symmetric part:

~ [∀x y(R(x, y) ⟹ R(y, x))]    =   ∃x∃y(R(x,y)Λ~ R(y,x))

In ∃x∃y(R(x,y) Λ~ R(y,x)) we are only excluding R(y,x) not R(x,x) therefore this relation is anti symmetric not asymmetric

---

@priyansh_1705 check my comment to prove this statement that its negation is not antisymmetric nor symmetric. 

Answer 2

x: boy,   y: girl
R(x,y) means x loves y.

Ok. Question says
For all boys & girls in the world, a boy loves a girl means that girl loves him too.. 
It is true sometimes too.
Hence satisfiable.
Negation of it is also satisfiable.
think logically or negate it mathematically then put this example.. In some cases these will be true.
Hence B is the answer.

Comments

@Ahwan

but here , 

∀x∀y(R(x,y)⟹R(y,x)) for all x,y we need to check.and atleast one is flase then answer is false.as for all.

then it should be not satisfiable. 

I know I am wrong but but i don't know where i am wrong.

---

aisa samjha ki zindgi bhar kaam ayega☠️

---

aisa samajh aya ki zindgi bhar kaam ayega ☠️

Answer 3

By using Truth table and predicate formulas, this could also be another version of the answer.

Answer 4

You can easily understand by this example:

let R(x,y) be x is greater than y.

then R(y,x) will be y is greater than x.

 

now for all x for all y (R(x,y) -> R(y,x))

can be proved to be false if we can come up with the case as "T->F". This can be easily done by taking value of x as 6 and value of y as 2.

so 6>2 is true and 2>6 is false. Therefore the value is false.

Since we have proved for some variables that the implied predicate is giving us false, therefore the given statement is definitely not valid.

But it is also not satisfiable till now. To make it satisfiable we must find at least one case for which we can get result as true.

This is also simple as take x = 2 and y = 6, so 2>6 is false and F implied anything is true. Therefore with x = 2 and y = 6 we made our predicate as True.

Since we got a true case therefore the predicate is "Satisfiable"

 

Now let's check for the negation.

the negation of predicate will be,

there exist x there exist y (R(x,y) ^ not of R(y,x))

not of R(y,x) means y is not greater than x.

 

let's take again x = 2 and y = 6, now this will make predicate false as F^anything is false.

therefore clearly negation of the given predicate is definitely not valid.

 

can we make it true for atleast a case?

let's check:

take x = 6 and y = 2

now 6>2 and also 2 is not greater than 6 

therefore the given predicate is true.

this means we have atleast a case for which negation is true. Therefore the negation is satisfiable.

 

so the answer is option b. "satisfiable and so is it's negation".

Comments

tnx,really a simple solution

---

In this kind of question are we allowed to take any relation for R(x,y)

Answer 5

Whenever a Predicate is satisfiable then it's negation is also satisfiable. So option B is correct.

Comments

Any valid statement is satisfiable but negation of valid is not satisfiable.

---

Not always true

Answer 6

short trick

valid means always true ...as we know that every relation is not symmetry so it is not valid.

satisfiable means given relation is sometimes true ...as we know that given relation is symmetry and The negation of given predicate formulae is ∃x∃y[R(x,y) and ~R(y,x)]

so it is satisfiable and so its a negation.

 

hope my answer helps u a lot