U_tad _ Ingeniería de software _ asignatura_ Matemática Discreta _ Logica y D

Vista previa del material en texto

LÓGICA Y DEMOSTRACIONES
Tema 4
Lógica y Matemática Discreta
 2021/2022
 Mar Angulo Martínez
 Álgebra de Boole
Álgebra de Boole: estructura que proporciona reglas y operaciones para trabajar con el conjunto binario {0,1}
 
Si designamos el conjunto binario B={0,1}. Una variable x es una variable booleana si únicamente toma los valores 0 y 1
 
Una función booleana es la que asigna como imagen sólo los valores 0 y 1 (verdadero/falso; TRUE/FALSE)
 
‹Nº›
 Álgebra de Boole
Las operaciones booleanas básicas:
 
Complemento booleano
Equivale al operador lógico de negación
 	 
Suma booleana
Equivale al operador lógico (Verdadero si alguno de los dos es verdadero)
	0+0=0	0+1=1		1+0=1		1+1=1
 
Producto booleano
Equivale al operador lógico (Verdadero si los dos son verdaderos)
	0.0=0	0.1=0		1.0=0		1.1=1
‹Nº›
 Álgebra de Boole
Expresión booleana de las variables x1, x2,….xn xi 
verifica:
x1, x2,….xn son expresiones booleanas
los elementos 0 y 1 son expresiones booleanas
Si E1 y E2 son expresiones booleanas, entonces , E1 . E2 y E1 + E2 son expresiones booleanas
‹Nº›
 Estructura de álgebra de Boole
B es el conjunto binario {0,1} dotado de una operación binaria, denominada SUMA (+) tal que BxB
		 (x,y)
 de otra operación binaria, denominada PRODUCTO (.) tal que 
		BxB
		(x,y)
y de una tercera operación, denominada COMPLEMENTO () tal que 
		B
		x
 Álgebra de Boole
‹Nº›
 Álgebra de Boole
el conjunto B tiene estructura de álgebra de Boole si verifica:
 1) Leyes de identidad x+0=x x.1=x
 2) Leyes dominativas	 	 x+=1 x.=0 
 3) Leyes asociativas (x+y)+z=x+(y+z) (x.y).z=x.(y.z) 
 4) Leyes conmutativas x+y = y+x x.y = y.x
 5) Leyes distributivas x+(y.z) = (x+y).(x+z) x.(y+z) = x.y + x.z
 
Nota
El conjunto de subconjuntos del universal U con las operaciones constituyen un álgebra de Boole.
Lo mismo ocurre en la lógica de proposiciones con las operaciones , T y F 
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
 Proposición
Es una expresión declarativa, una frase o un enunciado que puede ser verdadero o falso, pero no ambas cosas a la vez
Ejemplos				
Madrid es la capital de España	
2+2=5
El año 2020 es bisiesto
 
 
 Son proposiciones
¿el año 2020 es bisiesto?	
Identifica si esto es una proposición
X+2=5
 
 NO Son proposiciones
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
 Valor de verdad de una proposición 
es verdadero (TRUE), V, si la proposición es verdadera
Es falso (FALSE), F, si la proposición es falsa
 
Lógica proposicional (o Cálculo proposicional) se basa en ir construyendo proposiciones compuestas o nuevas proposiciones a partir de otras existentes utilizando operadores lógicos.
 
Tabla de verdad muestra las relaciones entre los valores de verdad de las proposiciones
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
 Negación de p ( Se lee “no p”
Conjunción de p y q (p ^ q) Se lee “p y q”
Es una proposición verdadera cuando tanto p como q son verdaderas y falsa en cualquier otro caso
 
Disyunción de p y q (p V q) Se lee “p o q”
Es una proposición falsa cuando tanto p como q son falsas y es verdadera en cualquier otro caso
 Operadores lógicos
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
Conectivo exclusivo de p y q (p q) Se lee “sólo p o sólo q”
Es una proposición verdadera cuando sólo una de las dos proposiciones es verdadera y falsa en cualquier otro caso
Lógica de Proposiciones
Ejemplo 1
p: un estudiante ha cursado la asignatura de cálculo
q: un estudiante ha cursado la asignatura de computación
¿Cómo expresarías la conjunción, la disyunción y el conectivo exclusivo de p y q?
¿Cómo serían las correspondientes tablas de verdad?
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
	p	q	p^q
	V	V	V
	V	F	F
	F	V	F
	F	F	F
	p	p	pVq
	V	V	V
	V	F	V
	F	V	V
	F	F	F
	p	p	pq
	V	V	F
	V	F	V
	F	V	V
	F	F	F
Conjunción de p y q	Disyunción de p y q 	 Conectivo exclusivo de p y q
Tablas de Verdad
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
Implicación(p q) (o condicional). Se lee “si p, entonces q”
Es falsa SÓLO en el caso de que p sea verdadera y q sea falsa
p se denomina hipótesis (premisa o antecedente) y q se denomina tesis (conclusión o consecuente)
Expresiones en el razonamiento matemático:
p implica q		si p, entonces q
P es suficiente para q	q es condición necesaria para p
q siempre que p		si no q, entonces no p
p sólo si q		q se deduce de p
Idea: pensar en una obligación, un compromiso o un contrato
‹Nº›
Recíproca(q p) (p q). Se lee “p es condición necesaria”
Es falsa SÓLO en el caso de que q sea verdadera y p sea falsa
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
Ejemplo 2
“Si consigues un mínimo de 5 en el examen final, apruebas la asignatura”
Ejemplo 3
“Si salgo elegido, bajaré los impuestos”
Contrarrecíproca(q p). Tiene la misma tabla de verdad que la implicación . Implicación y Contrarrecíproca son equivalentes
Inversa (p q). Tiene la misma tabla de verdad que la recíproca. Inversa y recíproca son equivalentes.
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
	p	q	pq
	V	V	V
	V	F	F
	F	V	V
	F	F	V
	p	q	pq
	V	V	V
	V	F	V
	F	V	F
	F	F	V
	Implicación 		 		Recíproca 	
Tablas de Verdad
‹Nº›
Lógica de Proposiciones
Nota importante:
El concepto matemático de implicación es independiente de la relación causa –efecto entre hipótesis y conclusión
La construcción “si p, entonces q” se utiliza de forma diferente en lógica que en programación
Lenguajes de programación: if p then S (segmento de programa)
 Ejemplo if 2+2=4 then x = x+1
Ejemplo 6
¿Cómo expresarías la recíproca, la contrarrecíproca y la inversa de la implicación “el equipo local gana siempre que llueve”?
‹Nº›
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
OPERACIONES ENTRE CONJUNTOS
AB = {x/ ó x
 A{x/ y x
A-B = { / x 
 
 
Lógica de Proposiciones
Doble implicación (equivalencia) (p q) Se lee “p si y sólo si q”
Es verdadera cuando p y q son simultáneamente verdaderas o falsas
p se denomina hipótesis (premisa o antecedente) y q se denomina tesis (conclusión o consecuente)
Ejemplo 4
¿Cómo formalizarías la frase “puedes acceder a Internet desde el campus sólo si estudias ciencias de la computación o no eres alumno de primero”?
Ejemplo 5
Y “no puedes montar en la montaña rusa si mides menos de 1,20 metros, a no ser que seas mayor de 16 años”
‹Nº›
Ejemplo 7
Dadas p, q y r, expresar los siguientes enunciados:
	
r las bayas del sendero están maduras
Las bayas del sendero están maduras, pero no se han visto osos pardos por la zona
No se han visto y 
Si las bayas del sendero están maduras, es seguro caminar por el sendero si, y sólo si, no se han visto osos pardos por la zona
No es seguro caminar por el sendero, pero no se han visto osos pardos por la zona y las bayas del senderoestán maduras
Para que sea seguro caminar por la zona, es necesario, pero no suficiente, que las bayas del sendero no estén maduras y que no se hayan visto osos pardos por la zona
No es seguro caminar por el sendero cuando se han visto osos pardos por la zona y las bayas del sendero están maduras
Lógica de Proposiciones
‹Nº›
Lógica de Proposiciones
	p	q	
	V	V	V
	V	F	F
	F	V	F
	F	F	V
	p	q	
	V	V	F
	V	F	V
	F	V	V
	F	F	F
	Equivalencia				p
‹Nº›
Lógica de Proposiciones
Ejemplo 8
Construye las tablas de verdad para cada una de estas fórmulas:
p 
‹Nº›
Lógica de Proposiciones
Tautología es una fórmula o proposición que es siempre verdadera
Contradicción es una fórmula o proposición siempre falsa
Contingencia es una proposición que no es ni tautología ni contradicción
Proposiciones lógicamente equivalentes (p
 
Ejemplo 9
Demuestra que las proposiciones y 
‹Nº›
Demostraciones
¿Cuándo es correcto un argumento matemático?
¿Qué métodos son válidos/aplicables para construir argumentos matemáticos?
‹Nº›
Demostraciones
Teorema es una sentencia que se puede verificar que es verdadera.
Lema: teorema muy sencillo que se emplea en la demostración de un teorema
Corolario es una proposición que se puede deducir fácil o directamente a partir de un teorema ya demostrado
Conjetura es una proposición que aún no ha sido demostrada
Axiomas o postulados (hipótesis del teorema) son sentencias que no requieren demostración 
La secuencia de sentencias que permiten efectuar esa verificación conforman un argumento que llamamos Demostración
Las reglas de inferencia son el enlace en cada uno de los pasos de una demostración, que permiten inferir conclusiones a partir de otras afirmaciones
 
‹Nº›
Demostraciones
Comprobar la validez de un razonamiento matemático: si construimos la tabla de verdad de la implicación y el resultado es una tautología
Ejemplo 10
A q
Ejemplo 11
A) 
‹Nº›
Demostraciones
	Reglas de inferencia		
	Regla de inferencia
	Tautología
p
p
pq
p
	Nombre
			Adición
			Simplificación
			Modus ponens
			Modus tollens
			Silogismo hipotético
			
‹Nº›
Demostraciones
Métodos de demostración 
Demostraciones directas
Se demuestra la implicación p (si p es verdadera, q también es verdadera)
Demostraciones indirectas
Se demuestra la implicación (si q es falsa, entonces p también es falsa)
	 
‹Nº›
Demostraciones
La reducción al absurdo
Se parte de una premisa falsa y se llega a demostrar algo que resulta ser una contradicción: encontrar una contradicción q tal que 
Falsa
Ejemplo 12: demostrar que es irracional
Demostración por casos
Demostrar que … 
	
‹Nº›
Demostraciones
Demostración por equivalencia	
Demostrar que 
El Principio General de Inducción
P() 
Ejemplo 13: demostrar que +…+
 
-1
‹Nº›
Predicado es una proposición que se refiere a uno o varios objetos (x,y,z…) variables de un conjunto. Se denota P(x,y,z…)
El valor de verdad o falsedad de un predicado depende del valor de verdad o falsedad de los objetos variables que maneja
El número total de variables de las que depende el predicado se denomina peso del predicado
Ejemplo 14
P(x) es el predicado de la proposición 8 + x = 15
El predicado sólo será Verdadero cuando el objeto x sea igual a 7
 Lógica de Predicados
‹Nº›
Ejemplo 15
P(x, y) es x+y=10 será cierto en función de los valores de x e y. P(3,7) es cierto; P(4,7) falso
Lógica de Predicados
Ejemplo 17
el predicado P(n): es un número entero par es cierto únicamente cuando n sea par
Ejemplo 16
P(x, y) es x+y=10 será cierto en función de los valores de x e y. P(3,7) es cierto; P(4,7) falso
‹Nº›
Lógica de Predicados
Conectivas entre predicados
 es el predicado que asocia x con la negación de P(x)
P(x) es el predicado que asocia x con la unión de proposiciones P(x) y Q(x)
P(x) es el predicado que asocia x con la intersección de proposiciones P(x) y Q(x)
‹Nº›
Lógica de Predicados
Una función proposicional P(x,y,z), una vez que se asignan valores concretos a cada uno de los valores, se convierte en una proposición.
La expresión P(x) significa que P(x) es cierta para todos los valores de x
(cuantificador universal)
La expresión P(x) asegura la existencia de valores de x para los que P(x) es cierta
(cuantificador existencial)
Ejemplo 18
 P(x,y) 
‹Nº›
Lógica de Predicados
Si queremos negar P(x) : es equivalente a decir que existe un x que no verifica P(x)
 
Y si queremos negar la existencia: es equivalente a asegurar que todos los valores verifican la negación
Ejemplo 19
P(x): x se mueve	Q(x): x tiene color
(P(x)∨ Q(x))	 P(x))∨ Q(x))
Todos los vehículos se mueven o tienen color no implica la veracidad de “todos los vehículos se mueven o todos tienen color. La recíproca sí es cierta
‹Nº›