Demuestre que {, ¬} es adecuado.

Question

Así que he estado pensando últimamente en cómo mostrar ese conjunto { $\lor, \lnot$ } es adecuado. He encontrado algunas ideas sobre cómo tendría que construir mi prueba, aunque no estoy muy seguro de cómo procesar ni si mis pensamientos son buenos.

En primer lugar, pensé que podía confiar en el hecho de que para cada fórmula $\psi$ existe una fórmula equivalente $\omega$ en DNF. Eso me daría un conjunto adecuado de S = { $\land, \lnot, \lor$ }. Entonces, tendría que demostrar, que puedo construir $\land$ conectivo de B = { $\lor, \lnot$ } set. Sin embargo, ¿cómo demuestro que si puedo construir conectivas de un conjunto adecuado S utilizando sólo conectivas del conjunto B, entonces el conjunto B es adecuado?

Otra idea fue utilizar la inducción estructural para mostrar el conjunto { $\lor, \lnot$ } es adecuado, para ello, sin embargo, no estoy seguro de cómo construir tanto la base, así como el paso de inducción.

Answer 1

Digamos que un $n$ -place Función booleana $G$ es realizado por un wff $\alpha$ cuyos símbolos de sentencia atómica son $A_1,...,A_n$ si $G(X_1,...,X_n)$ es igual al valor de verdad de $\alpha$ cuando $A_1,...,A_n$ reciben los valores de verdad $X_1,...,X_n$ respectivamente.

La clave para responder a tu pregunta es el siguiente resultado.

Teorema . Cada $n$ -place Función booleana $G$ se realiza mediante unos $\alpha$ .

Prueba . Si $G$ es constantemente falso, entonces $A_1 \wedge \neg A_1$ realiza $G$ . De lo contrario, supongamos que hay $k$ puntos en los que $G$ es cierto: $$X_1 = (X_{11},...,X_{1n}),...,X_k=(X_{k1},...,X_{kn}).$$

Ahora dejemos que $\beta_{ij}$ sea $A_j$ o $\neg A_j$ según $X_{ij}$ es verdadero o falso. Sea $\gamma_i = \beta_{i1} \wedge ... \wedge \beta_{in}$ y que $\alpha = \gamma_1 \vee ... \vee \gamma_k$ . Ahora compruebe que $\alpha$ realiza $G$ (Se lo dejo como ejercicio instructivo). QED

Observación . Observe que $\alpha$ en la prueba anterior está en DNF. A partir de esta observación y del teorema que acabamos de demostrar, vemos que $\{\vee, \wedge, \neg \}$ es adecuada.

Por último, tenemos

Teorema . El conjunto $\{\vee, \neg \}$ es adecuada.

Prueba . Sea $\alpha$ sea un wff que utilice sólo conectivos en $\{\vee, \wedge, \neg \}$ . Podemos demostrar por inducción en $\alpha$ que existe un wff tautológicamente equivalente $\alpha '$ utilizando sólo conectivos en $\{\vee, \neg \}$ . Y de esto se deduce que $\{ \vee, \neg \}$ es adecuada, ya que si $\alpha$ realiza $G$ y $\alpha \equiv \alpha '$ entonces $\alpha '$ realiza $G$ también.

El caso base en el que $\alpha$ es un símbolo de sentencia atómica es trivial (sea $\alpha '$ sea $\alpha$ ).

Para el paso inductivo, supongamos primero $\alpha$ es $\neg \beta$ . Entonces $\alpha '$ sea $\neg \beta '$ .

En segundo lugar, supongamos $\alpha$ es $\beta \wedge \gamma$ . Entonces $\alpha '$ sea $\neg(\neg \beta ' \vee \neg \gamma ')$ . Es fácil comprobar que $\alpha \equiv \alpha '$ . QED

Answer 2

B resultará adecuada, reinterpretando $\land$ en S como abreviatura de una fórmula con sólo las conectivas $\lor$ y $\lnot$ .

Por lo tanto, las formas normales disyuntivas funcionarían como si tuvieran abreviaturas.

Por ejemplo, una forma normal disyuntiva como

((A $\land$ B) $\lor$ ( $\lnot$ A $\land$ B))

consistiría en una abreviatura de

( $\lnot$ ( $\lnot$ A $\lor$$ \no $B)$ \lor $$\lnot$ ( $\lnot$$ \no $A$ \lor $$\lnot$ B)).

Pero, ¿está lo anterior en forma normal disyuntiva? (mi libro implica que no está en forma normal disyuntiva por definición y también lo hace Wikipedia)

Si no es así, entonces la forma normal disyuntiva no es necesaria para demostrar la adecuación expresiva.

Así que, aquí hay otra posibilidad:

Obsérvese que toda adecuación expresiva significa que podemos representar toda función de verdad. Podríamos representar todas las funciones de verdad de aridad n mediante todos los bits posibles que tengan (2^n) miembros (por (2^n) entiendo 2 a la enésima potencia).

Por lo tanto, tenemos una especie de orden natural para las salidas de las funciones de verdad de la siguiente manera:

[0, 1]

[00, 01, 10, 11]

[0000, 0001, 0010, ..., 1110, 1111]

[00000000, 000000001, ..., 11111111]

Por lo tanto, se podría intentar demostrar que existe una fórmula con $\lor$ y $\lnot$ que siempre puede dar salida a cualquiera de esos bits para una función de verdad de una aridad n dada, y luego tener algún tipo de inducción que nos permita subir una aridad.

Edición: El post muestra básicamente la idea clave de su artículo _Teoría general de las proposiciones elementales_ .

A grandes rasgos, la idea es que demuestres que puedes obtener las siguientes tablas de verdad:

p  F1(p)  F2(p)  F3(p)  F4(p)
0  0      0      1      1
1  0      1      0      1

Entonces mostramos que para cualquier tabla de verdad donde la función tiene aridad n, podemos construir cada tabla de verdad para aridad (n+1). Post utiliza el término 'orden' para lo que nosotros llamamos aridad.