Inductive bool : Set := true : bool | false : bool.
Inductive nat  : Set := O : nat | S : nat -> nat.

Fixpoint plus [n:nat] : nat -> nat :=
  [m:nat]
  Cases n of
     O     => m
   | (S n) => (S (plus n m))
  end.

Fixpoint mult [n:nat] : nat -> nat :=
  [m:nat]
  Cases n of
     O     => O
   | (S n) => (plus m (mult n m))
  end.

Fixpoint fact [n:nat] : nat  :=
  Cases n of
     O     => (S O)
   | (S n) => (mult (S n) (fact n))
  end.

Definition bnot :=
 [b:bool]
 Cases b of
    true  => false
  | false => true
 end.

Fixpoint is_even [n:nat] : bool :=
  Cases n of
     O     => true
   | (S n) => (bnot (bnot (is_odd n)))
  end
with is_odd [n:nat] : bool :=
  Cases n of
     O     => false
   | (S n) => (bnot (bnot (is_even n)))
  end
.

Fixpoint idn [n:nat] : nat :=
  Cases n of
     O     => O
   | (S n) => (S (idn n))
  end.

Definition test1 := (is_even (S (S O))).
Definition test2 := (is_even (S (S (S O)))).
Definition test3 := (idn (idn (S O))).
Definition test4 := (is_odd (fact (S (S (O))))).
Definition test5 := (is_odd (fact (S (S (S (S (S (S O)))))))).