LARA

Homework 01

Due Thursday, 26.02.2009, at 14:00.

Problem 0: Simple preparatory steps

Do not panic.

Make sure you have access to a working Scala language installation and learn how to use Pattern Matching in Scala. Some very simple examples that use pattern matching is this binary search in Scala:

sealed abstract class BST {
  def contains(key: Int): Boolean = (this : BST) match { 
    case Node(left: BST,value: Int, _) if key < value => left.contains(key)
    case Node(_,value: Int, right: BST) if key > value => right.contains(key)
    case Node(_,value: Int, _) if key == value => true
    case e : Empty => false
  }
}
case class Empty extends BST
case class Node(val left: BST, val value: Int, val right: BST) extends BST
 
object BinarySearchTree {
  def main(args: Array[String]): Unit =
    if (Node(Node(Empty(),3,Empty()),5,Empty()).contains(3)) println("Inside")
    else println("Outside")
}

You should be able to save this file as BinarySearchTree.scala, compile it with “scalac BinarySearchTree.scala”, run it with “scala BinarySearchTree”, and obtain as a result “Inside”.

Problem 1

(Programming Assignment)

Consider the definition of abstract syntax trees for propositional logic (see Propositional Logic Syntax) in Scala, built from operators for negation, conjunction, disjunction, and implication.

Write the evaluation function that takes a mapping from variable names to truth values and returns the truth value of the formula.

You can find a skeleton that is a good starting point for this problem and the next one in file propositional.scala.txt (remove the “.txt” file name suffix after saving the file).

Problem 2

(Programming Assignment)

Let $G$ be a propositional formula $G$ contains only conjunction, disjunction, negation, and implication (no equivalence). Negation-normal form of $G$, denoted $NNF(G)$, is a formula that

  • does not contain implication (only $\land$, $\lor$, $\lnot$)
  • negation applies only to variables and not to other formulas.

The following tautologies can be used to transform formula into an equivalent negation normal form:

\begin{equation*}\begin{array}{l}
  \lnot (p \land q) \leftrightarrow (\lnot p) \lor (\lnot q) \\
  p \leftrightarrow  \lnot (\lnot p) \\
  (p \rightarrow q) \leftrightarrow ((\lnot p) \lor q) \\
  \lnot (p \lor q) \leftrightarrow (\lnot p) \land (\lnot q)
\end{array}
\end{equation*}

Extend the solution for the previous problem with an implementation of the function $NNF$ in Scala, which takes the formula syntax tree and transforms it into an equivalent formula in negation-normal form. For example, the function should transform formula $\lnot ((\lnot p) \lor q)$ into $p \land \lnot q$. Similarly, it should transform $\lnot (p \rightarrow \lnot q)$ into $p \land q$.

Write also code that tests transformation to normal form by repeating several times the following steps:

  • generate a random assignment to propositional variables of the formula
  • compare the truth value of the original and of the transformed formula

Problem 3

(Paper and Pencil Assignment)

For the purpose of this task, it will be useful to write down recursive mathematical definition of NNF that follows your Scala implementation.

If $G$ is a propositional formula, let $size(G)$ denote the number of nodes in its syntax tree (as in the previous programming assignments). Find an integer constant $K$ such that, for every formula $G$ containing only $\land, \lor, \rightarrow,\lnot$ we have:

\begin{equation*}
    size(NNF(G)) \leq K \cdot size(G)
\end{equation*}

Once you guess the value $K$, prove that the above inequation holds for this $K$, using mathematical induction.

Optional Problem 4 (For Glory and Extra Credit)

(Paper and Pencil Assignment)

Is it possible to obtain such constant $K$ if the original formula has equivalence as well? Explain your answer.