Logic Expression evaluation with open-world assumption

Tweet

Now it is time to look at how to evaluate expressions against that stored knowledge.

Knowledge based reasoning in .net c#
Reasoning in Open or Closed models
Logic Expression evaluation with open-world assumption
Expression evaluation on object based models
Expression evaluation over time
Expression evaluation over time - Was?

Logic operators

Logical AND

The AND operator evaluates true, if both the right and the left side expression evaluate as true.
Leading to the following truth table:

AND	TRUE	FALSE
TRUE	TRUE	FALSE
FALSE	FALSE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 if (leftResult != EvaluationResult.True)
  return EvaluationResult.False;

 var rightResult = Right.TransformEvaluation(facts);
 if(rightResult != EvaluationResult.True)
  return EvaluationResult.False;

 return EvaluationResult.True;
}

Logical OR

The OR operator evaluates true, if any of the left or right side expressions evaluate as true.
This gives the following truth table:

OR	TRUE	FALSE
TRUE	TRUE	TRUE
FALSE	TRUE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 if (leftResult == EvaluationResult.True)
  return EvaluationResult.True;

 var rightResult = Right.TransformEvaluation(facts);
 if (rightResult == EvaluationResult.True)
  return EvaluationResult.True;

 return EvaluationResult.False;
}

Logical XOR

The XOR, i.e. the exclusive OR operator evaluates true, if either the left or the right hand side is true. But false if both are equal.
Truth table:

XOR	TRUE	FALSE
TRUE	FALSE	TRUE
FALSE	TRUE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 var rightResult = Right.TransformEvaluation(facts);

 if ((leftResult == EvaluationResult.True && rightResult == EvaluationResult.False)
  || (leftResult == EvaluationResult.False && rightResult == EvaluationResult.True))
  return EvaluationResult.True;
 
 return EvaluationResult.False;
}

Logical NOT

The NOT operator only has a right side value and evaluates true if it is false.
Truth table

NOT	TRUE	FALSE
-	FALSE	TRUE
-	-	-

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var result = Right.TransformEvaluation(facts);
 switch (result)
 {
  case EvaluationResult.False:
   return EvaluationResult.True;
  case EvaluationResult.True:
   return EvaluationResult.False;
  case EvaluationResult.NotSure:
   return EvaluationResult.NotSure;
  default:
   throw new ArgumentOutOfRangeException();
 }
}

Expression evaluation

Now that we have the basic logical operators to use to form our expressions. Lets look at how to evaluate:

In my code base I have a number of expression types, that include AND, OR, XOR, NOT and LEAF.

The leaf is a special case that contains one single KnowledgeItem and can be evaluated against the expression.

The leaf node evaluation is as follows:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 return facts[this];
}

So. The expression tree contains AND, OR, XOR and NOT operations but only the leaf nodes contains actual information that can be evaluated.
Also, you may have noted that the most of these operators above just Transform an result, and they only take into account True and False values, whereas in the open-world assumption we should also have the Unknown/NotSure value.
In my implementation I decided to evaluate each and every Leaf node at the start of the evaluation method. If any NotSure values were found, the result was not transformed. Meaning the logical operators were not hit. The evaluation method just returned NotSure directly.

public EvaluationResult Evaluate(AExpression expression)
{
 var facts = new Dictionary<ExpressionLeaf, EvaluationResult>();
 var leafNodes = expression.GetLeafNodes();
 foreach (var node in leafNodes)
 {
  var attr = node.Leaf as KnowledgeAttribute;
  if (attr != null)
  {
   facts.Add(node, KnowledgeStore.Evaluate(attr));
  }
  var rel = leaf as KnowledgeRelation;
  if (rel != null)
  {
   facts.Add(node, KnowledgeStore.Evaluate(rel));
  }
 }
 if (facts.Values.Any(x => x == EvaluationResult.NotSure))
  return EvaluationResult.NotSure;
 return expression.TransformEvaluation(facts);
}

All code provided as-is. This is copied from my own code-base, May need some additional programming to work.CodeProject
Good luck :)