READ BEFORE YOU START:

You will need to use Python to do this assignment. The code is using Python 3.7, but it should work with later versions. It will not run with Python 2.

Advice to run the assignment code on your personal computer:

1.   Download the S22022_A2.zip file.

2.   Extract all the contents in a folder dedicated to your assignment.

3.   Create a virtual environment to run the assignment code, in the previous folder (about using virtual environments with Python, seelink).

4.   Activate the virtual env. and run “pip install -r A2 \requirements.txt” to install all the packages needed in the virtual env.

5.   Run logic.py to see if you get any error (should not output anything as there are no function/class calls in it).

6.   You can then work in the virtual env. without “contaminating” your global python setup.

You should only make changes to the logic.py file. Do not change any other file. You should create a main() function to write your code to run your experiments.

For better readability (the markers will appreciate it), we ask you to add comments referring to the task you are solving.

There is quite a bit of code in the logic.py file as it can be used for other tasks. The instructions for each task in this assignment will guide you about which part you should focus on. However,

you should start by spending some time understanding how the code is structured and what the different parts can be used for. You should also have a run through the logic.ipynb Jupyter Notebook to understand the syntax and have an idea of what methods you can use to solve the tasks.

Make sure you read the last section “What you need to turn in” before you submit your assignment.

Topic: Propositional and Predicate Logic

It is an important part of learning to be a developer or computer scientist to be able to find the domain knowledge that you need to complete your tasks. You are not expected to already know the small amount of domain knowledge in biology that this assignment requires, but you are expected to be able to find it on the internet. If you’re really stuck with the domain knowledge, you may ask about, and share answers about the biology domain knowledge on Piazza. You may not share answers for the non-programming questions on Piazza, or in any other way. Similarly,  you  may  not  share  direct  answers  about  the  knowledge  representation  or programming parts of the task on Piazza or in any other way.

Task 1:  Propositional Logic Problem (2.5 marks)

DNA is made up of the four nucleotide bases Adenine (A), Thymine (T), Cytosine (C) and Guanine (G). Adenine and Guanine are purines. Cytosine and thymine are pyrimidines.     Pyrimidines always pair with purines.

An example of expressing a constraint in this domain in propositional calculus is: Constraint: If A is a base, it is either a purine or a pyrimidine, but not both.

Propositional calculus representation: base_A ⇒ purine_A ∨ pyrimidine_A ^ ¬ ( purine_A ^ pyrimidine_A)

Express the following constraints in propositional logic [1 mark altogether]

•   If T is a base, it is either a purine or a pyrimidine, but not both; similarly for C and G. [three formulas + example]

•   If A bonds with C (A_bondswith_C), it does not bond with T or G. Similarly for A bonds with T, G bounds with C, and G bounds with T [four formulas]

•   A does not bond with A; similarly, C, T or G do not bond with themselves [four formulas]

•   If A bonds with T, it is the case that A is a base and that T is a base, and it is either the case that A is a purine and T a pyrimidine, or vice versa. Similarly for A bonds with C, G bounds with C, and G bounds with T. [four formulas]

An important feature of formulas in propositional logic is whether they are satisfiable or not. That is, whether there is an assignment of the truth values  {true, false} to the proposition symbols above (e.g., base_a, purine_T or A_bondswith_C true, the rest false) such that the entire formula evaluates to true. Choose such an assignment to the propositions in the example and your 15 formulas and show that they each evaluate to true using a truth table [1.5 mark]. I.e., one choice of assignment for the proposition symbols should evaluate all your formulas to true.

It might be helpful to use the facts of biology as a guide to choosing which propositions are true and which are false in your choice of a satisfying assignment (also known as a model), although a satisfying assignment that does not agree with biology would be acceptable if you can find one; basic information about the biology of DNA and RNA is widely available on the Internet. For example, to agree with biology, your predicates for “A bonds with T” and for “G bonds to C” should be true.

Task 2: Predicate Logic Problem (1 mark)

Adding the following constraint to those in the previous question (Task 1), “If f A bonds with T, then T bonds with A, and similarly for all other pairs”, write a general version of the           bonds-with relation, bondsWith(Base1,Base2), in predicate calculus only using standard         quantifiers (3, ∀) connectives, the unary not (¬), equality (=) and the predicates:

•    base(X)

•   pyrimidine(X); purine(X)

And the constants:

•   adenine, thymine, cytosine and guanine

Task 3 : Use local search to check satisfiability (1.5 mark)

In the logic.py file, create a propositional logic Knowledge Base (KB), named dna_kb, and add to it all the formulas you designed in Task 1. (1 marks)

We willingly  do not  give more  information  about the  code here. You  should  study  it to understand by yourself what parts you need to use for this task. You should start by looking at the logic.ipynb Jupyter Notebook to understand the syntax used in the code and to guide your study.

Int: When you define your propositional symbols, you must write them in capital letters (you can use _ in your proposition symbol’s name, to separate words), else they will be interpreted as variables.

When your KB is built, use the appropriate method to check ifyour KB is satisfiable. Print out the result. What does the method return? (0.5 marks)

Task 4 : Build a FOL KB based on text (2.5 marks)

1.   Extract the essential information from the following text and represent it with predicates and rules in FOL (1 mark).

Text:

“Ants are closely related to bees and wasps, all belonging to the Hymenoptera order. Butterflies belong to the Lepidoptera order and beetles belong to the Coleoptera order. Those 3 orders are part of the Insecta class. Some might confuse them with spiders and scorpions which are respectively part of the Araneae and Scorpiones orders, both belonging to the Arachnida class. However, all these orders belong to the Arthropoda phylum. All of those are living animals.”

Example:

Keywords represented as predicates:

Insect(x): x is an insect

Hymenoptera(x): x is part of the Hymenoptera order

Predicate applied to a constant symbol:

Hymenoptera(Ant): ant is part of the Hymenoptera order

Rule:

Hymenoptera(x) ==> Insect(x): if x is part of the Hymenoptera order, then it is an insect

2.   In the logic.py file, create a FOL Knowledge Base (KB), named animals_kb, and add to it all the predicates and rules you designed previously. (1 mark) You can inspire yourself from the example of CriminalKB in the logic.ipynb Jupyter Notebook.

3.   Code the following questions using appropriate queries to your animal_kb and report the answers you get in the following table. Your answer should be in the form of a substitution list. You can use an appropriate method among the ones already coded in the logic.py file to formulate your queries. (0.5 mark)

Task 5 : Represent more complex information (2.5 marks)

1.   Following the  same process than Task 4, represent the essential information from the following text and add it to a new KB named ants_kb in the logic.py file (1 mark).

Text:

“Ants are known to form colonies. If one colony is close to a second one, and if they do not  attack  each  other,  then  they  unite  and  create  a  supercolony.  If  ants  form  a supercolony, they can defend themselves against a larger animal which attacks one of the colonies.

Colony C1 is close to colony C2, and they are peaceful towards each other. A wasp attacks the ants from colony C1.”

2.   Work out the answer to the following question using forward chaining: “Can colony C1 defend itself from the wasp?”

Explain your workings. Also explain and show what happens if colonies C1 and C2 are not close anymore. (0.5 mark)

3.   Verify your answer by implementing the query in the logic.py file. Report the output in the table below and explain how to interpret the answer from the output. (0.5 mark)

4.   Perform 3 again, using backward chaining this time. Explain the outputs. (0.5 marks)

5.   Additional question (not graded, for curiosity): Print out the clauses in your kb before and after performing forward and backward chaining. Are they the same in both cases? What happened?