[2021] Imperial College London - Principles of Programming - Q4 Boolean Algebra
Question 4 Boolean algebra
The objective of this question is to implement a very small computer symbolic algebra package for boolean algebra. For simplicity of implementation, we will not implement the __str__ special method, so the intention is that the following code will work as follows:
In [1]: from boolean.boolean import Symbol
In [2]: x = Symbol("x")
In [3]: y = Symbol("y")
In [4]: x & y | ~x
Out[4]: Or(And(Symbol('x'), Symbol('y')), Not(Symbol('x')))
4 (a)
(i) (1 mark)
In the boolean.boolean package create a class Expr whose constructor takes an arbitrary number of operands and stores them as an attribute named operands.
(ii) (2 marks)
Implement the Expr.__repr__ special method. It should return the class name followed by brackets containing a comma-separated list of the repr of each operand.
(iii) (1 mark)
Create a subclass Symbol of Expr representing a (boolean) algebraic symbol. The constructor should take and store a single value. Symbol objects should have an empty list of operands.
(iv) (1 mark)
Implement the Symbol.__repr__ special method. It should return the class name followed by the value in brackets.
4 (b)
(i) (2 marks)
Implement Or, And, and Not subclasses of Expr. These require no additional functionality, so the class body can simply be pass.
(ii) (2 marks)
Implement the __or__, __and__, and __invert__ special methods on Expr to return Or, And, and Not with the relevant operands.
4 (c) (7 marks)
The boolean.boolean module contains a simple recursive postorder tree visitor. Write a single dispatch function which conforms to the interface required by the visiting function of that visitor. This function should use boolean algebra identities to propagate Not down the expression tree so that after the visitor is applied, Not only applies to Symbol objects. For example:
In [1]: from boolean.boolean import Symbol, postvisitor, expand_negation
In [2]: x = Symbol("x")
In [3]: y = Symbol("y")
In [4]: expr = ~(x & ~y | ~x)
In [5]: postvisitor(expr, expand_negation)
Out[5]: And(Or(Not(Symbol('x')), Symbol('y')), Symbol('x'))
The transformations that your single dispatch function will need to apply are as follows:
Expr Output of visitor function
And Or applied to the result of the visitor applied to the operands.
Or And applied to the result of the visitor applied to the operands.
Symbol Not applied to the Symbol.
Not If the operand is a Symbol then that Symbol, otherwise the visitor applied to the operand.
4 (d)
(i) (2 marks)
Ensure that your code passes Flake8.
(ii) (2 marks)
Ensure that your code otherwise conforms to good programming style as we have learned in this course.
There is no need to write any docstrings in this exam.
Get the Solution to This Question
WeChat (微信)
WhatsApp
