9,953 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

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

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

@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

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

The negation of given predicate formulae is ∃x∃y[R(x,y) and ~R(y,x)]

It satisfies every relation(model) that is asymmetric except empty relation.
edited

@Deepak Poonia sir plz correct me ,if I go somewhere wrong.

What is model?

→ Model means an Interpretation which makes your formula True.

Interpretation means (Domain + Predicate).

What is satisfiable?

→ If there exist atleast one model means if there exist atleast one domain for which my statement is true.

What is valid?

→ If we consider every domain(finite domain and infinite domain) and for every domain my statement is true.Then we can say that this is valid

Now, R(x,y) : x divides y.

So,R(y,x): y divides x.

Let consider my domain , D = {2}

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

→ R(2,2) will be true as 2 divides 2. So,there exist a model.So, this is satisfiable.

1. Let consider my domain , D = {2}

R(2,2) is true and ~R(2,2) will be false.

Now the negation of ( ∀x∀y(R(x, y) ⟹ R(y, x)) )  will be  ∃x∃y(R(x,y)Λ~ R(y,x))

And so obvious that the expression will be false for this domain D. So the negation is surely not valid.

1.  Let consider my domain , D = {2,4}. R(2,4) is true and R(4,2) will be false. So ~R(4,2) will be true. ∃x∃y(R(x,y)Λ~ R(y,x)) this expression will be model.

So the negation will never be unsatisfiable for this expression.

We can conclude answer is option B.

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.

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

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.

by

Ok. sorry.  @Puja Mishra
For Q1 the answer will be B)

For Q2 the answer will be D)

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

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

1 comment

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

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

by

1
8,133 views