Differences
This shows you the differences between two versions of the page.
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. |