Formalise to first order logic and prove the conclusion semantically?

A

aficionado_1996

New member
Joined
Oct 19, 2020
Messages
5
I am reasonably comfortable converting English sentences to first order logic, as long as there are no nested quantifiers, or multiple variables (like x and y). I need to formalise following sentences to first order logic and then semantically check if a conclusion is possible (that is, if it is possible to find who stole the money, based on the given information), but not sure how to.

Sam says 'I did not steal the money'.
Tom says 'It was not me, either Sam or Jim stole the money'.
Jim says 'At least one among Sam and Tom speak the truth'.
The fact is that Sam and Jim were not both being truthful.

The predicates to be used are Lying(x) and Stole(x,y) where x represents Sam, Tom or Jim, and y represents money.
This is what I have come up with:

¬Stole(Sam, Money)
Stole(Sam, Money) ∨ Stole(Jim, Money)
¬Lying(Sam) ∨ ¬Lying(Tom)
Lying(Sam) ∨ Lying(Jim)

I am not sure if this counts as 'formalisation', and I have no idea how to proceed form here (regarding the semantic proof)
 
aficionado_1996 said:
I am reasonably comfortable converting English sentences to first order logic, as long as there are no nested quantifiers, or multiple variables (like x and y). I need to formalise following sentences to first order logic and then semantically check if a conclusion is possible (that is, if it is possible to find who stole the money, based on the given information), but not sure how to.

Sam says 'I did not steal the money'.
Tom says 'It was not me, either Sam or Jim stole the money'.
Jim says 'At least one among Sam and Tom speak the truth'.
The fact is that Sam and Jim were not both being truthful.

The predicates to be used are Lying(x) and Stole(x,y) where x represents Sam, Tom or Jim, and y represents money.
This is what I have come up with:

¬Stole(Sam, Money)
Stole(Sam, Money) ∨ Stole(Jim, Money)
¬Lying(Sam) ∨ ¬Lying(Tom)
Lying(Sam) ∨ Lying(Jim)

I am not sure if this counts as 'formalisation', and I have no idea how to proceed form here (regarding the semantic proof)
Click to expand...
Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:


Please share your work/thoughts about this problem.
 
I have no idea what is meant by "semantically." Could it mean "in English" or some other natural language?

I cannot help with the formalization, but I shall give you a clue: the culprit can be identified.
 
Subhotosh Khan said:
Please show us what you have tried and exactly where you are stuck.
Click to expand...

That's exactly what I have done.

I have mentioned that I arrived at the following:

¬Stole(Sam, Money)
Stole(Sam, Money) ∨ Stole(Jim, Money)
¬Lying(Sam) ∨ ¬Lying(Tom)
Lying(Sam) ∨ Lying(Jim)

The above statements aren't part of the question, it was my (partial) attempt at the answer.
 
JeffM said:
I have no idea what is meant by "semantically."
Click to expand...

It means that I should get the statements to a form like below:

S ⊨ A (S entails A)

where S is the set of statements from the Knowledge base, and A is implicit knowledge/assumption.

For this problem, I believe the implicit knowledge is 'Someone stole the money' (I need to represent this in a general form).

Once I am able to get to the form S ⊨ A, I can prove the entailment.


JeffM said:
the culprit can be identified
Click to expand...

Wow thank you! Are you able to explain, in English, how you determined that the culprit can be identified based on the given data? It is not necessary to know WHO the culprit is. Once I have this information, I'll attempt to formalise it myself.

Thank you!
 
Just to make sure we're on the same page: Is it true that this is a word for word copy of the problem as given to you?

Formalise following sentences to first order logic and then semantically check if a conclusion is possible (that is, if it is possible to find who stole the money, based on the given information):​
​
Sam says 'I did not steal the money'.​
Tom says 'It was not me, either Sam or Jim stole the money'.​
Jim says 'At least one among Sam and Tom speak the truth'.​
The fact is that Sam and Jim were not both being truthful.​
​
The predicates to be used are Lying(x) and Stole(x,y) where x represents Sam, Tom or Jim, and y represents money.​

I don't know how to "formalise" "Sam says ..."; are you supposed to use some symbol for that? I would be inclined not to use "Lying", but instead to turn it all into the following (pulling the first three lines into the fourth):

It is not true that 'Sam did not steal the money' and 'At least one of "Sam did not steal the money" and "either Sam or Jim stole the money" '.​
 
aficionado_1996 said:
It means that I should get the statements to a form like below:

S ⊨ A (S entails A)

where S is the set of statements from the Knowledge base, and A is implicit knowledge/assumption.

For this problem, I believe the implicit knowledge is 'Someone stole the money' (I need to represent this in a general form).

Once I am able to get to the form S ⊨ A, I can prove the entailment.




Wow thank you! Are you able to explain, in English, how you determined that the culprit can be identified based on the given data? It is not necessary to know WHO the culprit is. Once I have this information, I'll attempt to formalise it myself.

Thank you!
Click to expand...
Assume Sam is innocent.

Then what Sam said is true. Consequently what Jim said is true.

But that contradicts the presumably true statement that either Sam or Jim or both lied.

Thus Sam is guilty and lied, Tom is truthful as is Jim, and Jim and Sam did not both tell the truth.

I never studied symbolic logic so I have no clue how to present that proof by contradiction in formal terms. But it is not difficult to explain in a natural language. Anyone who ever had to deal with numerous personnel issues will have no difficulty dealing with something presented all in negations of which some must be lies.
 
Dr.Peterson said:
Is it true that this is a word for word copy of the problem as given to you?
Click to expand...

Yes it is

Here is a similar but simpler question with its solution, that was provided as an example. The answer to the question in this topic should be presented in a similar way. Does this provide a better idea of what I am trying to convey?

We have three stacked boxes P, Q and R from top to bottom. P is red and R is not red.
Is there a red box directly on top of a non red box?

Formalisation is done this way:

S = {On(P,Q), On(Q,R), Red(P), ¬Red(Q)}
A = ∃ x∃ y[Red(x) ∧ ¬Red(y) ∧ On(x,y)]

We need to show

S ⊨ A (S entails A)
That is, for some interpretation I, if I ⊨ S, then I ⊨ A

So the semantic proof is as below:

Let I be an interpretation such that I ⊨ S

case 1:
I ⊨ Red(Q)
I ⊨ Red(Q) ∧ ¬Red(R) ∧ On(Q,R)
I ⊨ A

case 2:

I ⊨ ¬Red(Q)
I ⊨ Red(P) ∧ ¬Red(Q) ∧ On(P,Q)
I ⊨ A

So for any I, if I ⊨ S, then I ⊨ A

Hence, S ⊨ A
 
I have a couple small things to say.

First, in the example, I think there is a typo in the definition of S, and the last Q should be R. I didn't work through the whole thing.

Second, I tend to be cautious answering questions about logic, because I know there are many flavors. I don't think I've seen "semantic proof", and in particular I don't know what is meant by an "interpretation" here. So I can't be much help on an actual proof, though I might be able to judge pieces of one.

Third, what you wrote in the OP doesn't look much like the example (just a small piece of the logic, without any of the entailments and interpretations); and on the other hand, the example has nothing like different people saying things and being liars, so I really have no idea what an answer would look like. It's very helpful to provide an example; but it would be far more helpful if you would try to offer an actual answer, from start to finish, so we could offer whatever opinions we are able to.
 
You must log in or register to reply here.
Top