Problem Description

A Horn Form Knowledge Base stores and manages a list of definite Horn Clauses. And such a knowledge base can be viewed as a conjunction of these Horn clauses.

A Logic AI Agent using the Horn Form Knowledge Base (HF_KB) as its representation system must support at least two methods TELL and ASK.

A sample main function shown below creates a HF_KB agent and communicates with the agent using its TELL and ASK methods.

#include "KB.h" // header file of the knowledge base agent
#include 
using namespace std;

int main()
{
   HF_KB myKB;
   String myQuery = "F";

   myKB.TELL("A^B^C", "D"); // tells A ^ B ^ C => D
   myKB.TELL("AB^E", "F");  // tells AB ^ E => F
   myKB.TELL("P1^P2", "B"); // tells P1 ^ P2 => B
   myKB.TELL("", "A");      // tells A
   myKB.TELL("", "P1");     // tells P1
   myKB.TELL("", "E");      // tells E
   if (myKB.ASK(myQuery))
      cout << "My knowledge base entails" << myQuery;
   else
      cout << "My knowledge base does not entail " << myQuery;
}

You can make the following assumptions about the agent's representation system:

• The knowledge base uses propositional logic language.
• There will be up to 200 Horn Clauses in the knowledge base.
• All symbols are literal strings. Each symbol consists only letters and digits, and always starts with a letter.
• These propositional logic symbols are case sensitive.
• ∧ is used as the conjunction connector.
• In method TELL, the second parameter string is guaranteed to contain exactly one symbol.
• In method TELL, if the first parameter string is an empty string, then this Horn clause is the proposition symbol contained in the second parameter string.
• In method ASK, the parameter string is guaranteed to contain exactly one symbol.
• There is no negation in any of the clauses and queries.

Your Tasks:

Develop this Logic AI agent program that uses propositional logic Horn Form Knowledge Base as its representation system. One specific requirement is that the agent's ASK method must be implemented using Backward Chaining method.

Provide an assignment report (a .txt or .pdf file) that includes at least the following information:

• How to compile and execute your program? If your source code files need to be placed into subfolders in order to use the makefile, explain how the files should be organized.
• Explain the concrete data structures used in your program to implement your knowledge base and the reason why you choose these particular data structures.
• Perform asymptotic analysis for your ASK method to prove that it runs in linear time to the size of the knowledge base.
• Any known bugs;
• Any comment you would like the marker to know.

What and How to Submit

You need to submit the following files for this assignment:

• source code file(s) -- I assume that they are written in C/C++, with the extension name .cpp and .h. And .rs is added already. If you use any other programming language in implementing your program, let me know the extension name(s) of these files before you attempt submitting. And make sure that your program can be compiled and executed on otter. Thanks.
• makefile, if there is one
• assignment report -- it should be either a text file (.txt) or a PDF file (.pdf).

Put all the files you want to submit in one folder on any cub/pup machine, submit them using the following command:
~liuh/bin/submit 485 A4 .

To check what file(s) you have submitted for this assignment, use the following command on otter:
~liuh/bin/checksubmit 485 A4

Alternatively, upload all the files you'd like to submit to VIU Learn, under the CSCI 485/Assessment/Assignment/A4 tab. Please don't zip your files. Just upload them in their original format.