Latest Entries »

BIENVENIDO

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)

Fuentes de información

TEMARIO UNIDAD 3


UNIDAD 3 LÓGICA DE PREDICADO

3.1 Lógica proposicional
3.1.1 Concepto de proposición
3.1.2 Proposiciones compuestas (Disyunción, Conjunción, Negación, Condicional y Bicondicional)
3.1.3 Tablas de verdad
3.1.4 Tautologías, Contradicción y Contingencia
3.1.5 Equivalencias lógicas
3.1.6 Reglas de inferencia
3.1.7 Argumentos válidos y no válidos
3.1.8 Demostración formal (Directa, Por contradicción)

3.2 Lógica de predicados.
3.2.1 Cuantificadores
3.2.2 Representación y evaluación de predicados

3.3 Álgebra declarativa.

3.4 Inducción matemática.

3.5 Aplicación de la lógica matemática en la computación.

Proposición logica

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:

PARA LOS TEMAS ANTERIORES:

http://sisbib.unmsm.edu.pe/bibvirtual/publicaciones/escri_pensam/1998_n1/la_logica_del_condic_y_la_imp.htm

http://es.wikipedia.org/wiki/Conjunci%C3%B3n_l%C3%B3gica

http://es.wikipedia.org/wiki/Negaci%C3%B3n_l%C3%B3gica

http://es.wikipedia.org/wiki/Disyunci%C3%B3n_l%C3%B3gica

http://www.mitecnologico.com/Main/Bicondicional

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 pq (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”).
(Tabla de verdad Bicondicional).

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.
a). (p∨q)⇔(q∨p) 35
b). (p∧q)⇔(q∧p)
c). (p↔q)⇔(q↔p)
  • 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.
a). (p∨q)'⇔(p'∧q')
b). (p∧q)'⇔(p'∨q')
c). (p∨q)⇔(p'∧q')'
b). (p∧q)⇔(p'∨q')'
  • Contrapositiva.
a). (p→q)⇔(q'→p') 36
  • Implicación.
a). (p→q)⇔(p'∨q)
b). (p→q)⇔(p∧q')'
c). (p∨q)⇔(p'→q)
d). (p∧q)⇔(p→q')'
e). [(p→r)∧(q→r)]⇔[(p∧q)→r]
f). [(p→q)∧(p→r)]⇔[p→(q∧r)]
  • Equivalencia
a). (p↔q)⇔[(p→q)∧(q→p)]
  • Adición.
a). p⇒(p∨q)
  • Simplificación: Indica que una conjunción esta implicada por cualquiera de sus miembros componentes.
a). (p∧q)⇒p
 Mas explicito a las tautologías fundamentales observa la siguiente imagen:
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
¬(¬p) ↔ p Doble Negación
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ^ q) ↔ ¬p ∨ ¬q Ley 2 de De Morgan
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
(p → q) ↔ (¬ p ∨ q) Condicional como cláusula
((p → q) ↔ (¬ q → ¬ p) Contrapositiva


Una contradicción es aquella proposición que siempre es falsa para todos los valores de verdad, una de las mas usadas 
y mas sencilla es p∧ p’ .Lo opuesto de la tautología es la contradicción, que es F en virtud de su forma lógica.
La negación de una tautología es siempre una contradicción (y viceversa).
 Como lo muestra su correspondiente tabla de verdad:


Una proposición compuesta cuyos resultados en sus deferentes líneas de la tabla de verdad dan como resultado
 1s y 0s se le llama contingente.


DE CALCULO PROPOSICIONLA ( TAUTOLOGIA Y CONTRADICCION):
http://www.monografias.com/trabajos16/calculo-proposicional/calculo-proposicional.shtml
http://www.mitecnologico.com/Main/TautologiasYContradicciones

http://racionalidadcolectiva.blogspot.com/2008/05/clase-3.html

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……p

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 :

http://www.mitecnologico.com/Main/EquivalenciaLogica

http://www.mitecnologico.com/Main/EquivalenciasLogicasYUtilizaciones

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:
  1. 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.
  2. 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.
  3. 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.