Probar que un conjunto de conectivas es inadecuada

Question

Es relativamente fácil demostrar que un determinado conjunto de conectivas es la adecuada. Esto es suficiente para mostrar que el estándar de las conectivas puede ser construido a partir de la serie dada. Está probado que el conjunto de $\{\lor, \land, \neg\}$ es la adecuada, y a partir de ese conjunto se puede inferir (aplicando De Morgan leyes y tal) $\{\lor, \neg\}$, $\{\land, \neg\}$ y $\{\to, \neg\}$ son también adecuados.

Sin embargo, estoy atascado tratando de entender cómo probar que un determinado conjunto de conectivas es insuficiente. Sé que tengo que demostrar que un estándar conectivo no se pueden construir utilizando sólo las conectivas de la serie, pero no puedo averiguar cómo hacerlo.

Para tu INFORMACIÓN, estoy tratando de probar que $\{\lor, \land\}$ $\{\leftrightarrow, \neg\}$ son inadecuados conjuntos de las conectivas.

Gracias de antemano.

Answer 1

Para $\{{\leftrightarrow},{\neg}\}$, aviso que si nos identificamos "verdadero" y "falso" con $1$ $0$ modulo $2$,$a\leftrightarrow b \equiv a+b+1 \pmod2$$\neg a \equiv a+1\pmod2$. Así que todo lo que podemos construir a partir de ellos estará representado por lineal de los polinomios modulo 2.

Podemos convertir esa idea de nuevo a una prueba directa de que no habla de la aritmética modular:

Lema. Suponga $f(x_1,\ldots,x_n)$ es una función Booleana construido a partir de $\leftrightarrow$$\neg$. A continuación, para $1\le i\le n$ posee , ya sea que $f$ no depende de $x_i$ a todos, o que invertir el valor de $x_i$ siempre va a invertir el valor de $f(x_1,\ldots,x_n)$.

Prueba. Por inducción estructural en $f$.

Desde $a\land b$ no tiene la propiedad especificada por el lema, no puede ser construido a partir de $\leftrightarrow$$\neg$.

Observe que la estructura de las pruebas de que un conjunto de conectivas es no adecuada es más variada que la estructura de las pruebas de que lo es. (Esto último es sólo una cuestión de mostrar que cada miembro de un conjunto adecuado puede ser expresado, que puede ser verificado por las tablas de verdad).

Answer 2

Hay un resultado en Robert Reckhow la tesis que caracteriza a la adecuada conjuntos de las conectivas. El resultado dice que, para un conjunto de conectivas para ser completo se necesita el siguiente:

• F y T (o fórmulas con estos valores),
• una extraña conjuntivo (conectivo, con arity mayor que 1 se llama extraño si se tiene un número impar de Ts en su tabla de verdad),
• un no-monótona conjuntivo (conectivo, que de inflexión de F a T va a hacer su cambio de valor de la T a la F).

Estas son las condiciones necesarias y suficientes para un conjunto de conectivas ser la adecuada. Si un conjunto de conectivas no es la adecuada, a continuación, se carece de una de estas. Tenga en cuenta que incluso las conectivas son cerrados bajo la composición así como la monotonía conectivas. Así que para demostrar que un conjunto de conectivas es insuficiente, por lo general es necesario para mostrar que

• todas las conectivas son monótonas, o
• todas las conectivas son incluso.

Para tus ejemplos, el primero es un conjunto de monotonía conectivas, el segundo es un conjunto de incluso conectivo. Así que no puede ser adecuado.

Answer 3

Sugerencia: Para el primer problema, probar, en principio, por inducción, que cualquier función proposicional $f(A)$ construido a partir de $\land$ $\lor$ siempre tendrá el valor de $1$ si $A$ valor $1$.

Necesitamos un similar "invariancia" la propiedad de las funciones construido a partir del conjunto $\{\leftrightarrow, \neg\}$. Yo sugeriría que el pensamiento de la tabla de verdad para una función $f(A,B)$ construido a partir de estas conectivas. Esta tabla de verdad ha $4$ entradas, correspondientes a las $4$ combinaciones posibles de valores de verdad de a$A$$B$. Demostrar por inducción que para todo $f$ construye a partir de nuestras dos conectivas, un número ($0$, $2$, o $4$) de las entradas se le asigna el valor True. Para el conectivo $\leftrightarrow$, hay un poco de detalle a mostrar que la si $g(A,B)$ es cierto para $2$ entradas, y $h(A,B)$ es cierto para $2$ entradas, $f(A,B)\leftrightarrow h(A,B)$ es cierto para un número par de entradas.

Answer 4

Para el primer problema con el que vamos a $\Phi$ el conjunto de proposiciones construido de la $a,\lor$, e $\land$. Puede ser descrito como sigue:

1. $a\in\Phi$.
2. Si $\varphi,\psi\in\Phi$,$\varphi\lor\psi,\varphi\land\psi\in\Phi$.
3. $\Phi$ es el más pequeño conjunto de proposiciones satisfactorio (1) y (2).

Ahora supongamos que $\varphi\in\Phi$, y considerar la tabla de verdad para $\varphi$:

$$\begin{array}{c|c} a&\varphi\\ \hline T&?_1\\ F&?_2 \end{array}$$

Yo afirmación de que el valor de verdad $?_1$ $T$ todos los $\varphi\in\Phi$, y por lo tanto $\lnot a\notin\Phi$.

Esto es claro en el caso de la proposición $a$. Supongamos que es verdad para las proposiciones $\varphi,\psi\in\Phi$. Luego tenemos el followint parcial de la tabla de verdad;

$$\begin{array}{c|c} a&\varphi&\psi&\varphi\lor\psi&\varphi\land\psi\\ \hline T&T&T&T&T \end{array}$$

Por lo tanto, es verdad lo de $\varphi\lor\psi$ $\varphi\land\psi$ como bueno, y por inducción es cierto para todos los $\varphi\in\Phi$.

Trate de encontrar una idea similar para el segundo problema: algunos de los bienes que $\leftrightarrow$ $\lnot$ conservar ese $\land,\lor$ o $\to$ no.