Si una fórmula $$ contains at most one occurrence of any sentence letter, then $$ no es una tautología. Las únicas conectivas en mi sistema son $$ and $ ¬ $. I think I should attempt this by induction on the complexity of $$ (el número de conectivos). Entonces tenemos dos casos a considerar: o bien $ = ¬$ o $ = $ , donde $$, $$ satisfacen la hipótesis de inducción. Estoy atascado aquí, ya que no puedo encontrar una propiedad de las oraciones que contienen como máximo una ocurrencia de cualquier letra de la oración para explotar.
Respuesta
¿Demasiados anuncios?
BrianO
Puntos
8258
Por inducción a la complejidad de las fórmulas $\phi$ demostramos la afirmación más fuerte:
Si $\phi$ contiene como máximo una ocurrencia de cualquier variable proposicional, entonces $\phi$ no es una tautología ni una contradicción.
Supongamos que $\phi$ contiene como máximo una ocurrencia de cualquier variable proposicional.
Si $\phi$ es atómica, entonces es sólo una variable proposicional, por lo que no es una tautología y no es una contradicción, ya que hay asignaciones de valores a su variable que dan a la fórmula el valor Falso, y otras que le dan el valor Verdadero.
Si $\phi$ es $\neg \psi$ y el resultado es válido para $\psi$ entonces es evidente que se mantiene para $\phi$ también.
Supongamos ahora que $\phi$ es $\psi\to\theta$ . Como se muestra en esta respuesta relacionada , si $\psi \to \theta$ es una tautología, entonces hay una variable proposicional que aparece en ambos $\psi$ y $\theta$ . Así que $\phi$ no es una tautología. Si $\phi$ fuera una contradicción, entonces $\neg\phi \equiv (\psi\land\neg\theta)$ sería una tautología, por lo que $\psi$ tendría que ser una tautología. Pero $\psi$ también tiene como máximo una ocurrencia de cada variable, así que por hipótesis de inducción $\psi$ no es una tautología después de todo, por lo tanto $\phi$ no es una contradicción.
