Como ya sabemos la sintaxis en lógica es la forma correcta de escribir una fórmula y la semántica es lo que significa. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Para determinar su valor seguimos las reglas simples que dimos en las definiciones básicas de acuerdo a su tabla de verdad. Esto lo hacemos mediante interpretaciones. Una interpretación de una fórmula es un conjunto de valores que se les asignan a sus proposiciones atómicas.
Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso en laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.
Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.
Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.
Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.
1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.
2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor. Ver Tema 1.5 Algebra Declarativa.
3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.
4. Escribir los encabezados de la tabla las fórmulas siguiendo la numeración que se le dió a las ramas en el árbol sintáctico.
5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.
6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando las tablas de verdad correspondiente del Conexiones Logicas y Jerarquias. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.
7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.
Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas:
i) (p → ¬q) v (¬p v r) ii) p → (q ^ r)iii) (p → ¬ r) ↔ (q v p)iv) ¬(p ¬ q) → ¬ r v) (¬p ^ q) → ¬(q v ¬r)
Solución: (Faltan las gráficas de los árboles, los quitaron)
i) Seguimos los pasos del algoritmo con la fórmula (p → ¬q) v (¬p v r)
viernes, 2 de octubre de 2009
Reglas De Inferencia
En un cálculo lógico, las reglas de inferencia o reglas de transformación son aquellos esquemas formales que nos permiten derivar unas fórmulas bien formadas (conclusiones) a partir de otras (premisas). Por ejemplo, la Regla de Eliminación del Condicional:
A → B
A
______
B
nos permite derivar la fórmula “p v q” de las fórmulas “p → (p v q)” y “p”.
Las reglas de inferencia no deben confundirse con las leyes lógicas o tautologías, puesto que éstas no pertenecen al metalenguaje del cálculo.
Primero presentamos los tipos de inferencia, la inferencia válida en computación y matemáticas y al final una serie de reglas que se utilizan para la inferencia deductiva.
La inferencia es la forma en la que obtenemos conclusiones en base a datos y declaraciones establecidas.
Un argumento, por ejemplo es una inferencia, donde las premisas son los datos o expresiones conocidas y de ellas se desprende una conclusión.
Los argumentos basados en tautologías representan métodos de razonamiento universalmente correctos. Su validez depende solamente de la forma de las proposiciones que intervienen y no de los valores de verdad de las variables que contienen. A esos argumentos se les llama reglas de inferencia. Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis en una demostración.
Una inferencia puede ser: Inductiva, deductiva, transductiva y abductiva. Ver Inferencia.
De los cuatro tipos de inferencia señalados anteriormente, en matemáticas y computaión solamente se acepta el deductivo para demostraciones formales; Ver Deducción. Por esta rezón se denominan Reglas de Inferencia Deductiva.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus 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
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
La comprobación de las reglas anteriores es directa y basta hacer fórmula con la conjunción de las premisas condicional la conclusión y probar que es una tautología, por ejemplo haciendo una tabla y obtener todos los valores verdaderos.
A → B
A
______
B
nos permite derivar la fórmula “p v q” de las fórmulas “p → (p v q)” y “p”.
Las reglas de inferencia no deben confundirse con las leyes lógicas o tautologías, puesto que éstas no pertenecen al metalenguaje del cálculo.
Primero presentamos los tipos de inferencia, la inferencia válida en computación y matemáticas y al final una serie de reglas que se utilizan para la inferencia deductiva.
La inferencia es la forma en la que obtenemos conclusiones en base a datos y declaraciones establecidas.
Un argumento, por ejemplo es una inferencia, donde las premisas son los datos o expresiones conocidas y de ellas se desprende una conclusión.
Los argumentos basados en tautologías representan métodos de razonamiento universalmente correctos. Su validez depende solamente de la forma de las proposiciones que intervienen y no de los valores de verdad de las variables que contienen. A esos argumentos se les llama reglas de inferencia. Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis en una demostración.
Una inferencia puede ser: Inductiva, deductiva, transductiva y abductiva. Ver Inferencia.
De los cuatro tipos de inferencia señalados anteriormente, en matemáticas y computaión solamente se acepta el deductivo para demostraciones formales; Ver Deducción. Por esta rezón se denominan Reglas de Inferencia Deductiva.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus 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
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
La comprobación de las reglas anteriores es directa y basta hacer fórmula con la conjunción de las premisas condicional la conclusión y probar que es una tautología, por ejemplo haciendo una tabla y obtener todos los valores verdaderos.
Induccion matematicas
G. Peano (1858–1932) propuso cinco propiedades fundamentales que caracterizan a los números naturales, Axiomas de Peano. Una de ellas conocida como el Principo de Inducción Matemática es actualmente una herramienta de uso práctico y teórico principalmente para matemáticos y personas que trabajan en Ciencias Computacionales.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
Principio de Inducción Matemática.
Si S en un conjunto de enteros positivos tal que
(B) 1 e S
(I) k e S Þ (k+1) e S
entonces S contiene todos los enteros positivos.
En en principio de Inducción Matemática son muy importantes los nombres asociados y en la literatura técnica, como es costumbre, no se presenta con detalle los pasos, por lo que resulta indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial(I) se llama Paso de Inducciónk e S se llama Hipótesis de InducciónY como ya se mencionó todo junto se llama Principio de Inducción Matemática.
Es importante que el alumno comprenda y memorice cada uno de estos conceptos y su participación directa en la propiedad.
Escencialmente lo que enuncia el principio de inducción matemática es, si logramos establecer que el primer entero positivo cumple, una propiedad, y si partiendo de que un entero arbitrario también la cumple, se puede comprobar que el entero siguiente también tiene la propiedad entonces concluimos que todos los enteros positivos tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene (B) F(1) es verdadera; o sea, se que cumple para n=1 (I) F(K) Þ F(k+1); Si se cumple para n = k entonces también se cumple para n=k+1.
Concluimos que la proposición es verdadera para todos los enteros positivos.
El Principio de Inducción Matemática se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas, usualmente en el conjunto de los números enteros positivos. Muchas propiedades que incluyen la definición de de factorial se pueden probar por Inducción Matemática, como el Teorema del Binomio de Newton, el Triángulo de Pascal y algunas propiedades de combinatoria que involucran combinaciones y permutaciones. Otra forma de utilizarla es para proporcionar definiciones y formalizar conceptos.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
Principio de Inducción Matemática.
Si S en un conjunto de enteros positivos tal que
(B) 1 e S
(I) k e S Þ (k+1) e S
entonces S contiene todos los enteros positivos.
En en principio de Inducción Matemática son muy importantes los nombres asociados y en la literatura técnica, como es costumbre, no se presenta con detalle los pasos, por lo que resulta indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial(I) se llama Paso de Inducciónk e S se llama Hipótesis de InducciónY como ya se mencionó todo junto se llama Principio de Inducción Matemática.
Es importante que el alumno comprenda y memorice cada uno de estos conceptos y su participación directa en la propiedad.
Escencialmente lo que enuncia el principio de inducción matemática es, si logramos establecer que el primer entero positivo cumple, una propiedad, y si partiendo de que un entero arbitrario también la cumple, se puede comprobar que el entero siguiente también tiene la propiedad entonces concluimos que todos los enteros positivos tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene (B) F(1) es verdadera; o sea, se que cumple para n=1 (I) F(K) Þ F(k+1); Si se cumple para n = k entonces también se cumple para n=k+1.
Concluimos que la proposición es verdadera para todos los enteros positivos.
El Principio de Inducción Matemática se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas, usualmente en el conjunto de los números enteros positivos. Muchas propiedades que incluyen la definición de de factorial se pueden probar por Inducción Matemática, como el Teorema del Binomio de Newton, el Triángulo de Pascal y algunas propiedades de combinatoria que involucran combinaciones y permutaciones. Otra forma de utilizarla es para proporcionar definiciones y formalizar conceptos.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
Algebra declarativa
los operadores lógicos con proposiciones, si esos operadores los combinamos podemos formar fórmulas lógicas.
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
Cuantificadores Y Restricciones
Dos casos centrales en el cálculo de predicados se presentan cuando se analiza si el predicado se cumple para la población completa y cuando se analiza para ver si cumple para un caso en particular al menos. Estos dos casos se llaman Universal y Particular o Existencial vienen a ser la interpretación o la semántica de los símbolos de cuantificadores que se vieron en la sección 1.4 Calculo de Predicados Definicion y se definen de la siguiente forma:
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Variables Y Particularizaciones
En cálculo de predicados tenemos expresiones con variables, las variables pertenecen a un conjunto o dominio previamente determinado. Por lo que es muy importante definir el dominio cuado interpretamos una fórmula mediante un predicado específico.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Definición
Una fórmula en lógica de predicados es una expresión que se puede obtener mediante alguna de las formas siguientes: i) p(x1, x2, … ,xn) donde p es un símbolo que representa un predicado y x1, x2, … ,xn son símbolos de variable.ii) (¬ F) donde F es una fórmula de lógica de predicados.iii) (F G) donde F y G son fórmulas de lógica de predicados y es cualquiera de los operadores ^, v, →, ↔iv) (∀ x) F, donde F es un fórmula en lógica de predicados.v) (∃ x) F, donde F es un fórmula en lógica de predicados.
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
Suscribirse a:
Entradas (Atom)
