CODEWITHSUNDEEP
listlogicpredicate
ddriver1
ddriver1

Reputation: 733

trouble understanding a tricky line in predicate logic

I'm having difficulty interpreting this formula that was from a past exam paper that I'm going through. xs is a list of natural numbers ([Nat]) and i, j, k are of sort Nat. The in(n,xs) function expresses that the natural number n exists in list xs.

∀i∀j∀k(in(i,xs) ^ in(j,xs) ^ in(k,xs) -> i=j v j=k v i=k)

I think I understand all the individual meanings:

∀i∀j∀k                                    ; for all Nats i, j, k
in(i,xs) ^ in(j,xs) ^ in(k,xs)             ; are in list xs
i=j v j=k v i=k                            ; at least 2 of i, j, k have the same number

But I cant go further than that.. I first thought it was saying that every number carries the same value since it doesnt indicate that i, j and k are not equal to one another but the answer feels a bit retarded given the length of this formula.

Any help would be great, thx and have a nice day

Upvotes: 1

Views: 99

Answers (1)

Francois G
Francois G

Reputation: 11985

Your formula says :

∀i∀j∀k                                    ; take three arbitrary Nat-s
in(i,xs) ^ in(j,xs) ^ in(k,xs)             ; if all three are in the sme list xs
->                                         ; then
i=j v j=k v i=k                            ; at least 2 of them are equal

Hence your list does not contain three distinct numbers. It may contain an arbitrary number of Nats. It can contain an arbitrary number of copies of a single Nat. It can also be empty.

This is a list verifying your property:

[1;1;1;1;2;2;2;2;2;1;1;1;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2]

If you repeat it an arbitrary number of times (concatenating it to itself), possibly infinitely, it still does verify your property. This also verifies your property:

[1;2]

But this one doesn't (counterexample: I pick i=1,j=3,k=2):

[1;2;3]

Upvotes: 1

Related Questions