3.2: Tablas de Verdad y Proposiciones Generadas por un Conjunto

Tablas de la Verdad

Considera la proposición compuesta\(c= (p \land q)\lor (\neg q \land r)\text{,}\) donde\(p\text{,}\)\(q\text{,}\) y\(r\) son proposiciones. Este es un ejemplo de una proposición generada por\(p\text{,}\)\(q\text{,}\) y\(r\text{.}\) Vamos a definir esta terminología más adelante en la sección. Dado que cada una de las tres proposiciones simples tiene dos posibles valores de verdad, se deduce que hay ocho combinaciones diferentes de valores de verdad que determinan un valor para\(c\text{.}\) Estos valores se pueden obtener de una tabla de verdad para\(c\text{.}\) Para construir la tabla de verdad, construimos a\(c\) partir de \(p\text{,}\)\(q\text{,}\)y\(r\) y de los operadores lógicos. El resultado es la tabla de verdad a continuación. Estrictamente hablando, las tres primeras columnas y la última columna conforman la tabla de la verdad para\(c\text{.}\) Las otras columnas son espacio de trabajo necesario para construir hasta\(c\text{.}\)

Tabla\(\PageIndex{1}\): Tabla de Verdad para\(c= (p \land q)\lor (\neg q \land r)\)

\(p\)	\(q\)	\(r\)	\(p\land q\)	\(\neg q\)	\(\neg q\land r\)	\((p\land q)\lor (\neg q\land r)\)
\ (p\) ">\(0\)	\ (q\) ">\(0\)	\ (r\) ">\(0\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(1\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(0\)
\ (p\) ">\(0\)	\ (q\) ">\(0\)	\ (r\) ">\(1\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(1\)	\ (\ neg q\ tierra r\) ">\(1\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(1\)
\ (p\) ">\(0\)	\ (q\) ">\(1\)	\ (r\) ">\(0\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(0\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(0\)
\ (p\) ">\(0\)	\ (q\) ">\(1\)	\ (r\) ">\(1\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(0\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(0\)
\ (p\) ">\(1\)	\ (q\) ">\(0\)	\ (r\) ">\(0\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(1\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(0\)
\ (p\) ">\(1\)	\ (q\) ">\(0\)	\ (r\) ">\(1\)	\ (p\ tierra q\) ">\(0\)	\ (\ neg q\) ">\(1\)	\ (\ neg q\ tierra r\) ">\(1\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(1\)	\ (r\) ">\(0\)	\ (p\ tierra q\) ">\(1\)	\ (\ neg q\) ">\(0\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(1\)	\ (r\) ">\(1\)	\ (p\ tierra q\) ">\(1\)	\ (\ neg q\) ">\(0\)	\ (\ neg q\ tierra r\) ">\(0\)	\ ((p\ tierra q)\ lor (\ neg q\ tierra r)\) ">\(1\)

Tenga en cuenta que las tres primeras columnas de la tabla de verdad son una enumeración de los ocho enteros binarios de tres dígitos. Esto estandariza el orden en que se listan los casos. En general, si\(c\) se genera por proposiciones\(n\) simples, entonces la tabla de verdad para\(c\) tendrá\(2^n\) filas siendo las primeras\(n\) columnas una enumeración de los enteros binarios de\(n\) dígitos. En nuestro ejemplo, podemos ver de un vistazo que para exactamente cuatro de los ocho casos,\(c\) será cierto. Por ejemplo, si\(p\) y\(r\) son verdaderas y\(q\) son falsas (el sexto caso), entonces\(c\) es verdad.

\(S\)Sea cualquier conjunto de proposiciones. Daremos dos definiciones de una proposición generada por S. La primera es un poco imprecisa, pero debe ser clara. La segunda definición se llama definición recursiva. Si te resulta confuso, usa la primera definición y vuelve a la segunda más tarde.

Proposiciones Generadas por un Conjunto

Definición \(\PageIndex{1}\): Proposition Generated by a Set

\(S\)Sea cualquier conjunto de proposiciones. Una proposición generada por\(S\) es cualquier combinación válida de proposiciones en\(S\) conjunción, disyunción y negación. O, para ser más precisos,

1. Si\(p \in S\text{,}\) entonces\(p\) es una proposición generada por\(S\text{,}\) y
2. Si\(x\) y\(y\) son proposiciones generadas por\(S\text{,}\) entonces así son\((x)\text{,}\)\(\neg x\text{,}\)\(x\lor y\), y\(x\land y\text{.}\)

Nota\(\PageIndex{1}\)

No hemos incluido lo condicional y lo bicondicional en la definición porque ambos pueden generarse a partir de conjunción, disyunción y negación, como veremos más adelante.

Si\(S\) es un conjunto finito, entonces podemos usar terminología ligeramente diferente. Por ejemplo, si\(S = \{p, q, r\}\text{,}\) pudiéramos decir que una proposición es generada por\(p, q\text{,}\) y\(r\) en lugar de\(\{p, q, r\}\text{.}\)

Se acostumbra utilizar la siguiente jerarquía para interpretar proposiciones, con paréntesis anulando este orden:

• Primero: Negación
• Segundo: Conjunción
• Tercero: Disjunction
• Cuarto: La operación condicional
• Quinto: La operación bicondicional

Dentro de cualquier nivel de la jerarquía, trabajar de izquierda a derecha. Usando estas reglas,\(p \land q \lor r\) se toma como significado\((p \land q)\lor r\text{.}\) Estas reglas de precedencia son universales, y son exactamente las que utilizan los lenguajes informáticos para interpretar expresiones lógicas.

Ejemplo\(\PageIndex{1}\): Examples of the Hierarchy of Logical Operations

Algunas expresiones abreviadas y sus versiones entre paréntesis:

1. \(p \land q \land r\)es\((p \land q) \land r\text{.}\)
2. \(\neg p \lor \neg r\)es\((\neg p) \lor (\neg r)\text{.}\)
3. \(\neg \neg p\)es\(\neg (\neg p)\text{.}\)
4. \(p \leftrightarrow q\land r\rightarrow s \)es\(p \leftrightarrow ((q\land r)\rightarrow s)\text{.}\)

Una proposición generada por un conjunto no\(S\) necesita incluir cada elemento de\(S\) en su expresión. Por ejemplo,\(\neg q \land r\) es una proposición generada por\(p, q\text{,}\) y\(r\text{.}\)

Ejercicios

Ejercicio\(\PageIndex{1}\)

Construir las tablas de verdad de:

1. \(\displaystyle p\lor p\)
2. \(\displaystyle p\land (\neg p)\)
3. \(\displaystyle p\lor (\neg p)\)
4. \(\displaystyle p \land p\)

Contestar

1. \(\displaystyle \begin{array}{cc} p & p\lor p \\ \hline 0 & 0 \\ 1 & 1 \\ \end{array}\)
2. \(\displaystyle \begin{array}{ccc} p & \neg p & p\land (\neg p) \\ \hline 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array}\)
3. \(\displaystyle \begin{array}{ccc} p & \neg p & p\lor (\neg p) \\ \hline 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array}\)
4. \(\displaystyle \begin{array}{cc} p & p\land p \\ \hline 0 & 0 \\ 1 & 1 \\ \end{array}\)

Ejercicio\(\PageIndex{2}\)

Construir las tablas de verdad de:

1. \(\displaystyle \neg (p\land q )\)
2. \(\displaystyle p \land (\neg q)\)
3. \(\displaystyle (p \land q)\land r\)
4. \(\displaystyle (p \land q) \lor (q \land r)\lor (r \land p)\)
5. \(\displaystyle \text{ }\neg p\lor \neg q\)
6. \(\displaystyle p \lor q \lor r \lor s\)

Ejercicio\(\PageIndex{3}\)

Vuelva a escribir lo siguiente con el menor número posible de paréntesis extraños:

1. \(\displaystyle (\neg ((p) \land (r))) \lor (s)\)
2. \(\displaystyle ((p) \lor (q)) \land ((r) \lor (q))\)

Contestar

1. \(\displaystyle \neg (p\land r)\lor s\)
2. \(\displaystyle (p\lor q) \land (r\lor q)\)

Ejercicio\(\PageIndex{4}\)

¿En qué orden se realizan las operaciones en las siguientes proposiciones?

1. \(\displaystyle p \lor \neg q \lor r\land \neg p\)
2. \(\displaystyle p \land \neg q \land r \land \neg p\)

Ejercicio\(\PageIndex{5}\)

Determinar el número de filas en la tabla de verdad de una proposición que contiene cuatro variables\(p, q, r, \textrm{ and } s\text{.}\)

Contestar

\(2^4 = 16\)filas.

Ejercicio\(\PageIndex{6}\)

Si hay 45 líneas en una hoja de papel, y quieres reservar una línea por cada línea en una tabla de verdad, ¿qué tan grande podría\(\lvert S\rvert \) ser si puedes escribir tablas de verdad de proposiciones generadas por\(S\) en la hoja de papel?