The Gateway to Computer Science Excellence
+39 votes
4.5k views

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

  1. satisfiable and valid
  2. satisfiable and so is its negation
  3. unsatisfiable but its negation is valid
  4. satisfiable but its negation is unsatisfiable
in Mathematical Logic by Boss (16.3k points)
edited by | 4.5k views
+1
Negation of above statement is $\exists_{x}\exists_{y}(R(x,y)Λ R(y,x)')$. And i think it does not imply antisymmetric or asymmetric relation. Please correct if i am wrong.
+6
Question says for all x and y,  if x is related to y then y is related to x.

This is symmetric property for sets.

valid means tautology (every case must satisfy)

If some cases satisfy but not all , then it is satisfiable

not all sets have symmetric property.

 

for example

relation: x is divisble by y

4 is divisible by 2 hence 4 is related to y but 2 is not divisible by 4 so 2 is not related to 4

thus symmetric property doesn't hold for this set

but it holds for some set(not all)

thus it is satisfiable and not valid

similarly negation of that statement is satisfiable but not valid

∃x∃y(R(x,y)Λ~ R(y,x))

This is the negation for the statement above

There exist some relation  xRy
and not yRx

This is clearly antisymmetric

Source: @amitesh sharma comments in answer
+1
I think the negation is a asymmetric relation, anti-symmetric says if R(x,y) and R(y,x) then x must be equal to y
+1

Hint: A formula is valid iff its negation is unsatisfiable. A formula is satisfiable iff its negation is invalid.

https://en.wikipedia.org/wiki/Satisfiability#Reduction_of_validity_to_satisfiability

+1

@rawan here is also a good link to understand the meaning before looking into the answer 

https://math.stackexchange.com/questions/258602/what-is-validity-and-satisfiability-in-a-propositional-statement

 

4 Answers

+55 votes
Best answer

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.

by Veteran (431k points)
edited by
0
Yes @Arjun you are correct. And if it is given that relation is symmetric as well , both  will be VALID too.

Correct me if wrong !!
+12
The given thing is not a relation- it is a logic formula. So, to make it valid we have to consider a set where only symmetric relations are possible.
0

@Arjun: you are correct BUT see in question it is mentioned that  for all x,y such that there is an order pair (x,y) in the RELATION R which is said to be Binary.

It means they are talking about some arbitrary order pair of Binary relation R

See again !!

+14
Yes. They are talking about arbitrary relations. And that is why it is not valid. If they talk about some specific set of relations and they all are symmetric, then the formula will be valid.
0

Yes if they say in the question that for symmetric relation R  ,

P: (x,y) ----> (y,x) is given

then according to me both   P and ~P are valid  because whenever (x,y) is present (y,x) is present and if (x,y) is not so won't be the (y,x)

0
I didn't get the solution? Can anyone please explain it elaborately?
0
Can someone elaborate. Question seems to be not clear to me
+36
Question says for all x and y,  if x is related to y then y is related to x.

This is symmetric property for sets.

valid means tautology (every case must satisfy)

If some cases satisfy but not all , then it is satisfiable

not all sets have symmetric property.

 

for example

relation: x is divisble by y

4 is divisible by 2 hence 4 is related to y but 2 is not divisible by 4 so 2 is not related to 4

thus symmetric property doesn't hold for this set

but it holds for some set(not all)

thus it is satisfiable and not valid

similarly negation of that statement is satisfiable but not valid
+2
antisymmetric or asymmetric
+6
∃x∃y(R(x,y)Λ~ R(y,x))

This is the negation for the statement above

There exist some relation  xRy
and not yRx

This is clearly antisymmetric
0
@Amitesh Sharma   @Arjun   Someone please answer these 2 questions

Q1  Meaning of satisfiable

A)  There exists a set such that all the relations defined on it are symmetric

B) There exists a set such that there exists a relation  defined on it which is symmetric  

C) For all the sets all the relations defined on it are symmetric

D) For all the sets there exists a relation defined on it which is symmetric

 

Q2  Meaning of valid

A)  There exists a set such that all the relations defined on it are symmetric

B) There exists a set such that there exists a relation  defined on it which is symmetric  

C) For all the sets all the relations defined on it are symmetric

D) For all the sets there exists a relation defined on it which is symmetric
+17

I don't get why people are pointing ∃x∃y(R(x,y)Λ~ R(y,x)) to be Anti-symmetric.

Okay if I follow above notion of anti-Symmetry

Consider a set A={1,2,3,4}

And relation S={(1,2) , (2,3) , (3,2) }

The Matrix of this relation is 

$\begin{pmatrix} 0&1 & 0&0 \\ 0 & 0& 1&0 \\ 0 & 1 & 0 &0\\ 0 & 0 &0 &0 \end{pmatrix}$

This relation is neither symmetric nor Anti-symmetric.

Because for symmetry, the off-diagonal 1's have a 1 in corresponding mirror-image treating diagonal as the mirror.

So, for (1,2) we don't have (2,1)

And, for Anti-Symmetry, we allow diagonal pairs (because of x=y) but only take either lower off-diagonal elements or upper off-diagonal elements but not both at a time for Anti-Symmetry.

But, according to definition of ∃x∃y(R(x,y)Λ~ R(y,x))

we see (1,2) satisfies this and hence it marks this relation as anti-symmetric. Which is false.

For anti-Symmetry, we have ∀x∀y(R(x,y)↔R(y,x))→(x=y)

For Asymmetry, we have ∀x∀y(R(x,y)→~R(y,x))

I think to go by as what Arjun sir said.

∀x∀y(R(x,y)⟹R(y,x))

This implies symmetry but since this does not hold true for all relations, so it is satisfiable but not valid.

It's negation ∃x∃y(R(x,y)Λ~ R(y,x)) also does not hold true for all relations, but for the relation shown as example above, this negation is satisfied. Hence, satisfiable but not valid.

So, answer option (B)

+3

@Ayush Upadhyaya useful explanation brother :) thanks 

+1

Actually confusion arises because

there are 2 thing to notice

1.Inner relation

2.Outer relation

When (x,y) satisfies then (y,x) satisfies

I think it obviously a valid relation

Because take any relation (x,y) satisfies (y,x) forms a loop (in cases of any matrix)

Say for example x=gold, y= silver

(gold makes ornaments as well as silver do) it implies (silver makes ornaments as well as gold do)

So, it satisfies all condition for x and y

Now take (gold makes ornaments as well as silver do)=P

(silver makes ornaments as well as gold do)=Q

what is the relation now? 

P=>Q

this is outer relation, which consists of single direction arrow

like if it is gold then it glitters

it cannot satisfies converse too.

So, it is only satisfiable

 

0
Beautifully explained! Thank you
0
I have a doubt that in the question there is ∀ and ∀ is true only if all the combinations of (x,y) is true and false even if one combination is false. Can we represent satisfiability using ∀?
0

@Ayush Upadhyaya

Simple and great explanation thanks :)

I have one doubt

For anti-Symmetry, we have ∀x∀y(R(x,y)↔R(y,x))→(x=y)

Instead of Biconditional , Implication will also do here right ?

And all this things can are true for Relation on different sets also right ?

Symmetry ==>∀x$\in$A ∀y$\in$B (R(x,y)-->R(y,x))

AntiSymmetry ==> ∀x$\in$A ∀y$\in$B (R(x,y)<-->R(y,x))-->(x=y)

0
If  $\forall$x$\forall y$[R(x,y) $\Rightarrow$ R(y,x)] is satisfiable means in any arbitary relation this implication holds not for all (x,y) in that relation but it holds for some (x,y) in that relation.

If this is correct then $\exists x\exists y$[R(x,y) $\Rightarrow$ R(y,x)] will be valid ????

One more doubt, If I come up with a relation like { (1,2), (2,4), (1,3)} then the given implication is not satisfiable,it's contradiction means false for all (x,y).

so finally what should I conclude??
0
For anti-Symmetry, we have ∀x∀y(R(x,y)↔R(y,x))→(x=y) is wrong.

It must be, ∀x∀y(R(x,y)^R(y,x))→(x=y)
+21 votes

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.

by Boss (12.4k points)
edited by
0
Doubt:

R (x,y) is a BINARY Relation

Means it is commutative or Symmetric, wouldnt that mean for a set (x,y), (y,x) also holds?

Making it a valid statement ?
0
It is satisfiable only. Not valid. It's negation too.
+9
Take another example. X divides Y means Y divides X ... It is satisfiable when both are same. So satisfiable. Not valid. Because not true in rest cases.
0
R(x,y)= x->y

Then, again we will get B.
0
Someone please answer these 2 questions

Q1  Meaning of satisfiable

A)  There exists a set such that all the relations defined on it are symmetric

B) There exists a set such that there exists a relation  defined on it which is symmetric  

C) For all the sets all the relations defined on it are symmetric

D) For all the sets there exists a relation defined on it which is symmetric

 

Q2  Meaning of valid

A)  There exists a set such that all the relations defined on it are symmetric

B) There exists a set such that there exists a relation  defined on it which is symmetric  

C) For all the sets all the relations defined on it are symmetric

D) For all the sets there exists a relation defined on it which is symmetric
0
Wat is the question ??
0
which qsn?
0
I am asking raj ...
0
Ok. sorry.  @Puja Mishra
0
For Q1 the answer will be B)

For Q2 the answer will be D)
0

@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.

0 votes

Simplest Approach! 

by Junior (923 points)
0
@sidelewis
How do you know it is satisfoable by taking example of X lives Y.I don't get it.
0 votes
Whenever a Predicate is satisfiable then it's negation is also satisfiable. So option B is correct.
by (29 points)
0
Any valid statement is satisfiable but negation of valid is not satisfiable.
Answer:

Related questions

+31 votes
8 answers
3
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
50,737 questions
57,367 answers
198,497 comments
105,266 users