CODEWITHSUNDEEP
answer-set-programmingclingo
bin gui
bin gui

Reputation: 1

How to use negation to select maximum in Clingo

In prolog, we could use negation to select maximum in a tuple like: p(X), not (p(Y), Y > X). % work in Prolog but not work in Clingo

How to use Clingo expression to get similar rules(if there are no bigger number than A, then A is the maximum). Thanks.

Upvotes: 0

Views: 1175

Answers (2)

tphilipp
tphilipp

Reputation: 466

I would like to extend the previous answer with two alternative solutions. I have done no performance comparisons with respect to the first answer.

  • Use of aggregates, see Clingo User Guide

    max(X) :- X = #max { Y : p(Y) }.

  • Guess and Check approach. The idea is that we guess the maximum and afterwards check whether it is indeed the maximum. Note that arithmetic expressions can be written in the head of rules.

    1 { max(X) : p(X) } 1.

    M >= X :- p(X), max(M).

Upvotes: 1

BobHU
BobHU

Reputation: 451

The following rules could represent if there is no bigger number than A, then A is the maximum.

non_max(X) :- p(X), p(Y), Y > X.
max(X) :- p(X), not non_max(X).

Basically, the rule you are representing is a rule with a universal quantifier, i.e.

∀b ∈ p(b), if a > b, then a is the maximum. (1)

If a is the maximum, then ∀b ∈ p(b), a > b. (2)

Transform (2) into its contrapositive, we have

If ∃b ∈ p(b), a < b, then b is not the maximum (3)

correspondingn rule of (3) is non_max(X) :- p(X), p(Y), Y > X.

Since max and non_max are mutually exclusive, then we have max(X) :- p(X), not non_max(X).

Upvotes: 0

Related Questions