YES

Problem:
 not(true()) -> false()
 not(false()) -> true()
 odd(0()) -> false()
 odd(s(x)) -> not(odd(x))
 +(x,0()) -> x
 +(x,s(y)) -> s(+(x,y))
 +(s(x),y) -> s(+(x,y))

Proof:
 DP Processor:
  DPs:
   odd#(s(x)) -> odd#(x)
   odd#(s(x)) -> not#(odd(x))
   +#(x,s(y)) -> +#(x,y)
   +#(s(x),y) -> +#(x,y)
  TRS:
   not(true()) -> false()
   not(false()) -> true()
   odd(0()) -> false()
   odd(s(x)) -> not(odd(x))
   +(x,0()) -> x
   +(x,s(y)) -> s(+(x,y))
   +(s(x),y) -> s(+(x,y))
  Matrix Interpretation Processor: dim=1
   
   interpretation:
    [+#](x0, x1) = 3x0 + 2x1 + 1,
    
    [odd#](x0) = 6x0 + 1,
    
    [not#](x0) = 2x0 + 4,
    
    [+](x0, x1) = 4x0 + 5x1,
    
    [s](x0) = x0 + 5,
    
    [odd](x0) = 2,
    
    [0] = 5,
    
    [false] = 2,
    
    [not](x0) = x0,
    
    [true] = 2
   orientation:
    odd#(s(x)) = 6x + 31 >= 6x + 1 = odd#(x)
    
    odd#(s(x)) = 6x + 31 >= 8 = not#(odd(x))
    
    +#(x,s(y)) = 3x + 2y + 11 >= 3x + 2y + 1 = +#(x,y)
    
    +#(s(x),y) = 3x + 2y + 16 >= 3x + 2y + 1 = +#(x,y)
    
    not(true()) = 2 >= 2 = false()
    
    not(false()) = 2 >= 2 = true()
    
    odd(0()) = 2 >= 2 = false()
    
    odd(s(x)) = 2 >= 2 = not(odd(x))
    
    +(x,0()) = 4x + 25 >= x = x
    
    +(x,s(y)) = 4x + 5y + 25 >= 4x + 5y + 5 = s(+(x,y))
    
    +(s(x),y) = 4x + 5y + 20 >= 4x + 5y + 5 = s(+(x,y))
   problem:
    DPs:
     
    TRS:
     not(true()) -> false()
     not(false()) -> true()
     odd(0()) -> false()
     odd(s(x)) -> not(odd(x))
     +(x,0()) -> x
     +(x,s(y)) -> s(+(x,y))
     +(s(x),y) -> s(+(x,y))
   Qed