Notas de matemáticas discretas

´ ´ CAP´ ITULO 2. METODOS DE DEMOSTRACION

Una sentencia que es modificada con el conectivo no es llamada la negaci´n o de la sentencia original. Simb´licamente, s´ P es una proposici´n entonces ¬P o ı o (no P ), denota la negaci´n de P . En el cuadro 2.1 se muestra la tabla de verdad o de NO. P 1 0 ¬P 0 1

Cuadro 2.1: Tabla de verdad de NO

Y La conjunci´n de P ,Q es denotada por P ∧ Q. Laconjunci´n es verdadera o o s´lo si P y Q son verdaderos. En el cuadro 2.2 se muestra la tabla de verdad de o Y. P 0 0 1 1 Q 0 1 0 1 P ∧Q 0 0 0 1

Cuadro 2.2: Tabla de verdad de Y

O La disyunci´n de P ,Q es denotada por P ∨ Q. La disyunci´n es verdadera si o o al menos uno de sus elementos es verdad P , Q es verdadero. En el cuadro 2.3 se muestra la tabla de verdad de O. P 0 0 1 1 Q 0 1 0 1 P∨Q 0 1 1 1

Cuadro 2.3: Tabla de verdad de O

O EXCLUSIVO El s´ ımbolo ⊕ representa el O EXCLUSIVO (XOR), que es incluido en muchos lenguajes de programaci´n. Una proposici´n P ⊕ Q se lee como “P o Q pero no o o ambos”. En el cuadro 2.4 se muestra la tabla de verdad de XOR.

´ 2.1. LOGICA PROPOSICIONAL P 0 0 1 1 Q 0 1 0 1 P ⊕Q 0 1 1 0

11

Cuadro 2.4: Tabla de verdad de XOR IMPLICACIONPara dos declaraciones P ,Q, decimos “P implica Q” y se escribe P → Q para denotar la implicaci´n de Q por P . La proposici´n P es llamada la hip´tesis o o o o antecedente de la implicaci´n; Q es llamada la conclusi´n o consecuente de la o o implicaci´n. En el cuadro 2.5 se muestra la tabla de verdad de la IMPLICAo CION. P 0 0 1 1 Q 0 1 0 1 P →Q 1 1 0 1

Cuadro 2.5: Tabla de verdad deIMPLICACION Como ejemplo, consideremos que el profesor dice a sus alumnos: “si obtienes 9 o m´s en el examen, aprobaras el curso”. Entonces: a P : Obtienes 9 o m´s en el examen. a Q: Apruebas el curso. Una vez que se termina el curso, existen 4 posibles situaciones: o o 1. La calificaci´n del examen ha sido menor que 9 y no se aprob´ el curso. La promesa no ha sido rota, pues no se cumpli´ con P . o 2. Lacalificaci´n del examen ha sido menor que 9 y se aprob´ el curso. La o o promesa no ha sido rota, es posible que por otras razones se haya aprobado. 3. La calificaci´n del examen ha sido mayor o igual que 9 y no se aprob´ el o o curso. La promesa ha sido rota, pues se ha cumplido con P y no se ha aprobado el curso. 4. La calificaci´n del examen ha sido mayor o igual que 9 y se aprob´ el o o curso. Lapromesa ha sido cumplida. SI Y SOLO SI Otra declaraci´n com´n en matem´ticas es “P si y s´lo si Q”, o simb´lio u a o o camente P ↔ Q. Esto es llamado la equivalencia de dos proposiciones, P , Q. Formulaciones alternativas son:

12

´ ´ CAP´ ITULO 2. METODOS DE DEMOSTRACION si P entonces Q, y si Q entonces P Q es una condici´n necesaria y suficiente para P o La tabla de verdad de SII se muestraen el cuadro 2.6. P 0 0 1 1 Q 0 1 0 1 P ↔Q 1 0 0 1

Cuadro 2.6: Tabla de verdad de SII

2.1.3.

F´rmulas, Tautolog´ y Contradicciones o ıas

Una f´rmula o forma l´gica f (x, y, z, . . .) es una expresi´n l´gica en la que o o o o x, y, z, . . . son proposiciones o variables l´gicas. Por ejemplo (x → y) → z y o (x ∧ ¬y) ∨ z son f´rmulas. o Por convenci´n los conectores en una f´rmula sinpar´ntesis son aplicados o o e en el siguiente orden de prioridad: ¬ (prioridad m´s alta) a ∧ ∨ →, ↔ (prioridad m´s baja) a los par´ntesis refuerzan la prioridad para subexpresiones encerradas. Los conece tores con la misma precedencia son aplicados de izquierda a derecha. Entonces la f´rmula (x ∧ ¬y) ∨ z puede ser escrita sin par´ntesis como x ∧ ¬y ∨ z; las o e f´rmulas (x → ¬y) → z, x → ¬(y → z) yx → (¬y → z) son diferentes. o Tautolog´ ıa Una f´rmula que siempre es verdad se conoce como tautolog´ Entonces o ıa. x ∨ ¬x es una tautolog´ Si dos f´rmulas f y g tienen valores id´nticos en sus ıa. o e tablas de verdad, entonces f ↔ g es una tautolog´ Esto es, si dos f´rmulas f ıa. o y g son l´gicamente equivalentes, denotado por f ≡ g, si y s´lo si f ↔ g es una o o tautolog´ ıa. Por ejemplo,...