Ejercicio

Teoría elemental de 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 efectuardiversas 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 1 0

p' 0 1

A continuación se describen lasprincipales 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 0 0 1 0 0

1 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. Seescribe p  q, y se lee "p o q".

p q pq 1 1 1 0 0 1 0 0 1 1 1 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 1 0 0 1 0 0 0 1 1 0

Condicional: es aquella proposición que es falsa únicamente cuando lacondició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 0 1 0

0 1 0 0

1 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 0 0 1 0 0 1 0 0 1

Una proposición sedice 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 asignarningú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' sonequivalentes. 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 conm = 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, ... }"...