Lenguaje natural y matemático: lógica y algoritmos

Temáticas:

❖ Proposiciones❖ Cuantificadores❖ Estructuras matemáticas ❖ Algoritmos❖ Algoritmos recursivos

La lógica es el estudio del razonamiento deductivo en la que en un argumento

matemático debe estar justificada una conclusión por si misma o se debe

deducir de afirmaciones precedentes.

¿Qué es lógica matemática?

¿Qué se construye la lógica?

Se construye con proposiciones definidas como una oración declarativa que es

verdadera V o falsa F y usando operadores o conectivos lógicos. Las siguientes

son proposiciones del lenguaje natural

Toronto es la capital de Canadá 2+2=3

CONTENIDO OVA

Conjunción: Corresponde al conector “y” y se denota por ∧. Es verdadera cuando ambas proposiciones p y q son verdaderas

Negación Corresponde a la conectiva “no” y se denota por¬.

Disyunción: Corresponde al conector “o” y se denota por ∨. Es falsa cuando ambas p y q son falsas y verdadera en cualquier otro caso

Proposiciones p y q: construcción

de tablas de verdad

p ¬pV FF V

p q p ∧ qV V VV F FF V FF F F

p q p ∨ qV V V

V F V

F V V

F F F

CONTENIDO OVA

Implicación: Corresponde al conector “implica” y se denota por→. Es falsa cuando p es verdadera y q es falsa y verdadera en cualquier otro caso.

Doble implicación : Corresponde al conector “si y sólo si” y se denota por ↔. Es verdadera cuando p y q son ambas verdaderas o ambas falsas.

p q p → qV V VV F FF V VF F V

p q p ↔ q

V V V

V F F

F V F

F F V

Una asignación de valor de verdad V ́o F a cada una de las variables proposicionales involucradas se extiende a cualquier fórmula proposicional C de la siguiente manera:

1. Si C es una variable proposicional p entonces v(C)=v (p)

2. Si C es de una de las formas (¬A), (A∧B), (A∨B) o (A→B), entonces v(C) está dado en términos de v(A) y v (B) por la tabla de verdad del conectivo correspondiente.

Ejemplo. ¬p ∨ q

Valor de verdad y tabla de verdad

p q ¬p ¬p ∨ qV V F VV F F FF V V VF F V V

CONTENIDO OVA

Tautología es forma proposicional que toma el valor V cualquiera que sea la asignación de valores a las variables proposicionales involucradas.

Ejemplo. p ∨(¬p) es una tautología por ser una proposición siempre verdadera (principio del medio excluido) y p∧¬p es una contradicción por ser siempre falso:

p ¬p p∧(¬p)

V F VF V V

p∧(¬p)

VV

Tautología Contradicción

Tautología y Equivalencia

CONTENIDO OVA

Se dice que A y B son lógicamente equivalentes, es decir A⇔B, si la forma proposicional (A↔B) es una tautología.

Ejemplo. Mostrar que ¬(p∨q) ≡ ¬p∧¬q es lógicamente equivalente.

Tautología y Equivalencia

p q p ∨ q ¬(p ∨ q) ¬p ¬q ¬p∧¬qV V V F F F FV F V F F V FF V V F V F FF F F V V V V

CONTENIDO OVA

El predicado hace referencia a una propiedad que puede tener un sujeto. En enunciado

siguiente “x es mayor que 3” se tiene dos partes, la primera es la variable x que es el sujeto

del enunciado y la segunda parte “mayor que 3” es el predicado.

Ejemplo Este enunciado se puede denotar como P(x) donde P es el predicado, x es la variable y de forma completa corresponde a la función proposicional P en x.

Predicados y cuantificadores

CONTENIDO OVA

Cuantificador Existencial: Existe un objeto x en el universo de discurso U o dominio, para el cual P(x) es verdadero.

Cuantificador Universal:  Es la proposición que afirma que P(x) es verdadera para todo objeto x en el universo de discurso.

Cuantificadores anidados: son cuantificadores que se localizan dentro del alcance de otros cuantificadores.

Predicados y cuantificadores

∀x P(x), x ∈ U

∃ x Q(x), x ∈ U

Esta proposición es verdadera si para todo x ∈ U se tiene que P(x) es verdadera.

Esta proposición es verdadera si existe (al menos) un x ∈ U tal que P(x) es verdadera.

∀x∃y(x + y = 0))

CONTENIDO OVA

Un conjunto es una colección desordenada de objetos u elementos. Se dice que un conjunto contiene a sus elementos.

1. El conjunto V de vocales se escribe como V = {a, e, i, o, u}

2. El conjunto O de los enteros positivos menores de 10 puede escribirse como O = {1, 3, 5, 7, 9}

3. Diagrama de Venn para representar el conjunto V de vocales

Estructuras matemáticas: Conjuntos

CONTENIDO OVA

Tamaño del conjunto: Sea S un conjunto. Si

hay n elementos distintos en S, donde n

es un entero no negativo, decimos

que S es un conjunto finito y n es un cardinal de S.

Estructuras matemáticas: Conjuntos

Subconjuntos:El conjunto A se dice que es subconjunto de B si y sólo si todo elemento de A es

también un elemento de B.

Conjunto potencia: Para considerar todas las combinaciones de

elementos de un conjunto S, se construye

un nuevo conjunto cuyos elementos son

todos los posibles subconjuntos de S,

conjuntos con cuantificadores

el dominio de una conjunto S se restringe

explícitamente haciendo uso de una

notación particular ∀x(x ∈ S → P (x)).

Conjuntos

CONTENIDO OVA

Estructuras matemáticas: Funciones

CONTENIDO OVA

Sean A y B conjuntos. Una función f de A en B es una asignación de exactamente un

elemento de B a cada elemento de A. Se escribe f(a)=b si b es el único elemento de B

asignado por la función f al elemento a de A. Si f es una función de A en B se escribe

como f: A → B.

CONTENIDO OVA

Funciones inyectivas, sobreyectivas y biyectivas.

a) inyectiva, no sobre b) sobre, no inyectiva c) inyectiva y sobre d) no inyectiva, no sobre e) No es función

CONTENIDO OVA

Funciones inversas: Sea f una función biyectiva del conjunto A en el conjunto B. La

función inversa de f es la función que asigna un elemento b que pertenece a B el único

elemento a de A tal que f(a)=b. La función inversa de f se denota por f-1.

CONTENIDO OVA

Funciones compuestas: sea g una función del conjunto A al conjunto B y sea f una

función del conjunto B al conjunto C. La composición de las funciones f y g

denotada para todo a∈A por f ◦ g, se define como: (f ◦ g)(a) = f (g(a)).

CONTENIDO OVA

Un algoritmo es una secuencia de instrucciones precisas para llevar a cabo una tarea y cumple con las siguientes características:

∙ Entrada. El algoritmo recibe datos de entrada.

∙ Salida. El algoritmo produce una salida.

∙ Precisión. Los pasos se establecen con precisión.

∙ Determinismo. Los resultados intermedios de cada paso de ejecución son únicos y

están determinados sólo por las entradas y los resultados de los pasos anteriores.

∙ Carácter finito. El algoritmo termina; es decir, se detiene después de ejecutar un

número finito de instrucciones.

∙ Corrección. La salida producida por el algoritmo es correcta; es decir, el algoritmo

resuelve el problema sin errores.

∙ Generalidad. El algoritmo se aplica a un conjunto de entradas.

Algoritmos

CONTENIDO OVA

procedure max(a1, a2, ..., an: integers)

max := a1

for i := 2 to n

if max < ai then max := ai

return max{max is the largest element}

En esta construcción se prueba la condición, y si es cierta, se ejecuta la instrucción.

Estructura Función

for variable := valor inicial to valor final

empezar el bucle la variable es asignada con el valor inicial, si el valor inicial es menor o igual al valor final, se ejecuta el bloque de instrucciones

if condición then instrucción

se prueba la condición, y si es cierta, se ejecuta la instrucción.

Ejemplo: algoritmo para encontrar el máximo valor

CONTENIDO OVA

El análisis de un algoritmo se refiere al proceso de derivar estimaciones del tiempo y el

espacio necesarios para ejecutarlo. Cuando un conjunto que tiene n elementos tiene 2n

subconjuntos, el programa requerirá al menos 2n unidades de tiempo para la ejecución.

Ejemplo. Suponer que el tiempo en el peor caso para una entrada de tamaño n está descrito

por la siguiente función:

t (n) = 60n2 + 5n + 1

Análisis de algoritmos

CONTENIDO OVA

Análisis de algoritmos

Ejemplo. Suponer que el tiempo en el peor caso para una entrada de tamaño n está descrito por la siguiente función:

t (n) = 60n2 + 5n + 1

al evaluar esta función con diferentes valores se obtienen los resultados mostrados en la tabla a continuación:

t(n) crece como lo hace n2 cuando n se incrementa y entonces se dice que t(n) es del orden n2 y se escribe:

CONTENIDO OVA