LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
sav08:homework01 [2009/03/11 17:22]
vkuncak
sav08:homework01 [2015/04/21 17:30] (current)
Line 91: Line 91:
  
 Negation-normal form of a propositional formula contains only conjunction,​ disjunction,​ and negation operators. ​ Such formula should not contain implication operator. ​ Moreover, negation only can only apply to variables and not to other formulas. ​ The following tautologies can be used to transform formula to negation normal form: Negation-normal form of a propositional formula contains only conjunction,​ disjunction,​ and negation operators. ​ Such formula should not contain implication operator. ​ Moreover, negation only can only apply to variables and not to other formulas. ​ The following tautologies can be used to transform formula to negation normal form:
-\[\begin{array}{l}+\begin{equation*}\begin{array}{l}
   \lnot (p \land q) \leftrightarrow (\lnot p) \lor (\lnot q) \\   \lnot (p \land q) \leftrightarrow (\lnot p) \lor (\lnot q) \\
   p \leftrightarrow ​ \lnot (\lnot p) \\   p \leftrightarrow ​ \lnot (\lnot p) \\
Line 97: Line 97:
   \lnot (p \lor q) \leftrightarrow (\lnot p) \land (\lnot q)   \lnot (p \lor q) \leftrightarrow (\lnot p) \land (\lnot q)
 \end{array} \end{array}
-\]+\end{equation*}
 Extend the solution for the previous problem with a function that takes formula syntax tree and transforms it into an equivalent formula in negation-normal form.  For example, the function should transform formula $\lnot (p \rightarrow \lnot q)$ into formula $p \land q$. Extend the solution for the previous problem with a function that takes formula syntax tree and transforms it into an equivalent formula in negation-normal form.  For example, the function should transform formula $\lnot (p \rightarrow \lnot q)$ into formula $p \land q$.
  
Line 115: Line 115:
  
 For example For example
-\[+\begin{equation*}
    ​W({(p+qp)*}\,​ p) = (r_p \cup (r_q \circ r_p))^* \circ r_p    ​W({(p+qp)*}\,​ p) = (r_p \cup (r_q \circ r_p))^* \circ r_p
-\]+\end{equation*}
  
 Is it the case that that if an equality $r_1 = r_2$ holds for all values of variables representing subsets of $\Sigma^*$, then $W(r_1) = W(r_2)$ holds for all values of relation variables? ​ If so, prove it.  If not, give a counterexample. Is it the case that that if an equality $r_1 = r_2$ holds for all values of variables representing subsets of $\Sigma^*$, then $W(r_1) = W(r_2)$ holds for all values of relation variables? ​ If so, prove it.  If not, give a counterexample.