• Author / Uploaded
• Deyvar Andres

Citation preview

Matemáticas Discretas LOGICA PROPOSICIONAL

Matemáticas Discretas




Estudio de objetos discretos Habilidad para razonar y argumentar Base otras áreas en computación      

Bases de datos Lenguajes formales Inteligencia Artificial Procesamiento Lenguaje natural Especificación formal de programas Web semántica..

Lógica






Base razonamiento matemático Argumentación Reglas para dar significado preciso a enunciados Base construcción argumentos válidos Aplicaciones variadas(diseño circuitos lógicos, verificación de programas, etc.)

Lógica Razonamiento lógico

Todos los matemáticos utilizan sandalias Cualquier persona que utilice sandalias es algebrista Por lo tanto, todos los matemáticos son algebristas.

Lógica Proposicional  Proposición  Notación:p,q,r,...  Constantes proposicionales:v,f  Valor de verdad (V, F)  Operadores (conectivos) lógicos  Fórmulas simples y compuestas  Precedencia de operadores lógicos

Lógica Proposicional Ejemplos de proposiciones Bogotá es la capitalde Colombia Lima es la capitalde Perú 2+ 2 = 5

Lógica Proposicional Ejemplos afirmaciones no proposiciones

¿Quéhora es? Mañana lloverá

Lógica Proposicional Indique cuáles de las siguientes expresiones son proposiciones x+ 1 = 7 11 es un número primo Andrés vivirá 60 años Sara es inteligente

Lógica Proposicional Representación:letras delalfabeto q:Bogotá es la capital de Colombia r:Lima es la capital de Perú p:2 + 2 = 5

Cada proposición tiene un valor de verdad,e indica si ésta es Verdadera (V)o Falsa (F)

Proposiciones Simples y Compuestas El secreto de la longevidad consiste en evitar el estrés
Hoy es miércoles y la temperatura es de 21ºC
Si no llueve voy a la clase de MD
No es cierto que Juan perdió el examen

Negación Sea p:Bogotá es la capital de Colombia, ¬p indica, Bogotá NO es la capital de Colombia Cómo son los valores de verdad de p y de ¬p

Negación Posibles valores de verdad de proposición p se pueden representar en la siguiente tabla p ¬p V

F

F

V

Tabla de verdad para la negación de una proposición

Conjunción p:Bogotá es la capitalde Colombia q:W ashington es la capitalde USA p ∧ q :Bogotá es la capitalde Colombia y W ashington es la capitalde USA.

Conjunción p

q

V V

V F

p∧q V F

F F

V F

F F

Tabla de verdad para la conjunción

Tabla de verdad para la conjunción

Ejemplos Los Red Soxganaron la serie mundial y los Yankees fueron eliminados

Ayer el Dólar bajó 5 pesos y el Euro subió 25

En este salón hay más hombres que mujeres y además tienen un buen promedio de calificaciones

Disyunción Los estudiantes quienes han visto cálculo o ITI pueden ver Algoritmia y Programación

En su plato de entrada puede tomar sopa o ensalada

Disyunción or -inclusivo Los estudiantes quienes han visto Cálculo o ITI pueden ver Algoritmia y Programación

or -exclusivo En su plato de entrada puede tomar sopa o ensalada

OR-inclusivo Los estudiantes quienes han visto Cálculo o ITI pueden ver Algoritmia y Programación V V F F

V F V F

? ? ? ?

OR-inclusivo p V V F F

q V F V F

pvq p∨ ∨q V V V F

Tabla de verdad del OR-inclusivo

OR-Exclusivo En su plato de entrada puede tomar sopa o ensalada

V V F F

V F V F

? ? ? ?

OR-Exclusivo (p ⊕ q) En su plato de entrada puede tomar sopa o ensalada p V V F F

q V F V F

p⊕q F V V F

Tabla de verdad del OR-exclusivo

Simbolización Usted puede hacer el examen parcial o el opcional Aquellas personas de 20 años o más, pueden entrar al concierto Carlos fue a jugar Béisbol o fue al cine Hamlet fue escrito en 1601 o en 1688 Sarah quiere a Oscar o a Juan

Condicional Considere la siguiente proposición

Si es un día soleado entonces voy a la playa

¿Quédebe ocurrir para que no se cumpla la proposición?

Condicional p V V F F

q V F V F

p
q V F V V

Tabla de verdad del Condicional

Recíproca Recríproca de p → q es la proposición q → p p:Hoy es martes q:Tengo un examen hoy p →q:Si hoy es martes entonces tengo un examen q →p:Si tengo un examen entonces es martes

Contrapositiva Contrapositiva de p
q es la proposición ¬q →¬p p:Hoy es martes q:Tengo un examen hoy ¬ q → ¬ p:Si NO tengo un examen entonces NO es martes

Bicondicional Sean p y q dos proposiciones, el bicondicional pq es la proposición que es verdadera cuando p y q tiene el mismo valor de verdad

p V V F F

q V F V F

p
q V F F V

Tabla de verdad del Bicondicional

Precedencia Operadores Conectivo

Significado

Proposición Compuesta

Nombre en lógica

∧

Y

p∧q

Conjunción

∨

O

p∨q

Disyunción

¬

No

¬p




Si .. Entonces

p
q

Condicional



Si y solo si

pq

Bicondicional

Negación

Formalización




Evita ambiguedad lenguaje natural Facilita análisis Determinación valor de verdad

Formalización Ejemplo Tienes una cuenta de correo electrónico en la EISC si estas matriculado en ITI o si eres estudiante del PAIS •Identificar frases componentes •Asignarles variable proposicional •Utilizar conectivos

Formalización Tienes una cuenta de correo electrónico en la EISC si estas matriculado en ITI o si eres estudiante del PAIS  Identificar frases componentes y Asignarles variables proposicionales • p:tienes una cuenta de correo electrónico en EISC • q:Estas matriculado en ITI • r:Eres estudiante del PAIS

 Utilizar conectivos

(q∨ ∨ r) → p

Formalización:ejercicios


No puedes conducir si eres menor de edad, a no ser que tengas un seguro especial




No se puede actualizar campos de un registro de la base de datos a menos que tengas un perfil de administrador

Operaciones con bits:aplicación Aplicación de lógica digital: Bits y conectivos lógicos
Construcción de compuertas lógicas
Bit:dos valores posibles 0 y 1 (Verdadero (V) es 1 y que Falso (F) es 0).
Variabl e Booleana:variable cuyo valor puede ser V o F.
Operaciones con Bits:conectivo lógicos (AND, OR, NOT, XOR)


Aplicación Cadenas de Bits:sucesión de cero o más bits operaciones aplicadas a cadenas de bits 0110110110 1100011101 1110111111 Operador ???? 0100010100 1010101011

Interpretación Asignación de valores de verdad a las variables proposicionales

Modelo de una fórmula Una Interpretación I que satisface la fórmula ϕ es un MODELO de ϕ

Tipos de Proposiciones


Tautología (Válidez)




Contradicción (Insatisfactiblidad)




Contingencia (Satisfactibilidad)

Validez,Satisfactibilidad Fórmula válida: si y solo si es verdadera para todas las interpretaciones. Fórmula insatisfactible (o inconsistente):si y solo si es falsa para todas las interpretaciones. Fórmula no válida:si y solo si hay al menos una interpretación que la haga falsa Fórmula satisfactible: si y solo si al menos una interpretación la hace verdadera

Ejercicio Clasificar las siguientes proposiciones como Tautología,Contradicción o Contingencia (¬p ∧ p)
¬ (p ∨ (¬ p ∧ q))
(¬ p ∨ q) (p →q)
(¬p ∧ ¬q)
¬(p ∨ q)

Equivalencia Lógica Dos fórmulas ϕ , δ son lógicamente equivalentes si para toda interpretación toman el mismo valor de verdad (ϕ ≡ δ)

Equivalencia Lógica Dos fórmulas ϕ , δ son lógicamente equivalentes si y solo si ϕ ↔ δ es una tautología

Equivalencia Lógica p V V F F

q V F V F

p ∨ q ¬(p ∨ q) V F V F V F F V

Equivalencia Lógica p V V F F

q V F V F

¬p F F V V

¬q F V F V

¬p ∧ ¬q F F F V

Equivalencia Lógica Las proposiciones (¬p ∧ ¬q) y ¬(p ∨ q) son entonces lógicamente equivalentes

Dos proposiciones compuestas p y q son lógicamente equivalentes si p  q es una tautología

Ejercicio Indique si las siguientes proposiciones compuestas son lógicamente equivalentes
p
q y ¬p ∨ q
p ∨ (q ∧ r)

y (p ∨ q ) ∧ (p ∨ r)


¬(p ⊕ q) y p ↔ q

Equivalencia Lógica Equivalencia p∧v⇔p p∨f⇔p p∨v⇔V p∧f⇔F (p
q) ⇔ (¬ p ∨ q) p∧¬p⇔F

Más Equivalencias Lógicas Doble Negación :p ≡ ¬¬p Idempotencia :p ∧ p ≡ p Idempotencia :p ∨ p ≡ p Ley asociativa :p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r Ley asociativa :p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r Ley de contrarrecíproca :(p → q) ≡ (¬q → ¬p) Ley conmutativa :p ∧ q ≡ q ∧ p Ley conmutativa :p ∨ q ≡ q ∨ p Ley distributiva :p ∨ ( q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r) Ley distributiva :p ∧ ( q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r)

Más Equivalencias Lógicas Leyes de DeMorgan:¬(p ∨ q) ≡ ¬p ∧ ¬q ¬(p ∧ q) ≡ ¬p ∨ ¬q Ley de implicación:p → q ≡ ¬p ∨ q Ley de cobertura:p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p Ley de contradicción:¬p ∧ p ≡ F ¬p ∨ p ≡ V

Equivalencia Lógica Muestre que ¬ ( p ∨ (¬ p ∧ q) ) y ¬p ∧ ¬q son lógicamente equivalentes 

Método 1:Construir una tabla de verdad 1:



Método 2:Utilizar las equivalencias lógicas 2:

conocidas, y partiendo desde una de las dos proposiciones lograr deducir la otra

Ejercicio Partir de p  p ∧ q hasta llegar a la proposición p ∧ 

 p  p ∧ q⇔ ???

Ejercicio Muestre que (¬p → ¬q) → q es lógicamente equivalente con (¬ p ∨ q) ∧ q

Muestre que ( p ∧ q ) → (p ∨ q) es una tautología

Más Ejercicios Muestre que las siguientes proposiciones compuestas son tautologías (p ∧ q)
p p
(p ∨ q) ¬p
(p
q) (p ∧ q)
(p
q)

Consecuencia Lógica Sean A y B dos formulas. Se dice B es consecuencia lógica de A (A  B) si toda interpretación que hace verdadera a A hace verdadera a B

Consecuencia Lógica Teorema 1 A  B si y solo si A →B es una tautología Por Ejemplo (¬p ∨ q) ∧ p q dado que (¬p ∨ q) ∧ p → q es una tautología

Consecuencia Lógica Ejercicio Demuestre que (¬p ∨ q) ∧ p → q es una tautología