Algumas das fórmulas a seguir são válidas (tautologias), outras não. Para cada fórmula, demonstre se ela é válida ou defina uma interpretação que a interprete como sendo falsa.
Passo 1
O enunciado pede para ver se a fórmula (\forall x) p(x) \rightarrow p(x) é válida (tautologia) ou, em caso contrário, dar uma interpretação que a torne falsa. O conteúdo é Semântica de Lógica de 1ª ordem, vamos precisar da definição de satisfatibilidade de
e de conectivo “
”.
Passo 2
Seja
qualquer estrutura e seja
qualquer atribuição de variáveis. Precisamos mostrar que
. Avaliamos a implicação em dois casos:
Caso 1: . Pela semântica de
, para todo
vale
. Em particular, para
temos
. Então o antecedente é verdadeiro e o consequente também, logo a implicação é verdadeira.
Caso 2: . Aqui o antecedente da implicação é falso, e uma implicação com antecedente falso é sempre verdadeira. Portanto, em qualquer caso a implicação vale.
Caso 1:
Caso 2:
Passo 3
Como o argumento não depende de nenhuma escolha especial de
ou de
, a fórmula é verdadeira em toda interpretação e toda atribuição. Logo, é válida (tautologia).
Resposta
A fórmula é válida (tautologia).