examples/guide-to-asp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Explaining Answer Set Solving\n",
    "\n",
    "This is a short guide that shows how Answer Set Programming works. We will use [clingo](https://potassco.org/clingo/) in Python for this, and throughout this document we will use the syntax that clingo uses for answer set programming.\n",
    "\n",
    "<!-- [guide](https://github.com/potassco/guide/releases/tag/v2.2.0) -->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import clingo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(If you want to learn in more detail about any of the features of answer set programming with clingo that are explained in this guide, please have a look at the official [Potassco guide](https://github.com/potassco/guide/releases/).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Printing answer sets\n",
    "\n",
    "We start by defining a short function that uses the clingo python package to give us the answer sets of a given answer set program (and display the atoms in the answer set sorted alphabetically)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_answer_sets(program):\n",
    "    # Load the answer set program, and call the grounder\n",
    "    control = clingo.Control();\n",
    "    control.add(\"base\", [], program);\n",
    "    control.ground([(\"base\", [])]);\n",
    "    # Define a function that will be called when an answer set is found\n",
    "    # This function sorts the answer set alphabetically, and prints it\n",
    "    def on_model(model):\n",
    "        sorted_model = [str(atom) for atom in model.symbols(shown=True)];\n",
    "        sorted_model.sort();\n",
    "        print(\"Answer set: {{{}}}\".format(\", \".join(sorted_model)));\n",
    "    # Ask clingo to find all models (using an upper bound of 0 gives all models)\n",
    "    control.configuration.solve.models = 0;\n",
    "    # Call the clingo solver, passing on the function on_model for when an answer set is found\n",
    "    answer = control.solve(on_model=on_model)\n",
    "    # Print a message when no answer set was found\n",
    "    if answer.satisfiable == False:\n",
    "        print(\"No answer sets\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use the function `print_answer_sets()` as follows to print all answer sets of a given answer set program `program`. (We will get to what answer set programs are.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer set semantics\n",
    "\n",
    "Answer set programming is based on the *answer set semantics* for logic programs. This is easiest explained if we start looking at propositional logic programs. Such a program consists of several rules of the following form:\n",
    "\n",
    "```\n",
    "a :- b_1, ..., b_n, not c_1, ..., not c_m.\n",
    "```\n",
    "\n",
    "where each of $a$, $b_i$ and $c_i$ are propositional atoms (that start with a lowercase letter). In such a rule, `a` is called the *head* and `b_1, ..., not c_m` is called the *body*. The order of elements within the body of the rule does not matter. This rule is roughly interpreted as: \"$a$ is true if $b_1$, ..., $b_n$ are true, and $c_1$, ..., $c_m$ are not true.\"\n",
    "\n",
    "You are also free to choose $n=0$, $m=0$, or both. In case both $n=0$ and $m=0$, the rule is simply written as `a.` (and the rule is interpreted as \"$a$ is true\"). So the following are valid rules in a logic program:\n",
    "\n",
    "```\n",
    "a.\n",
    "a :- b_1, ..., b_n.\n",
    "a :- not c_1, ..., not c_m.\n",
    "```\n",
    "\n",
    "An *interpretation* for a logic program is typically taken to be a set $I$ of propositional atoms. All atoms in the set $I$ are true in this interpretation, and all atoms that are not in $I$ are false in the interpretation.\n",
    "\n",
    "### Models for positive programs\n",
    "\n",
    "Answer sets are a particular type of models for logic programs. To explain the particular property that answer sets should have, we first have a look at models for positive programs.\n",
    "\n",
    "A *positive program* is a logic program that does not contain negations (`not`). In other words, it is a set of rules that are all either of the form `a.` (interpreted as: \"$a$ is true\") or of the form `a :- b_1, ..., b_n.` (interpreted as \"if $b_1$, ..., $b_n$ are true, then $a$ should also be true\"). So, a positive program can be seen as a set of facts (`a.`) and logical implications ($(b_1 \\wedge \\dotsm \\wedge b_n) \\rightarrow a)$, written as `a :- b_1, ..., b_n`).\n",
    "\n",
    "A *model* for a positive program is an interpretation $I$ that makes all the logical statements encoded by the rules in the program true. However, some of these models make more sense than others. For example, for the program `a. b :- a.`, the interpretation $I = \\{a,b\\}$ is a model, but so is $I = \\{a,b,c\\}$. The first of these two looks reasonable, but the second not so much. For example, to make the rules in the program true, we need to include $a$ and $b$ in the interpretation, but what justification do we have for putting $c$ in?\n",
    "\n",
    "For positive programs, we are interested in *minimal models*: models $M$ such that no (strict) subset $M' \\subseteq M$ also makes the program true. For a positive program $P$, we define the *answer sets* of $P$ to be the set of all minimal models of $P$. It turns out that if a positive program $P$ has a model, then there is always a single unique minimal model of $P$.\n",
    "\n",
    "So let's try this out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {a, b_1, b_2, b_3, c}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- b_1, b_2, b_3.\n",
    "    b_1.\n",
    "    b_2 :- c.\n",
    "    b_3 :- c.\n",
    "    c.\n",
    "    d :- e.\n",
    "    e :- d.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Taking the unique minimal model of a positive program nicely matches with our intuition of what we want from models. We include all atoms that are declared to be true in the program (in our example: $a$ and $c$). Then we add other atoms that we must include to make all if-then rules true (for example, adding $b_2$ because we already included $c$ and because `b_2 :- c` is in the program), until we are done.\n",
    "\n",
    "In our example, we don't include $d$ and $e$, because there is no reason to add them to the model. (We could have added both to the model, and still satisfy all if-then rules.)\n",
    "\n",
    "### Programs with negation\n",
    "\n",
    "For logic programs where some rules contain a negation (`not`), things don't turn out to be as easy as simply iterating all if-then rules until we reach a fixpoint. For example, look at the following program:\n",
    "\n",
    "```\n",
    "a.\n",
    "c :- a, not b.\n",
    "d :- c.\n",
    "b :- d.\n",
    "```\n",
    "\n",
    "If we would use the strategy of applying if-then rules as long as we can, we would first add $a$, then $c$ (due to the rule `c :- a, not b.`), then $d$ (`d :- c.`), and $b$ (`b :- d.`). But then by adding $b$, we made the application of the rule `c :- a, not b.` invalid (because it only works to justify adding $c$ if $b$ is not true).\n",
    "\n",
    "Nevertheless, we want to select from all the models of a program with negation those models that we are interested in (the answer sets). The idea is to guess an interpretation $I$, use this interpretation to make a version $P^I$ of the program $P$ without negation ($P^I$ is called the *reduct* of $P$ w.r.t. $I$), and then check that $I$ is the unique minimal model of $P^I$—if this is the case, then $I$ is an *answer set* of $P$.\n",
    "\n",
    "Let's see how this works with a simple example. Take the following program $P$ (lines starting with `%` are comments):\n",
    "```\n",
    "% the program P\n",
    "c.\n",
    "d :- c, not b.\n",
    "b :- not d.\n",
    "```\n",
    "Take also the interpretation $I_1 = \\{c,d\\}$. The new program $P^{I_1}$ we get from $P$ by:\n",
    "1. Removing all rules containing some `not a` in the body such that $a \\in I_1$. So in our example, we remove `b :- not d.`, because $d \\in I_1$.\n",
    "1. Removing all remaining statements `not a` from the rest of the program. For all of these statements it holds that $a \\not\\in I_1$, otherwise we would have removed the entire rule containing the `not a` in step (1). So in our example, we change `d :- c, not b.` into `d :- c.`.\n",
    "\n",
    "So in our example, the program $P^{I_1}$ becomes:\n",
    "```\n",
    "% the reduct P^{I_1}\n",
    "c.\n",
    "d :- c.\n",
    "```\n",
    "\n",
    "Now, we have that $I_1 = \\{c,d\\}$ is the unique minimal model of $P^{I_1}$, so $I_1$ is an answer set of $P$.\n",
    "\n",
    "Let's check with clingo what the answer sets of our example program $P$ are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b, c}\n",
      "Answer set: {c, d}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    c.\n",
    "    d :- c, not b.\n",
    "    b :- not d.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indeed, $\\{c,d\\}$ is one of the answer sets. Let us also verify why, for example, $I_2 = \\{b,c,d\\}$ is not an answer set. If we apply the same rules (1) and (2) to $P$ based on $I_2$, we get the program $P^{I_2}$:\n",
    "```\n",
    "% the reduct P^{I_2}\n",
    "c.\n",
    "```\n",
    "(We remove both of the rules `d :- c, not b.` and `b :- not d.` because both $b \\in I_2$ and $d \\in I_2$.)\n",
    "\n",
    "And since $I_2 = \\{b,c,d\\}$ is not the unique minimal model of $P^{I_2}$ (which is $\\{c\\}$), $I_2$ is not an answer set of $P$.\n",
    "\n",
    "### Answer set semantics for programs with negation\n",
    "\n",
    "So, to summarize, the answer sets of a propositional logic program $P$, are all interpretations $I$ for which it holds that $I$ is the unique minimal model of $P^I$, where $P^I$ is obtained from $P$ by:\n",
    "1. Removing all rules containing some `not a` in the body such that $a \\in I$.\n",
    "1. Removing all remaining statements `not a` from the rest of the program.\n",
    "\n",
    "\n",
    "### Example 0: no answer sets\n",
    "\n",
    "It turns out that when we allow negation in the logic programs, it is not guaranteed that an answer set exists. Take the following example program $P$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No answer sets\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not a.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With only one atom, there are only two relevant interpretations: $I_1 = \\emptyset$ and $I_2 = \\{a\\}$. Both are not answer sets of this program $P$. We get the following two reducts $P^{I_1}$ and $P^{I_2}$:\n",
    "```\n",
    "% the reduct P^{I_1}\n",
    "a.\n",
    "\n",
    "% the reduct P^{I_2} (empty)\n",
    "```\n",
    "Since $I_1$ is not the minimal model of $P^{I_1}$, and $I_2$ is not the minimal model of $P^{I_2}$, neither is an answer set of $P$.\n",
    "\n",
    "## Some (more) examples\n",
    "\n",
    "Now that we know what the definition is of answer sets for propositional logic programs, let's look at a few examples to get a bit more feeling for it.\n",
    "\n",
    "### Example 1: binary choice\n",
    "\n",
    "Take this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b}\n",
      "Answer set: {a}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The rules `a :- not b.` and `b :- not a.` allow us to make a binary choice between $a$ and $b$. If we take $a \\in I$, these two rules are replaced by `a.` in $P^I$, and similarly, if we take $b \\in I$, the two rules are replaced by `b.` in $P^I$. In other words, we can pick either $a$ or $b$, and $P^I$ will contain a fact justifying our choice.\n",
    "\n",
    "If we take $I = \\{a,b\\}$, then $P^I$ becomes the empty program (containing no rules), and $\\{a,b\\}$ is not the unique minimal model of the empty program (the empty set is), so $\\{a,b\\}$ is not an answer set of our program.\n",
    "\n",
    "### Example 2: more binary choice\n",
    "\n",
    "Now take this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b, d}\n",
      "Answer set: {a, d}\n",
      "Answer set: {b, c}\n",
      "Answer set: {a, c}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "    \n",
    "    c :- not d.\n",
    "    d :- not c.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, we took two sets of rules encoding the choice between $a$ and $b$, on the one hand, and $c$ and $d$, on the other hand. The resulting program has four answer sets, corresponding to the four combinations of choices.\n",
    "\n",
    "### Example 3: overlapping choice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b, c}\n",
      "Answer set: {a}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "    \n",
    "    a :- not c.\n",
    "    c :- not a.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we again have two sets of rules that each encode a binary choice. One of these is between $a$ and $b$, and the other between $a$ and $c$. This yields two possible combinations of choices ($a,b$, and $a,c$). The answer sets of this program correspond exactly to these two combinations.\n",
    "\n",
    "### Example 4: constraints\n",
    "\n",
    "Suppose now that we want to encode the choices $a/b$ and $c/d$, but that we want to rule out one of the combinations of choices. To do this, we can use a *constraint*, which is a rule with an empty head. For example, the rule `:- a, c.` is a constraint that can be interpreted as \"$a$ and $c$ may not both be true\". Another way to look at this rule is as the logical implication $(a \\wedge c) \\rightarrow \\bot$, where $\\bot$ denotes falsity.\n",
    "\n",
    "Let's see how we can use this constraint in an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b, c}\n",
      "Answer set: {a, d}\n",
      "Answer set: {b, d}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "    \n",
    "    c :- not d.\n",
    "    d :- not c.\n",
    "    \n",
    "    :- a, c.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 5: another constraint\n",
    "\n",
    "We can also use negations in constraints. For example, the constraint `:- not a, not c.` can be interpreted as \"$a$ and $c$ may not both be false.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {a, c}\n",
      "Answer set: {b, c}\n",
      "Answer set: {a, d}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "    \n",
    "    c :- not d.\n",
    "    d :- not c.\n",
    "    \n",
    "    :- not a, not c.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variables\n",
    "\n",
    "So far, we looked at propositional atoms only. However, in many cases it would be very convenient to use (first-order) variables to range over a certain domain, rather than spelling out everything in the language of propositional logic. Fortunately, this is functionality that we can use.\n",
    "\n",
    "For example, we can use predicates with constants wherever we used propositional atoms so far. These constants can be numbers, constants (starting with a lowercase letter, e.g., `charlie`), or compound terms built up using function symbols (e.g., `bestfriend(charlie)`).\n",
    "\n",
    "Note that here the line between predicates (and propositional atoms) and function symbols is blurred a bit: we may use `bestfriend(charlie)` (a) as a unary predicate `bestfriend` applied to the constant `charlie`, or (b) as function symbol `bestfriend` applied to the constant `charlie`.\n",
    "\n",
    "Note also that terms that are syntactically different from each other are always interpreted as semantically different as well: `bestfriend(charlie)` and `bobbie` are always different (even though one can think of an interpretation where the function symbol `bestfriend` applied to `charlie` is the same as `bobbie`).\n",
    "\n",
    "Let's phrase one of our previous examples using predicats:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(b)}\n",
      "Answer set: {choose(a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choose(a) :- not choose(b).\n",
    "    choose(b) :- not choose(a).\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To really use the power of this first-order notation, we can use variables. Variables start with an uppercase letter. Let's start with an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,a)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choice(1).\n",
    "    choice(2).\n",
    "    choose(X,a) :- not choose(X,b), choice(X).\n",
    "    choose(X,b) :- not choose(X,a), choice(X).\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does this example work, exactly? Variables are universally quantified, so the rule `a(X) :- b(X).` expresses that for each $c$ for which $b(c)$ holds, also $a(c)$ must hold. What clingo does is spelling out all the different relevant instantiations of rules with variables. This is called *grounding*. (Programs without variables are called *ground programs*.) So under the hood, clingo first changed our previous example into the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,a)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choice(1).\n",
    "    choice(2).\n",
    "    choose(1,a) :- not choose(1,b), choice(1).\n",
    "    choose(1,b) :- not choose(1,a), choice(1).\n",
    "    choose(2,a) :- not choose(2,b), choice(2).\n",
    "    choose(2,b) :- not choose(2,a), choice(2).\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Safe rules\n",
    "\n",
    "In order to make sure that the grounding process works, you can only use rules that are *safe*. What this means is that every variable that appears in the rule must appear in some positive (that is, non-negated) element of the body. So for example, the following rules are *unsafe* (because the variable `Y` does not appear positively in the body):\n",
    "\n",
    "```\n",
    "a(Y) :- not b(Y).\n",
    "a(X,Y) :- c(X).\n",
    "```\n",
    "\n",
    "If you ask clingo to find answer sets for a program that contains unsafe rules, it will throw an error message.\n",
    "\n",
    "## Abbreviations and other additional features\n",
    "\n",
    "We have seen all the basic features of answer set programming. However, clingo and the language of answer set programming make our life easier by providing some further features. Let's look at some of them by means of some further examples.\n",
    "\n",
    "### Example 6: enumerating numbers\n",
    "\n",
    "Suppose that we want to declare `choice(i)` for all integers between 1 and 10. Rather than spelling out ten facts, we can simply write `choice(1..10).` So we can write our previous choice example as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,b), choose(2,a)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,b)}\n",
      "Answer set: {choice(1), choice(2), choose(1,a), choose(2,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choice(1..2).\n",
    "    choose(X,a) :- not choose(X,b), choice(X).\n",
    "    choose(X,b) :- not choose(X,a), choice(X).\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 7: showing only some predicates in the answer sets\n",
    "\n",
    "In our choice example, we might be interested in only part of the answer set. Namely, in the binary predicate `choose`. We know that every answer set will contain `choice(1)`, etc. We can declare a statement that says we want to show the binary predicate `choose`: `#show choose/2.`. If you issue one or more show statements, then all predicates for which no show statement is issued are automatically hidden from answer sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(1,b), choose(2,b)}\n",
      "Answer set: {choose(1,b), choose(2,a)}\n",
      "Answer set: {choose(1,a), choose(2,b)}\n",
      "Answer set: {choose(1,a), choose(2,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choice(1..2).\n",
    "    choose(X,a) :- not choose(X,b), choice(X).\n",
    "    choose(X,b) :- not choose(X,a), choice(X).\n",
    "    #show choose/2.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 8: declaring constants\n",
    "\n",
    "Suppose that we want to use a number that we will use more often in a program, and that we want to be able to change it easily in a single place. Then we can declare this number as a constant, as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(1,b), choose(2,b)}\n",
      "Answer set: {choose(1,b), choose(2,a)}\n",
      "Answer set: {choose(1,a), choose(2,b)}\n",
      "Answer set: {choose(1,a), choose(2,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    #const k=2.\n",
    "    choice(1..k).\n",
    "    choose(X,a) :- not choose(X,b), choice(X).\n",
    "    choose(X,b) :- not choose(X,a), choice(X).\n",
    "    #show choose/2.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(1,b), choose(2,b), choose(3,b)}\n",
      "Answer set: {choose(1,b), choose(2,a), choose(3,b)}\n",
      "Answer set: {choose(1,b), choose(2,b), choose(3,a)}\n",
      "Answer set: {choose(1,b), choose(2,a), choose(3,a)}\n",
      "Answer set: {choose(1,a), choose(2,b), choose(3,b)}\n",
      "Answer set: {choose(1,a), choose(2,b), choose(3,a)}\n",
      "Answer set: {choose(1,a), choose(2,a), choose(3,b)}\n",
      "Answer set: {choose(1,a), choose(2,a), choose(3,a)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    #const k=3.\n",
    "    choice(1..k).\n",
    "    choose(X,a) :- not choose(X,b), choice(X).\n",
    "    choose(X,b) :- not choose(X,a), choice(X).\n",
    "    #show choose/2.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 9: abbreviating facts\n",
    "\n",
    "Instead of using `choice(1..3).`, we could also use the statement `choice(1;2;3).`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choice(1), choice(2), choice(3)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    choice(1;2;3).\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 10: choice rules\n",
    "\n",
    "Suppose that we want a program that encodes a choice between all subsets of a given set. For example, let $A = \\{a_1,a_2\\}$ and suppose that we want to write a program whose answer sets (restricted to some predicate `choose/1`) correspond exactly to the four subsets of $A$. We can do this as follows, using the technique that we saw in the examples about binary choice:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {}\n",
      "Answer set: {choose(b)}\n",
      "Answer set: {choose(a)}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    element(a;b).\n",
    "    choose(X) :- not unchoose(X), element(X).\n",
    "    unchoose(X) :- not choose(X), element(X).\n",
    "    #show choose/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, we can also encode this, more conveniently, using so-called choice rules. For example, the rule `{ choose(a;b) }.` represents exactly what the above example did:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {}\n",
      "Answer set: {choose(b)}\n",
      "Answer set: {choose(a)}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    { choose(a;b) }.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, equivalently, written as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {}\n",
      "Answer set: {choose(b)}\n",
      "Answer set: {choose(a)}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    { choose(a); choose(b) }.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use these choice rules in the head of a rule, also with a non-empty body of the rule (e.g., `{ choose(a;b) } :- make_choice.`).\n",
    "\n",
    "### Example 11: cardinality rules\n",
    "\n",
    "A construct that is similar to choice rules is that of cardinality rules. These are rules that encode a choice between subsets of a given set that satisfies some cardinality conditions. For example, we can modify the example above so that only subsets of size at least 1 and at most 2 are given:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(a)}\n",
      "Answer set: {choose(b)}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    1 { choose(a); choose(b) } 2.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use these cardinality expressions in the body of a rule:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {}\n",
      "Answer set: {choose(b), exactly_one}\n",
      "Answer set: {choose(a), exactly_one}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    { choose(a); choose(b) }.\n",
    "    exactly_one :- 1 { choose(a;b) } 1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 12: conditional literals\n",
    "\n",
    "Another convenient feature is the use of conditional literals. This we can use to express a set of statements for which another property is true. This works as in the following example, where we declare several items using `item/1`, and then encode a choice of exactly two of these items using a cardinality rule where we express the set using conditional literals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(b), choose(c)}\n",
      "Answer set: {choose(a), choose(c)}\n",
      "Answer set: {choose(a), choose(b)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    item(a;b;c).\n",
    "    2 { choose(X) : item(X) } 2.\n",
    "    #show choose/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 13: arithmetic\n",
    "\n",
    "You can use integers as constants. Moreover, you can use arithmetic operations (e.g., comparing integers, addition, multiplication, etc)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {at_most_five(1), at_most_five(2), at_most_five(3), at_most_five(4), at_most_five(5)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    number(1..10).\n",
    "    four(4).\n",
    "    at_most_five(N) :- number(N), four(F), N <= F+1.\n",
    "    #show at_most_five/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, these arithmetic operations can only be applied to variables whose value can be determined by means of other predicates. Therefore, if arithmetic operations involve variables that do not appear in a positively occurring atom in the body of the rule, clingo will throw an error message. (Such rules are not *safe*, as we explained before.)\n",
    "\n",
    "In the following example, the rule for `double(X,Y)` contains arithmetic operations on `X` and `Y`, and these variables do not occur in a positive atom in the body, and so the rule is not safe and clingo will throw an error message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RuntimeError: \"grounding stopped because of errors\"\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    print_answer_sets(\"\"\"\n",
    "        number(1..10).\n",
    "        double(X,Y) :- not letter(X), not letter(Y), Y = 2*X.\n",
    "        #show double/2.\n",
    "    \"\"\");\n",
    "except RuntimeError as e:\n",
    "    print(\"RuntimeError: \\\"{}\\\"\".format(str(e)));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can make the rule for `double(X,Y)` safe as follows, for example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {double(1,2), double(2,4), double(3,6), double(4,8), double(5,10)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    number(1..10).\n",
    "    double(X,Y) :- number(X), number(Y), Y = 2*X.\n",
    "    #show double/2.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 14: aggregates\n",
    "\n",
    "Another useful feature that clingo offers is the use of *aggregates*: `#sum`, `#count`, `#max`, `#min`, `#even`, and `#odd`. These aggregates operate on a (multi)set of atoms.\n",
    "\n",
    "They can be used as follows, for example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(1), choose(4), total(2)}\n",
      "Answer set: {choose(2), choose(4), total(2)}\n",
      "Answer set: {choose(1), choose(2), total(4)}\n",
      "Answer set: {choose(3), choose(4), total(3)}\n",
      "Answer set: {choose(2), choose(3), total(5)}\n",
      "Answer set: {choose(1), choose(3), total(5)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    cost(1,2).\n",
    "    cost(2,2).\n",
    "    cost(3,3).\n",
    "    cost(4,0).\n",
    "    2 { choose(I) : item(I) } 2.\n",
    "    total(D) :- D = #sum { C,item(I) : item(I), choose(I), cost(I,C) }.\n",
    "    #show total/1.\n",
    "    #show choose/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above example, we use `C,item(I)` in the `#sum` aggregate to make sure that whenever there are more items with the same cost, all of their costs are counted towards the total. If we were to replace `C,item(I)` by `C`, several items with the same cost `C` would (all together) only contribute `C` to the sum.\n",
    "\n",
    "Here is another example, now using the `#count` aggregate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {item(1), item(2), item(3), item(4), total(4)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    total(D) :- D = #count { item(I) : item(I) }.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, an example using `#max`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {choose(1), choose(2), highest(2)}\n",
      "Answer set: {choose(1), choose(3), highest(3)}\n",
      "Answer set: {choose(2), choose(3), highest(3)}\n",
      "Answer set: {choose(1), choose(4), highest(4)}\n",
      "Answer set: {choose(2), choose(4), highest(4)}\n",
      "Answer set: {choose(3), choose(4), highest(4)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    2 { choose(I) : item(I) } 2.\n",
    "    highest(D) :- D = #max { I : item(I), choose(I) }.\n",
    "    #show highest/1.\n",
    "    #show choose/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimization\n",
    "\n",
    "We can also use optimization statements, to select from all answer sets of a given answer set program those answer sets that minimize or maximize a particular property. To illustrate this, we will define a short function that will give us all optimized answer sets for a given answer set program."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_optimal_answer_sets(program):\n",
    "    # Load the answer set program, and call the grounder\n",
    "    control = clingo.Control();\n",
    "    control.add(\"base\", [], program);\n",
    "    control.ground([(\"base\", [])]);\n",
    "    # Define a function that will be called when an answer set is found\n",
    "    # This function sorts the answer set alphabetically, and prints it\n",
    "    def on_model(model):\n",
    "        if model.optimality_proven == True:\n",
    "            sorted_model = [str(atom) for atom in model.symbols(shown=True)];\n",
    "            sorted_model.sort();\n",
    "            print(\"Optimal answer set: {{{}}}\".format(\", \".join(sorted_model)));\n",
    "    # Ask clingo to find all optimal models (using an upper bound of 0 gives all models)\n",
    "    control.configuration.solve.opt_mode = \"optN\";\n",
    "    control.configuration.solve.models = 0;\n",
    "    # Call the clingo solver, passing on the function on_model for when an answer set is found\n",
    "    answer = control.solve(on_model=on_model)\n",
    "    # Print a message when no answer set was found\n",
    "    if answer.satisfiable == False:\n",
    "        print(\"No answer sets\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this function in place, we will illustrate how optimization statements work.\n",
    "\n",
    "Consider the following example, where we have facts declaring four items and a score for each of these items. We also have a cardinality rule that states that we should select between 2 and 3 of these items. This gives us 10 answer sets in total:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {select(3), select(4)}\n",
      "Answer set: {select(2), select(3)}\n",
      "Answer set: {select(2), select(4)}\n",
      "Answer set: {select(2), select(3), select(4)}\n",
      "Answer set: {select(1), select(2)}\n",
      "Answer set: {select(1), select(4)}\n",
      "Answer set: {select(1), select(2), select(4)}\n",
      "Answer set: {select(1), select(3)}\n",
      "Answer set: {select(1), select(3), select(4)}\n",
      "Answer set: {select(1), select(2), select(3)}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    score(1,5).\n",
    "    score(2,4).\n",
    "    score(3,4).\n",
    "    score(4,2).\n",
    "    2 { select(I) : item(I) } 3.\n",
    "    #show select/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's add an optimization statement, that states that we should maximize the total score for the items that we select. This shows that only 2 of the 10 answer sets maximize this total score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal answer set: {select(1), select(2), select(3)}\n"
     ]
    }
   ],
   "source": [
    "print_optimal_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    score(1,5).\n",
    "    score(2,4).\n",
    "    score(3,4).\n",
    "    score(4,2).\n",
    "    2 { select(I) : item(I) } 3.\n",
    "    #maximize { S,I : select(I), score(I,S) }.\n",
    "    #show select/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How this works is as follows. The statement `{ S,I : select(I), score(I,S) }` refers to the set of all pairs `S,I` for which `select(I), score(I,S)` holds in the answer set. Then the `#maximize` statements indicates that only those answer sets should be taken for which the sum of all `S` in such pairs `S,I` is maximal. You may also use `#maximize` statements with tuples of different arity (e.g., triples, or 1-tuples). In this case, however, we need to include `I` in the tuples, because otherwise the score for item 2 and item 3 would only be counted once in the total score.\n",
    "\n",
    "This works similarly using `#minimize` instead of `#maximize`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal answer set: {select(2), select(4)}\n",
      "Optimal answer set: {select(3), select(4)}\n"
     ]
    }
   ],
   "source": [
    "print_optimal_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    score(1,5).\n",
    "    score(2,4).\n",
    "    score(3,4).\n",
    "    score(4,2).\n",
    "    2 { select(I) : item(I) } 3.\n",
    "    #minimize { S,I : select(I), score(I,S) }.\n",
    "    #show select/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see why we need the tuple `S,I` in this `#minimize` statement, consider the following example, where we replace `S,I` by just `S` in the `#minimize` statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal answer set: {select(2), select(3)}\n"
     ]
    }
   ],
   "source": [
    "print_optimal_answer_sets(\"\"\"\n",
    "    item(1..4).\n",
    "    score(1,5).\n",
    "    score(2,4).\n",
    "    score(3,4).\n",
    "    score(4,2).\n",
    "    2 { select(I) : item(I) } 3.\n",
    "    #minimize { S : select(I), score(I,S) }.\n",
    "    #show select/1.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now selecting items 2 and 3 yields the mimimal total score, because both add score 4 to the set `{ S : select(I), score(I,S) }`, and now the score 4 gets only counted once, which is not what we had in mind."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Disjunction\n",
    "\n",
    "There is an extension of answer set programming that allows us to use disjunction in the head of rules, and clingo supports this. The following example illustrates how we can do this (with the operator `;` in the head of a rule):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {a, b}\n",
      "Answer set: {a, c}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a.\n",
    "    b ; c :- a.\n",
    "\"\"\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make sure that we have a good foundation for this, we make sure that our definition of *answer sets* also works for programs with rules that have disjunction in the head.\n",
    "\n",
    "The idea is the same. We guess an interpretation $I$, use this interpretation to make a version $P^I$ of the program $P$ without negation (the *reduct* of $P$ w.r.t. $I$), and then check that $I$ is a minimal model of $P^I$—if this is the case, then $I$ is an *answer set* of $P$.\n",
    "\n",
    "The reduct $P^{I}$ we get from $P$ by:\n",
    "1. Removing all rules containing some `not a` in the body such that $a \\in I$.\n",
    "1. Removing all remaining statements `not a` from the rest of the program.\n",
    "So this is also exactly the same as for the case without disjunction in the head of rules.\n",
    "\n",
    "The only thing that we need to update is what it means for $I$ to be a (minimal) model of $P^I$. We consider rules `a ; b :- c_1, ..., c_n` as the logical implication $(c_1 \\wedge \\dotsm \\wedge c_n) \\rightarrow (a \\vee b)$. That is, we interpret disjunction in the head as logical disjunction in the consequent of the implication. Using this, we can use a similar definition of what an answer set is: an interpretation $I$ that is a minimal (w.r.t. set inclusion) model of the reduct $P^I$ of the program $P$ w.r.t. $I$.\n",
    "\n",
    "To take an example, consider the program that we used as example above:\n",
    "```\n",
    "% the program P\n",
    "a.\n",
    "b ; c :- a.\n",
    "```\n",
    "Consider the interpretation $I_1 = \\{a,b\\}$. The reduct $P^{I_1}$ is:\n",
    "```\n",
    "% the reduct P^{I_1}\n",
    "a.\n",
    "b ; c :- a.\n",
    "```\n",
    "And $I_1$ is in fact a minimal model of $P^{I_1}$. If we remove $a$ from $I_1$, we get the interpretation $\\{b\\}$, which does not satisfy `a.`. This is also the case if we remove $a$ and $b$ from $I_1$. If we instead only remove $b$ from $I_1$, we get the interpretation $\\{a\\}$, which does not satisfy `b ; c :- a.`. Thus, $I_1$ is a minimal model of $P^{I_1}$.\n",
    "\n",
    "### Using default negation to represent disjunctive choices\n",
    "\n",
    "As we have seen above, we can add disjunction to the head of rules. However, in many cases this is not needed to express disjunctive choices. For example, as we have already seen earlier, we can encode a choice between two atoms (say, `a` and `b`) using several rules as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer set: {b}\n",
      "Answer set: {a}\n"
     ]
    }
   ],
   "source": [
    "print_answer_sets(\"\"\"\n",
    "    a :- not b.\n",
    "    b :- not a.\n",
    "\"\"\");"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}