View
15
Download
0
Category
Preview:
Citation preview
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
Recommended