Logica y Conjuntos

Lógica proposicional

Una proposición es cualquier enunciado lógico al que se le pueda asignar un valor de verdad (1) o falsedad (0).
Dada una proposición p, se define la negación de p como la proposición p' que es verdadera cuando p es falsa y que es falsa cuando p es verdadera. Se lee "no p".
A partir de una o varias proposiciones elementales se pueden efectuar diversas operaciones lógicas para construir nuevas proposiciones; en este caso, se necesita conocer su valor de verdad o falsedad en función de los valores de las proposiciones de que se componen, lo cual se realiza a través de las tablas de verdad de dichas operaciones. Por ejemplo, la tabla de verdad de la negación es la siguiente:

A continuación se describen las principales operaciones lógicas entre dos proposiciones p,q y sus tablas de verdad:
Conjunción: es aquella proposición que es verdadera cuando p y q son verdaderas, y falsa en cualquier otro caso. Se escribe p Ù q, y se lee "p y q".

Disyunción: es aquella proposición que es verdadera cuando al menos una de las dos p o q es verdadera, y falsa en caso contrario. Se escribe p Ú q, y se lee "p o q".

Disyunción exclusiva: es aquella proposición que es verdadera cuando una y sólo una de las dos p o q es verdadera, y falsa en cualquier otro caso. Se escribe p Ú q, y se lee "p o q pero no ambas". Se usa muy poco.

Condicional: es aquella proposición que es falsa únicamente cuando la condición suficiente p es verdadera y la condición necesaria q es falsa. Se escribe p Þ q, y se lee "si p entonces q".

Bicondicional: es aquella proposición que es verdadera cuando p y q tienen el mismo valor de verdad, y falsa en caso contrario. Se escribe p Û q, y se lee "si y sólo si p entonces q".

Una proposición se dice que es una tautología si su valor de verdad es siempre 1 independientemente de los valores de las proposiciones que lo componen; por ejemplo: p Ú p'.
Una proposición se dice que es una contradicción si su valor de verdad es siempre 0 independientemente de los valores de las proposiciones que lo componen; por ejemplo: p Ù p'.
Una paradoja es una proposición a la que no se le puede asignar ningún valor de verdad; suelen estar relacionadas con incorrecciones en el lenguaje lógico. Por ejemplo: p="la proposición p es falsa".
Dos proposiciones p y q se dicen equivalentes si tienen la misma tabla de verdad en función de las proposiciones elementales que lo componen; esta definición equivale a decir que la proposición p Û q es una tautología. Por ejemplo, las proposiciones
p Þ q
y
q' Þ p'
son equivalentes. Esta ley se llama "ley del contrarrecíproco", y se usa en los razonamientos por reducción al absurdo. Se pueden obtener fácilmente más "resultados lógicos" a través de su relación con la teoría de conjuntos.

Números naturales : principio de inducción
Admitivos como intuitivo el concepto de número natural; así, podemos enumerar los números naturales en orden creciente:
N = { 1,2,3,4,5, ... }
Cuando se quiere demostrar que una proposición relativa a números naturales es cierta, se necesita el Principio de Inducción:
"Sea S el conjunto de números naturales para los que la proposición p(n) es cierta; supongamos que
m Î S
y que
n Î S Þ n+1 Î S
Entonces S = { m,m+1,m+2, ... }"
(es decir, la propiedad se verifica para todo número natural a partir de m; normalmente se usa con m = 1).
Algunas veces, cuando se quiere demostrar que la proposición es cierta para n+1, es necesario usar que la proposición se verifica para todo k < n+1; en ese caso se utiliza el Principio de Inducción completa:
"Sea S el conjunto de números naturales para los que la proposición p(n) es cierta; supongamos que
m Î S
y que
m,m+1, ... ,n Î S Þ n+1 Î S
Entonces S = { m,m+1,m+2, ... }"
Ejercicio: pruébese por inducción la fórmula del binomio de Newton

(Indicación: utilícense las propiedades de los números combinatorios).

Teoría de Conjuntos
NOCION INTUITIVA DE CONJUNTOUn conjunto es la reunión en un todo de objetos bien definidos y diferenciables entre si, que se llaman elementos del mismo.
Si a es un elemento del conjunto A se denota con la relación de pertenencia a Î A. En caso contrario, si a no es un elemento de A se denota aÏ A.
Ejemplos de conjuntos:
Æ : el conjunto vacío, que carece de elementos.
N: el conjunto de los números naturales.
Z: el conjunto de los números enteros.
Q : el conjunto de los números racionales.
R: el conjunto de los números reales.
C: el conjunto de los números complejos.
Se puede definir un conjunto:
por extensión, enumerando todos y cada uno de sus elementos.
por comprensión, diciendo cuál es la propiedad que los caracteriza.
Un conjunto se suele denotar encerrando entre llaves a sus elementos, si se define por extensión, o su propiedad característica, si se define por comprensión. Por ejemplo:
A := {1,2,3, ... ,n}
B := {pÎ Z p es par}
Se dice que A está contenido en B (también que A es un subconjunto de B o que A es una parte de B), y se denota A Í B, si todo elemento de A lo es también de B, es decir, a Î A Þ a Î B.
Dos conjuntos A y B se dicen iguales, y se denota A = B, si simultáneamente A Í B y B Í A; esto equivale a decir que tienen los mismos elementos (o también la misma propiedad característica).
Para cualquier conjunto A se verifica que ÆÍ A y A Í A; B Í A es un subconjunto propio de A si A ¹ Æ y B ¹ A.
El conjunto formado por todos los subconjuntos de uno dado A se llama partes de A, y se denota à (A). Entonces, la relación B Í A es equivalente a decir B Î Ã (A). Ejemplos:
Si A = {a,b} entonces à (A) = {Æ ,{a},{b},A}.
Si a Î A entonces {a} ÎÃ (A).
Cuando en determinado contexto se consideran siempre conjuntos que son partes de uno dado U, se suele considerar a dicho U como conjunto universal o de referencia.
OPERACIONES ENTRE CONJUNTOSDados dos conjuntos A y B, se llama diferencia al conjunto A - B := {a Î A a Ï B}. Asimismo, se llama diferencia simétrica entre A y B al conjunto A D B := (A - B) È (B - A).
Si A Î Ã (U), a la diferencia U - A se le llama complementario de A respecto de U, y se denota abreviadamente por A' (U se supone fijado de antemano).
Es fácil ver que si A y B son subconjuntos cualesquiera de U se verifica:
Æ ' = U .
U ' = Æ .
(A')' = A .
A Í B Û B' Í A' .
Si A = { x Î U p(x) es una proposición verdadera} entonces A' = { x Î U p(x) es una proposición falsa}.
Se llama unión de dos conjuntos A y B al conjunto formado por objetos que son elementos de A o de B, es decir: A È B := { x x Î A Ú x Î B}.
Se llama intersección de dos conjuntos A y B al conjunto formado por objetos que son elementos de A y de B, es decir: A Ç B := {x x Î A Ù x Î B}.
Si A y B son subconjuntos de un cierto conjunto universal U, entonces es fácil ver que A - B = A Ç B'. En este caso, la llamadas operaciones booleanas (unión e intersección) verifican las siguientes propiedades :
PROPIEDADES
UNION
INTERSECCION
1.- Idempotencia
A È A = A
A Ç A = A
2.- Conmutativa
A È B = B È A
A Ç B = B Ç A
3.- Asociativa
A È ( B È C ) = ( A È B ) È C
A Ç ( B Ç C ) = ( A Ç B ) Ç C
4.- Absorción
A È ( A Ç B ) = A
A Ç ( A È B ) = A
5.- Distributiva
A È ( B Ç C ) = ( A È B ) Ç ( A È C )
A Ç ( B È C ) = ( A Ç B ) È ( A Ç C )
6.- Complementariedad
A È A' = U
A Ç A' = Æ
Estas propiedades hacen que partes de U con las operaciones unión e intersección tenga una estructura de álgebra de Boole. Además de éstas, se verifican también las siguientes propiedades:
A È Æ = A , A Ç Æ = Æ ( elemento nulo ).
A È U = U , A Ç U = A ( elemento universal ).
( A È B )' = A' Ç B' , ( A Ç B )' = A' È B' ( leyes de Morgan ).
Dados dos conjuntos A y B, se define el producto cartesiano de ambos como el conjunto de pares ordenados:
A ´ B := { (a,b) : a Î A Ù b Î B}
Dos pares (a,b) y (c,d) de A ´ B son iguales si a = c y b = d; análogamente, dados cuatro conjuntos A,B,C,D se verifica
A ´ B = C ´ D Û ( A = C Ù B = D )
Se llama grafo relativo a A ´ B a todo subconjunto G Í A ´ B. Dado un grafo G relativo a A ´ B, se llama proyección de G sobre A al conjunto
ProyAG := { a Î A : (a,b) Î G, $ b Î B}
Análogamente se define la proyección ProyBG de G sobre B.
Por último, los conceptos anteriores pueden generalizarse a familias de conjuntos. Si para cada elemento i de un conjunto (de índices ) I se tiene un conjunto Ai , entonces se define el conjunto { Ai : i Î I } y se denomina familia de conjuntos indicada por I. También se suele denotar por { Ai } i Î I . De forma análoga se define una familia de elementos ( ai ) i Î I .
Dada una familia de conjuntos { Ai } i Î I se definen:
È i ÎI Ai := { a : a Î Ai , $ i Î I }
Ç i Î I Ai := { a : a Î Ai , " i Î I }
Õ i Î I Ai := { (ai) : ai Î Ai , " i Î I }
Las propiedades de la unión e intersección siguen siendo válidas para familias de conjuntos, y en particular las leyes de Morgan :
( È i Î I Ai )' = Ç i Î I A'i , (Çi Î I Ai )' = Èi Î I A'iDIAGRAMAS DE VENN
Los conjuntos de suelen representar gráficamente mediante "diagramas de Venn", con una línea que encierra a sus elementos. Así, todas las operaciones entre conjuntos se pueden representar gráficamente con el fin de obtener una idea más intuitiva.
A Í B

A È B

A Ç B

A - B

A D B

RELACION ENTRE LA TEORIA DE CONJUNTOS Y LA LOGICA PROPOSICIONAL
Existe una relación muy estrecha entre la Teoría de Conjuntos y la Lógica Proposicional. Para mostrar dicha relación, denotemos por letras mayúsculas A,B ... los conjuntos y por las correspondientes minúsculas a,b ... sus propiedades características (es decir, la proposición lógica que caracteriza a los elementos de cada conjunto); entonces se tiene la siguiente correspondencia:
conjuntos
A Í B
A = B
A È B
A Ç B
A'
A - B
A D B
proposiciones
a Þ b
a Û b
a Ú b
a Ù b
a'
a Ù b'
a Ú b
Además, el conjunto vacío se corresponde con una contradicción y el conjunto universal con una tautología. Mediante esta correspondencia, todos los resultados sobre conjuntos se pueden reescribir en términos de lógica proposicional y viceversa; a modo de ejemplo:
A È ( A Ç B ) = A
a Ú ( b Ù c ) Û a
A È ( B Ç C ) = ( A È B ) Ç ( A È C )
a Ú ( b Ù c ) Û ( a Ú b ) Ù ( a Ú c )
( A È B )' = A' Ç B'
( a Ú b )' Û a' Ù b'
PROPOSICIONES CON CUANTIFICADORES
Los símbolos " (cuantificador universal) y $ (cuantificador existencial) se utilizan en Matemáticas para enunciar proposiciones logicas relativas a objetos matemáticos.
Sea A un conjunto y p(x) una proposición o propiedad que hace referencia a un elemento x.
(1) Cuantificador universal : La expresión
" x Î A Þ p(x)
se lee "para todo x que pertenece a A se verifica p(x)", representa la proposición
{ x Î A : p(x) } = A
(2) Cuantificador existencial : La expresión
$ x Î A p(x)
se lee "existe x que pertenece a A tal que p(x)", representa la proposición
{ x Î A : p(x) } ¹ Æ

La negación de cualquiera de las dos proposiciones anteriores se realiza negando la proposición p(x) y cambiando el cuantificador universal por el cuantificador existencial, o viceversa.
Así, la negación de la proposición "" x Î A Þ p(x)" es "$ x Î A p(x)' ", mientras que la negación de "$ x Î A p(x)" es "" x Î A Þ p(x)' "