Matematicas Discretas

TEMA:

RESUMENES DEL TEMARIO DE LA UNIDAD III TEMAS DEL 3.1.4 AL 3.5



MATERIA:

MATEMATICAS DISCRETAS





NOMBRE DE LA PROFESORA:

Ing. LAURA MORON VAZQUEZ



CARRERA:

INGENIERIA INFORMATICA







FECHA DE ENTREGA:

3 de diciembre de 2012











INDICE

UNIDAD III

3.1.4 TAUTOLOGIAS, CONTRADICCION Y CONTINGENCIA

3.1.5 EQUIVALENCIASLOGICAS

3.1.6 REGLAS DE INFERENCIA

3.1.7 ARGUMENTOS VALIDOS Y NO VALIDOS

3.1.8 DEMOSTRACION FORMAL (DIRECTA POR CONTRADICION)

3.2 LOGICA DE PREDICADOS

3.2.1 CUANTIFICADORES

3.2.2 REPRESENTACION Y EVALUACION DE RESULTADOS

3.3 ALGEBRA DECLARATIVA

3.4 INDUCCION MATEMATICA

3.5 APLICACIÓN DE LA LOGICA MATEMATICA EN LA COMPUTACION3.1.4 TAUTOLOGIAS, CONTRADICCION Y CONTINGENCIA

Definiciones:

• Tautología: Son todas aquellas formulas que son ciertas para cualquier valoración de los símbolos proposicionales que contiene.

ϕ ∈ LΣ ϕ tautología ⇔ ∀ V [ϕ]V = 1 (o V ⎞ϕ )

• Contradicción: Son todas aquellas formulas que son falsas para cualquier valoración de los símbolos proposicionales quecontiene.

ϕ ∈ LΣ ϕ contradicción ⇔ ∀ V [ϕ]V = 0 (o V ⎞ ϕ )

• Contingencia: Son todas aquellas formulas cuyo valor de verdad o falsedad dependen de la valoración de los símbolos proposicionales que contiene.

Ejemplo:

Demostrar que ϕ = (p → q) ∧ p ∧ ¬q es una contradicción.

Reducción al absurdo:

➢ Supongamos que existe valoración V tal que V➢ Entonces V p → q, V p, V ¬q

➢ Pero no es posible [p → q]V = 1 con V(p) = 1 y V(q) = 0

ƒ























3.1.5 EQUIVALENCIA LOGICA

Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos.

En lógica, las sentencias p y q son lógicamente equivalentes siposeen el mismo contenido lógico.

Sintácticamente p y q son equivalentes si cada una puede probar a la otra. Semánticamente p y q son equivalentes si ambas tienen el mismo valor de verdad en cada modelo.

La equivalencia lógica de p y q a veces se denota:



• o bien [pic]



Sin embargo, estos símbolos son también utilizados para denotar el bicondicional. La interpretación propiadepende del contexto y aunque ambos conceptos están fuertemente relacionados, la equivalencia lógica es diferente de la equivalencia material.





























3.1.6 REGLAS DE INFERENCIA

Regla de inferencia es un esquema para construir inferencias válidas. Estos esquemas establecen relaciones sintácticas entre un conjunto de fórmulas llamados premisas y unaaserción llamada conclusión.

Las reglas también se aplican a la lógica informal y a las discusiones, pero la formulación es mucho más difícil y polémica.

Las reglas también se aplican a la lógica informal y a las discusiones, pero la formulación es mucho más difícil y polémica.

Como se mencionó la aplicación de una regla de inferencia es un procedimiento puramente sintáctico. Sin embargodebe también ser el válido o mejor dicho preservar la validez. Para que el requisito de preservación de la validez tenga sentido es necesaria una cierta forma semántica para las aserciones de las reglas de inferencia y las reglas de inferencia en sí mismas.

Reglas de Inferencia Deductiva:

MPP Modus ponendo ponens
A → B
A
- – - – -
B



MTT Modus tollendo tollens
A → B
¬B
- – - –-
¬A











SD Silogismo Disyuntivo
A ∨ B
¬A
- – - – -
¬B



SH Silogismo hipotético
A → B
B → C
- – - – -
A → C



LS Ley de simplificación
A ∧ B
- – - – -
A



LA Ley de adición
A
- – - – -
A ∨ B



Contra positiva

A → B
- – - – -
¬B → ¬A









3.1.7 – AGUMENTOS VALIDOS E INVALIDOS

En matemáticas y en lógica un argumento no...