YES

TRS:

  f(x,y,z) -> g(<=(x,y),x,y,z)
  g(true(),x,y,z) -> z
  g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y))
  p(0()) -> 0()
  p(s(x)) -> x

max/plus interpretations on N:

  f_A(x1,x2,x3) = max{2, x1, x2, x3}
  f#_A(x1,x2,x3) = max{5, 5, 5, 1}
  g_A(x1,x2,x3,x4) = max{1, 2, x2, x3, x4}
  g#_A(x1,x2,x3,x4) = max{4, 3 + x1, 4, 4, 5}
  <=_A(x1,x2) = max{1, 1, -1}
  <=#_A(x1,x2) = max{0, 4, 0}
  true_A = 0
  true#_A = 0
  false_A = 4
  false#_A = 0
  p_A(x1) = max{2, -1 + x1}
  p#_A(x1) = max{6, 7}
  0_A = 1
  0#_A = 8
  s_A(x1) = max{0, 1 + x1}
  s#_A(x1) = max{0, x1}

precedence:

  f > g = <= = true = false = s > p > 0