Conceptos de lgica elemental Clculo proposicional bivalente Se presentan los conceptos bsicos de la lgica bivalente, necesarios para realizar demostraciones en las matemticas elementales. Se usan tablas de verdad para definir, de manera precisa, el papel de las conectivas lgicas y para constatar la equivalencia lgica entre proposiciones, as como para identificar tautologas. Contenido -Proposiciones -Conectivas lgicas -Tautologas y contradicciones -Conectivas posibles ms EnlaceCitaCorreo electrnicoImprimir FavoritoRecopilar esta pgina Proposiciones Ideas primitivas Se adoptarn como ideas primitivas las siguientes: proposicin, verdadero, falso. Por tanto, ellas se aceptarn sin definicin; en el lenguaje cotidiano, una proposicin es una expresin oral o escrita que tiene sentido completo; una afirmacin o enunciado. Usualmente la estructura gramatical de una proposicin incluye un sujeto y un verbo, por lo menos. En lo que sigue, se entender por proposicin una expresin a la cual se le pueda atribuir, inequvoca y exclusivamente la calidad de verdadera (v) o de falsa (f). Verdad y falsedad Sobre la verdad o falsedad de un enunciado, con el que se representa algn fenmeno del entorno, conviene hacer algn comentario; para aceptarlo como verdadero es necesario constatar si dicho enunciado es una representacin aceptable como vlida para el entorno al que se refiera.Pero tal constatacin puede ser una tarea muy difcil (o incluso imposible) de realizar por parte de un observador, pues la validez de una representacin slo puede constatarse mediante comparacin con el original; pero como tal comparacin debe hacerla el observador mismo, ella est sujeta a los mrgenes de error del observador. Esto sin entrar en la discusin sobre el concepto de realidad. La verdad o falsedad que se atribuya a un enunciado puede depender tambin de la teora a la quetal enunciado se refiere. Este tema se ampliar ms adelante. Proposiciones simples y no simples Una proposicin es simple, si no es posible descomponerla en otras proposiciones.Si un enunciado se puede descomponer en dos o ms proposiciones simples, se dir que es no simple.El ligamen entre dos o ms proposiciones simples se realiza por medio de operaciones binarias llamadas conectivas lgicas. Lo que aqu se tratar no tiene como objetivo decidir sobre la calidad de verdad o de falsedad para proposiciones simples, sino sobre la calidad del resultado de ligar dos o ms proposiciones simples a las cuales se les haya atribuido previamentela calidad de verdaderas o de falsas. El clculo proposicional bivalente Como ya se ha dicho, una proposicin debe ser, necesaria y exclusivamente, verdadera o falsa; esto significa que la lgica que se usar es bivalente: hay solamente dos valores posibles: v, f. Se hace nfasis en este hecho porque en la vida real se pueden presentar situaciones que precisan de ms de dos valores. Por ejemplo, del enunciado est lloviendo se puede afirmar que es verdadero o que es falso (segn lo que en efecto est ocurriendo, para el observador). Pero el enunciado maana llover no es verdadero ni falso; es probable, y la medida de su probabilidad se expresa con un nmero real comprendido entre cero y uno; el valor cero se asigna a la imposibilidad; el valor uno, a la certeza.Notaciones En forma anloga a como se hizo para simbolizar conjuntos, de manera general, con letras maysculas: A, B, C, etc., se simbolizarn las proposiciones, de manera general, con letras minsculas: p, q, r, etc. La negacin de la proposicin p se simbolizar con p. La calificacin de verdadera o de falsa para una proposicin dada, o para el resultado de ligar dos o ms proposiciones mediante conectivas lgicas, se simboliza con v y con f, respectivamente, como ya se ha venido haciendo. Variables y enunciados condicionales Debido a su estructura gramatical, una afirmacin como x es un divisor de 12 podra considerarse como proposicin; sin embargo, no es verdadera ni falsa, porque se refiere a una variable: x. El valor de verdad de esta afirmacin depende de la manera como se interprete la variable x; si x es, por ejemplo, 5, la proposicin es falsa; si es 4, por ejemplo, es verdadera.Se ha usado la letra x para simbolizar una variable, pero se puede usar cualquier otra letra o smbolo; en realidad se debera usar un espacio en blanco con la posibilidad de ser llenado adecuadamente para que el enunciado condicional deje de serlo y se transforme en una proposicin. Un enunciado que tenga la estructura gramatical de una proposicin pero contenga variables, se llamar enunciado condicional. Conjunto solucin Se llama conjunto solucin de un enunciado condicional con una variable al conjunto de los valores que puede tomar dicha variable para que el enunciado dado se transforme en una proposicin verdadera. En relacin con el ejemplo anterior (x es un divisor de 12), el conjunto solucin es {1, 2, 3, 4, 6, 12}. En efecto, por ejemplo, para x = 2 se obtiene 2 es un divisor de 12 que es una proposicin aceptada como verdadera en la teora correspondiente. Tambin se define, de manera similar,el conjunto solucin para el caso de que el enunciado condicional contenga dos o ms variables. Tablas de verdad Anlogas a las tablas de pertenencia (ver Conceptos bsicos sobre conjuntos), son las tablas de verdad. Una primera tabla permite describir el comportamiento de una proposicin, simbolizada con p,y el de su negacin, simbolizada con p.

pvf pfv

Hay 4 posibilidades de verdad o falsedad que se dan cuando intervienen dos proposiciones p, q,como se puede ver en la siguiente tabla.

Casos 1234 pvfvf qvvff Conectivas lgicas La conectiva Esta conectiva corresponde a la conjuncin y del lenguaje cotidiano. El valor de verdadde la proposicin es v, siempre que tanto el valor de verdad de p como el valor de verdad de q sean v; en cualquier otro caso, el resultado es f. La siguiente tabla define a esta conectiva y hace explcita la descripcin anterior.

pvfvf qvvff vfff La conectivaEsta conectiva corresponde a la conjuncin o, en el sentido inclusivo; la que se suele expresar con y/o. El valor de verdad de la proposicin p q es f en el caso de que tanto el valor de verdad de p como el de q sea f; en los dems casos el resultado es v. La siguiente tabla hace explcita la descripcin anterior. pvfvf qvv f f p qvvvf

Tautologas y contradicciones Una tautologa es una proposicin (simple o compuesta) cuya tabla de verdad da como resultado v, en todos los casos. Se simbolizar con V, de manera genrica. La proposicin V, que se simbolizar con F, de manera genrica, es una contradiccin; su tabla de verdad da f, en todos los casos.Conectivas posibles Las conectivas lgicas, entre proposiciones, guardan analoga con las operaciones entre conjuntos. Dadas dos proposiciones, p, q, se obtiene una nueva proposicin al ligar a estas proposiciones por medio de una conectiva; el valor de verdad de la proposicin resultante depende de los respectivos valores de verdad de las proposi-ciones dadas, p, q. Si se simboliza con una conectiva genrica entre las proposiciones p, q, se puede esquematizar una tabla de verdad genrica, como sigue.Casos 1234 pvfvf qvvff p q Se puede entonces realizar una tabla, similar a la tabla que describe operaciones entre dos conjuntos, en la que p y q toman el lugar de A y B, respectivamente y en la que v y f, toman el lugar de s y n, respectivamente. pvfvf qvvff 1Vvvvv 2(p q)fvvv 3p qvfvv 4qffvv 5p qvvfv 6pfvfv 7p qvffv 8()fffv 9vvvf 10 fvvf 11pvfvf 12p (q)ffvf 13qvvff 14(p) qfvff 15p qvfff 16Fffff Comentarios sobre esta tabla -Dado que hay 16 posibles conectivas entre dos proposiciones, por las razones expuestas antes, el llenado de las diferentes columnas de la tabla, a partir de la fila marcada con 1, se realiza de manera sistemtica alternando v y f (en la primera columna), alternando v, v y f, f (en la segunda columna), v, v, v, vy f, f, f, f (en la tercera columna), v, v, v, v, v, v, v, vy f, f, f, f, f, f, f, f (en la cuarta columna). De esta manera se obtienen todas las posibilidades en las cuatro casillas de cada fila, de manera anloga a lo que se hace en la tabla de las posibles operaciones entre dos conjuntos. -Tambin, como en el caso de la tabla anloga para conjuntos, se han destacado en color rojo las filas 1, 4, 6, 11, 13 y 16, para indicar que estos casos no son de inters debido a los resultados que all se obtienen. As, para el caso 1, la conectiva correspondiente entre las proposiciones p, q, dara como resultado una proposicin verdadera sin importar el valor de verdad de p y de q. En el caso 4, el resultado correspondera a los valores de verdad de la proposicin q, sin importar el valor de verdad de la proposicin p. Algo similar ocurre para los casos 6, 11 y 13. En el caso 16, el resultado sera una contradiccin, sin importar los valores de verdad de p y de q. - Previamente a la elaboracin de esta tabla, se han definido las conectivas y, lo mismo que la negacin de una proposicin p, simbolizada con p. Usando estos tres conceptos se han elaborado proposiciones compuestas para dos proposiciones simples, p y q. Esta situacin es anloga tambin a la que se da en la tabla correspondiente para conjuntos, en la que adems de las operaciones y , se emplea el concepto de complemento de un conjunto A, simbolizado con C A, para describir las operaciones posibles entre dos conjuntos A, B. Por ejemplo, para la fila 2 los resultados son f, v, v, v, que corresponden a (p q); lo anlogo en la tabla relativa a conjuntos son los resultados n, s, s, s, que corresponden a C(A B). Algo similar ocurre en las filas 8, 12 y 14, como puede verificarse. - En las filas 3, 5, 7 y 10 aparecen smbolos especiales, diferentes de , , , pero se pueden expresar en trminos de ellos, con lo que la analoga que se ha venido observando no se rompe. As, en la fila 5, por ejemplo, se podra haber escrito (p) q, cuyo anlogo en la tabla relativa a conjuntos es CA B. Sobre estos smbolos especiales, que corresponden a conectivas lgicas especiales, se dan detalles a continuacin. La conectiva La expresin pq (fila 5 en la tabla) se puede leer si p entonces q, pues corresponde, aproximadamente, a esta forma de expresarse en el lenguaje cotidiano.Se define,de manera precisa, mediante una tabla de verdad en la que el resultado es f, solamente cuando p es verdadera y q es falsa; en los dems casos, el resultado es v. Esta conectiva tambin se puede expresar mediante los smbolos , , , como se ver ms adelante.

pvfvf qvvff p qvvfv

La conectiva La expresin p q (fila 3 en la tabla) se puede leer p porque q, o 'p, si q' pues corresponde, aproximadamente, a esta forma de expresarse en el lenguaje cotidiano. Se define,de manera precisa, mediante una tabla en la que el resultado es f, solamente cuando p es falsa y q es verdadera; en los dems casos, el resultado es v. Esta conectiva tambin se puede expresar mediante los smbolos , , , como se ver ms adelante. pvfvf qvvff p qvfvv

La conectiva La expresin p q (fila 7 en la tabla) se puede leer p si y solamente si q, que es tpico de enunciados matemticos en los que se pone en evidencia la equivalencia lgica entre dos proposiciones; se suele abreviar con ssi. Se define mediante una tabla en la que el resultado es v, cuando p y q tienen el mismo valor de verdad y es f cuando tienen valores de verdad diferentes. Esta conectiva tambin se puede expresar mediante los smbolos , , ,,, como se ver ms adelante.Nota. 'p ssi q' se puede analizar como sigue: (1) 'p, si q', es decir, 'si q, entonces p'; (2) 'p, slo si q', es decir, 'si no q, entonces no p', es decir, 'si p, entonces q'. pvfvf qvvff p qvffv

La conectiva La expresin p q (fila 10 de la tabla) se puede leer p o q, donde la conjuncin o se entiende en el sentido exclusivo como en par o impar, positivo o negativo. La tabla de verdad con la que se define esta conectiva tiene valores respectivamente opuestos a los de la tabla correspondiente a la conectiva ; es decir, el resultado es v cuando los valores de verdad de p y de q son diferentes y es f, cuando p y q tienen el mismo valor de verdad. pvfvf qvvff p q fvvf

Conectivas y conjunto solucin Si se designa con p(x) a un enunciado condicional que contiene a la variable x, decir que A es el conjunto solucin de p(x) significa queA es el conjunto constituido por los elementos del referencial que hacen verdadera a p(x), cuando se sustituye a la variable x por uno cualquiera de los elementos de A. Por ejemplo, si p(x) es el enunciado condicional (x -3)(x + 5) = 0, el conjunto A = {3, -5} es su conjunto solucin; el conjunto referencial correspondiente puede ser, en este caso, el de los nmeros enteros. En este mismo referencial, el conjunto solucin de (2x -3)(4x + 5) es el conjunto vaco. Si el referencial adoptado fuera el de los nmeros racionales, para este mismo enunciado condicional, el conjunto solucin sera {3/2, -5/4}. Al determinar el conjunto solucin de un enunciado condicional compuesto (de proposiciones simples ligadas por conectivas), se puede observar que dicho conjunto solucin es precisamente el que est relacionado con las conectivas, desde el punto de vista de la analoga existente entre las tablas de pertenencia y las tablas de verdad. As, por ejemplo, si A, B son los conjuntos solucin respectivos de los enunciados condicionales p(x), q(x), entonces el conjunto solucin de la proposicin compuesta p(x)q(x), es A B, pues los x del referencial que estn en la interseccin entre A y B, son precisamente los que hacen verdaderos, simultneamente, a los enunciados p(x) y q(x). Para dar un ejemplo puntual e ilustrativo, si el referencial es R = {(1, 1), (1, 2), (1, 3), , (20, 20)} (constituido por todas las parejas ordenadas (x, y) que se forman con los nmeros enteros comprendidos entre 1 y 20) y los enunciados condicionales que se dan son: p(x, y): 4x 3y = 8 q(x, y): 2x + 5y = 30 entonces el conjunto solucin de p(x, y) es A = {(5, 4), (8, 8), (11, 12), (14, 16), (17, 20)}; el conjunto solucin de q(x, y) es B = {(5, 4), (10, 2)}.El conjunto solucin de p(x, y) q(x, y) es A B = {(5, 4)}. De manera similar, se verifica que el conjunto solucin de p(x)q(x), es el conjunto A B, ya que los nicos elementos del referencial que hacen falsa a la proposicin p(x)q(x), son los que no estn ni en A ni en B. Si A es el conjunto solucin de p(x), entonces el conjunto solucin de p(x) es, naturalmente, CA. Si el enunciado condicional es p(x)q(x), su conjunto solucin es CA B, supuesto que el conjunto solucin de p(x) es A y el conjunto solucin de q(x) es B. Ejemplo.Sea R = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} el referencial que se va a adoptar;se considerarn los siguientes enunciados condicionales: p(x) = [x es primo]; q(x) = [x + 1 es par]. Los conjuntos solucin respectivos son entonces, A = {2, 3, 5, 7, 11} y B = {1, 3, 5, 7, 9, 11}. El enunciado condicional que se va a considerar es si x es primo, entonces x + 1 es par. El conjunto solucin debe ser CA B; como CA = {1, 4, 6, 8, 9, 11}, entonces CA B = {1, 3, 4, 5, 6, 7, 8, 9, 11}. Se verifica que cada uno de los elementos de este conjuntohace que el enunciado condicional dado se convierta en una proposicin verdadera (en el contexto de la teora aritmtica correspondiente); por ejemplo, x = 4 hace que p(x) sea falso y q(x) tambin; x = 7 hace que p(x) sea verdadero y q(x) tambin; x = 1 hace que p(x) sea falso y q(x) sea verdadero. Para ningn elemento de este conjunto ocurre que p(x) sea verdadero y q(x) sea falso. Como se puede observar, el conjunto solucin de este ejemplo contiene a todos los elementos del referencial, con excepcin de 2 y de 10. Esta observacin es importante porque tiene que ver con el hecho de que A no est contenido en B. Si el conjunto A est contenido en el conjunto B, entonces, segn la teora elemental de conjuntos, A CB = ; es decir, no hay elementos de A por fuera de B, en el referencial adoptado. Si en la igualdad anterior se aplica el complemento a los dos lados de la igualdad anterior y se usan las leyes de De Morgany de doble complementacin, se obtiene, CA B = R. El tipo de ejemplo ms usual para ilustrar el uso de la conectiva corresponde a inclusin entre conjuntos: Si x es divisor de 6 entonces x es divisor de 18 o bien, si x es humano, entonces x es mortal. El ejemplo referente a nmeros primos y nmeros pares, dado antes, corresponde a una situacin ms general en la que el conjunto solucin de p(x) no est contenido en el conjunto solucin de q(x). Para determinar el conjunto solucin de p(x) q(x), se puede buscar el caso anlogo al de la tabla de verdad en la referente a conjuntos. El caso buscado es el de la fila 7, que corresponde a C(A B), o sea al complemento de la diferencia simtrica entre los conjuntos A y B. La equivalencia lgica La equivalencia lgica entre dos proposiciones es el concepto anlogo al de igualdad entre dos conjuntos. En este ltimo caso, se ha dicho que un criterio para verificar que A = B, consiste en constatar que la tabla de pertenencia de A es idntica a la de B. En el caso de las proposiciones p, q, se dir que p es lgicamente equivalente a q, siempre que los resultados de las tablas de verdad de p y de q sean idnticas. Los smbolos p, q representan aqu proposiciones simples, o expresiones en las que intervienen dos o ms proposiciones simples, ligadas por conectivas lgicas.La equivalencia lgica entre los enunciados condicionales p(x) y q(x) corresponde a la igualdad entre sus respectivos conjuntos solucin. Si se observan las propiedades, de las operaciones interseccin y unin entre conjuntos, se pueden encontrar, por analoga, equivalencias lgicas entre proposiciones, construyendo las tablas de verdad correspondientes. Se puede verificar, a manera de ejemplo, la equivalencia lgica entre las proposiciones [p q] y [( q) ( p)], usando una tabla de verdad:

pvfvf qvvff pfvfv qffvv p qvvfv ( q) ( p)vvfv

Propiedades de operaciones entre proposiciones Mediante tablas de verdad, similares a la anterior, se puede constatar la equivalencia lgica entre las parejas de proposiciones de la tabla que sigue a continuacin; las proposiciones de la columna de la izquierda son respectivamente equivalentes a las de la columna de la derecha. En el caso de que aparezcan tres proposiciones (p, q, r), se debern considerar 8 casillas horizontales que deben llenarse con v o con f, en la tabla de verdad que se construya.Para efectuar este llenado sistemticamente (como en el caso de los conjuntos) se llenar la primera fila con v, f, v, f, v, f, v, f; la segunda, con v, v, f, f, v, v, f, f; la tercera, con v, v, v, v, f, f, f, f; la cuarta con v, v, v, v, f, f, f, f.

A manera de ejemplo, se muestra la tabla para constatar la equivalencia lgica entre lasproposiciones yvfvfvfvf vvffvvff vvvvffff vvvvvvff vfvfvfff vfffvfff vfvfffff vfvfvfff Algunas tautologas importantes Como se ha dicho, una tautologa es una proposicin (simple o compuesta) cuya tabla de verdad tiene como resultado v en todos los casos. Tambin se ha afirmado que una contradiccin es la negacin de una tautologa; por tanto, una contradiccin se caracteriza por medio de una tabla en la cual, como resultado, hay f en todos los casos. Por la importancia que tienen para el proceso de demostracin, se mencionan las siguientes tautologas: -- -----(p q) [p (q v r)] -

La tabla de verdad para, que se suele llamar modus ponens es la siguiente: vfvf vvff vvfv vffv vvvv

La tabla de verdad para, que se suele llamar silogismo, es la siguiente:vfvfvfvf vvffvvff vvvvffff vvfvvvfv vvvvffvv vvvvfvfv vvfvfffv vvvvvvvv

De manera similar se verifica, mediante tablas de verdad, cada una de las tautologas que se enunciaron antes Debe quedar claro que una proposicin que no sea una tautologa, no tiene por qu ser, necesariamente, una contradiccin. Al negar una tautologa s se obtiene una contradiccin, y recprocamente.Por ejemplo, p . p es una contradiccin, o sea que (p . p), que es equivalente a la proposicin p v p, es una tautologa. La proposicin (p v q) (p . q) no es tautologa ni contradiccin, pues es verdadera en unos casos y falsa en otros. Condicin necesaria y/o suficiente En la proposicin p q, se llama p el antecedente y q el consecuente. Tambin se dice que q es la condicin necesaria y que p es la condicin suficiente. Se puede ilustrar esta distincin con un ejemplo: si x es mltiplo de 6, entonces x es mltiplo de 2. Es suficiente, en efecto, ser mltiplo de 6, para ser mltiplo de 2 (pero no es necesario); en cambio,s es necesario ser mltiplo de 2 para ser un mltiplo de 6 (aunque no es suficiente). Es posible que una condicin necesaria sea tambin suficiente. Por ejemplo, entre nmeros enteros, para que un nmero de dos o ms cifras sea mltiplo de 3 es necesario y suficiente que la suma de esas cifras sea mltiplo de 3. Se puede decir entonces, que un nmero xde dos o ms cifras es mltiplo de 3, ssi, la suma de las cifras de x es mltiplo de 3. (Por ejemplo, 4782 = 31594, pero 1594 no es mltiplo de 3). Esto quiere decir que son verdaderas, las dos proposiciones siguientes: (x es mltiplo de 3) (la suma de las cifras de x es mltiplo de 3) (la suma de las cifras de x es mltiplo de 3) (x es mltiplo de 3). Proposiciones relacionadas con p q Con una proposicin de la forma p q(implicacin) se relacionan las siguientes: q p, que se llama su recproca; ( p) ( q), que se llama su contraria ( q) ( p), que se llama su contrarrecproca. Se ha comprobado antes, con una tabla de verdad, que una implicacin y su contrarrecproca son lgicamente equivalentes. Dada la proposicin (p . q) r, se relacionan con ella las siguientes: [p . ( r)] ( q) [( r) . q] ( p). Cada una de estas dos proposiciones se llama una contrarrecproca parcial de la proposicin original. Mediante tablas de verdad se puede verificar que la proposicin (p . q) r es lgicamente equivalente con cada una de sus contrarrecprocas parciales. Reglas de inferencia La palabra inferencia se relaciona con el verbo inferir que significa sacar consecuencia o deducir una cosa de otra. La inferencia juega un papel de la mayor importancia en la matemtica, debido a que, a partir de algunos hechos establecidos o comprobados, en todo caso aceptados como verdaderos, se pueden deducir vlidamente otros. La validez de las deducciones se respalda con las reglas de inferencia, que a su vez se respaldan con tautologas. Sin embargo, las reglas de inferencia no garantizan nada en relacin con la verdad de un enunciado particular, sino que solamente garantizan la validez de una deduccin, a la luz de la lgica bivalente. El siguiente ejemplo ilustra lo que se acaba de afirmar; a partir del enunciadotodos los tringulos tienen 4 lados (aceptado como verdadero) se puede deducir vlidamente que todos los paralelogramos son tringulos.Las reglas de inferencia que se mencionarn a continuacin son las que con mayor frecuencia se utilizan en las demostraciones; no se incluyen, por tanto, todas las que seenunciaron en la lgica clsica. Las denominaciones latinas hacen referencia a su origen histrico. Se mencionar, en primer lugar, la regla que, en la lgica clsica, se llama modus ponens y que esquemticamente se suele presentar de la manera siguiente: p p q ______ q Las proposiciones que aparecen arriba de la lnea se llaman premisas. La proposicin que aparece debajo de la lnea se llama conclusin.El modus ponens se puede expresar tambin en la forma siguiente, que es una tautologa, como ya se ha verificado mediante una tabla de verdad: [p . (p q)] q. Una segunda regla de inferencia es la llamada modus tollens, cuya presentacin esquemtica es: p q q _______ p Si se observa con algn cuidado, se puede ver que el modus tollens es, en realidad, una manera alternativa de enunciar el modus ponens, pues si en lugar de escribir la proposicin p q se escribe su contrarrecproca (que, como se sabe, le es equivalente) se obtiene el modus ponens, enunciado en trminos de las negaciones de las proposiciones p, q:( q) ( p) p ________ p Una tercera regla se llama silogismo: p q q r ______ p r Nota: el orden en que se escriban las premisas en estos esquemas es indiferente, ya que se entiende que las premisas estn ligadas por la conectiva . . La cuarta regla que se mencionar se llama modus tollendo ponens: p v q p __________ q Tambin se debe tener en cuenta que F p es una tautologa, sin importar cul sea el valor de verdad de p, debido a la definicin de la conectiva simbolizada con .Cuantificadores Un enunciado condicional (o sea uno que contiene variables) no es verdadero ni falsa, como ya se ha dicho. Pero se puede convertir en una proposicin de la cual se puede afirmar que es verdadera o que es falsa, es decir en una proposicin categrica, si las variables que aparezcan se reemplazan por constantes, o sea por elementos especficos del referencial. En tal caso lo que se obtiene es una proposicin categrica particular. Por ejemplo, si el referencial es el conjunto de los nmeros enteros y el enunciado condicional es x es un divisor de 12, se puede reemplazar la variable x por un nmero entero, para obtener una proposicin categrica particular; si x es, digamos 3, la proposicin resultante es verdadera; si es, digamos 7, la proposicin resultante es falsa. Pero un enunciado condicional tambin se puede transformar en una proposicin categrica general. Para ello se emplean operadores llamados cuantificadores. Se har referencia solamente a dos de ellos, aunque en el lenguaje corriente se utilizan otras expresiones de cuantificacin que se pueden reducir a las que se consideran aqu. El enunciado condicional x es un divisor de 12 se puede transformar en una proposicin categrica general, si se antepone a ella la expresin para todo x. En este caso, se obtiene una proposicin falsa. Pero si se antepone la expresin para algn x, la proposicin que se obtiene es verdadera (en ambos casos, los calificativos verdadera y falsa se refieren a criterios compatibles con la teora correspondiente). La expresin para todo x se llama cuantificador universal, aplicado a x. La expresin para algn x se llama cuantificador existencial, aplicado a x. Estos cuantificadores juegan un papel destacado en el lenguaje matemtico. Se emplean para ellos smbolos especiales (, -). Las siguientes son formas generales de presentar estos cuantificadores. La primera establece que para todo x (del referencial dado) se cumple P(x), que es una afirmacin que se hace sobre x: x, P(x) La segunda forma establece que existe por lo menos un x (del referencial dado) tal que se cumple P(x): - x, P(x). Hay una forma especial del cuantificador existencial en la que se establece tambin la unicidad: existe uno y un solo x tal que P(x). En smbolos, -! x, P(x). En el lenguaje corriente se usan tambin los cuantificadores: todos, algunos, ninguno, son los ms usuales. El primero corresponde al cuantificador universal; el segundo, al cuantificador existencial; el tercero corresponde a una forma de expresar el cuantificador universal, mezclado con una negacin.Por ejemplo, si el referencial es el conjunto de los nmeros enteros, el enunciado ningn nmero primo mayor que 2 es par se puede traducir as: x, (x > 2, . , x es primo, . , x es par). Cuantificadores y conectivas lgicas Tambin se pueden asociar los cuantificadores a las conectivas lgicas, como se puede ver en el siguiente ejemplo. Dado el conjunto A = {1, 2, 3, 4}, y tomando como referencial el conjunto de los nmeros enteros, se puede decir que todos los elementos de A son menores que 5: x e A, x < 5. Esta es una manera de abreviar la expresin 1 < 5, . ,2 < 5, . , 3 < 5, . , 4 < 5, que es una proposicin compuesta, constituida por proposiciones simples ligadas por la conectiva .. Tambin se puede afirmar que algunosde los elementos de A son pares (por lo menos un x de A es par): - x e A, x es par; esto equivale a decir que la siguiente proposicin compuesta es verdadera: 1 es par, v , 2 es par, v , 3 es par, v , 4 es par. Efectivamente, no todas esas afirmaciones, ligadas por la conectiva v , son falsas. La asociacin que se ha descrito, entre cuantificadores y conectivas lgicas justifica lo que se establece a continuacin, en relacin con proposiciones cuantificadas: [ x, P(x)] es equivalente con - x, [P(x)] [- x, P(x)] es equivalente a x, [P(x)]. Ejemplos.(1) Dada la proposicin todos los nmeros enteros son primos, su negacin es algunos nmeros enteros no son primos; esta ltima es equivalente a no todos los nmeros enteros son primos o bien, existe por lo menos un nmero entero que no es primo. (2) Dada la proposicin algunos divisores de 36 son impares, su negacin es ningn divisor de 36 es impar. Axiomas, postulados, definiciones La diferencia entre el concepto de axioma y el de postulado se remonta a Aristteles, para quien los axiomas son verdades universales, comunes a todas las ramas de la ciencia y postulados, las verdades que sustentan el desarrollo de una particular rama de la ciencia.En la literatura matemtica se suele usar indistintamente la denominacin axioma o postulado; se entiende por tal un enunciado cuya verdad se acepta sin demostracin; se prefiere que sea intuitivamente evidente. Los aristotlicos reservaron, como ya se dijo, la denominacin axioma para verdades universales, aplicables a todas las ciencias, como las llamadas leyes del pensamiento conocidas como: -Principio de contradiccin: es imposible para cualquier cosa ser y no ser, en el mismo sentido. -Principio del medio excluido: De dos afirmaciones contradictorias, una debe ser verdadera. -principio de identidad: a es a Para los aristotlicos, los postulados son principios no demostrables de una ciencia en particular. Hoy en da no se habla de principios no demostrables, por cuanto la eleccin de los postulados, lo mismo que la de las ideas primitivas, es totalmente libre, en el sentido de que se puede adoptar cualquier conjunto de postulados para una teora dada, con la nica condicin de que no se contradigan unos a otros.Es deseable que el nmero de postulados, sea el menor posible, y que sean independientes unos de otros, en el sentido de que ninguno de ellos pueda deducirse de los dems. Tambin debe ser lo ms reducido posible el nmero de ideas primitivas que se adopten. Una definicin es un enunciado por medio del cual se explica el significado de una notacin (palabra, frase, smbolo o expresin). Para ser aceptable, una definicin no debe involucrar al concepto que se est definiendo. Este criterio de aceptacin para una definicin, hace que sea imposible, en el desarrollo de una teora, definir absolutamente todos los trminos empleados.Algunos trminos deben tomarse como primitivos, o sea que de ellos no se da una definicin, sino que se acepta la idea intuitiva que cada quien tenga del asunto. El significado de una idea primitiva, para efectos del desarrollo de una teora, se precisa mediante el desarrollo de la teora misma, de manera que, en lo esencial, todos los usuarios compartan el mismo significado. Teoremas y demostracionesUn teorema es un enunciado que debe justificarse, desde el punto de vista de la lgica, dentro de la teora que se est desarrollando. El proceso de justificar un enunciado (una afirmacin) se llama demostracin. La necesidad de demostrar se debe, en principio, a una limitacin humana en cuanto a la posibilidad de tener presentes, de manera simultnea, todos los pasos lgicos que hacen legtima o lgicamente aceptable una afirmacin dada. Pero tambin se debe a un criterio de rigurosidad en el desarrollo de una teora.As, por ejemplo, se considera evidente que 3 + 2 = 5; este hecho no requiere demostracin, a menos que se desee hacerla a manera de ejercicio lgico. Pero asegurar que se cumple 345 978 = 337410 es algo que requiere de un proceso, en este caso un algoritmo, basado en la teora correspondiente, con el que se justifica la afirmacin. Gran parte de la actividad matemtica se dedica a la demostracin de enunciados; por medio de esa actividad se desarrolla la teora y se le proporciona la solidez necesaria, hacindola objetivamente confiable, o sea independizndola de la opinin o de la percepcin que cada persona tenga de los hechos. En una demostracin de un enunciado matemtico juega un papel preponderante la lgica bivalente, en particular, las reglas de inferencia descritas antes. El conocimiento de tales reglas proporciona un criterio sobre el cual se establecen estrategias de demostracin y tambin un criterio para saber cundo el proceso de demostracin est completo. Sin embargo, las reglas de inferencia, por s solas, no proporcionan mtodos infalibles para demostrar cualquier enunciado; es necesario, adems, un buen conocimiento de la teora y no pocas veces una buena dosis de intuicin para buscar el camino adecuado. Con frecuencia es necesario hacer conjeturas y verificarlas en casos particulares, para afianzarse en alguna etapa de la demostracin. La observacin cuidadosa de modelos de demostracin para situaciones de caractersticas diversas, proporciona elementos tiles para enfrentarse a teoremas no conocidos ode carcter no rutinario. Casi siempre un teorema se presenta en la forma de un enunciado que consta de dos partes: la hiptesis y la tesis, ligadas por una implicacin: h t. La hiptesis(h) consta de una o ms afirmaciones que se aceptan sin discusin, como punto de partida (premisas) para obtener como conclusin la tesis (t). Mtodos de demostracinLos mtodos de demostracin se pueden dividir en dos grandes clases: - mtodo directo - mtodos indirectos. El mtodo directo consiste en partir de la hiptesis y llegar a la tesis, a travs del uso reiterado del silogismo en un nmero de etapas que puede variar segn el caso que se considere. El siguiente es un esquema de una demostracin directa: h p1 p1 p2 p2 p3 . . . pn-1 pn pn t Todos los enunciados de la lista anterior se suponen ligados por la conectiva . . Del primero y el segundo enunciados se deduce que h p2, usando el silogismo. De este resultado y el cuarto, se deduce que h p3; se contina de esta manera hasta que se llega a concluir que h t. Si lo que se quiere probar es la afirmacin t, se aplica el modus ponens: h h t ______ t. A continuacin se da un ejemplo de demostracin directa. El enunciado que se va a demostrar es el siguiente: el producto de dos nmeros enteros impares es un nmero entero impar.Se comienza por analizar el enunciado, para identificar la hiptesis y la tesis. Para el efecto, se puede reformular el enunciado en una forma equivalente: si a es impar y b es impar, entonces a b es impar (el referencial es el conjunto de los nmeros enteros y a, b, representan enteros cualesquiera; por brevedad, no se usan cuantificadores explcitamente). h:a es impar y b es impar h p1:a = 2n + 1 y b = 2m + 1 (n, m enteros) p1 p2:a b = 2mn + 2m + 2n + 1 p2 p3:a b = 2(mn + m + n) + 1 p3 t:a b es impar. Como puede verse, es necesario el conocimiento de la teora para afirmar, por ejemplo, que si a, b son nmeros impares, entonces deben ser, de la forma 2n + 1, 2m + 1, respectivamente, donde n, m son enteros; tambin es necesaria la teora para expresar el producto a b, a partir de las expresiones anteriores. La descripcin del proceso completo de la demostracin anterior exigira ms detalles; as, a partir de h p1 y p1 p2, se deduce, h p2; de h p2 y p2 p3 se deduce, h p3; a partir de h p3 y p3 t se deduce, finalmente, h t. En cuanto a los mtodos indirectos, estn basados en equivalencias lgicas entre la proposicin h t y proposiciones tales como ( t) ( h), [h . ( t)] F. Estos mtodos indirectos se emplean cuando la forma directa no parece fcil, o no es viable. Cuando se reemplaza h t por ( t) ( h), que es su contrarrecproca, se parte de la negacin de la tesis y se llega, por el mtodo de la forma directa, a la negacin de la hiptesis.Ejemplo: probar (en los enteros) que si x2 es par, entonces, x es par. Se usar la proposicin contrarrecproca: Si x no es par, entonces x2 no es par. Un esquema de la demostracin es el siguiente: x no es par x es impar x = 2n + 1, para algn entero n x2 = 4n2 + 4n + 1 x2 = 2(2n2 + 2n) + 1 x2 es impar x2 no es par.Cuando se reemplaza h t por [h . ( t)] F, que le es lgicamente equivalente, se acepta la hiptesis, se niega la tesis, y a partir de esto se deduce, por el mtodo directo, una falsedad, es decir, un enunciado que contradiga un hecho previamente establecido, bien sea un axioma de la teora, o un teorema ya demostrado. Esta forma indirecta de demostrar se conoce como reduccin al absurdo. Ejemplo: probar (en los nmeros reales) que si= r, entonces r no es un nmero racional. Se usar el mtodo de reduccin al absurdo, o sea que se parte de la negacin del enunciado: = r y r es un nmero racional. De esta afirmacin se deduce sucesivamente, r = a/b, donde a, b son enteros, b 0 a = rb a2 = 2b2 a continuacin, se descomponen los nmeros a, b en sus factores primos: (p1 p2 ... ps)2 = 2.(q1 q2 ... qt)2 contradiccin con T.F.A. (*) (*) T.F.A. es el teorema fundamental de la aritmtica, segn el cual, la descomposicin de un nmero entero en sus factores primos es nica.Se ha llegado a una contradiccin con el T.F.A., porque en el paso anterior al final se escribe una igualdad en cuyo miembro izquierdo hay un nmero par de factores primos (2s factores), mientras que en el miembro de la derecha hay, adems del factor 2, otros 2t factores primos, o sea que el miembro de la derecha contiene un nmero impar de factores primos. Pero, el hecho de que el miembro de la izquierda y el de la derecha estn ligados por igualdad, significa que el mismo nmero entero se ha podido descomponer de dos maneras distintas, como el producto de factores primos. Un teorema puede consistir tambin en un enunciado de igualdad, como el que afirma que (cos x)2 + (sen x)2 = 1, en donde no se tiene la forma h t, al menos explcitamente, y se debe usar la teora correspondiente (en este caso la trigonometra) para establecer la igualdad. Una estrategia, para demostraciones como esta, consiste en partir de uno de los miembros de la igualdad y transformarlo hasta obtener el otro miembro. A veces, se puede proceder por reduccin al absurdo, suponiendo que la igualdad no se cumple y deduciendo alguna contradiccin con algn hecho que se ha establecido previamente. Si la hiptesis del teorema es una proposicin compuesta de proposiciones simples, ligadas por la conectiva., se puede realizar una demostracin indirecta, usando como reemplazo del enunciado original, una contrarrecproca parcial.Un ejemplo de esto es: probar, en los nmeros reales, que si a.b = 0, entonces se cumple a = 0, y/o, b = 0; es decir, al menos uno de los factores es cero.Se comenzar por reemplazar este enunciado por el de su contrarrecproca:Si a 0, y, b 0, entonces, a.b 0.A su vez, se reemplazar este enunciado por una contrarrecproca parcial:si a 0, y, a.b = 0, entonces, b = 0.Ahora es fcil la demostracin de este ltimo enunciado, en forma directa: como se tiene a 0, existe el inverso multiplicativo de a, o sea 1/a; si en a.b = 0 se multiplica a ambos lados por 1/a, se obtiene b = 0, como conclusin. Una clase importante de teoremas son los teoremas de existencia y los teoremas que, adems de existencia, incluyen unicidad. La demostracin de un teorema de existencia consiste en exhibir un ejemplar del referencial que verifique la afirmacin del enunciado. La demostracin de la unicidad consiste, usualmente, en aventurar la hiptesis de que hay ms de un ejemplar del referencial que satisface al enunciado (que hay al menos dos) y probar que los dos supuestos ejemplares se identifican.Por ejemplo, probar, en los enteros, que la solucin de la ecuacin a + x = b, existe y es nica para enteros a, b cualesquiera, dados. La existencia se prueba buscando un ejemplar que satisfaga a la ecuacin. Por los medios que proporciona la teora, se encuentra quex = b + (-a) es solucin de la ecuacin; esto ltimo se verifica sustituyendo x por b + (-a) en la ecuacin dada. Queda as demostrada la existencia de la solucin.Para probar la unicidad, se aventura la afirmacin de que existen al menos dos soluciones, x1, x2.Entonces se deben cumplir las igualdades,a + x1 = b, a + x2 = b,o sea que debe cumplirse, a + x1 = a + x2 (ya que dos cosas iguales a una tercera son iguales entre s).De aqu se deduce, por la teora correspondiente, que x1 = x2, o sea la unicidad de la solucin. Una ltima forma general de demostracin que se mencionar, por ahora, es la demostracin por contraejemplo. Esta forma de demostracin se utiliza cuando se quiere probar que una proposicin, cuantificada universalmente, es falsa. En tal caso, lo que se hace es probar que su negacin (que involucra un teorema de existencia) es una proposicin verdadera. Por ejemplo, se quiere probar que la proposicin todos los nmeros primos son impares es falsa. Para ello, debe probarse que es verdadera su negacin: existe por lo menos un nmero primo que no es impar; la demostracin consiste en exhibir un ejemplar que satisfaga a esta ltima afirmacin. Tal ejemplar es 2 (adems es el nico que cumple con esta condicin). Con esto queda probada la falsedad de la proposicin dada.A continuacin se dan otros ejemplos de demostraciones. Para ello se adoptan como axiomas del lgebra de conjuntos los siguientes: (1)Las operaciones unin e interseccin son conmutativas. (2)El conjunto vaco es elemento idntico para la unin y el referencial es elemento idntico para la interseccin. (3)La interseccin es distributiva con respecto a la unin y la unin es distributiva con respecto a la interseccin. (4)Para cada subconjunto A del referencial existe el complemento CA, que cumple con: A CA = RA CA = . se puede demostrar como teorema, por ejemplo, la idempotencia de la unin entre conjuntos: A A = A. El siguiente es un esquema de la demostracin: A = A por el axioma (2) = A (A CA)por el axioma (4) = (A A) (A CA)por el axioma (3) = (A A) R por el axioma (4) = A A por el axioma (2). Usando la definicin dada para la inclusin, en trminos de interseccin y de complemento, se pueden demostrar algunas propiedades de dicha relacin.Definicin: A _ B, ssi, A CB = . Se demostrar, por ejemplo, que si A _ B y B _ C, entonces, A _ C. La hiptesis es, A _ B y B _ C. La tesis es, A _ C. De la hiptesis se deduce que A CB = y tambin que B CC = . Se quiere llegar a probar que A _ C, o sea que A CC = .Para el efecto, se puede escribir,A CC = (A CC) R = (A CC) (B CB) = (A CC B) (A CC CB) = (A B CC) (A CB CC) = (A ) ( CC) = = . En estos ejemplos de demostracin se aprecia claramente lo que se haba afirmado en relacin con una buena dosis de intuicin para escoger el camino ms adecuado.