Este blog esta realizado con el fin dar informar a los alumnos conocimientos básicos referente a Matemáticas discretas en la computación haciendo énfasis en la lógica Matemática.
Te sugerimos que para tener una interacción mas amigable con el entorno del blog visites el temario que se encuentra en el menú de la derecha en el cual accesaras mas fácil y rápidamente al tema de tu preferencia; así como también que sigas la secuencia de los temas para que tengas un mejor entendimiento de los mismos, ya que algunos dependen de otros.
Nosotros somos :
Escobar Bravo Jose Roberto
Gutierrez Cabrera Obed de Jesús
Ortiz Dominguez Paulina Astrid
Santiago Regalado Ángel de Jesús
Recuerda que «La matemática es la ciencia del orden y la medida, de bellas cadenas de razonamientos, todos sencillos y fáciles.» René Descartes (1596-1650)
La proposicion es un enunciado declarativo que puede tener caracteres de verdad o falso pero no ambos.
Enunciados declarativos:
*El día esta nublado—–Verdadero
*Carlos esta matriculado en el tecnológico—-Verdadero
NOTA: Una proposición no puede ser escrita como pregunta ni como admiración un enunciado de exclamación o que represente ambigüedad (que no pueda ser determinado si es verdadero o falso).
PROPOSICIÓN SIMPLE:
Atomo declarativo o unidad definida que puede ser determinada como falso o verdadero.
PROPOSICIÓN COMPUESTA:
Se conforma por dos o mas proposicion simples y se relaciona por conectores o conectivos.
Una proposición compuesta es una frase que consta de uno o varios sujetos y de un predicado que afirma algo en torno a dichos sujetos.Los sujetos de una proposicon simple deben ser todos terminos singulares. El predicado debe contener un verbo que exprese la accion sobre los sujetos.En matematicas se usan ciertos simbolos para representar predicados de uso frecuente como: el simbolo «_», como representante del predicado «es igual a «, y el simbolo «<» como sustituto de «es menor que».
Las proposiciones compuestas son las siguientes:
1.-Disyunción
La conectiva ‘o’ disyunción tiene dos sentidos y a ellos se alude ya en el lenguaje ordinario cuando se distingue entre ‘o’ y ‘o’. Cada uno de dichos sentidos es expresado en la logica setencial mediante un signo propio.La conectiva ‘o’ corresponde a la llamada disyuncion inclusa es simbolizada por el signo ‘V’ insertado entre dos fórmulas.La disyunción de las proposiciones simples pVq que se lee: «p o q» es falsa si ambas proposiciones son falsas. El operador lógico disyuncion también se denomina OR y representa la suma lógica.Esta se puede describir mediante una tabla de verdad, una tabla de verdad de una proposición P formada por las proposiciones P1….,Pn donde V indica verdadero y F falso, de modo que para cada una de estas combinaciones se indica el valor de verdad de P.
p V q
se lee: ‘p o q’.La conectiva ‘o….o’ corresponde a la llamada disyuncion exclusiva y es simbolizada por el signo ‘≠’ insertado entre dos formulas.
P ≠ q
Se lee ‘o o q’.
Ejemplo:
Antonio se dedica a la natación o al alpinismo
Se entiende de las dos siguientes maneras:
1.- Antonio se dedica a la natación o al alpinismo ( o a ambos) (ejemplo de disyuncion inclusiva)
2.- Antonio se dedica a la natación al alpinismo ( pero no a ambos) (ejemplo de disyuncion exclusiva)
Toda disyunción afirma que es cierto lo que afirma por lo menos una de sus componentes esto se define en cuanto a su interpretación
2.-Conjunción
La conjuncion de dos proposiciones simples P^q ( que se lee: » p y q») es verdadera si ambas proposiciones son verdaderas. La conjuncion (^), es una conectiva logica que denomina el operador logico AND y representa el producto logico, y es una proposición de la forma Py Q donde estos son proposiciones cuales quiera.
La conectiva ‘y’ o conjuncion es simbolizada por el signo ‘.’ insertado entre dos formulas. Asi,
p .q
Se lee ‘ p y q’
Te mostramos unos ejemplos sencillos para comprender el estudio de la conjunción.
Antonio es mentiroso y Juan es mentiroso,
Se formula de modo mas idomatico escribiendo:
Antonio y Juan son mentirosos
Si p es la proposición: «1 es un número impar» y q es la proposición: «3 es un número primo», entonces p ^ q será la proposición: «1 es un número impar y 3 es un número primo». En donde se observa que p ^ q su valor de verdad es verdadero, pues tanto p: «1 es un número impar», como q: «3 es un número primo»,ambos son verdaderos.
Si p es la proposición: «París está en Francia» y q es la proposición: «2 es un número impar», entonces la proposición: p ^ q será «París está en Francia y 2 es un número impar», donde su valor de verdad es: falso, pues el valor de verdad de q: «París está en Francia» , es verdadero, pero el valor de q: «2 es un número impar» es falso.
La tabla de verdad es la siguiente:
3.-Negación
La negacion de p, denotada por ṗ, es la proposicion
no p
Las proposiciones pueden ser simples o compuestas.Para designarlas se emplean letras latinas minusculas: p, q, r, s, etc.Para negar una proposicion simple se emplea el simbolo ~ de tal forma que ~p ( se lee «no p»), y es tal, que si p es verdadera (1), ~p seria falsa (O), y viceversa.El operador negacion (~) tambien se denomina NOT por razones obvias ‘_’ prefijado a la letra setencial o al enunciado. Asi,
-p
se lee ‘no p’
Ejmplo:
No (Nehru es frances) Aqui sedice que la cenectiva designa ‘particula conectiva’. se usa el adjetivo sustantivo.
o bien seria:
No es el caso que Nehru sea frances Se observa que en el lenguaje logico ‘no’ antecede al enunciado, en el lenguaje ordinario (en español) sigue al sujeto
En una expresion mas idomatica a los dos ejemplos anteriores es:
Nehru no es frances.
La conectiva ‘no’ o negacion es la unica conectiva singular de las mentadas.
El valor de verdad de la proposiicon ṗ se define mediante la tabla de verdad.
4.-Condicional
Si p y q son proposicionales, la proposicion compuesta de la siguiente forma:
si p entonces q
es una proposicion codicional y se denota
p–>q
Donde las componetes P,Q son proposiciones cuales quiera.La primera componete de una condicional es La proposicion p es la hipotesis ( o antecedente) y la segunda proposicion q es la conclusion (o consecuente).
EJEMPLO:
Si X es multiplo de A, entonces X es par
Nota: Procura poner el verbo en subjuntivo cuando una componente vaya precedida de «que». En ( Q cada vez P), se hace salvedad de esta regla.
Cuando la hipotesis de una condicional es una conjuncion, suele repetirse la palabra «si» tantas veces como componentes tiene la hipotesis.
Ejemplo, en lugar de:
Si P y Q entonces R:
se escribe:
Si P y si Q entonces R.
Ejemplo de lo anterios es:
si la condicional es:
Si P entocnes Q.
reciproca es:
Si Q entonces P.
Contrapuesta es:
Si ~ Q entocnes ~p.
a cada condicional le asocian otras dos que juegan un papel importante: la reciproca y la contrapuesta de la condicional dada.
El valor de la proposicion condicional p–>q se define mediante la siguiente tabla de verdad:
5.-Bicondicional
Una bicondicional es la conjuncion de una condicional y su reciproca.
Sus siete maneras diferentes de enunciar una misma condicional es:
1.- Si P entonces Q y, reciprocamente, Si Q entoncesP
2.-Si P entonces Q, y reciprocamente.
3.-Si p, y solo entonces, Q.
4.-P si Q, y solo entonces.
5.-P si Q, y solo si Q.
6.- P si, y solo si , Q.
7.- A fin de que P es necesario y eficiente que Q.
Si p y q son proposiciones, la proposicion compuesta
p si y solo si q
es una proposicion bicondicional y se denota
p <–> q.
El valor de verdad de la proposicon p <–> q se define mediante la siguiente tabla de verdad:
Las tablas de verdad se utilizan en lógica simbolica para establecer la validez de las proposiciones. La construcción de las tablas de verdad simplifican la tarea de determinar la verdad o falsedad de una proposición.
Dado como ejemplo dos proposiciones, pueden presentarse cuatro posibles caso:
1.- Ambas proposiciones son verdaderas
2.- La primera es verdadera y la segunda es falsa
3.- La segunda es verdadera y la primera falsa
4.- Las dos son falsas.
(En la tabla se muestran las combinaciones posibles de dos proposiciones cualesquiera.)
Tabla de verdad de la negación (No):
Las proposiciones pueden ser simples o compuestas. Para designarlas se emplean letras minúsculas como p,q,r,s etc..
Para negar una proposición simple se emplea el símbolo ~ de tal forma que ~p (que se lee como “no p”) y es tal que si p es verdadera, ~p sera falsa y viceversa. El operador negación (~) también se denomina “No”.
(Tabla de verdad de la negación)
Tabla de verdad de la conjunción (Y):
La conjunción de dos proposiciones simples p^q (que se lee “p y q”) es verdadera si ambas proposiciones son verdaderas. La conjunción (^), es una conectiva lógica que se denomina el operador lógico “Y” y se representa el producto lógico.
Observe que en la tabla de verdad para dos proposiciones simples tiene cuatro renglones que contienen todas las posibilidades o alternativas de combinación de los valores de verdad de las proposiciones simples.
Mediante inspección de las tablas notamos que ambas proposiciones deben ser verdaderas para que el conjunto sea verdadero
Tabla de verdad de la disyunción (O):
La disyunción de dos proposiciones simples pᵛq (que se lee : “p o q”) es falsa si ambas proposiciones son falsas. El operador lógico disyunción también se denomina “O” y representa la suma lógica.
Mediante inspección de las tablas notamos que el conjunto solo es falso si ambas proposiciones son falsas.
Tabla de verdad de si…entonces (Ͻ):
La proposición condicional se representa p→q (que se lee «si p entonces q») y se considera falsa solo si el antecedente (p) es verdadero y el consecuente (q) es falso.
En cualquier otro caso la proposición condicional se considera verdadera.
(tabla de la proposición condicional)
Tabla de verdad Bicondicional (↔):
Llámese bicondicional a una proposición que es verdadora si ambos factores son verdaderos, tambien es verdadera si ambos factores son falsos y falsa en los otros casos.
Se representa p↔q ( que se lee «p si y solo si q»).
Tautología, es aquella proposición (compuesta) que es cierta para todos los valores de verdad de sus variables.
Las tautologías no son como podría pensarse, un inútil objeto de lujo en la lógica. Las tautologías desempeñan pues un papel fundamental en los procesos de la deducción dentro de esta lógica.
Las tautologías son muy importantes en lógica matemática ya que se consideran leyes en las cuales nos podemos apoyar
para realizar demostraciones.
Ejemplo:
La expresión ‘(p ^ q) → (p ∨ r)’ es una tautología
Se construye el árbol como el que se muestra y una vez numerado se forma el árbol empezando por el número más grande en orden descendiente.
Utilizamos el anterior árbol para construir la tabla.
p
q
r
¬ r
p ∧ q
p ∨ ¬ r
(p ∧ q) → (p ∨ ¬ r)
V
V
V
F
V
V
V
V
V
F
V
V
V
V
V
F
V
F
F
V
V
V
F
F
V
F
V
V
F
V
V
F
F
F
V
F
V
F
V
F
V
V
F
F
V
F
F
F
V
F
F
F
V
F
V
V
Observa que la última columna tiene unicamente V por que se comprueba que es una tautología.
Un ejemplo típico es la contrapositiva cuya tabla de verdad se indica a continuación:
A continuación se cita una lista de las tautologías más conocidas y reglas de inferencia de mayor uso:
Doble negación: Según esta pueden eliminarse las dobles negaciones.
a). p''⇔p
Leyes conmutativas: Indican que pueden conmutarse los miembros de conjunciones, disyunciones y bicondicionales.
Leyes asociativas: Indica que pueden agruparse como se quiera los miembros de conjunciones, disyunciones y bocondicionales.
a). [(p∨q)∨r]⇔[p∨(q∨r)]
b. [(p∧q)∧r]⇔[p∧(q∧r)]
Leyes distributivas: Indican que una conjunción pueden distribuirse en una disyunción, que una disyunción puede distribuirse en una conjunción y que un condicional puede distribuirse en una conjunción o en una disyunción.
a). [p∨(q∧r)]⇔[(p∨q)∧(p∨r)]
b. [p∧(q∨r)]⇔[(p∧q)∨(p∧r)]
Leyes de idempotencia.
a). (p∨p)⇔p
b). (p∧p)⇔p
Leyes de Morgan: Indican que una conjunción negativa puede ser transformada en una disyunción de negaciones.
Decimos que dos proposiciones p , q son equivalentes cuando cada una de ella implica a la otra.Todas las conectivas, por definición, son equivalentes entre sí. Esto permite sustituir a una conectiva por otra en un sistema axiomático formalizado de acuerdo a ciertas reglas previamente establecidas. También es posible reducir cualquier fórmula a una fórmula elemental en la que las conectivas sean únicamente la conjunción, la disyunción y la negación. Esto permite simplificar mucho la estructura de un lenguaje formalizado porque con ello se puede reducir la cantidad de conectivas utilizadas.
A fin de indicar la equivalencia de dos proposiciones p, q se emplea cualquiera de los giros siguientes:
(E1) P es equivalente a Q
(E2) P = Q
(E3) P implica a Q, y viceversa
(E4) P es condición necesaria y suficiente para Q
El camino usual para probar la equivalencia de dos proposiciones consiste en deducir cada una de ellas a partir de la otra.
Muchas de las leyes de la lógica se expresan en términos de equivalencia.
Supongamos que las proposiciones compuestas P y Q estan formadas por las proposiciones p1……pn.
Decimos que P y Q son logicamente equivalentes y escribimos p ≡ q ,siempre que dados cualesquiera valores de verdad de p1……pn
P y Q sean ambas verdaderas o ambas falsas.
En algunos casos, es posible que dos proposiciones compuestas tengan los mismos valores de verdad, sin importar los valores de verdad de sus proposiciones constituyentes.
Tales proposiciones son lógicamente equivalentes.
Observa la siguiente lista de equivalencias, algunas de las cuales ya se han visto en las leyes lógicas, es de utilidad cuando se busca la simplificación de fórmulas complejas :
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.
Las reglas de inferencia logica, entre otras, son: el Modus Ponendo Ponens (MPP), el Modus Tollendo Tollens (MTT) y el Modus Tollendo ponens (MTP), expresiones latinas que traducen: Metodo que afirmando afirma, Metodo que negando niega y Metodo que negando afirma respectivamente.
Modus Ponendo Ponens (MPP):
Este método de inferencia establece que si una implicación es cierta y ademas también es cierto su antecedente, entonces su consecuente es necesariamente verdadero; de manera simbolica esto se expresa asi:
[(p→q) ᶺ p] → q
Modus Tollendo Tollens (MTT):
Esta regla de inferencia dice que si una implicación es verdadera y es falso su consecuente, entonces su antecedente sera necesariamente falso; de manera simbolica esto se expresa asi:
[(p→q) ᶺ ~q] →q
Modus Tollendo Ponens (MTP):
Esta ley se enuncia así: si una disyunción es verdadera y una de sus proposiciones simples es falsa, entonces necesariamente la otra proposición sera verdadera; de manera simbólica se expresa asi:
[(pᵛq) ᶺ ~p] →q o [(pᵛq) ᶺ ~p] → p
Un argumento es valido si de la conjuncion ( ᶺ ) de las premisas se implica la conclusion, es decir, siempre que todas las premisas sean verdaderas, la conclusion sera tambien verdadera.
Un argumento es un raciocino que se hae con el objeto de aceptar o rechazar una tesis; es la aceveracion de una proposicion, llamada conclusion o tesis, obtenida de otros enunciados denominados premisas o hipotesis.
La demostración es un razonamiento que prueba la validez de un nuevo conocimiento; es el enlace entre los conocimientos adquiridos y los conocimientos anteriores.
Los procedimientos de demostración que permiten establecer la conexión lógica entre las proposiciones fundamentales de la teoria, sus consecuencias sucesivas, hasta deducir la conclusion o tesis que asi se demuestra.
Los principales tipos de demoostracion son:
Demostración directa: La demostración directa de una proposicion t (teorema), es un conjunto de proposiciones o premisas que son postulados o proposiciones de validez aceptada, y de las cuales se infiere t como consecuencia inmediata.
Demostración indirecta: Se realiza una demostración indirecta cuando se establece la validez de una tesis t probando que las consecuencias de su contraria son falsas.
Demostración por recursión: Cuando la tesis se prueba por medio de inducción matemática.
A estos tipos de demostración se oponen dos métodos de refutación.
La refutación es el razonamiento que prueba la falsedad de una hipótesis o la inconsecuencia de su supuesta demostración; los métodos de refutación son la refutación por contradicción y la refutación por contra ejemplo.
Un argumento es una secuencia de afirmaciones, todas las afirmaciones excepto la última se llamarán premisas, suposiciones o hipótesis, la declaración final se llamará conclusión.
Argumentar consiste en deducir una conclusión a partir de una premisa que se tienen por verdaderas. Un argumento, por lo tanto, estará compuesto de unas premisas y de una conclusión
Lo que hace que podamos hablar de razonamiento es la relación que existe entre los enunciados que llamamos premisas y la conclusión.
Diremos que un argumento es argumento válidosi para cualquier valor de las variables proposicionales involucradas en las fórmulas que hacen verdaderas las premisas la conclusión es verdadera.
Argumento: Conjunto de formulas para el razonamiento logico.
Argumento Valido: Un argumento es valido si se cumple:
Un argumento puede ser válido con premisas y conclusión verdaderas.
Pero también puede ser válido con premisas falsas y conclusión verdadera, o incluso con premisas y conclusión falsas.
Lo que NUNCA será es válido con premisas verdaderas y conclusión falsa.
De la propia definición de argumento válido se puede deducir una metodología para verificar la validez de un argumento:
1. Identificar las premisas y la conclusión
2. Construir una tabla de verdad que incluya las premisas y la conclusión
3. Señalar de la tabla sólo aquellos renglones que hacen que todas las premisas sean verdaderas.
Estos se llamarán renglones críticos
4. Verificar que para los renglones críticos, la conclusión es verdadera. En tal caso se tiene un Argumento válido.
5. Detectar si existe un renglón crítico con conclusión falsa. En cuyo caso se dirá Argumento inválido.
Las premisas pueden ser verdaderas o falsas, la conclusión puede ser verdadera o falsa, y el argumento puede ser válido o inválido.
Evaluación de los argumentos mediante tablas de verdad:
Todos los argumentos pueden convertirse en un condicional, pues despues de todo lo que un argumento esta afirmando, es que si las premisas son verdaderas, entonces la conclusion tambien lo es. Dicho de otro modo :
P1 ∧ P2 ∧ … ∧ Pn→C
Es decir, un argumento es, en realidad, un condicional en el que en antecedente es la conjunción de todas las premisas (P1∧P2∧…∧Pn) y el consecuente es la conclusión.
Como sabemos, la tabla de verdad del condicional nos dice que este solo es falso cuando el antecedente es verdadero y el consecuente es falso, y verdadero en el resto de los casos.
Esto coincide completamente con la definición de argumento valido, segun la cual una argumento será válido exactamente en los mismos casos en que el condicional que le corresponde lo sea. Como un condicional no puede ser verdadero si el antecedente es verdadero y el consecuente falso, un argumento no podrá ser válido si las premisas son verdaderas y la conclusión falsa.
No siempre es fácil averiguar intuitivamente si un argumento es válido o no, por lo que en ocasiones es necesario recurrir a métodos más fiables que la intuición. Dado que podemos convertir cualquier argumento en un condicional, podemos usar el método de las tablas de verdad para averiguar si un argumento dado es válido o no.
Evidentemente, un argumento sólo será válido cuando el condicional correspondiente sea una tautología y no será válido en el resto de casos (si es una contradicción o si es una contingencia).
Premisa1) Si estudio entonces aprobaré
Premisa2) No he estudiado
Conclusión: No aprobaré
Lo primero que debemos hacer para evaluar o decidir si el argumento es válido o no, es formalizarlo:
Formalización de la premisa1): p→q (si estudio entonces aprobaré)
Formalización de la premisa2): ¬p (no estudio)
Formalización de la concusión: ¬q (no apruebo)
En segundo lugar, tenemos que convertir el argumento en un condicional. Como hemos visto, el antecedente del condicional estará formado por la conjunción de todas las premisas, y el consecuente por la conclusión, de modo que obtenemos lo siguiente:
[( p → q ) ᶺ ¬p] → q
Éste es, en consecuencia, el condicional que le correspon de al argumento del ejemplo. Es el momento de hacer su tabla de verdad, que quedará como sigue:
Como vemos, la tabla de verdad nos revela que el condicional analizado es una contingencia, lo que significa que puede ser verdadero o no, es decir, que es posible que sus premisas sean verdaderas y su conclusión falsa. Por lo tanto el argumento correspondiente no será válido, como dedujimos intuitivamente en el apartado anterior.
Este blog esta realizado con el fin dar informar a los alumnos conocimientos básicos referente a Matemáticas discretas en la computación haciendo énfasis en la lógica Matemática.
matediscretasu3
Discrete Mathematics 
