2.3. Knowledge Representation

2.3.1. First Order Logic

Rules are written using First Order Logic, or predicate logic, which extends Propositional Logic. Emil Leon Post was the first to develop an inference based system using symbols to express logic - as a consequence of this he was able to prove that any logical system (including mathematics) could be expressed with such a system.
A proposition is a statement that can be classified as true or false. If the truth can be determined from statement alone it is said to be a "closed statement". In programming terms this is an expression that does not reference any variables:
10 == 2 * 5
Expressions that evaluate against one or more variables, the facts, are "open statements", in that we cannot determine whether the statement is true until we have a variable instance to evaluate against:
Person.sex == "male"
With SQL if we look at the conclusion's action as simply returning the matched fact to the user:
select * from People where People.sex == "male"
A row represents a fact in the database and for any rows that are returned from the example above, it is inferred that those facts are male people. The following diagram shows how the above SQL statement and People table can be represented in terms of an Inference Engine.
SQL as a simplistic Inference Engine

Figure 2.4. SQL as a simplistic Inference Engine


So in Java we can say that a simple proposition is of the form 'variable operator value', where we often refer to "value" as being a literal value, and a proposition can be thought as a field constraint. Further to this propositions can be combined with conjunctive and disjunctive connectives, which is the logic theorists way of saying '&&' and '||'. The following shows two open propositional statements connected together with a single disjunctive connective.
      
      person.getEyeColor().equals("blue") || person.getEyeColor().equals("green")
This can be expressed using a disjunctive Conditional Element connective - which actually results in the generation of two rules, to represent the two possible logic outcomes.
      
      Person( eyeColour == "blue" ) || Person( eyeColor == "green" )
Disjunctive field constraints connectives could also be used and would not result in multiple rule generation.
      
      Person( eyeColour == "blue"||"green" )
Propositional Logic is not Turing complete, limiting the problems you can define, because it cannot express criteria for the structure of data. First Order Logic (FOL), or Predicate Logic, extends Propositional Logic with two new quantifier concepts to allow expressions defining structure - specifically universal and existential quantifiers. Universal quantifiers allow you to check that something is true for everything; normally supported by the 'forall' conditional element. Existential quantifiers check for the existence of something, in that it occurs at least once - this is supported with 'not' and 'exists' conditional elements.
Imagine we have two classes - Student and Module. Module represents each of the courses the Student attended for that semester, referenced by the List collection. At the end of the semester each Module has a score. If the Student has a Module score below 40 then they will fail that semester - the existential quantifier can be used used with the "less than 40" open proposition to check for the existence of a Module that is true for the specified criteria.
    
    public class Student {
    private String name;
    private List modules;

    ...
    }
    
    public class Module {
    private String name;
    private String studentName;
    private int score;
Java is Turing complete in that you can write code, among other things, to iterate data structures to check for existence. The following should return a List of students who have failed the semester.
    
    List failedStudents = new ArrayList();
    
    for ( Iterator studentIter = students.iterator(); studentIter.hasNext() {
        Student student = ( Student ) studentIter.next();
        for ( Iterator it = student.getModules.iterator(); it.hasNext(); ) {
            Module module = ( Module ) it.next();
            if ( module.getScore() < 40  ) {
                failedStudents.add( student ) ;
                break;
            }
        }
    }
Early SQL implementations were not Turing complete as they did not provide quantifiers to access the structure of data. Modern SQL engines do allow nesting of SQL, which can be combined with keywords like 'exists' and 'in'. The following show SQL and a Rule to return a set of Students who have failed the semester.
      select 
    * 
from 
    Students s 
where exists (  
    select 
        * 
    from 
        Modules m 
    where 
        m.student_name = s.name and 
        m.score < 40 
)
    rule "Failed_Students"
    when
        exists( $student : Student() && Module( student == $student, score < 40 ) )