Es un conocido metateorema que una fórmula proposicional que sólo tenga como conectiva lógica al bicondicional material "=" (la equivalencia de valor de verdad) es tautológica si y sólo si cada constante proposicional aparece un número par de veces. Por ejemplo, la fórmula [(p = q) = r] = [r = (q = p)] es tautológica pero la fórmula [(p = q) = r] = [r = (r = p)] no pues la r aparece un número impar de veces. Se notará que la primera fórmula es además un palíndromo.
Todo palíndromo repite su primera parte en sentido inverso, así es que los palíndromos que usen sólo bicondicionales materiales son un subconjunto (propio) de las tautologías que usan sólo bicondicionales materiales. Es decir, quien hable en palíndromos puede obtener la infalibilidad al precio de limitar su lenguaje a la conectiva "=". Claro, sería un lenguaje incapaz de expresar todas las funciones proposicionales, pero consideraciones de este tipo rara vez detienen a los lógicos o a los palindromistas.