More Advanced Features

Negation

• How does Ergo decide what is true?
  • A fact that is directly asserted in the KB (knowledge base) is inferred as true, unless there is a conflicting rule which defeats that inference. This potential for defeat is called "defeasibility". One rule may have higher priority than another rule and thereby override/block that second rule's conclusion from being established. We will further explain defeasibility, in due course.
  • Facts are inferred (or proven) using rules together with other true facts that satisfy the conditions (the bodies) of those rules, again with the potential for defeat.
• Then what is not true?
  • Everything else!
• Ergo has two kinds of negation: negation-as-failure (\naf) and explicit negation (\neg).
  • Negation-as-failure refers to the aforementioned principle by which one may conclude that something is not true, if it cannot be proven true. Intuitively, \naf p means that p is not known to be true. There are many non-trivial details to fill in this picture, but this is what negation-as-failure looks like from ten miles above the surface.
  • Explicit negation is a much simpler concept. Sometimes we want to say that something is known to be false (as opposed to not being known to be true). This is what explicit negation is. Intuitively, \neg p is falsehood in the stronger sense of believing the opposite of p is true, rather than just the absence of believing that p is true. Explicit negation allows one to assert, as well as to inquire about, false facts; negation-as failure allows one only to inquire.

Negation-As-Failure (\naf) and the Truth Value undefined:

• \naf fact means it's not a provable fact.
• \naf can appear only in queries and rule bodies -- never in rule heads or asserted facts. For example:

• Negation-as-failure is known to be "non-monotonic" meaning that our overall knowledge does not necessarily grow as we acquire new facts. For instance, from the above information we can derive man(Socrates). However, if we are told that Socrates is a pet fish, i.e., fish(Socrates) is added to the knowledge base then man(Socrates) is no longer derivable and, in fact, the query \naf man(Socrates) will be answered as true. By contrast, classical logic is "monotonic": every conclusion inferrable from the previous KB is still a conclusion after the addition of more explicit assertions to that KB.
• Negation-as-failure also leads to 3-valued logic, where the third truth value is undefined. This is one of those pesky details that rears its head as we descend from ten miles high closer to earth.
• The undefined truth value enables the logic to represent situations where knowledge involves paradoxes. It also enables the logic to represent situations where knowledge involves bounded rationality, i.e., situations where we either don't care to know or cannot obtain precise answers and therefore settle for undefinedness. Intuitively, p having truth value "undefined" represents an indeterminate status of belief, where one cannot (or does not care to) determine that p is true or that \naf p is true.
• An example of negation-as-failure leading to paradox and undefined truth value is when one has the asserted rule:

boat(?X) :- \naf boat(?X).

Both boat(Socrates) and \naf boat(Socrates) end up being undefined: not undefined in the sense of having no value, but in the sense of having the truth value undefined. If we assume that Socrates, say, is not a boat then the above rule immediately derives a contradiction. If we assume that Socrates is a boat then we discover that there is no support for such a conclusion: no fact explicitly says this and the above rule certainly doesn't endorse such a conclusion; such a conclusion would be "unfounded".

• In general, ascertaining what is "unfounded" in this way is not completely obvious, but there is a beautiful theory (invented in approximately 1989) that crosses the t's and dots all i's on this subject. It is called the well-founded semantics for negation-as-failure, and this is what Ergo's \naf is based upon.

Explicit Negation (\neg)

• \neg means the user is explicitly stating that something is false; it is known to be false. For example:

• The explicit negation \neg is similar to, but weaker than, negation in classical logic. For instance, in classical logic fish(Socrates) ∨ ¬ fish(Socrates) is always true. Not so in the well-founded semantics and Ergo: fish(Socrates) \or \neg fish(Socrates) can be false (in the naf sense) or undefined. For example, if neither fish(Socrates) nor \neg fish(Socrates) is explicitly present (or derivable) then the above disjunction is false (again, in the naf sense).
• An important semantic property is: \neg implies \naf. That is, if \neg foo is derivable then \naf foo is derivable with at least as much certainty as \neg foo. What does "as much certainty" mean? The three truth values are ordered on the scale of truth as follows: false < undefined < true. So, if \neg foo is undefined then \naf foo must be undefined or true. If \neg foo is true then so must be \naf foo. This semantic property is a kind of consistency property, which says that if one knows that foo is false then one should not be able to prove foo being true or undefined.

Note: \neg cannot be meaningfully applied to built-ins and standard libraries. For instance, the following statements don't make sense:

• \neg a = b
  • Will get a compiler error: applying \neg to a builtin does not make sense, as \neg is used to assert explicit negative information that is provided by the user.
• \neg write(foobar)@\prolog
  • This will give a compiler error, as explicit negation is inapplicable to Prolog calls.
• \neg write(foobar)@\io
  • This will also give a compiler error. The problem here is that \neg is applied to a standard Ergo library rather than to user-supplied rules and facts.

Tips on \naf and \neg

• Use \naf only in rule bodies or queries, never in rule heads or facts.
• It's OK to use \neg anywhere, i.e., in heads as well as bodies. Except in the context of builtins and standard libraries.
• \neg implies \naf, but not vice versa.

Rule Descriptors

Ergo uses descriptors to record key meta-information about a rule. Descriptors are always at the beginning of the rule, in a frame-like sub-expression that looks like this:

@!{ruleId} and/or @{tag} and/or @@{strict} and/or @@{defeasible}

Note: @@{strict} and @@{defeasible} must not appear together in the same rule.

• For example, the following descriptor assigns a unique explicit rule id, 'rule 24', to a rule whose formula is p(?X) :- q(?X), and makes that rule be defeasible:

@!{rule24} @@{defeasible} p(?X) :- q(?X).

• Note: Ergo supports a generalized form of defeasible reasoning. The above rule needs the following directive at the top of the appropriate module (before any rules are given):

:- use_argumentation_theory.

• Tags can be assigned for the purpose of prioritizing with respect to defeasibility. For example, the tag veryHigh can be assigned to a rule:

@!{rule25} @{veryHigh}  g(?X) :- h(?X).

Rule Conflict, Overriding, and Defeat

What if two rules try to draw conflicting conclusions? It's usually undesirable to conclude both foo and \neg foo, i.e., an explicit contradiction. To avoid such a situation, one can declare (i.e., specify) the rules to be defeasible and define (i.e., specify) prioritization between them. A higher-priority rule's attempted conclusion will defeat a lower-priority rule's attempted conclusion, and only the higher-priority's rule conclusion will be actually drawn. If no priorities are given then there will be an impasse and no contradiction will result: the truth values for both foo and \neg foo will be false or undefined.

For example, in the following rule set, two different rules attempt to conclude p(a) and \neg p(a) given the fact q(a):

:- use_argumentation_theory.

@{foo} p(a) :- q(a).

@{bar} \neg p(a) :- q(a).

q(a).

First, we must tell the system that we want to use defeasible rules. This is done via the use_argumentation_theory directive. Then we need to tell which rules are supposed to be defeasible. This is done by attaching tags to such rules (@{...}). Tags are used as identifiers through which we define priorities among rules. In the above situation, neither p(a) nor \neg p(a) has higher priority and neither will be inferred -- both inferences are "defeated." As one can see in the next two queries where No answers found will be the result:

p(a).

\neg p(a).

In order to give priority to one of the rules, the \overrides builtin predicate can be used, as in the following example:

:- use_argumentation_theory.

@{foo} p(a) :- q(a).

@{bar} \neg p(a) :- q(a).

q(a).

\overrides(foo,bar).

• Now the query, p(a), gives the result Yes, while the query \neg p(a) gives the result, No answers found. These results are expected because, in the Ergo file, the rule foo (with the head p(a)) overrides the rule bar (with the head \neg p(a)).

Another Example of Reasoning with Defeasible Rules

Please download nixon.ergo and load in Ergo to work through the following example. The following example, known as the Nixon Diamond, illustrates defeasible reasoning further. Nonmonotonicity arises due to multiple inheritance. Let us assume the following knowledge base:

• Since Nixon is a Quaker, one can derive that he is a pacifist. However, when we add the fact that Nixon is also a Republican, we have a conflict.
• To resolve the conflict we can define an additional rule using the \overrides predicate to tell Ergo that we want the @{republican} rule to take priority over the @{quaker} rule.
• Remember to add

    :- use_argumentation_theory

at the top of this rule set. If we then query the ruleset for any person that is not a pacifist, Nixon is given as an answer since that rule had priority:

Clicking on 'Why?' brings up a justification window with the explanation:

There are no answers for any person that is a pacifist since that rule was defeated (overriden):

Asking 'Why Not?' by right-clicking on 'No answers found' above results in the following explanation:

An annotated and executable example of defeasibility and overrides from the e-commerce domain can be found here:

E-Commerce Volume Pricing Discount Example: Defeasible Rules

Function Terms

Predicates are made up of a name and arguments. Arguments can be constants, variables, or more complex function terms.

Function terms are formed by applying a function to a tuple of arguments. The arguments can be constants, variables, or function terms themselves.

These functions are logical constructors. They are not evaluated as in, e.g., Java. (However, see User-Defined Functions below, which are indeed evaluated.)

Function terms can be nested:

Function terms can be used with operators like equality:

It should be noted, however, that equality (:=:) should be used sparingly, as it imposes heavy computational demands.

HiLog (higher-order terms)

• A predicate or function itself can be any kind of term: a variable -- or even a functional term.
• In the socrates.ergo example, if we were interested in knowing

Which facts are about Socrates?

We can use this query: ?X(Socrates).

Why? Because man(Socrates) is an asserted fact and mortal(Socrates) is inferred. This can be seen by right-clicking on mortal in the query window above and selecting 'Why?' from the pop-up menu. The following justification window is shown.

• Predicate names themselves can be functional terms also. For example, the predicate ancestorThru(mentor) is used as a functional term:

The \is Operator: Evaluation of Expressions

How does one say 2+2? Turns out there is a twist: the default treatment of '+', '-', and the other arithmetic operators is that they are understood as function symbols that are simply written in the infix notation. In other words, 2+2 is simply another term whose "canonical" form is +(2,2). Likewise, 2+3*?X ** -1 is nothing but the term +(2,**(*(3,?X),-1)). So, for instance, the query

?X = 2+2.

yields the answer

?X = 2 + 2

1 solution(s) in 0.0000 seconds

and not ?X = 4, as one might have expected. There are good reasons for such treatment of arithmetic operators, but here we will focus on how to make them work like in arithmetic. For this, Ergo provides an evaluation operator \is. For instance, the queries

?X \is 2+1.

?_P = 2.3, ?Y \is 2+3*?_P** -1.

will yield the answers

?X = 3

?Y = 2.1449

The \is operator is multi-duty: it can evaluate other kinds of expressions as well. For instance, it can convert terms to symbolic constants and concatenate them:

?X \is  abc || ' cde ' || 2.34 || ' ' || f(a,b).

yields the answer

?X = 'abc cde 2.3399999999999999 f(a,b)'

Expressions can also be evaluated in-line. For instance, instead of writing

p(?X) :-  q(?Y,?Z), ?X \is ?Y*3, ?V \is ?Z+1, r(?V).

one could write

p(\is ?Y*3) :-  q(?Y,?Z),  r(\is ?Z+1).

or even just

p(= ?Y*3) :-  q(?Y,?Z),  r(= ?Z+1).

The \is operator can do even more, like append lists and perform other operations. Details can be found in ErgoAI Reasoner User's Manual, section "Arithmetic (and related) Expressions."

Aggregation

Aggregate operators are well-known from SQL and other languages. In Ergo, however, aggregates are more powerful and easier to write than in SQL-like languages. Predefined aggregation operators in Ergo include

• avg
• sum
• min
• max
• count
• setof
• bagof

and others. The last two are, strictly speaking, not aggregation operators, but comprehension operators -- they are used to collect items into lists based on various conditions. The first five, on the other hand, just compute certain numbers based on the selected data items. However, they are usually lumped together because of the similar syntax.

An example of a use of an aggregate operator avg:

Aggregation syntax is described in detail in section "Aggregate Operators" of the ErgoAI Reasoner User's Manual.

Aggregates Example

Please load salary.ergo for an example of using the aggregate operators avg, min, and setof using the frame syntax.

• In the example, salary information (in $1,000's) over three years is given for three employees (John, Ed, and Sue) of a fictional company.

John : Employee[salary(2013)->100,

                salary(2014)->110,

                salary(2015)->120 ]. 

Ed : Employee[salary(2013)->200,

              salary(2014)->220,

              salary(2015)->240 ].

Sue :  Employee[salary(2013)->300,

                salary(2014)->330,

                salary(2015)->360 ].

• In order to count employees, the aggregation operator count{...} is used:

In order to find the average salary of all employees in 2014, the aggregation operator avg{...} is used:

The calculation is explained in the justification window by right-clicking on the answer and selecting 'Why?'

• Similarly, queries for minimum (min), maximum (max), and the unique years for which salary information is available (setof) can be performed. Try running the queries yourself. See salary.ergo for the specific query syntax.

User-Defined Functions (UDFs)

User-defined functions (UDFs) support a form of evaluable expressions that are evaluated in-place. This amounts to rewriting of terms containing UDFs into other terms -- roughly similar to certain aspects of functional programming.

• For example:

\udf fatherOf(?x) := ?y \if father(?x,?y).         /* specifies the UDF fatherOf */

\udf incr(?x) := ?y \if ?y \is ?x+1.               /* specifies the UDF incr */

\udf teacherOf(?x) := ?y \if taughtBy(?x,?y).      /*specifies the UDF teacherOf */

teachesCompSci(teacherOf(?x)) :- class(?x), cs(?x). /* utilizes the UDF teacherOf */

ageOf(John,incr(?A)) :- ageOf(Mary,?A).            /* utilizes the UDF incr */

knows(Bob,fatherOf(John)).                         /* utilizes the UDF fatherOf */

• The symbol :- can be also used in lieu of \if in the above UDFs.

More details are given in the ErgoAI Reasoner User's Manual, section "User Defined Functions".

Note that a UDF expression (e.g., fatherOf(John) ) is not a functional term, even though it syntactically looks similar to a functional term.

Delay Quantifiers

This is a feature for expert users only who understand more about the computational aspects of how reasoning algorithms work in Prolog and Ergo. Delay quantifiers (or pragmas) specify that certain subgoals in rule bodies or queries should be delayed, i.e., dynamically resequenced to come later within the execution ordering of subgoals, until certain variables meet certain conditions like becoming ground (i.e., variable-free) or becoming bound (i.e., "nonvar").

• A delay quantifier has one of these forms:

must(Condition)^Goal

wish(Condition)^Goal

Note: delay quantifiers can be combined, if they refer to different variables.

• For example: If John is an employee of Acme and John manages Acme, then he is the CEO.

?X[ceo->?Y] :-

must(ground(?X) \or nonvar(?Y))^?X[employee -> ?Y],

manages(?Y,?X).

The effect is that if by the time ?X[employee ->?Y] gets to be evaluated neither ?X is ground nor ?Y is bound, the evaluation is delayed past the time manages(?Y,?X) is evaluated (and presumably binds one or both variables). The effect is that the subgoals in the above rule get reordered automatically, if this is needed for a more efficient computation. More details are given in the ErgoAI Reasoner User's Manual, section "Rearranging the Order of Subgoals at Run Time".

Pay also attention to the suggested style of writing rules that have multiple subgoals in the body, including the subgoals involving delay quantifiers.

Ergo Directives

Ergo has compiler directives and executable directives. They affect the semantics of the modules where they appear and/or performance. The compiler directives are in effect only during the compilation of the containing file, while the executable directives take effect right after they are executed (as queries) until their effect is canceled by other directives. Some directives can be used both at compile time and as executable directives; some can be used only at compile time; and some only at run time as executable directives.

The compile time directives always appear inside Ergo files and look like this:

:- some-directive.

The run time directives look exactly like queries. They can be embedded in files in which case they look like this:

?- some-directive.

or they can be typed interactively into terminal window, into the input area of the Studio Listener window, and even into the Studio Query window. The Ergo directives are described in ErgoAI Reasoner User's Manual in appropriate places and many are also summarized in the section "Compiler Directives." Here we describe just a few directives in order to convey the idea of how they are used.

• setsemantics{Option1,Option2,...} -- this is used to alter the semantics and can be used both as a compiler directive or as an executable directive. Here are some examples of these options:
  • equality=none -- the symbol :=: is treated just as an equivalence relation with no other special properties.
  • equality=basic -- the symbol :=: is treated as equality. This is a very powerful, but expensive option.
  • subclassing=strict -- statements like p::p, for any p, are false and if it is derived by rules then a warning about cyclicity of the subclass relation is issued.
  • subclassing= nonstrict -- statements like p::p are true and no warnings about cyclicity of :: are issued.
• use_argumentation_theory -- this is a compiler-only directive; used when one intends to use defeasible rules. Without this, all rules would be strict.
• defsensor -- a compiler-only directive that is used to introduce Ergo sensors.
• iriprefix -- this directive can be used both at compile time and also at run time; it introduces prefixes for compact IRIs.