# HG changeset patch # User Adam Chlipala # Date 1318277524 14400 # Node ID aaeba4cfd0759cc1ba6151f10bed8b270813965a # Parent c7faf3551c5d67ad5ee26e990352c43a2a0de6c4 Work around coqdoc bug diff -r c7faf3551c5d -r aaeba4cfd075 src/Subset.v --- a/src/Subset.v Mon Oct 10 16:01:31 2011 -0400 +++ b/src/Subset.v Mon Oct 10 16:12:04 2011 -0400 @@ -930,7 +930,7 @@ (** All of the notations defined in this chapter, plus some extras, are available for import from the module [MoreSpecif] of the book source. %\begin{enumerate}%#
    # -%\item%#
  1. # Write a function of type [forall n m : nat, {n <= m} + {n > m}]. That is, this function decides whether one natural is less than another, and its dependent type guarantees that its results are accurate.#
  2. # +%\item%#
  3. # Write a function of type [forall n m : nat, {][n <= m} + {][n > m}]. That is, this function decides whether one natural is less than another, and its dependent type guarantees that its results are accurate.#
  4. # %\item%#
  5. # %\begin{enumerate}%#
      # %\item%#
    1. # Define [var], a type of propositional variables, as a synonym for [nat].#
    2. # @@ -941,7 +941,7 @@ %\item%#
    3. # Define a function [negate] that returns a simplified version of the negation of a [prop]. That is, the function should have type [forall p : prop, {p' : prop | forall truth, propDenote truth p <-> ~ propDenote truth p'}]. To simplify a variable, just negate it. Simplify a negation by returning its argument. Simplify conjunctions and disjunctions using De Morgan's laws, negating the arguments recursively and switching the kind of connective. Your [decide] function may be useful in some of the proof obligations, even if you do not use it in the computational part of [negate]'s definition. Lemmas like [decide] allow us to compensate for the lack of a general Law of the Excluded Middle in CIC.#
    4. # #
    #%\end{enumerate}% #
  6. # -%\item%#
  7. # Implement the DPLL satisfiability decision procedure for boolean formulas in conjunctive normal form, with a dependent type that guarantees its correctness. An example of a reasonable type for this function would be [forall f : formula, {truth : tvals | formulaTrue truth f} + {forall truth, ~ formulaTrue truth f}]. Implement at least %``%#"#the basic backtracking algorithm#"#%''% as defined here: +%\item%#
  8. # Implement the DPLL satisfiability decision procedure for boolean formulas in conjunctive normal form, with a dependent type that guarantees its correctness. An example of a reasonable type for this function would be [forall f : formula, {truth : tvals | formulaTrue truth f} + {][forall truth, ~ formulaTrue truth f}]. Implement at least %``%#"#the basic backtracking algorithm#"#%''% as defined here: %\begin{center}\url{http://en.wikipedia.org/wiki/DPLL_algorithm}\end{center}% #
    http://en.wikipedia.org/wiki/DPLL_algorithm
    # It might also be instructive to implement the unit propagation and pure literal elimination optimizations described there or some other optimizations that have been used in modern SAT solvers.#
  9. #