Logica matematica

CURSO PROPEDÉUTICO DE MATEMÁTICAS

LÓGICA MATEMÁTICA

Raúl Ernesto González Torres
Cinvestav-Guadalajara
1 2

3

4

Contenido
Proposiciones Conectivos lógicos y tablas de verdad Tautologías, contradicciones y consecuencias lógicas Leyes de equivalencia. Álgebra booleana de proposiciones Cuantificadores universal y existencial. Fórmulas cuantificadas Métodos básicos de demostración enmatemáticas

Bibliografía
Notas de Álgebra Moderna
Raúl Ernesto González T., Ed. Iteso, 1996

Matemáticas Discretas
R. Johnsonbaugh, Ed. Prentice-Hall, 1999

Matemáticas Discreta y Combinatoria
Ralph P. Grimaldi, Ed. Pearson, 1997

Elements of Discrete Mathematics
C. L. Liu, Ed. McGraw-Hill, 1985

5

6

Proposiciones
Proposición es una afirmación de la cual podemos decir
quees falsa, o bien que es verdadera, pero no ambas cosas. EJEMPLOS: Son proposiciones

Proposiciones
De aquí en adelante, denotaremos a una proposición mediante una letra (como p, q, r, etc.), posiblemente con algún subíndice Para cada proposición hay dos posibles valores de verdad que le podemos asignar: V (verdadero) ó F (falso) y si tenemos una proposición p a la cual se le ha asignado elvalor de verdad V (o bien, el valor F), diremos también que p es verdadera (o que es falsa).

No son proposiciones d) “x + 2 = 3”. e) “¿Qué hora es?”. f) “20 ÷ 3”. g) “Esta afirmación es falsa”

a) “Tepic es la capital de Nayarit”. b) “Hay vida en Marte”. c) “4 + 5 = −8”.

7

8

Conectivos lógicos y tablas de verdad
Podemos formar nuevas proposiciones a partir proposiciones dadas medianteel uso de conectivos lógicos. Algunos de ellos son: ∧ ∨ ⇒ ⇔ ¬ “y” “o” “si —, entonces” “si y sólo si” “no” conjunción disyunción implicación doble implicación negación

Sean P y Q proposiciones. Formamos una nueva proposición, ¬P (que se lee “no P”), y la llamamos la negación de P. También podemos formar una nueva proposición usando cualquiera de estos símbolos:

∧, ∨, ⇒ y ⇔
Cada una de estasproposiciones se denota y llama por: (P ∧ Q) (P ∨ Q) (P ⇒ Q) (P ⇔ Q) la conjunción de P y Q la disyunción de P y Q la implicación de P y Q la doble implicación de P y Q

El significado que les damos trata de acercarse al uso común tanto como sea posible.

9

10

Tablas de verdad
El valor de verdad que le asignamos a cada una de las proposiciones compuestas depende de los valores deverdad asignados a las proposiciones más simples que las forman, tal como se establece en las tablas de verdad siguientes: p V V F F q V F V F ¬p F F V V p∧q V F F F p∨q V V V F p⇒q V F V V p⇔q V F F V

EJEMPLO: Construyamos la tabla de verdad de la proposición P:= (p1 ⇒ p3) ⇔ (¬p1 ∨ ¬p3) p1 V V F F p3 V F V F ¬p1 F F V V ¬p3 F V F V p1 ⇒ p3 V F V V ¬p1 ∨ ¬p3 F V V V P F F V V

11

12

La Islade los Caballerosos y los Bribones
Es una isla en la que hay sólo dos tipos de individuos: • • Los (o las) caballerosos, que siempre dicen la verdad Los (o las) bribones, que siempre mienten

McGregor tocó una puerta. El marido salió y preguntó qué deseaba. “Estoy realizando un reportaje sobre los habitantes de la isla”, replicó McGregor. ¿Podría información Necesitodecirme cuál de ustedes es,si acaso, un caballeroso y cuál es sobre usted y su esposa. un bribón?

El reportero McGregor ha ido de visita a la isla para interrogar a sus habitantes

¡Los dos somos bribones!
¿De cuál tipo es el marido y de cuál es la esposa?

13

14

McGregor fue a la casa siguiente y le preguntó al marido: ¿Son bribones los dos?

La siguiente casa visitada por McGregor resultó aún másintrigante. Ahí le preguntó al marido: ¿Puede decirme algo acerca de usted y su esposa? Si yo soy caballeroso, entonces también lo es mi esposa.

Al menos uno de los dos lo es.
¿De cuál tipo es cada uno?

¿De cuál tipo es el marido y de cuál es la esposa?

15

16

Tautologías y contradicciones
Sea T una proposición que se forma con las n letras proposicionales p1, p2 , ... , pn usando los...