Cardinalidad de tautologías de lógica proposicional

Question

Me pregunto cuantas tautologías en lógica proposicional. Estoy pensando que debe ser por lo menos contable, desde ($P{1} \wedge P{2} \wedge \cdots P{n}) \models P{i}$ debe ser una tautología para cualquier número natural $n$ y cualquier $i \in {1,2,\cdots,n}$, donde cada $P_{k}$ es un símbolo de oración $k \in \mathbb{N}$.

Pero igual no, ¿hay? ¿¿Uno explicar/Mostrar? Estoy seguro de que esto se ha pedido antes en algún lugar - se agradecería cualquier referencia. ¡Gracias!

Atentamente,

Vien

Answer 1

Estoy suponiendo que tu lengua tiene solamente un número contable de variables proposicionales. En este caso, usted puede mostrar fácilmente que el número de proposiciones para empezar es contable (sugerencia: el conjunto de cadenas finitas sobre un lenguaje contable es contable).

Por lo tanto no puede existir más que un conjunto contable de tautologías. En la otra dirección, es más simple si $p_i$ es una variable proposicional entonces $p_i\to p_i$ es una tautología. Por lo tanto, hay exactamente $\aleph_0$.

Answer 2

Supongamos que el lenguaje sólo tiene una variable proposicional y su única conectivo consiste en el material condicional C. La cardinalidad del conjunto de todas las finito de cadenas para que el lenguaje es como en la mayoría de los contables. Desde todas las tautologías venir como finito de cadenas, se sigue que el conjunto de todas las tautologías viene como en la mayoría de los contables.

Ahora, el Cpp viene como una tautología en este idioma. En consecuencia, se sostiene que para todos los valores de verdad en la verdad de que el Cpp se evalúa como true. Todas las fórmulas se califican como de verdad-funcional. En consecuencia, si una fórmula $\alpha$ evalúa a true o false, entonces C$\alpha$$\alpha$ se evalúa como true. De ello se deduce que la regla de uniforme sustitución puede aplicarse a tautologías. En consecuencia, si nos uniformemente sustituir p con Cpp, que se denota p/Cpp de ahora en adelante, en cualquier fórmula $\beta$, entonces el resultado de la sustitución nos da una fórmula $\beta$' tal que $\beta$' califica como una tautología.

Ahora, vamos a formar una secuencia que inicia con la Cpp como su primera fórmula. Definir la (n+1) fórmula de la secuencia como el resultado de p/Cpp en la fórmula n. Por ejemplo, desde la primera fórmula de nuestra secuencia es Cpp, CCppCpp es la segunda fórmula de nuestra secuencia. Desde CCppCpp es la segunda fórmula, CCCppCppCCppCpp es la tercera. Puesto que p aparece en la (n+1) fórmula no importa lo que la fórmula n es, de la fórmula (n+1) siempre se puede obtener formado. Por lo tanto, tenemos una interminable secuencia de tautologías en este idioma. En consecuencia, este lenguaje tiene countably muchos tautologías.