Tema 70 Logica proposicional. Ejemplos y aplicaciones al razonamiento matematico 2015-16 PDF

Preview

Summary

Lógica proposicional...

Description

TEMARIO DE  MATEMÁTICAS TEMA 7 0: LÓGI CA PROPOSICIONAL. Y APLICACIONES AL EJEMPLOS RAZONAMIENTO MATEM ÁTICO. I. LÓGICA PROPOSICIONAL I.1. PROPOSICIÓN LÓGICA I.2. TABLAS DE VERDAD I.3. TAUTOLOGÍA Y CONTRADICCIÓN I.4. ÁLGEBRA DE BOOLE DE LAS PROPIEDADES I.5. FUNCIONES PROPOSICIONALES. CUANTIFICADORES

II. EJEMPLOS Y APLICACIONES DE LA LÓGICA AL RAZONAMIENTO MATEMÁTICO. II.1. TEORÍA MATEMÁTICA II.2. RAZONAMIENTO LÓGICO. REGLAS DE INFERENCIA LÓGICA II.3. RAZONAMIENTO MATEMÁTICO. MÉTODOS DE DEMOSTRACIÓN. ■ Demostración por implicación directa ■ Demostración por cadena de implicaciones ■ Demostración del contrarrecíproco ■ Demostración por reducción al absurdo ■ Demostración mediante un contraejemplo ■ Demostración por doble implicación ■ Demostración por inducción

III. BIBLIOGRAFÍA

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

                         

2

TEMA 7 0: LÓGI CA PROPOSICIONAL. Y APLICACIONES AL EJEMPLOS RAZONAMIENTO MATEM ÁTICO. Aplicamos constantemente el razonamiento lógico en Ciencias Sociales, Naturales, Físicas, Matemáticas y por supuesto, es la vida cotidiana. La Lógica es la disciplina que trata de los métodos de los razonamientos. Aporta reglas y técnicas para determinar si un argumento es o no válido. Su historia, a grandes rasgos, se divide en tres etapas: Lógica griega, Lógica escolástica y Lógica matemática. La Lógica contemporánea nace a mediados del siglo XIX, con la publicación del primer libro de Boole, en el que construye y desarrolla la Lógica formal como un nuevo tipo de Álgebra, demostrando que suministraba un algoritmo fácil para el razonamiento silogístico. Ya en el siglo XIX, Russell y Whitehead diseñan un programa para demostrar que toda la Matemática pura podía deducirse de un pequeño número de principios lógicos fundamentales, justificando así el punto de vista de Russell, para quien la Matemática y la Lógica son indistinguibles. Sin embargo, en 1931 Kurt Gödel demostró que en un sistema formulado de manera estrictamente lógica, tal como el que habían desarrollado Russel y Whitehead para la aritmética de los números naturales, hay siempre proposiciones indecidibles a partir de los axiomas del sistema, esto es, que no pueden ser demostradas ni refutadas. Este Teorema de Gödel suele considerarse el más importante de la lógica matemática. Para desarrollar este tema seguiré el esquema expuesto anteriormente.

I. LÓGICA PROPOSICIONAL I.1. PROPOSICIÓN LÓGICA Una proposición es una oración declarativa que es verdadera o falsa, pero no ambas cosas a la vez. El cálculo proposicional estudia las relaciones entre las proposiciones.

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

3

                         

Ejemplo: “La diagonal de un cuadro de lado 1 mide 2 ” es una proposición, en tanto que “x+2=1” no lo es, ya que es verdadera o falsa dependiendo del valor de x. Si una proposición es verdadera, se dice que toma el valor de verdad “verdadero”, y se simboliza “1”; si es falsa, su valor de verdad es “falso”, simbolizándose “0”. Los conectivos lógicos van a ser símbolos que permiten conectar entre sí proposiciones lógicas o modificar su valor de verdad. Los conectivos más usados son: SÍMBOLO

CONECTIVO

OPERACIÓN

EJEMPLO

LÓGICO "No"

ASOCIADA

p "No es cierto que p"

Negación

"y"

p q ; "p y q"

Conjunción

"o"

p q ; "p o q o ambas"

Disyunción inclusiva

"o"

p q ; "p o q pero no ambas"

Disyunción exclusiva

"Si ...

p

entonces..." "Si y sólo si"

p

q ; "Si p, entonces q" q ; "Si y sólo si p, entonces q"

Condicional Bicondicional

Una proposición es simple o atómica si no contiene ningún conectivo lógico, y es compuesta o molecular en caso contrario. Ejemplos de proposiciones simples: •

11 es un número primo (la denotaremos por p)

•

6 es un número primo (la denotaremos por q)

Ejemplos de proposiciones compuestas: •

6 no es un número primo ( q)

•

11 es un número primo y 6 no lo es (p

q)

I.2. TABLAS DE VERDAD La idea central del cálculo proposicional es que el valor de verdad de una proposición construida a partir de otras, con los conectivos lógicos anteriores, queda

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

4

                         

completamente determinado por los valores de verdad de las proposiciones que intervienen. Así, el método más conveniente para analizar los valores de verdad de una proposición molecular es una tabla, en la que aparezcan, por ejemplo, por columnas, las diversas proposiciones atómicas que la componen, y por filas, los posibles valores de verdad que puedan tomar, teniendo cuidado de escribir todas las combinaciones que existan entre los posibles valores de todas ellas. Estas tablas reciben el nombre de tablas de verdad. Sirvan como ejemplo las tablas de verdad correspondientes a las proposiciones moleculares: p, p ∨ q , p → q , p ↔ q ,p •

q.

Negación de una proposición p: p p p 1 0 0 1 Es verdadera si p es falsa, y es falsa si p es verdadera

•

Disyunción inclusiva de dos proposiciones p,q : p ∨ q p 1 1 0 0 Es verdadera cuando una

q p∨ q 1 1 0 1 1 1 0 0 o las dos proposiciones componentes son

verdaderas •

Conjunción de dos proposiciones p,q :

p ∧q

p q p∧ q 1 1 1 0 1 0 0 0 1 0 0 0 La conjunción de dos proposiciones es verdadera sólo cuando ambas lo son.

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

5

                         

•

Proposición condicional de p y q : p → q p 1 1 0 0

q 1 0 1 0

p →q 1 0 1 1

La proposición p → q es falsa sólo si p es verdadera y q es falsa. En esta proposición, p recibe el nombre de antecedente, y q de consecuente. •

Proposición bicondicional de p y q : p ↔ q p q p q 1 1 1 1 0 0 0 0 1 0 0 1 Esta proposición es verdadera si p y q son ambas verdaderas o ambas falsas.

•

Disyunción exclusiva de p y q : p q p q p q 1 1 0 1 0 1 1 0 1 0 0 0 Es verdadera sólo si una de las dos proporciones que la integran lo es. Calculemos ahora el valor de verdad de la proposición (p q)

(p

q) a

partir de los valores de verdad de las proposiciones simples y moleculares que la forman. Para ello, construyamos su tabla de verdad. p 1 1 0 0

q 1 0 1 0

p q 1 0 0 0

(p q) p q 1 0 0 1 1 0 1 0

(p q)

(p

q)

1 1 0 0

Por tanto, la proposición es verdadera cuando p lo es.

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

6

                         

I.3. TAUTOLÓGÍA Y CONTRADICCIÓN Una tautología es una proposición molecular que siempre es verdadera, independiente del valor de verdad de sus partes constituyentes. En una tabla de verdad, la columna correspondiente a una tautología se caracteriza porque sólo aparece el valor de verdad 1. Una contradicción o absurdo es una proposición molecular que siempre es falsa, independientemente del valor de verdad de sus partes constituyentes. En una tabla de verdad, la columna correspondiente a una contradicción se caracteriza porque sólo aparece el valor de verdad 0. Dos proposiciones moleculares P y Q se dice que son lógicamente equivalentes si la proposición bicondicional P ↔ Q es una tautología. Lo notaremos P ⇔Q .

De estas definiciones se deduce que todas las tautologías son lógicamente equivalentes entre sí, y que todas las contradicciones son lógicamente equivalentes entre sí. Notaremos por ʊ a una tautología y por  a una contradicción.

A continuación se recogen algunas propiedades de las tautologías y contradicciones en relación a otras proposiciones moleculares. Se demuestran fácilmente escribiendo la tabla de verdad correspondiente. Detallamos algunas de ellas a modo de ejemplo. El resto se demuestra de forma análoga. 1.

La negación de una tautología es una contradicción:

ʊ 1

2.

ʊ 0

ʊ

⇔

 0

La negación de una contradicción es una tautología: ⇔

ʊ

  ʊ 0 1 1

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

7

                          

3.

La disyunción inclusiva de una proposición y su negación es una

tautología: p ( p) ⇔ ʊ . p 1 0

4.

p 0 1

ʊ

p ( p) 1 1

1 1

La conjunción de una proposición y su negación es una contradicción:

[ p ( p) ⇔  ] 5.

La conjunción de una proposición y una tautología es lógicamente

equivalente a la misma proposición: (p 6.

La disyunción inclusiva de una proposición y una tautología es una

tautología: (p 7.

ʊ ⇔ ʊ)

La conjunción de una proposición y una contradicción es una

contradicción: (p 8.

ʊ⇔p)

 ⇔ )

La disyunción inclusiva de una proposición y una contradicción

es

lógicamente equivalente a la misma proposición: (p  ⇔ p) Ejemplos de tautologías: •

Ley de identidad: p → p p p p 1 0 1 0

•

Ley de contraposición Tollendo Tollens: p 1 1 0 0

q p q 1 1 0 0 1 1 0 1

p 0 0 1 1

q 0 1 0 1

q

p

(p

1 0 1 1

(p q)

q) ( q 1 1 1 1

( q

p) p)

Ejemplo de contradicción: p ( p) p 1 0

p p ( p) 0 0 1 0

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

8

                          

I.4. ÁLGEBRA DE BOOLE DE LAS PROPOSICIONES Sea P el conjunto de todas las proposiciones lógicas y consideremos en P las operaciones disyunción (inclusiva) y su conjunción. Es claro que estas dos operaciones son internas en P.

ʊ) ⇔ p, y

Hemos visto anteriormente que (p

(p  ⇔ p), luego el elemento

neutro de la conjunción es una tautología, y el de la disyunción (inclusiva) una contradicción. El conjunto P con las operaciones conjunción, disyunción y negación cumple las siguientes propiedades:

p ∧ p ⇔ p 1. Propiedades idempotentes:  p ∨ p ⇔ p p ∧ p ⇔ q ∧ p 2. Propiedades conmutativas:  p ∨ q ⇔ q ∨ p  ( p ∧ q) ∧ r ⇔ p ∧ ( q∧ r) 3. Propiedades asociativas:   ( p ∨ q) ∨ r ⇔ p∨ ( q∨ r) 4. Propiedades de absorción o simplificativas:

p ∧ (p ∨ q) ⇔ p  p ∨ (p ∧ q ) ⇔ p

p ∧ (q ∨ r ) ⇔ (p ∧ q ) ∨ ( p ∧ r ) 5. Propiedades distributivas:  p ∨ (q ∧ r ) ⇔ (p ∨ q ) ∧ (p ∨ r ) p⇔  y p

6. Propiedades de la negación: p

p ⇔ ʊ

Por tanto, el conjunto P es un retículo (verifica propiedades 1,2,3,4) distributivo y complementario, es decir,

es un álgebra de Boole, llamada

álgebra de Boole de las proposiciones. Es, además, un álgebra binaria o valorada, ya que cada proposición lógica puede tomar el valor de verdad 0 ó 1. Se verifican también las siguientes propiedades: 7. Propiedad de la doble negación:

p⇔ p

8. Leyes de De Morgan: (p

q) ⇔

p

q

(p

q) ⇔

p

q

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

                          

9

Todas estas propiedades se demuestran mediante las tablas de verdad, análogamente a como se han demostrado los ejemplos anteriores.

I.5. FUNCIONES PROPOSICIONALES. CUANTIFICADORES Sea E un conjunto no vacío, que llamaremos referencial. Una función proposicional sobre E es una expresión f(x) tal que al sustituir x por cualquier elemento t ∈ E se obtiene una proposición f(t) cuyo valor de verdad está perfectamente determinado. Ejemplo: Sea E = ℤ , y consideremos la expresión f(x) definida así: “f(x) : x es impar”. Es una función proposicional, pues a partir de ella se obtienen proposiciones como: f(1): 1 es impar, cuyo valor de verdad es 1; f(2): 2 es impar, cuyo valor de verdad es 0. Una función proposicional f(x) determina una partición en el conjunto E.

E f,1 es la clase verdad: Subconjunto de E formado por todos los elementos para los que la proposición es verdadera.

E f,0 es la clase falsa: Subconjunto de E formado por todos los elementos para los que la proposición es falsa. Para las funciones proposicionales se definen la conjunción, disyunción y negación de modo análogo a como se hizo con las proposiciones. Sean f(x) y g(x) dos funciones proposicionales sobre un mismo referencial E. Se comprueba fácilmente que las siguientes propiedades son ciertas: 1. La clase verdad de la función proposicional conjunción es igual a la intersección de las clases verdad de las dos funciones proposicionales.

Ef ∧ g,1 = E f,1 ∩ E g,1 2. La clase verdad de la función proposicional disyunción es igual a la unión de las clases verdad de las dos funciones proposicionales. Ef ∨ g,1 = E f,1 ∪ E g,1 3. La clase verdad de la función proposicional negación es igual al complementario de la clase verdad de la función proposicional. E¬ f,1 = E f,1

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

                          

10

De un modo análogo al visto para las proposiciones se demuestra que el conjunto de las funciones proposicionales tiene estructura de álgebra de Boole. Sea f(x) una función proposicional definida en el conjunto referencial E. Si ocurre que Ef,1 = E , se dice que f(x) se cumple para todo elemento de E. Lo notamos: ∀x ∈ E : f(x) . El símbolo ∀ , que transforma una función proposicional en una proposición, recibe el nombre de cuantificador universal. Si ocurre que al menos para uno de los elementos del referencial, a ∈ E , la función proposicional se hace cierta, se dice que existe al menos un elemento a de E que cumple f(x) y se nota: ∃a ∈ E : f(x) . El símbolo ∃ , que transforma una función proposicional en una proposición, se llama cuantificador existencial. Veamos dos ejemplos: • Sea E = { 2,4,6,8} . Consideremos la función proposicional “f(x): x es múltiplo de 2”. Se tiene que:

∀ x ∈ E : x es múltiplo de 2 • Sea E = { 2,4,6,8,9,10}. Consideremos la función “f(x): x es múltiplo de 3”. Entonces:

∃x ∈ E : x es múltiplo de 3 En cuanto a la negación de proposiciones cuantificadas, obsérvese que basta cambiar el cuantificador y negar la función proposicional:

( ∀x : f(x) ) equivale a ∃x : ( ∃x : f(x))

equivale a ∀x :

f(x) f(x)

II. EJEMPLOS Y APLICACIONES DE LA LÓGICA AL RAZONAMIENTO MATEMÁTICO II.1. TEORÍA MATEMÁTICA Las Teorías Matemáticas suelen seguir el siguiente esquema: 1. Términos primitivos: Definiciones iniciales de los elementos u objetos matemáticos que se utilizarán en la Teoría.

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

                          

11

2. Axiomas o postulados: Principios básicos que rigen los términos primitivos, considerados a priori como verdaderos y admitidos sin demostración. Los axiomas han de ser compatibles, independientes y suficientes en número. 3. Proceso de demostración o deducción: Proceso en el que se obtienen resultados posteriores, deducidos de los axiomas y las definiciones. Son los Teoremas, Corolarios, que completan la Teoría Matemática. Por ejemplo, en la Geometría Clásica, los términos primitivos serían las nociones de punto, recta y plano; los axiomas, los Postulados de Euclides; el proceso de deducción, todos los resultados de esta Teoría.

II.2. RAZONAMIENTO LÓGICO. REGLAS DE INFERENCIA LÓGICA De forma análoga a la Teoría Matemática, el razonamiento lógico sigue el siguiente esquema: 1. Proposiciones lógicas y términos de enlace entre éstas, que ya hemos visto en la primera parte del tema, y que hacen el papel de los términos primitivos. 2. Axiomas o principios lógicos, que son los siguientes: • Principio de Identidad: Todo objeto de una Teoría, cualquiera que sea su naturaleza, es igual a sí mismo. • Principio de Exclusión: Toda proposición relativa a un objeto es verdadera o falsa, excluyéndose una tercera posibilidad. • Principio de Contradicción: Toda proposición relativa a un objeto no puede ser simultáneamente verdadera y falsa. 3. Inferencia lógica, que es el nombre que recibe el proceso de deducción del razonamiento lógico. Veamos en qué consiste. Uno de los objetivos principales de la lógica es deducir conclusiones a partir de un conjunto de proposiciones conocidas, llamadas premisas. Este proceso de deducción recibe el nombre de inferencia lógica. Una inferencia lógica es válida cuando el paso de las premisas a la conclusión satisface alguna de las reglas de inferencia que a continuación veremos.

Queda totalmente prohibida la copia, reproducción, modificación, distribución u otro uso no autorizado de este temario.

                          

12

Para que la conclusión sea verdadera, han de serlo las premisas. Recíprocamente, de unas premisas verdaderas se obtiene una conclusión verdadera. • Regla de modus Ponens: “Si las premisas de un razonamiento son una condicional y su antecedente, se deduce su consecuente como conclusión”. Esquemáticamente: p → q Pr emisas p  q ] Conclusión Ejemplo: Supongamos que nos vienen dadas las siguientes proposiciones como premisas: R Si hoy es lunes, mañana es martes. R Hoy es lunes. Si p= Hoy es lunes, y q= Mañana es martes, dado que tenemos como premisas p → q , p, podemos deducir q, es decir, “Mañana es martes”. A c...