Reference no: EM132607517

Simple info about assignment

Part 1
In the first part of this worksheet, your task will be to complete an implementation of the propositional resolution algorithm introduced in week 3 lectures.
The implementation of this algorithm spans two Haskell modules:
• Main.hs: This module contains the functions implementing the resolution algorithm itself. You should be able to view this module now, in the editor on the right.
• Formula.hs: This module contains a series of type definitions for working with propositional formulas in conjunctive normal form, and some useful functions for creating and manipulating such formulas. You can see its contents if you select the 'Formula.hs' tab above the code in the editor window. You can switch between the two files using these tabs.
Most of the work in implementing this algorithm has already been done. Your task will be to understand the existing code and fill in a few key functions which are missing. The next few slides will give you a short tour of the contents of these modules, and then you'll be ready to get to work!

Before we dive into completing the implementation in Main.hs, let's make sure we understand the types involved.
Head over to the Formula.hs file in the code editor. This script defines three new types:
1. a Literal represents a propositional variable or its negation, such as A, or ¬A;
2. a list of Literals forms a Clause;
3. and a list of Clauses specifies a Formula.
The Clause and Formula types capture propositional formulas in conjunctive normal form.
For example, the propositional formula:
(A∨¬B)∧(¬C)∧(¬A∨C)
could be represented as the Haskell Formula:
[[Pos 'A', Neg 'B'], [Neg 'C'], [Neg 'A', Pos 'C']]

Below these type definitions, there are several useful functions for manipulating Formulas, Clauses and Literals:
• negate_literal creates a literal with the opposite sign of the input literal.
• negate_formula converts the negation of an existing formula into conjunctive normal form, so that it can also be used as a formula.
• reduce is used on either clauses (to remove duplicate literals and sort the literals in the clause) or on formulas (to remove duplicate clauses). Sorting is necessary because we'd like two clauses to be considered equal independent of the order of their literals (since disjunction is a commutative operation).
• remove_tautologies filters tautological clauses out of a formula, which is useful because these clauses don't effect the logical properties of the formula.

For the exact details, you can read the definitions of each of these functions.

Finally, we have included a function called translate that will translate strings into formulas, to make this module easier to experiment with.
To represent a formula as a string, we use an upper-case alphabetical character to represent each propositional literal (with a preceding '-' for a negation) and we begin each clause with a '

To obtain the formula mentioned above, we would call:
translate "$A-B$-C$-AC"

At this point, you might like to try translating a few of your own propositional formulas to familiarise yourself with these types and the translate function. When you are ready, move on to the next slide.

Back in the other Haskell file Main.hs, you'll find a partially-completed implementation of the propositional resolution algorithm.
The entry-point to this algorithm is the function unsatisfiable, which uses some of the functions from Formula.hs to prepare the input Formula and then kicks off the process of resolving all possible combinations of the formula's clauses together in all possible ways (by repeatedly calling evolve). Thanks to the useful higher-order function until, this process will repeat until either of the following happens:
1. The empty clause [] is generated, in which case we know that the original formula is unsatisfiable, or
2. No further clauses can possibly be generated and we haven't generated [], in which case we know that the original formula is satisfiable.
You can study unsatisfiable and evolve to get a complete picture of how this is achieved, but the important thing for our purposes is that the resolution algorithm is essentially a process of repeatedly resolving two clauses together in every possible way until either an empty clause is generated or until every possible resolvent has been generated.
Where's the code that performs this single resolution step? That's where you come in.
• The first problem will ask you to implement a function resolve_on which takes two clauses and a particular literal and generates the resolvent clause that is produced by this particular resolution step.
• The second problem will ask you to implement a function resolvents which takes two clauses and resolves them on every pair of complementary literals present in the clauses, thereby producing all possible resolvents of the two clauses.
• At this point you'll have a working algorithm for proving unsatisfiability. For the third problem, you'll be asked to apply this algorithm to create a function that proves logical consequence relationships between two formulas.

Actual questions

Q1. Scroll to the bottom of Main.hs, where you will find an incomplete definition of the function resolve_on.
resolve_on is meant to take a Literal and two Clauses as input and return the new Clause generated by resolving the two input clauses on this literal. We assume that the literal occurs in the first input clause, and its negation occurs in the second. The function should ensure the returned clause is sorted and has no duplicate literals.
For example:

Q2.
Next we'll put the resolve_on function to use within the algorithm. Begin this problem by copying over your successful solution to the previous problem.

Above the definition of resolve_on, you'll find an incomplete definition of the function resolvents.
resolvents is meant to take two Clauses as input and return a list of all clauses which may be generated by resolving these two clauses together, on any of their literals. Depending on the combination of literals in the two clauses, there may be zero, one or many such clauses. The returned list may contain these clauses in any order.
For example:

Q3.
Now that you have finished these two tasks, you have a working resolution algorithm and you can use the unsatisfiable function to test the satisfiability of your formulas.
However, often we would like to use the resolution technique to prove not just the satisfiability or unsatisfiability of a single propositional formula, but logical consequence relationships between two propositional formulas.
Your final task for this section of the worksheet is to implement an additional function inside Main.hs to do just that. This function should be pretty simple, and should make use of the existing unsatisfiable function. For this to work, you'll need to copy over your solutions from the previous problems once again.
Write a function entails which takes two Formulas f and g and returns True if and only if formula g is a logical consequence of f (in which case, we would say that f entails g). Don't forget a type signature!
For example:

Part 2
Simple info about assignment

In the second part of this worksheet, your task will be to complete an implementation of Wang's algorithm.
Wang's algorithm is an approach to validity checking of arbitrary propositional formulas. It is named after the logician Hao Wang, 1921-1995. Once again, most of a working Haskell implementation of this algorithm is provided, and you are asked to complete it. The code spans two more Haskell modules:
• Main.hs contains the functions implementing Wang's algorithm itself.
• Exp.hs contains a series of type definitions for working with arbitrary propositional formulas (not necessarily in conjunctive normal form), and a large amount of parsing code enabling us to input these formulas using a textual representation.
Once you complete the implementation, you'll have one more tool for experimenting with propositional formulas. For example, you may like to use it to verify the validity of formulas discussed in previous tutorials or lectures.
Before we explore the algorithm itself, let's take a look at the types and functions defined inside Exp.hs.
At the top of this file, you'll see a type definition for an Exp (short for expression). This type defines a 'structure tree' which can be used to represent propositional formulas containing any number of logical connectives in any structure. For example, the propositional formula:
((¬(P⇒Q))⇔(P∧¬Q))
Would be represented as the Exp:
BIIM (NOT (IMPL (VAR 'P') (VAR 'Q'))) (AND (VAR 'P') (NOT (VAR 'Q')))
The remainder of the file Exp.hs is taken up by some parsing functions. We will not be concerned about the detail of these functions for now. Suffice it to say that they define the function parse which will turn a string like "((~(P => Q)) <=> (P & (~Q)))" into a Haskell expression of type Exp (in this case, an Exp representing the propositional formula discussed above).
This parse function will therefore prove very handy, because it's much easier to type out this string representation than the complex nested Haskell expression above.
On to Wang's algorithm, defined inside Main.hs.
The workhorse function of Wang's algorithm is called wang; its type definition is at the top of the file. The function wang repeatedly (recursively) applies our sequent rewriting rules until a set of fully reduced sequents has been obtained. These various rewriting cases take up most of the rest of the file. According to the rules of Wang's algorithm, these sequents are all tautological if and only if the original formula was.
The function maintains four lists:
• The list left contains the current unreduced left-hand side (LHS) of the sequent.
• The list right contains the current unreduced right-hand side (RHS) of the sequent.
• The list reducedLeft contains the fully reduced parts of the LHS (that is, just propositional letters). These letters are stored in a list of characters.
• The list reducedRight contains the fully reduced parts of the RHS (that is, just propositional letters). These letters are stored in a list of characters.
In an initial call (made by the function valid), only right is non-empty, the rest are [].
After repeated rewriting, left and right will be empty, and we only a fully reduced LHS and RHS remains. At this point, to determine whether a sequent LHS ? RHS is valid boils down to whether some propositional letter occurs on both reducedLeft and reducedRight.

Actual Question

Q1
All but one of the cases for the function wang have been implemented already. However, if you scroll down to the bottom of Main.hs, you will see that the last case, where left and right are empty, always returns True. This 'base case' of the algorithm should instead return True if and only if the fully-reduced sequent is valid. As we have discussed, this amounts to checking whether there is some propositional letter occuring in both reducedLeft and reducedRight.

Q2

With the derivation and implementation of one additional logical connective under our belt, it's your turn to try. This problem asks you to extend our implementation of Wang's algorithm to handle formulas involving the biimplication connective (⇔). You'll want to start by copying over your solution to the previous exercise.

Extend the implementation of Wang's algorithm to allow formulas with biimplication connectives (⇔). Start by deriving some rewriting rules for when this connective appears on the left or right side of the sequent, then add the required recursive cases to the algorithm. After you are finished, the valid function should be able to deal with formulas involving biimplications.

Q3.
At this point, our implementation of Wang's algorithm provides a decision procedure for propositional validity. In this challenge, your task is to extend this solution to give us a decision procedure for propositional satisfiability.

Like with resolution, the code required to achieve this will be trivial, now that we have access to a completed implementation of Wang's algorithm for checking validity. Begin by copying forward your solution to the previous exercise into the bottom of this version of Main.hs.

First, think about how we might use an algorithm that checks for validity to check for satisfiability instead. When you are ready, add a new function sat :: Exp -> Bool, which takes an Exp as input and uses Wang's algorithm to check if the formula represented by this Exp is satisfiable.

Attachment:- info about assignment.rar