¿Cómo probar un conjunto de conectivos sentenciales es incompleta?

Question

En la Página 52, Matemáticas, Introducción a la Lógica, Herbert B. Enderton（2ed),

Mostrar que $\{\lnot, \# \}$ no es completa.

Un conjunto de conectivos símbolos es completa, si cada función $G : \{F, T\}^n \to \{F, T\}$ $n > 1$ puede ser realizado por un wff(bien formado fórmula) utilizando sólo la conectivo símbolos de ella. Un hecho conocido es el conjunto $\{\lnot, \land \}$ es completa.

$\#$ es un tres-lugar sentential conectivo. Durante tres arbitrarias wffs, $A$, $B$ y $C$, $\#ABC$ es tautologically equilvalent a: $$(A\land B)\lor(A\land C)\lor(B\land C)$$

He aquí cómo ahora entiendo:

El problema puede reducirse a mostrar, dadas dos wffs $A$$B$, no hay nada tautologically equivalente a $A \land B$ mediante $\lnot$$\# $. Por simplicidad, suponga $A$ $B$ no son generadas por cualquier otro wffs y existe un número finito de wffs $\{ C_i:i \leq n\}$que no son generadas por otros wffs.

Si el tautogocial equilvalent de $A \land B$ existen, no se puede excluir la aparición de $C_i$.

También estoy tratando de usar la inducción, pero me atoré al $C_i$s están involucrados.

Answer 1

Peter Smith enfoque es probablemente la mejor manera de pensar acerca de este tipo de problemas en general. En este caso hay otro bastante simple enfoque. Observe primero que el conectivo $\#$ es simétrica en sus tres argumentos: si $XYZ$ es cualquier permutación de $ABC$, $\#ABC$ es equivalente a $\#XYZ$. De esta manera es fácil ver que todas las combinaciones de exactamente dos frases, letras de $A$ $B$ $\#$ son equivalentes a $\#AAB$ o a $\#ABB$. Por otra parte, $\#AAB$ equivale simplemente a $A$, e $\#ABB$$B$; esto sugiere tratando de mostrar que mientras trabajamos en la mayoría de las dos frases, cartas, $\#$ básicamente no hace nada.

Reclamo: Cada wff que puede ser construido a partir de la sentencia de cartas de $A$ $B$ y las conectivas $\neg$ $\#$ es equivalente a uno de $A,B,\neg A$, e $\neg B$.

Prueba: La afirmación es fácilmente demostrado por inducción sobre la complejidad de la wff. Es cierto para wffs sin conectivo: son, simplemente,$A$$B$. Supongamos que $\varphi$ tiene al menos un conectivo. A continuación, $\varphi$ es $\neg\psi$ para algunos wff $\psi$ o $\#\psi_0\psi_1\psi_2$ para wffs $\psi_0,\psi_1$, e $\psi_2$. Supongamos que $\varphi=\neg\psi$. La hipótesis de inducción se asegura de que $\psi$ es equivalente a uno de $A,B,\neg A$, e $\neg B$, e $\varphi$ es por tanto equivalente a uno de $\neg A,\neg B,A$, e $B$, respectivamente.

Ahora supongamos que $\varphi=\#\psi_0\psi_1\psi_2$. De nuevo la hipótesis de inducción se asegura de que cada uno de $\psi_0,\psi_1$, e $\psi_2$ es equivalente a uno de $A,B,\neg A$, e $\neg B$. Cualquier conjunto de tres elegidos de $\{A,B,\neg A,\neg B\}$ necesariamente contiene dos copias de uno de los cuatro wffs o un wff y su negación, por lo $\varphi$ es equivalente a $\#XXY$ o $\#X\neg XY$ algunos $X,Y\in\{A,B,\neg A,\neg B\}$. Pero $\#XXY$ es equivalente a $X$, e $\#X\neg XY$ es equivalente a $Y$, por lo que en cada caso $\varphi$ es equivalente a uno de $A,B,\neg A$, e $\neg B$. El reclamo sigue ahora por inducción. $\dashv$

Desde $A\land B$ no es equivalente a $A,B,\neg A$, o $\neg B$, $\{\neg,\#\}$ no es completa.

(He implícitamente utilizado el hecho de que si $\psi_0,\psi_1$, e $\psi_2$ son equivalentes a $\psi_0',\psi_1'$, e $\psi_2'$, respectivamente, a continuación, $\#\psi_0\psi_1\psi_2$ es equivalente a $\#\psi_0'\psi_1'\psi_2'$. Esto es claro a partir de la consideración de las correspondientes tablas de verdad.)

Answer 2

Es sufficies para probar el caso $n=2$.

Deje $G_1,G_2,G_3,G_4:\{C_0,C_1\}\rightarrow\{T,F\}$ ser dada por $G_1(C_0)=T=G_1(C_1)$, $G_2(C_0)=T,G_2(C_1)=F$, $G_3(C_0)=F,G_3(C_1)=T$ y $G_4(C_0)=F=G_4(C_1).$

$(1)$ Vamos a demostrar por inducción sobre las fórmulas construida a lo largo de $\{C_0,C_1\}$ en el idioma $\{¬,\#,@\}$ que no existe una fórmula equivalente a $C_0\wedge C_1$ o $¬(C_0\wedge C_1)$ donde $$@ABC=(A\vee B)\wedge(A\vee C)\wedge(B\vee C).$$

Usted tiene que demostrar que para cualquier fórmulas $A,B,C$, $\#ABC$ y $@ABC$ son equivalentes; (sugerencia: $\#ABC$ es verdadera si y sólo si al menos dos elementos de $A,B,C$ son verdaderas, y lo mismo vale para los $@ABC$)

Esto claramente tiene para atómica fórmulas.

Supongamos que $A,B,C$ son fórmulas que la condición de $(1)$ mantiene. A continuación, $(1)$ mantiene para $¬A$. $(2)$

Supongamos $\#ABC$ es equivalente a $C_0\wedge C_1$,$G_1(\#ABC)=T$, por lo que podemos suponer sin pérdida de generalidad que $G_1(A)=T$; debido a la forma de $\#ABC$. También se $G_i(\#ABC)=F$$i=2,3,4$, luego por la forma de $\#ABC$ se sigue que $G_i(A)=F$$i=2,3,4$, lo que implica $A$ es equivalente a $C_0\wedge C_1$, contradiciendo la hipótesis inductiva, por lo $(1)$ mantiene para $\#ABC$.$(3)$

Si $\#ABC$, el equivalente a $¬(C_0\wedge C_1)$, $@¬A¬B¬C$ sería el equivalente a $C_0\wedge C_1$, $\#¬A¬B¬C$ sería equivalente a $C_0\wedge C_1$, contradiciendo $(2)$$(3)$.

Desde $\#ABC$ $@ABC$ son equivalentes, esto termina la prueba.

Answer 3

En pp. 12-13 de A Introducción Concisa a la Lógica Matemática , por W. Rautenberg, el autor señala que$\{\lnot, \# \}$ define con precisión la clase de funciones booleanas auto-duales . De este modo, en este caso particular, fácilmente se deduce que ningún operador no dual (como cualquier operador booleano esencialmente binario) puede definirse a partir de$\lnot$ y$\#$ solo.