YES
Trs:
 {          not(true()) -> false(),
           not(false()) -> true(),
  evenodd(s(x), s(0())) -> evenodd(x, 0()),
   evenodd(0(), s(0())) -> false(),
        evenodd(x, 0()) -> not(evenodd(x, s(0())))}
 Comment:
  We consider a non-duplicating trs.
  BOUND:
   Automaton:
    {          true_3() -> q13 | q10 | q6,
               true_2() -> q13 | q10 | q6,
               true_1() -> q6,
               true_0() -> q6,
             not_2(q13) -> q13 | q10 | q6,
             not_1(q10) -> q6,
              not_0(q6) -> q6,
              false_3() -> q13 | q10 | q6,
              false_2() -> q6,
              false_1() -> q13 | q10 | q6,
              false_0() -> q6,
               s_2(q11) -> q12,
                s_1(q7) -> q9,
                s_0(q6) -> q6,
                  0_2() -> q11,
                  0_1() -> q7,
                  0_0() -> q6,
     evenodd_2(q6, q12) -> q13,
      evenodd_1(q6, q9) -> q10,
      evenodd_1(q6, q7) -> q13 | q10 | q6,
      evenodd_0(q6, q6) -> q6}
   Strict:
   {}
   Qed