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:

p p'
1 0
0 1

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".

p q pq
1 1 1
1 0 0
0 1 0
0 0 0
 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".

p q pq
1 1 1
1 0 1
0 1 1
0 0 0

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.

p q pq
1 1 0
1 0 1
0 1 1
0 0 0

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".

p q pq
1 1 1
1 0 0
0 1 1
0 0 1
 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".

p q pq
1 1 1
1 0 0
0 1 0
0 0 1

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

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 CONJUNTO

Un 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:

o  : el conjunto vacío, que carece de elementos.

o N: el conjunto de los números naturales.
o Z: el conjunto de los números enteros.
o Q : el conjunto de los números racionales.
o R: el conjunto de los números reales.
o C: el conjunto de los números complejos.

Se puede definir un conjunto:

o por extensión, enumerando todos y cada uno de sus elementos.

o 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:

o A := {1,2,3, ... ,n}

o 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 CONJUNTOS

Dados 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  B
:= (A  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:

o '=U.
o U ' = .
o (A')' = A .
o A  B  B'  A' .
o 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
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:

o A   = A , A   =  ( elemento nulo ).
o A  U = U , A  U = A ( elemento universal ).
o ( 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:

o  i I Ai := { a : a  Ai ,  i  I }
o  i  I Ai := { a : a  Ai ,  i  I }
o  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'i
DIAGRAMAS 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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  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)' "

Conjuntos finitos : Combinatoria

La Combinatoria es la parte de las Matemáticas que se dedica al estudio
de los conjuntos finitos.

Puesto que la propiedad principal de estos conjuntos es que se puede

representar su número de elementos
mediante un número natural (llamado cardinal de dicho conjunto), la tarea
básica de la Combinatoria es
precisamente el cálculo del cardinal de dichos conjuntos.

Para dicho cálculo se necesita definir los llamados números

combinatorios:

(1) Números factoriales: se define n! mediante la ley de recurrencia

n! = n · (n-1)!

y la condición inicial 0! := 1. De forma iterativa, se tiene

n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1

n! es el número de permutaciones de n elementos, es decir, es el

número total de formas de ordenar n elementos
 de todas las formas distintas posibles.

(2) Coeficientes binomiales: se definen por la fórmula

El número "n sobre k" es el número de combinaciones de n

elementos tomados de k en k, es decir,
el número de subconjuntos distintos de k elementos que tiene un
conjunto con n elementos.

Los coeficientes binomiales tienen dos propiedades básicas:

(a)

(b)

Como aplicación de los números combinatorios y del Binomio de

Newton, podemos contar el número total de
subconjuntos que tiene un conjunto A con n elementos, es decir, el
cardinal de partes de A; para ello, notemos
que el número de tales subconjuntos se obtiene sumando el número
de subconjuntos de 0 elementos más los de
1 elemento, más los de 2 elementos, y así hasta los de n elementos, es
decir:
 Pero esta cantidad corresponde a desarrollar mediante el binomio de
Newton la expresión

(1+1)n = 2n

Así pues se obtiene que #  (A) = 2n si # A = n.

 Relaciones y proporciones
Mucha gente utiliza los términos "relación" y "proporción" como si significaran lo
mismo, pero ¡mucho cuidado! No es así.

 Relación: compara una parte con otra parte.

 Proporción: compara una parte con el todo. El término proporción también se

refiere a una ecuación con relaciones a cada lado de la igualdad.

Por ejemplo, si comparamos el número de chicos y chicas en tu clase de

matemáticas, utilizaríamos una relación, mientras que si comparamos el número
de chicas con respecto al total de estudiantes de la clase, entonces utilizaríamos
una proporción.
Las relaciones se pueden escribir de tres formas distintas. Digamos que en tu
pueblo hay 25 vampiros y 10 hombres lobo. La relación entre vampiros y hombres
lobo puede ser escrita como:
25 a 10,
25 : 10, ó

Seguramente te diste cuenta de que la última se parece mucho a una fracción. Y,

al igual que las fracciones, las relaciones y proporciones pueden ser reducidas,
exactamente igual como se reducen las fracciones. Al dividir entre 5 nos queda:
5 a 2,
5 : 2, ó
 Combinaciones y permutaciones

¿Qué diferencia hay?

Normalmente usamos la palabra "combinación" descuidadamente, sin pensar en si

el orden de las cosas es importante. En otras palabras:

"Mi ensalada de frutas es una combinación de manzanas, uvas y

bananas": no importa en qué orden pusimos las frutas, podría ser "bananas,
uvas y manzanas" o "uvas, manzanas y bananas", es la misma ensalada.

"La combinación de la cerradura es 472": ahora sí importa el orden. "724"

no funcionaría, ni "247". Tiene que ser exactamente 4-7-2.

Así que en matemáticas usamos un lenguaje más preciso:

Si el orden no importa, es una combinación.

Si el orden sí importa es una permutación.

¡Así que lo de arriba se podría llamar "cerradura de

permutación"!

Con otras palabras:

Una permutación es una combinación ordenada.

Para ayudarte a recordar, piensa en "Permutación... Posición"

Permutaciones

Hay dos tipos de permutaciones:

 Se permite repetir: como la cerradura de arriba, podría ser "333".

 Sin repetición: por ejemplo los tres primeros en una carrera. No puedes
quedar primero y segundo a la vez.

1. Permutaciones con repetición

Son las más fáciles de calcular. Si tienes n cosas para elegir y eliges r de ellas, las
permutaciones posibles son:

n × n × ... (r veces) = nr

(Porque hay n posibilidades para la primera elección, DESPUÉS hay n posibilidades

para la segunda elección, y así.)

Por ejemplo en la cerradura de arriba, hay 10 números para elegir (0,1,...,9) y eliges 3
de ellos:

10 × 10 × ... (3 veces) = 103 = 1000 permutaciones

Así que la fórmula es simplemente:

r
n

donde n es el número de cosas que puedes

elegir, y eliges r de ellas
(Se puede repetir, el orden importa)

2. Permutaciones sin repetición

En este caso, se reduce el número de opciones en cada paso.

Por ejemplo, ¿cómo podrías ordenar 16

bolas de billar?

Después de elegir por ejemplo la "14" no

puedes elegirla otra vez.
Así que tu primera elección tiene 16 posibilidades, y tu siguiente elección tiene 15
posibilidades, después 14, 13, etc. Y el total de permutaciones sería:

16 × 15 × 14 × 13 ... = 20,922,789,888,000

Pero a lo mejor no quieres elegirlas todas, sólo 3 de ellas, así que sería solamente:

16 × 15 × 14 = 3360

Es decir, hay 3,360 maneras diferentes de elegir 3 bolas de billar de entre 16.

¿Pero cómo lo escribimos matemáticamente? Respuesta: usamos la "función factorial"

La función factorial (símbolo: !) significa que se multiplican números

descendentes. Ejemplos:

 4! = 4 × 3 × 2 × 1 = 24
 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
 1! = 1

Nota: en general se está de acuerdo en que 0! = 1. Puede que parezca curioso que no
multiplicar ningún número dé 1, pero ayuda a simplificar muchas ecuaciones.

Así que si quieres elegir todas las bolas de billar las permutaciones serían:

16! = 20,922,789,888,000

Pero si sólo quieres elegir 3, tienes que dejar de multiplicar después de 14. ¿Cómo lo
escribimos? Hay un buen truco... dividimos entre 13!...

16 × 15 × 14 × 13 × 12 ...
= 16 × 15 × 14 = 3360
13 × 12 ...

¿Lo ves? 16! / 13! = 16 × 15 × 14

La fórmula se escribe:

donde n es el número de cosas que puedes

 elegir, y eliges r de ellas
(No se puede repetir, el orden importa)

Ejemplos:

Nuestro "ejemplo de elegir en orden 3 bolas de 16" sería:

16! 16! 20,922,789,888,000

= = = 3360
(16-3)! 13! 6,227,020,800

¿De cuántas maneras se pueden dar primer y segundo premio entre 10 personas?

10! 10! 3,628,800

= = = 90
(10-2)! 8! 40,320

(que es lo mismo que: 10 × 9 = 90)

Notación

En lugar de escribir toda la fórmula, la gente usa otras notaciones como:

Combinaciones

También hay dos tipos de combinaciones (recuerda que ahora el orden no importa):

 Se puede repetir: como monedas en tu bolsillo (5,5,5,10,10)

 Sin repetición: como números de lotería (2,14,15,27,30,33)

1. Combinaciones con repetición

En realidad son las más difíciles de explicar, así que las dejamos para luego.

2. Combinaciones sin repetición

Así funciona la lotería. Los números se eligen de uno en uno, y si tienes los números
de la suerte (da igual el orden) ¡entonces has ganado!
La manera más fácil de explicarlo es:

 imaginemos que el orden sí importa (permutaciones),

 después lo cambiamos para que el orden no importe.

Volviendo a las bolas de billar, digamos que queremos saber qué 3 bolas se eligieron,
no el orden.

Ya sabemos que 3 de 16 dan 3360 permutaciones.

Pero muchas de ellas son iguales para nosotros, porque no nos importa el orden.

Por ejemplo, digamos que se tomaron las bolas 1, 2 y 3. Las posibilidades son:

El orden importa El orden no importa

1 2 3
1 3 2
2 1 3
123
2 3 1
3 1 2
3 2 1

Así que las permutaciones son 6 veces más posibilidades.

De hecho hay una manera fácil de saber de cuántas maneras "1 2 3" se pueden
ordenar, y ya la sabemos. La respuesta es:

3! = 3 × 2 × 1 = 6

(Otro ejemplo: 4 cosas se pueden ordenar de 4! = 4 × 3 × 2 × 1 = 24 maneras

distintas, ¡prueba tú mismo!)

Así que sólo tenemos que ajustar nuestra fórmula de permutaciones para reducir por
las maneras de ordenar los objetos elegidos (porque no nos interesa ordenarlos):

Esta fórmula es tan importante que normalmente se la escribe con grandes paréntesis,
así:
 donde n es el número de cosas que puedes
elegir, y eliges r de ellas
(No se puede repetir, el orden no importa)

Y se la llama "coeficiente binomial".

Notación

Además de los "grandes paréntesis", la gente también usa estas notaciones:

Ejemplo

Entonces, nuestro ejemplo de bolas de billar (ahora sin orden) es:

16! 16! 20,922,789,888,000

= = = 560
3!(16-3)! 3!×13! 6×6,227,020,800

O lo puedes hacer así:

16×15×14 3360
= = 560
3×2×1 6

Así que recuerda, haz las permutaciones, después reduce entre "r!"

... o mejor todavía...

¡Recuerda la fórmula!

Es interesante darse cuenta de que la fórmula es bonita y simétrica:

Con otras palabras, elegir 3 bolas de 16 da las mismas combinaciones que elegir 13
bolas de 16.

16! 16! 16!

= = = 560
3!(16-3)! 13!(16-13)! 3!×13!

Triángulo de Pascal

Puedes usar el triángulo de Pascal para calcular valores. Baja a la fila "n" (la de arriba
es n=0), y ve a la derecha "r" posiciones, ese valor es la respuesta. Aquí tienes un
trozo de la fila 16:

1 14 91 364 ...
1 15 105 455 1365 ...
1 16 120 560 1820 4368 ...

1. Combinaciones con repetición

OK, ahora vamos con este...

Digamos que tenemos cinco sabores de helado: banana, chocolate,

limón, fresa y vainilla. Puedes tomar 3 paladas. ¿Cuántas variaciones
hay?

Vamos a usar letras para los sabores: {b, c, l, f, v}. Algunos ejemplos
son

 {c, c, c} (3 de chocolate)
 {b, l, v} (uno de banana, uno de limón y uno de vainilla)
 {b, v, v} (uno de banana, dos de vainilla)

(Y para dejarlo claro: hay n=5 cosas para elegir, y eliges r=3 de ellas.
El orden no importa, ¡y sí puedes repetir!)

Bien, no puedo decirte directamente cómo se calcula, pero te voy a enseñar

una técnica especial para que lo averigües tú mismo.
 Imagina que el helado está en contenedores, podrías decir
"sáltate el primero, después 3 paladas, después sáltate
los 3 contenedores siguientes" ¡y acabarás con 3 paladas
de chocolate!

Entonces es como si ordenaras a un robot que te trajera

helado, pero no cambia nada, tendrás lo que quieres.

Ahora puedes escribirlo como (la flecha es saltar, el círculo es

tomar)

Entonces los tres ejemplos de arriba se pueden escribir así:

{c, c, c} (3 de chocolate):

{b, l, v} (uno de banana, uno de limón y uno de

vainilla):

{b, v, v} (uno de banana, dos de vainilla):

OK, entonces ya no nos tenemos que preocupar por diferentes sabores, ahora tenemos
un problema más simplepara resolver: "de cuántas maneras puedes ordenar flechas y
círculos"

Fíjate en que siempre hay 3 círculos (3 paladas de helado) y 4 flechas (tenemos que
movernos 4 veces para ir del contenedor 1º al 5º).

Así que (en general) hay r + (n-1) posiciones, y queremos que r de ellas tengan
círculos.

Esto es como decir "tenemos r + (n-1) bolas de billar y queremos elegir r de ellas". Es
decir, es como el problema de elegir bolas de billar, pero con números un poco
distintos. Lo podrías escribir así:

donde n es el número de cosas que puedes

elegir, y eliges r de ellas
(Se puede repetir, el orden no importa)
Es interesante pensar que podríamos habernos fijado en flechas en vez de círculos, y
entonces habríamos dicho "tenemos r + (n-1) posiciones y queremos que (n-
1) tengan flechas", y la respuesta sería la misma...

¿Qué pasa con nuestro ejemplo, cuál es la respuesta?

(5+3-1)! 7! 5040
= = = 35
3!(5-1)! 3!×4! 6×24

En conclusión

¡Uau, es un montón de cosas que absorber, quizás tendrías que leerlo otra vez para
entenderlo todo bien!

Pero saber cómo funcionan estas fórmulas es sólo la mitad del trabajo. Averiguar cómo
se interpreta una situación real puede ser bastante complicado.

Por lo menos ahora sabes cómo se calculan las 4 variantes de "el orden sí/no importa"
y "sí/no se puede repetir".