CODEWITHSUNDEEP
first-order-logic
Sahil
Sahil

Reputation: 9486

Explanation of this first order logic statement?

I was going through the document here about problems on FOL, I have to convert the expression in corresponding FOL.

Exactly one student passed the test.

The two options are as follows, I am not sure what either of the two represents

[∃x:student(x)∧passed(x, test)∧[∀y: (student(y)∧passed(y, test))⟹x=y]

[∃x:student(x)∧passed(x, test)∧[∃y:student(y)∧passed(y, test)∧x=y]]

So could somebody help me figure out the meaning of these. I know what the right answer is but can't make any sense of the two representations above. I was thinking along the lines of 

[∃x:student(x)∧passed(x, test)∧[∀y: (student(y)∧x != y => !passed(y, test))]

Is my representation correct?

Upvotes: 2

Views: 160

Answers (3)

Sam Segers
Sam Segers

Reputation: 1951

[∃x:student(x)∧passed(x, test)∧[∀y: (student(y)∧passed(y, test))⟹x=y]

There exists a student x that passed the test and all students that passed the test are x (GOOD)

[∃x:student(x)∧passed(x, test)∧[∃y:student(y)∧passed(y, test)∧x=y]]

There exists a student x that passed the test and there exists a student y that passed the test that is x (FALSE, it does not exclude that multiple students passed the test)

[∃x:student(x)∧passed(x, test)∧[∀y: (student(y)∧x != y => !passed(y, test))]

There exists a student that passed the test and all students that are not x have not passed the test (Also good, equivalent to first)

Upvotes: 3

dsetton
dsetton

Reputation: 826

As I understand it, both the answer you came up with and the right alternative are correct, but the way they phrased it is more commonly found when describing uniqueness in First Order Logic problems. Why? I think this has to do with how you would go about proving your statement.

When trying to prove that there is one and only one entity that has a given property, the usual steps are:

  1. First prove existence of entity with the desired condition;
  2. Then, assume there exist two entities (say, a and b) that both satisfy the condition, and logically deduce their equality, i.e. a = b.

See more about this here: https://en.wikipedia.org/wiki/Uniqueness_quantification

Upvotes: 0

John Coleman
John Coleman

Reputation: 52008

Your representation is correct since what you have inside the scope of the universal quantifier is roughly the contrapositive of what the correct answer has inside its universal quantifier A ^ B => C is logically equivalent to A ^ !C => !B

Upvotes: 0

Related Questions