La capacidad de una declaración lógica para representar una función de verdad de dos lugares.

Question

¿Cómo puedo determinar qué funciones de verdad de dos lugares se pueden representar usando una declaración lógica construida a partir de un subconjunto de dos conectores lógicos en $ \{\rightarrow, \wedge, \vee ,\equiv \}$ ?

por ejemplo $\{\rightarrow, \wedge\}$

Answer 1

Para cualquier función de verdad X de dos lugares, podemos escribir su tabla de verdad de la siguiente manera:

p   q   X(p, q)
0   0   ?1
0   1   ?2
1   0   ?3
1   1   ?4

donde, por supuesto, ?1, ?2, ?3 y ?4 pertenecen a {0, 1}. Note que todas las fórmulas bien formadas de la lógica proposicional pueden construirse a partir de las variables y los conectivos. Por ejemplo (usando notación polaca) la fórmula CKpqNDrArs se puede construir a través de la secuencia (p, q, Kpq, r, r, s, Ars, DrArs, NDrArs, CKpqNDrArs). Así, podemos construir cualquier fórmula bien formada usando dos (o 1 o 3 o 4) conectivos de esta manera, y ver cómo funcionan sus tablas de verdad y ver si las columnas de las tablas de verdad terminan repitiéndose o si obtenemos nuevas columnas. Por ejemplo... si solo tenemos la implicación "C", podemos escribir

p  q   Cpq  CpCpq Cpp  Cqp  Cqq  CqCpq CCpqp  CCpqq  CCpqCpq 
0  0   1    1     1    1               0      0      
0  1   1    1     1    0               0      1
1  0   0    0     1    1               1      1
1  1   1    1     1    1               1      1

He dejado algunos espacios en blanco, ya que tienen valores duplicados de otro que ya tenemos. Generé este ejemplo (manualmente) usando (p, q, Cpq) como conjunto inicial y encontrando todas las posibles sustituciones en Cxy a partir de ese conjunto. Luego, dejando solo aquellas columnas que no son duplicadas de alguna otra columna, podemos usar cada fórmula bien formada encima de la columna para ver si obtenemos una nueva columna que no está en nuestra lista. Eventualmente, dado que el número de columnas posibles es finito, eventualmente podremos ver qué funciones de verdad pueden representarse (y también podríamos demostrar esto usando el conjunto de todas las fórmulas encima de la columna, como usé el conjunto inicial anterior, que en el siguiente paso solo obtendremos una columna que ya tenemos. Dado que este procedimiento puede generar todas las fórmulas en dos variables, se seguirá que ninguna otra función de verdad binaria puede generarse usando solo los conectivos que hemos seleccionado).