Assignment 6 (Model Checking Algorithm)

QUESTION
Implement Sentence, Symbol, Not, And, Or, Implication, Biconditional and recursive model_check. Test operators, all six supplied inference cases, and an original three-proposition knowledge base. Explain why removing P from (P -> Q) AND (Q -> R) AND P changes entailment of R.

SOURCE NOTE
All 17 original notebook tasks are included below.

To implement a Propositional Logic Inference System using the Model Checking algorithm in Python.

## Learning Objectives

After completing this experiment, students will be able to:

1. Represent propositions using Python classes.
2. Implement logical operators such as NOT, AND, OR, Implication and Biconditional.
3. Represent a Knowledge Base (KB) and Query.
4. Generate possible truth-value assignments called models.
5. Implement Model Checking to determine logical entailment.

## Problem Statement

Develop a Python-based Propositional Logic Inference System that determines whether a given Query logically follows from a Knowledge Base using Model Checking.

The system should support:

- Atomic propositions
- NOT
- AND
- OR
- Implication
- Biconditional
- Model Checking

Final Knowledge Base:

(P → Q) ∧ (Q → R) ∧ P

Query:

R

## Theory

A proposition is a statement that can have either a True or False value.

Examples:

P = It is raining.

Q = The road is wet.

The following logical operators will be implemented:

| Operator | Symbol | Meaning |
|----------|--------|---------|
| NOT | ¬P | Opposite of P |
| AND | P ∧ Q | Both P and Q must be True |
| OR | P ∨ Q | At least one must be True |
| Implication | P → Q | If P is True, Q should be True |
| Biconditional | P ↔ Q | P and Q have the same truth value |

### Model Checking

Model checking determines whether:

KB ⊨ Query

A Knowledge Base entails a Query if the Query is True in every possible model in which the Knowledge Base is True.

# Task 1: Create the Base Sentence Class

Create a base class named `Sentence`.

The class should contain the following methods:

1. `evaluate(model)`
2. `formula()`
3. `symbols()`

### Requirements

- `evaluate(model)` should evaluate a logical sentence.
- `formula()` should return the logical formula as a string.
- `symbols()` should return all symbols present in the sentence.

### Student Task

Complete the following class.

# Task 2: Create the Symbol Class

Create a class named `Symbol` that inherits from `Sentence`.

For example:

P = Symbol("P")

The class should:

1. Store the name of the symbol.
2. Return its truth value from the given model.
3. Return the symbol name as its formula.
4. Return the symbol as a set.

### Example Model

model = {
    "P": True
}

For the above model, evaluating P should return True.

### Student Task

Complete the following class.

# Task 3: Implement NOT

Implement the logical NOT operator.

NOT P is represented as:

¬P

The NOT operation reverses the truth value.

If:

P = True

then:

¬P = False

If:

P = False

then:

¬P = True

### Student Task

Create the `Not` class by completing the code below.

# Task 4: Implement AND

Implement the logical AND operator.

P ∧ Q is True only when both P and Q are True.

Truth Table:

| P | Q | P ∧ Q |
|---|---|-------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |

### Student Task

Create the `And` class.

# Task 5: Implement OR

Implement the logical OR operator.

P ∨ Q is True when at least one of P or Q is True.

Truth Table:

| P | Q | P ∨ Q |
|---|---|-------|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |

### Student Task

Create the `Or` class.

# Task 6: Implement Implication

Implement:

P → Q

An implication is False only when:

P = True and Q = False

Truth Table:

| P | Q | P → Q |
|---|---|-------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |

### Student Task

Create the `Implication` class.

# Task 7: Implement Biconditional

Implement:

P ↔ Q

A biconditional is True when P and Q have the same truth value.

Truth Table:

| P | Q | P ↔ Q |
|---|---|-------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |

### Student Task

Create the `Biconditional` class.

# Task 8: Create Propositions

Create three propositions:

P
Q
R

Use the `Symbol` class created above.

### Student Task

Create the three symbols and display them.

# Task 9: Test the Logical Operators

Create the following model:

P = True
Q = False

Use the model to test:

1. P
2. ¬P
3. P ∧ Q
4. P ∨ Q
5. P → Q
6. P ↔ Q

### Student Task

Write Python code to evaluate all six expressions.

# Task 10: Implement Model Checking

Now implement the Model Checking algorithm.

The function should determine whether:

KB ⊨ Query

### Algorithm

1. Collect all symbols present in the Knowledge Base and Query.
2. Generate all possible truth assignments.
3. If the Knowledge Base is True for a model, check the Query.
4. If the Query is False in even one model where the KB is True, return False.
5. Otherwise return True.

### Student Task

Complete the following function.

### Hint

Use recursion.

For each symbol, create two possibilities:

- Symbol = True
- Symbol = False

# Task 11: Test Case 1

Knowledge Base:

P → Q

Query:

Q

### Question

Does the Knowledge Base entail Q?

### Expected Output

False

### Student Task

Create the Knowledge Base and Query and use `model_check()` to obtain the result.

# Task 12: Test Case 2

Knowledge Base:

(P → Q) ∧ P

Query:

Q

This represents:

1. If P is true, then Q is true.
2. P is true.

Therefore, according to Modus Ponens:

Q should be true.

### Expected Output

True

### Student Task

Construct the Knowledge Base and Query using the classes developed above.

# Task 13: Test Case 3

Knowledge Base:

(P ∨ Q) ∧ ¬P

Query:

Q

### Question

Does the Knowledge Base entail Q?

### Expected Output

True

### Student Task

Construct the Knowledge Base using:

- And
- Or
- Not

Then perform model checking.

# Task 14: Test Case 4

Knowledge Base:

P ↔ Q

Query:

P

### Question

Does the Knowledge Base entail P?

### Expected Output

False

### Student Task

Implement the test using the `Biconditional` class.

Also explain in one or two sentences why the answer is False.

# Task 15: Three-Condition Inference

Consider the following Knowledge Base:

(P → Q) ∧ (Q → R) ∧ P

Query:

R

### Reasoning

If:

P → Q

and:

Q → R

and:

P

then:

P → Q → R

Therefore, R should follow from the Knowledge Base.

### Student Task

Construct the complete Knowledge Base using nested `And` and `Implication` objects.

Then use Model Checking to determine whether:

KB ⊨ R

# Task 16: Modify the Knowledge Base

Now remove the fact P from the Knowledge Base.

New Knowledge Base:

(P → Q) ∧ (Q → R)

Query:

R

### Student Task

1. Modify the Knowledge Base.
2. Run Model Checking.
3. Observe the result.
4. Explain why the answer is different from Task 15.

# Task 17: Create Your Own Knowledge Base

Create your own Knowledge Base using:

- At least 3 propositions
- At least 2 different logical operators

Your Knowledge Base should contain meaningful logical relationships.

For example, you may use:

P, Q, R

### Student Task

1. Create the Knowledge Base.
2. Create a Query.
3. Apply Model Checking.
4. Record whether the KB entails the Query.
5. Explain the result.


