Sección 4: Sentencias de SL
- Page ID
- 101653
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)La frase 'Las manzanas son rojas, o las bayas son azules' es una oración del inglés, y la oración '\(A\)(\(B\))' es una oración de SL. Aunque podemos identificar frases de inglés cuando las encontramos, no tenemos una definición formal de 'oración de inglés'. En SL, es posible definir formalmente lo que cuenta como sentencia. Este es un aspecto en el que un lenguaje formal como SL es más preciso que un lenguaje natural como el inglés.
Es importante distinguir entre el lenguaje lógico SL, que estamos desarrollando, y el lenguaje que utilizamos para hablar de SL. Cuando hablamos de un idioma, el lenguaje del que estamos hablando se llama el lenguaje objeto. El lenguaje que usamos para hablar del lenguaje objeto se llama metalenguaje.
El lenguaje objeto en este capítulo es SL. El metalenguaje es el inglés, no el inglés conversacional, sino el inglés complementado con cierto vocabulario lógico y matemático. La frase '(\(A\)\(B\))' es una oración en el lenguaje objeto, ya que utiliza únicamente símbolos de SL. La palabra 'oración' no es en sí misma parte de SL, sin embargo, por lo que la frase 'Esta expresión es una oración de SL' no es una oración de SL. Se trata de una frase en el metalenguaje, una frase que utilizamos para hablar de SL.
En esta sección, daremos una definición formal por 'sentencia de SL. ' La definición misma se dará en inglés matemático, el metalenguaje.
letras de oración con subíndices, según sea necesario |
\(A\),\(B\),\(C\),... ,\(Z\) \(A\)1,\(B\) 1,\(Z\) 1,\(A\) 2,\(A\) 25,\(J\) 375,... |
conectivos | ¬, &, ↓, →, ↔ |
paréntesis | (,) |
Define una expresión de sl como cualquier cadena de símbolos de SL. Toma cualquiera de los símbolos de SL y escríbelos, en cualquier orden, y tienes una expresión.
Fórmulas bien formadas
Dado que cualquier secuencia de símbolos es una expresión, muchas expresiones de SL serán gobbledegook. Una expresión significativa se llama fórmula bien formada. Es común usar el acrónimo w; el plural es ws.
Obviamente, las letras de oración individuales como\(A\) y\(G\) 13 serán ws. Podemos formar más ws a partir de estos mediante el uso de los diversos conectivos. Usando la negación, podemos obtener ¬\(A\) y ¬\(G\) 13. Usando la conjunción, podemos obtener\(A\) &\(G\) 13,\(G\) 13 &\(A\),\(A\) &\(A\), y\(G\) 13 y\(G\) 13. También podríamos aplicar negación repetidamente para obtener ws como ¬¬\(A\) o aplicar negación junto con conjunción para obtener ws como ¬ (\(A\)&\(G\) 13) y ¬ (\(G\)13 &¬\(G\) 13). Las combinaciones posibles son infinitas, incluso comenzando solo con estas dos letras de oración, y hay indefinidamente muchas letras de oración. Entonces no tiene sentido tratar de enumerar todos los ws.
En su lugar, describiremos el proceso mediante el cual se pueden construir wf s. Considerar negación: Dado cualquier\(\mathcal{A}\) wde SL, ¬\(\mathcal{A}\) es un wde SL. Aquí es importante que no\(\mathcal{A}\) sea la letra de la oración\(\mathcal{A}\). Más bien, se trata de una variable que representa cualquier wen absoluto. Observe que esta variable no\(\mathcal{A}\) es un símbolo de SL, por lo que ¬ no\(\mathcal{A}\) es una expresión de SL. En cambio, es una expresión del metalenguaje que nos permite hablar indefinitamente de muchas expresiones de SL: todas las expresiones que comienzan con el símbolo de negación. Porque\(\mathcal{A}\) es parte del metalenguaje, se le llama metavariable.
Podemos decir cosas similares para cada una de las otras conectivas. Por ejemplo, si\(\mathcal{A}\) y\(\mathcal{B}\) son w de SL, entonces (\(\mathcal{A}\)&\(\mathcal{B}\)) es un w de SL. Proporcionando cláusulas como esta para todos los conectivos, llegamos a la siguiente definición formal para una fórmula bien formada de SL:
1. Toda oración atómica es un w.
2. Si\(\mathcal{A}\) es un wff, entonces ¬\(\mathcal{A}\) es un wff de SL.
3. Si\(\mathcal{A}\) y\(\mathcal{B}\) son ws, entonces (\(\mathcal{A}\)&\(\mathcal{B}\)) es un w.
4. Si\(\mathcal{A}\) y\(\mathcal{B}\) son ws, entonces (\(\mathcal{A}\)soa\(\mathcal{B}\)) es un w.
5. Si\(\mathcal{A}\) y\(\mathcal{B}\) son ws, entonces (\(\mathcal{A}\)→\(\mathcal{B}\)) es un w.
6. Si\(\mathcal{A}\) y\(\mathcal{B}\) son ws, entonces (\(\mathcal{A}\)↔\(\mathcal{B}\)) es un w.
7. Todos y sólo los ws de SL pueden ser generados por las aplicaciones de estas reglas.
Observe que no podemos aplicar de inmediato esta definición para ver si una expresión arbitraria es un w. Supongamos que queremos saber si ¬¬¬D es o no un wde SL.
Mirando la segunda cláusula de la definición, sabemos que ¬¬¬ es un wsi ¬¬\(D\) es un wsi ¬¬\(D\) es un w. Entonces ahora tenemos que preguntarnos si ¬¬\(D\) es o no un w. De nuevo mirando la segunda cláusula de la definición, ¬¬\(D\) es un wsi ¬\(D\) es. Nuevamente, ¬\(D\) es un wsi\(D\) es un w. Ahora\(D\) es una letra de oración, una oración atómica de SL, así que sabemos que\(D\) es una w por la primera cláusula de la definición. Entonces, para una fórmula compuesta como¬¬¬\(D\), debemos aplicar la definición repetidamente. Eventualmente llegamos a las oraciones atómicas a partir de las cuales se construye el w.
Definiciones como esta se llaman recursivas. Las definiciones recursivas comienzan con algunos elementos base especificables y definen formas de componer indefinamente los elementos base. Así como la definición recursiva permite construir oraciones complejas a partir de partes simples, puedes usarla para descomponer oraciones en sus partes más simples. Para determinar si algo cumple o no con la definición, es posible que tenga que volver a referirse a la definición muchas veces.
El conectivo que miras primero al descomponer una oración se llama el operador lógico principal de esa oración. Por ejemplo: El operador lógico principal de ¬ (\(E\)(\(F\)→\(G\))) es la negación, ¬. El principal operador lógico de (¬\(E\) (\(F\)→\(G\))) es la disyunción,.
Sentencias
Recordemos que una oración es una expresión significativa que puede ser verdadera o falsa. Dado que las expresiones significativas de SL son las ws y dado que cada w de SL es verdadera o falsa, la definición para una sentencia de SL es la misma que la definición para una w. No todos los idiomas formales tendrán esta característica agradable. En el lenguaje QL, que se desarrolla más adelante en el libro, hay ws que no son oraciones.
La estructura recursiva de las oraciones en SL será importante cuando consideremos las circunstancias bajo las cuales una sentencia en particular sería verdadera o falsa. La oración ¬¬¬\(D\) es verdadera si y sólo si la oración ¬¬\(D\) es falsa, y así sucesivamente a través de la estructura de la oración hasta llegar a los componentes atómicos: ¬¬¬\(D\) es verdadera si y sólo si la oración atómica\(D\) es falsa. Volveremos a este punto en el próximo capítulo.
Convenciones notacionales
Un wlike (\(Q\)&\(R\)) debe estar rodeado de paréntesis, porque podríamos volver a aplicar la definición para usar esto como parte de una oración más complicada. Si negamos (\(Q\)&\(R\)), obtenemos ¬ (\(Q\)&\(R\)). Si solo tuviéramos\(Q\) &\(R\) sin los paréntesis y pusiéramos una negación delante de él, tendríamos ¬\(Q\) &\(R\). Es muy natural leer esto con el significado de lo mismo que (¬\(Q\) &\(R\)), algo muy diferente que ¬ (\(Q\)&\(R\)). La frase ¬ (\(Q\)&\(R\)) significa que no es el caso que ambos\(Q\) y\(R\) son verdaderos;\(Q\) podría ser falsa o\(R\) podría ser falsa, pero la oración no nos dice cuál. La frase (¬\(Q\) &\(R\)) significa específicamente que\(Q\) es falso y eso\(R\) es cierto. Como tal, los paréntesis son cruciales para el significado de la oración.
Entonces, estrictamente hablando,\(Q\) &\(R\) sin paréntesis no es una frase de SL. Sin embargo, al usar SL, a menudo podremos relajar la definición precisa para facilitarnos las cosas. Esto lo haremos de varias maneras.
Primero, entendemos que\(Q\) &\(R\) significa lo mismo que (\(Q\)&\(R\)). Como cuestión de convención, podemos dejar entre paréntesis que ocurren alrededor de toda la oración.
Segundo, a veces puede resultar confuso mirar oraciones largas con muchos pares de paréntesis anidados. Adoptamos la convención de usar corchetes '[' y ']' en lugar de paréntesis. No hay diferencia lógica entre (\(Q\))\(P\) y [\(P\)\(Q\)], por ejemplo. La oración difícil de manejar (((\(H\)\(I\)→\(I\)\(H\)) (→\(K\))\(J\)) & ()) podría escribirse de esta manera: (\(I\)\(J\)→\(H\)\(K\))\(H\)\(I\)
Tercero, a veces vamos a querer traducir la conjunción de tres o más oraciones. Para la frase 'Alice, Bob y Candice fueron todos a la fiesta', supongamos que dejamos que\(A\) signifique 'Alice fue',\(B\) signifique 'Bob went', y\(C\) signifique 'Candice fue'. La definición solo nos permite formar una conjunción a partir de dos oraciones, por lo que podemos traducirla como (\(A\)&\(B\)) &\(C\) o como\(A\) & (\(B\)&\(C\)). No hay razón para distinguir entre estos, ya que las dos traducciones son lógicamente equivalentes.
No hay diferencia lógica entre el primero, en el que (\(A\)&\(B\)) está unido con\(C\), y el segundo, en el que\(A\) está unido con (\(B\)&\(C\)). Así que también podríamos escribir\(A\) &\(B\) &\(C\). Como cuestión de convención, podemos dejar fuera paréntesis cuando juntamos tres o más oraciones.
Cuarto, una situación similar surge con múltiples disyunciones. 'O Alice, Bob, o Candice fueron a la fiesta' se puede traducir como (\(A\)\(B\))\(C\) o como\(A\) (\(B\)\(C\)). Dado que estas dos traducciones son lógicamente equivalentes, podemos escribir\(A\) “\(B\)”\(C\).
Estas dos últimas convenciones sólo se aplican a múltiples conjunciones o disyunciones múltiples. Si una serie de conectivos incluye tanto disyunciones como conjunciones, entonces los paréntesis son esenciales; como con (\(A\)&\(B\))\(C\) y\(A\) & (\(B\)\(C\)). También se requieren los paréntesis si hay una serie de condicionales o bicondicionales; como con (\(A\)→\(B\)) →\(C\) y\(A\) ↔ (\(B\)↔\(C\)).
Hemos adoptado estas cuatro reglas como convenciones notacionales, no como cambios en la definición de una oración. Estrictamente hablando,\(A\) a\(B\) partir de entonces, todavía no\(C\) es una sentencia. En cambio, es una especie de taquigrafía. Lo escribimos en aras de la conveniencia, pero realmente nos referimos a la oración (\(A\)(\(B\)\(C\))).
Si hubiéramos dado una definición diferente para un w, entonces estos podrían contar como ws. Podríamos haber escrito la regla 3 de esta manera: “Si\(\mathcal{A}\),\(\mathcal{B}\),... \(\mathcal{Z}\)son ws, entonces (\(\mathcal{A}\)&\(\mathcal{B}\) &... &\(\mathcal{Z}\)), es un w.” Esto facilitaría la traducción de algunas frases en inglés, pero tendría el costo de complicar nuestro idioma formal. Tendríamos que tener en cuenta la compleja definición cuando desarrollamos tablas de verdad y un sistema de prueba. Queremos un lenguaje lógico que sea expresivamente simple y nos permita traducir fácilmente del inglés, pero también queremos un lenguaje formalmente simple. Adoptar convenciones notacionales es un compromiso entre estos dos deseos.