YES
TRS:
 {         not(false()) -> true(),
            not(true()) -> false(),
        evenodd(x, 0()) -> not(evenodd(x, s(0()))),
  evenodd(s(x), s(0())) -> evenodd(x, 0()),
   evenodd(0(), s(0())) -> false()}
 DP:
  Strict:
   {      evenodd#(x, 0()) -> not#(evenodd(x, s(0()))),
          evenodd#(x, 0()) -> evenodd#(x, s(0())),
    evenodd#(s(x), s(0())) -> evenodd#(x, 0())}
  Weak:
  {         not(false()) -> true(),
             not(true()) -> false(),
         evenodd(x, 0()) -> not(evenodd(x, s(0()))),
   evenodd(s(x), s(0())) -> evenodd(x, 0()),
    evenodd(0(), s(0())) -> false()}
  EDG:
   {(evenodd#(s(x), s(0())) -> evenodd#(x, 0()), evenodd#(x, 0()) -> evenodd#(x, s(0())))
    (evenodd#(s(x), s(0())) -> evenodd#(x, 0()), evenodd#(x, 0()) -> not#(evenodd(x, s(0()))))
    (evenodd#(x, 0()) -> evenodd#(x, s(0())), evenodd#(s(x), s(0())) -> evenodd#(x, 0()))}
   SCCS:
    Scc:
     {      evenodd#(x, 0()) -> evenodd#(x, s(0())),
      evenodd#(s(x), s(0())) -> evenodd#(x, 0())}
    SCC:
     Strict:
      {      evenodd#(x, 0()) -> evenodd#(x, s(0())),
       evenodd#(s(x), s(0())) -> evenodd#(x, 0())}
     Weak:
     {         not(false()) -> true(),
                not(true()) -> false(),
            evenodd(x, 0()) -> not(evenodd(x, s(0()))),
      evenodd(s(x), s(0())) -> evenodd(x, 0()),
       evenodd(0(), s(0())) -> false()}
     SPSC:
      Simple Projection:
       pi(evenodd#) = 0
      Strict:
       {evenodd#(x, 0()) -> evenodd#(x, s(0()))}
      EDG:
       {}
       SCCS:
        
        Qed