¿Cuál sería la función para hacer una fórmula falsa?

Question

Produzca un contraejemplo para demostrar que el siguiente wfs no es lógicamente válida:

$$(\exists x)(\forall y)(A (x,y)\land ¬A (y,x)\implies[A (x,x) \iff A(y,y)])$$

He probado estas interpretaciones para ver que el wfs no es válido pero ninguna funciona:

Dominio= $\mathbb N, A(x,y)=x<y$

Dominio= $\mathbb N, A(x,y)=x=y$

Dominio= $\mathbb N, A(x,y)=x>y$

Dominio= $\mathbb N, A(x,y)=x$ e y son pares/Impares

Answer 1

Dos consejos

Primero, tienes la declaración:

$$(\exists x)(\forall y)(A (x,y)\land ¬A (y,x)\rightarrow [A (x,x) \leftrightarrow A(y,y)])$$

(He sustituido el $\implies$ con $\rightarrow$ y $\iff$ con $\leftrightarrow$ ya que los primeros se utilizan normalmente para las afirmaciones metrológicas sobre la implicación lógica y la equivalencia)

pero quieres que sea falso. OK, así que queremos:

$$\neg (\exists x)(\forall y)(A (x,y)\land ¬A (y,x)\rightarrow [A (x,x) \leftrightarrow A(y,y)])$$

que sea cierto. Bueno, puede ayudar a empujar la negación hacia adentro:

$$\neg (\exists x)(\forall y)(A (x,y)\land ¬A (y,x)\rightarrow [A (x,x) \leftrightarrow A(y,y)]) \Leftrightarrow$$

$$(\forall x)(\exists y)(A (x,y)\land ¬A (y,x)\land \neg [A (x,x) \leftrightarrow A(y,y)]) \tag{*}$$

Esto es probablemente un poco más fácil de trabajar y pensar que el original. Por ejemplo, debería quedar claro que la relación $A$ no puede ser simétrica.

En segundo lugar, si los mundos "típicos" no funcionan como contraejemplos, se puede intentar inventar un mundo que tenga uno o más objetos $a$ , $b$ , $c$ ..., que están o no en alguna relación $A$ entre sí, sin ni siquiera intentar interpretar lo que significan esos objetos y esa relación.

De hecho, para hacer esto de forma algo sistemática, se podría considerar primero un mundo en el que hay un objeto $a$ Veremos si podemos construir un contraejemplo, y si no, añadiremos más objetos si es necesario. Ahora, con un objeto no vas a poder satisfacer $(*)$ ya que necesitaría ambos $A(a,a)$ y $\neg A(a,a)$ .

Bien, pero ¿qué pasa si añadimos un segundo objeto $b$ ? Bueno, eso tampoco va a funcionar: sin tener en cuenta el bicondicional, necesitas $A(a,b)$ y $\neg A(b,a)$ para satisfacer la declaración de $a$ pero también necesitas $A(b,a)$ y $\neg A(a,b)$ para satisfacer la declaración de $b$ Así que ahí también hay una contradicción.

Bien, ¿entonces qué hay de añadir un tercero? ¿O tal vez un cuarto? Pruébalo y verás qué pasa. Por supuesto, a medida que tenga más objetos, es posible que quiera empezar a utilizar una pequeña tabla para llevar la cuenta de las relaciones que tiene o no tiene, es decir, algo así como

\begin{array}{c|c|c|c|c|} A&a&b&c&d\\ \hline a&1&1&0&0\\ \hline b&0&0&..&..\\ \hline c&1&..&..&..\\ \hline d&1&..&..&..\\ \hline \end{array}

Buena suerte.