Dark Mode

9,280 views

52 votes

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

- satisfiable and valid
- satisfiable and so is its negation
- unsatisfiable but its negation is valid
- satisfiable but its negation is unsatisfiable

2

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

2

65 votes

Best answer

0

edited
Jul 9
by samarpita

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

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

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

2

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

2

24 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.**