Logica binaria

Cap´ ıtulo 1: Fundamentos: L´gica y o Demostraciones Clase 1: L´gica Proposicional o
Matem´tica Discreta - CC3101 a Profesor: Pablo Barcel´ o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica y Demostraciones a o

1 / 30

¿Qu´ es la l´gica? e o
La l´gica es el estudio de las leyes del pensamiento (Kant, 1785). o En la actualidad se considera que la l´gica es elestudio de qu´ es o e lo que hace que un argumento se considere correcto (en forma y no en contenido). En otros t´rminos, de cu´ndo una conclusi´n se deduce e a o l´gicamente de ciertas premisas. o Ejemplo: ¿Es el siguiente argumento v´lido? a Todos los hombres son mortales. S´crates es hombre. o Por lo tanto, S´crates es mortal. o ¿Hay algo en este argumento que dependa de S´crates mismo? o

P.Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica y Demostraciones a o

2 / 30

Ejemplo de razonamiento l´gico o

Ejercicio: ¿Cu´l es la forma del siguiente argumento? a Si Pedro estudia en el DCC o en el CMM, entonces tomar´ CC4OC. a Pedro estudia en el DCC. Por tanto, Pedro tomar´ CC4OC. a

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica yDemostraciones a o

3 / 30

Ejemplo de razonamiento l´gico o

Ejercicio: ¿Cu´l es la forma del siguiente argumento? a Si Pedro estudia en el DCC o en el CMM, entonces tomar´ CC4OC. a Pedro estudia en el DCC. Por tanto, Pedro tomar´ CC4OC. a

(p ∨ q) → r p r

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica y Demostraciones a o

3 / 30

Aplicaciones de la l´gica en CS oLa l´gica es la base de todo el razonamiento matem´tico, y o a tambi´n de todo el razonamiento automatizado. e Tiene aplicaciones pr´ticas en CS en los siguientes campos (entre a muchos otros):
◮ ◮ ◮ ◮ ◮

Dise˜o de hardware; n ingenier´ de software; ıa bases de datos; inteligencia artificial; lenguajes de programaci´n. o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos:L´gica y Demostraciones a o

4 / 30

L´gica proposicional o

Empezaremos con el ejemplo m´s b´sico de lenguaje l´gico: la a a o l´gica proposicional. o Esta est´ construida a partir de proposiciones, que son oraciones a que son verdaderas o falsas (pero no ambas).
◮ 6 Santiago es la capital de Chile, (1 + 1 = 3), (1 + 1 = 3 ).

Las siguientes, en cambio, no son proposiciones:
◮

¿Qu´ horaes?, (x + 1 = 2). e

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica y Demostraciones a o

5 / 30

Valores de verdad

Nos evitaremos problemas sem´nticos, y denotaremos nuestras a proposiciones por letras min´sulas p, q, r , . . . , p1 , p2 , . . . . u Cada proposici´n tiene un valor de verdad asignado, que puede ser o 1 (si la proposici´n es verdadera) o 0 (si laproposici´n es falsa). o o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1: Fundamentos: L´gica y Demostraciones a o

6 / 30

Oraciones
o Una oraci´n se construye a partir de las proposiciones p, q, r , . . . , usando adem´s tres s´ a ımbolos nuevos: ¬, ∨, ∧.
◮

Dada una proposici´n p, la oraci´n ¬p denota que ’p es o o o falso’. Se llama la negaci´n de p. Dadas proposiciones p y q,la oraci´n p ∨ q denota que ’p o o o q’, y se llama la disyunci´n de p y q. Dadas proposiciones p y q, la oraci´n p ∧ q denota que ’p y o q’, y se llama la conjunci´n de p y q. o

◮

◮

En general los s´ ımbolos ¬, ∨, ∧ se aplican no s´lo a las o proposiciones sino tambi´n a las oraciones: e
◮

(¬(p ∨ (q ∧ r ))) ∨ s, (p ∨ q) ∨ r .

P. Barcel´ o

–

Matem´tica Discreta - Cap. 1:Fundamentos: L´gica y Demostraciones a o

7 / 30

Par´ntesis e

En las oraciones anteriores utilizamos par´ntesis para evitar e ambiguedades en el orden de aplicaci´n de los s´ o ımbolos ¬, ∨, ∧:
◮

¿Qu´ significa p ∨ q ∨ r ? e

Usualmente asumimos que ¬ siempre se aplica antes que cualquier otra operaci´n, y por tanto, ¬p ∧ q es lo mismo que (¬p) ∧ q. o

P. Barcel´ o

–

Matem´tica...