Matematicas discretas

Matematicas discretas El estudiante obtiene los conocimientos basicos y aprende las tecnicas necesarias para el analisis y desarrollo de algoritmos, asi tambien se favorece el razonamiento logico la capacidad logico, de abstraccion y la capacidad logico matematica del estudiante, estudiante que le permitira formular soluciones basadas en herramientas computacionales Logica y calculo proposicional La resolucion de problemas, diseno de g programacion requieren q algoritmos y p g un razonamiento logico completo. La logica trata los metodos y el arte del razonamiento sistematico. . 1 Logica proposicional El alfabeto proposicional consiste de lo siguiente: p p g Un conjunto de variables denominadas atomos: P, Q, R,… Un conjunto d conectivos lo de logicos (Negacion, o Conjuncion, Disyuncion, Implicacion y Equivalencia). Los simbolos d parentesis. i b l de e 1. 1 Logica proposicional Una proposicion es una sentencia declarativa q que es verdadera o falsa pero no ambas. p Por ejemplo: “la manana es fria” Formulas o u as Una formula bien formada se define como: Una formula atomica es una formula. P es na fo formula, tambien lo sera ¬P l be l a Si P y Q son formulas entonces la conjuncion, j , disyuncion, implicacion y equivalencia de P

Lo sentimos, pero las muestras de ensayos completos están disponibles solo para usuarios registrados

Elija un plan de membresía
y Q tambien lo sera sera. Una expresion es una formula si y unicamente si se puede demostrar por las anteriores condiciones. Formulas o u as La implicacion recibe el nombre de formula p condicional y la equivalencia el de formula bicondicional. bicondicional La jerarquia de los conectivos logicos se aplica de la siguiente forma: Negacion,Conjuncion, Disyuncion, Condicional y bicondicional. Proposiciones compuestas

Una proposicion que es indivisible se conoce como proposicion primitiva primitiva. Las sentencias derivadas de las primitivas y de varios conectores logicos como no, ¬ y, o, si… entonces i si y solo si se conocen como proposiciones compuestas. Ejercicios 2. Sean p “El es alto” y q “El es galan”. Escriba los siguientes enunciados en forma simbolica con p y q (1) El es alto y galan ( ) (2) El es alto pero no es galan p g (3) es falso que el es bajo o galan. (4) El no es alto ni galan. ( ) (5) El es alto, o el es bajo y galan. , j g (6) No es verdad que el es bajo o que no es galan Tablas de T bl d verdad d d

Las tablas de verdad son una forma conveniente de p p p mostrar los valores de una proposicion compuesta. En su construccion, usamos 1 para verdadero y 0 para falso, falso aunque tambien es comun utilizar T y F F. P ¬P 1 0 0 1 P ¬P T F F T Ejercicios 3. Determinar el valor de verdad de cada uno de los siguientes enunciados compuestos. (1) Si 3 + 2 = 7, entonces 4 + 4 = 8 (2) No es verdad que 2 + 2 = 5 si, y solo si, 4 + 4 = 10 ( ) (3) Paris esta en Inglaterra o Londres esta en Francia.. g .. (4) No es verdad que 1+1 = 3 o que 2+1 = 3 (5) Es falso que si Paris esta en Inglaterra, entonces Londres esta en Francia.

Tabla de verdad de y La conjuncion de p, q es denotada por p ? q. Ejemplo 1: Sea p = Paris esta en Francia, y q = 2 + 2 = 4 Podemos establecer los siguientes enunciados: (1) Paris esta en Francia y 2 + 2 = 4 (2) P i esta en Francia y 2 + 2 = 5 Paris ta F i (3) Paris esta en Inglaterra y 2 + 2 = 4 (4) Paris esta en Inglaterra y 2 + 2 = 5 p V V F F q p? q V V F F V F F F V1: Si p es verdadero y q es verdadero, entonces p ? q es , verdadero; en otro caso p ? q es falso. La conjuncion es verdadera solo si p y q son verdaderos. Tabla de verdad de o La disyuncion de p, q es denotada por p v q.

Ejemplo 2: Ej l 2 Sea p = Paris esta en Francia, y q = 2 + 2 = 4 Podemos establecer los siguientes enunciados: (1) Paris esta en Francia o 2 + 2 = 4 (2) Paris esta en Francia o 2 + 2 = 5 (3) Paris esta en Inglaterra o 2 + 2 = 4 (4) Paris esta en Inglaterra o 2 + 2 = 5 p V V F F q pVq V V F V V V F F V2: Si p es verdadero o q es verdadero, o si ambos p y q son verdaderos entonces p v q es verdadero; en otro caso p v q es falso. Es decir, la disyuncion de dos enunciados es falsa y solamente si los dos enunciados componentes son falsos. Una sentencia que es modificada con el conectivo no, es llamada la negacion de la sentencia original.

Simbolicamente, Simbolicamente si p es una proposicion entonces ¬p (no p), denota la negacion de p. Ejemplo 3: Sea p = Paris esta en Francia Consideremos los siguientes enunciados: (1) Paris esta en Francia (2) Es falso que Paris esta en Francia (3) P i no esta en F Paris ta Francia i p ¬p V F F V cada uno negacion de (1) (2) y (3) son Tabla de verdad de no V3: Si p es verdadero entonces ¬p es falso; si p es falso entonces ¬p es verdadero Es decir: el valor de la negacion de un enunciado es siempre el opuesto del valor del enunciado Tabla de verdad de implicacion p

La implicacion de p, q es denotada por p > q. Ejemplo 4: Ej l 4 Sea p = Paris esta en Francia, y q = 2 + 2 = 4 Podemos establecer los siguientes enunciados: (1) Si Paris esta en Francia entonces 2 + 2 = 4 (2) Si Paris esta en Francia entonces 2 + 2 = 5 (3) Si Paris esta en Inglaterra entonces 2 + 2 = 4 (4) Si Paris esta en Inglaterra entonces 2 + 2 = 5 p V V F F q p>q V V F F V V F V V4: El condicional p > q es verdadero a menos que p sea verdadero y q sea falso. Es decir, un enunciado verdadero no puede implicar uno falso falso. La doble implicacion de p, q es denotada por p – q.

Ejemplo 6: Ej l 6 Sea p = Paris esta en Francia, y q = 2 + 2 = 4 Podemos establecer los siguientes enunciados: (1) Paris esta en Francia solo si 2 + 2 = 4 (2) Paris esta en Francia solo si 2 + 2 = 5 (3) Paris esta en Inglaterra solo si 2 + 2 = 4 (4) Paris esta en Inglaterra solo si 2 + 2 = 5 p V V F F q p-q V V F F V F F V Tabla de verdad de doble implicacion V5: El bicondicional p – q es verdadero solamente si p y q tienen el mismo valor de verdad. Es decir, si los dos enunciados son verdaderos, o si ambos son falsos, entonces la doble implicacion es verdadera falsos verdadera.

Polinomios y polinomios Boolianos Las sumas finitas (+), productos (*) y diferencias (-) de ( ) las variables (o indeterminadas) x, y, . . . Sometidas a las reglas usuales del algebra ordinaria, constituyen los p polinomios en dichas variables. Ejemplo 7-1: Los siguientes son polinomios en dos variables: f(x, ) 2x f( y) = 2 2 – xy + y3 = x*x – x*y + y*y*y + * * * * x*x g(x, g(x y) = (x + y)* (x – y) = x2 – y 2 y) Ejemplo 7-2: Sean los polinomios del ejemplo 7-1: f(2, f(2 3) = 2*2 – 2*3 + 3*3*3 + 2*2 = 4 – 6 + 27 + 4 = 29 g(3, 1) = (3 + 1)* (3 – 1) = 4 * 2 = 8 Polinomios y polinomios boolianos

Las operaciones suma, producto y diferencia, definidas , p j entre numeros reales, inducen operaciones semejantes llamadas asimismo suma, producto y diferencia entre p polinomios. Ejemplo 7-3: Sean los polinomios del ejemplo 7-1: f(x, y) – g(x, y) = (2×2 – xy + y3) – (x2 – y 2) f(x, y) * g(x, y) = (2×2 – xy + y3) * (x2 – y 2) Supongamos ahora que las letras p, q, . . . que h l l anteriormente denotaban enunciados, ahora son variables. P d i bl Podemos combinar estas variables por l bi t i bl las conectivas ? , v, ¬,> y – para construir expresiones que > se llaman polinomios boolianos boolianos.

Polinomios boolianos Ejemplo 7-4: Los siguientes son polinomios boolianos en dos variables: f(p, q) = ¬p v (p > q) g(p, q) = (p – ¬q) ? q Y ademas se pueden emplear los simbolos ? , v, ¬,> y – > como conectivas para los polinomios boolianos; asi se puede hablar de la conjuncion, disyuncion y negacion de p polinomios boolianos. Ejemplo 7-5: Sean los polinomios boolianos del ejemplo 7-4. Entonces: f(p, q) ? g(p, q) = [¬p v (p > q)] ? [(p – ¬q) ? q] f(p f(p, q) > g(p, q) = [ p v (p > q)] > [(p – ¬q) ? q] g(p [¬p Suponiendo ahora que cada una de las variables p, q, . . . de un polinomio booliano f(p, q . . ) se reemplazan respectivamente por un enunciado particular d d l denotado d por p0, q0, . . . , la expresion f(p0, q0 . . . ) ) Es tambien un enunciado y tiene por lo mismo un valor de d d d verdad. Ejemplo 7-6: Sean f(p, q) = ¬p ? (p > q) y p0 : “2 + 2 = 5” y q0 : “1 + 1 = 2” Entonces f(p0, q0) quiere decir: “2 + 2 ? 5, y si 2 + 2 = 5 entonces 1 + 1 = 2” 2 5 2 Por V4, ro = p0 > q0 es verdadero. Notese que so = ¬p0 es verdadero. Por lo tanto, por V1 q p ,p 1, f(p0, q0) = S0 ? r0 es tambien verdadero. Polinomios boolianos Polinomios boolianos Observacion 1: Sea un polinomio booliano f(p, q. . . y sean los ) enunciados p? 0, q? 0, . . . con el mismo valor de verdad q que los enunciados p0, q0, . . . Entonces f(p? 0, q? 0 . . . ) ) tiene el mismo valor de verdad que f(p0, q0 . . . ) Proposiciones y tablas de verdad Definicion 1: Se llama proposicion un polinomio booliano en las variables p, q, . . . y se le denota por P(p, q. . . ), Q(p, q. . . ). . . ), ) o simplemente por P, Q, . . . Por la observacion 1, el valor de verdad de una proposicion P(p, q. . . ) evaluado sobre enunciados cualesquiera, es funcion solamente de los valores de verdad y no de los enunciados particulares mismos.

Asi, pues, se habla del “valor d verdad” d cada una d l h bl d l “ l de d d” de d de las variables, p, q. . . , y del “valor de verdad de la proposicion P( q. . . ). i io P(p, ) Proposiciones y tablas de verdad La relacion entre el valor de verdad de una proposicion P(p, q. . . ) y los valores de verdad de sus variables p, q. . (p, q ) q . , se muestra por medio de una tabla de verdad. Por ejemplo, la tabla de verdad de la proposicion j p , p p ¬(p ? ¬q) se construye como sigue: p V V F F q V F V F ¬q p F V F V ? ¬q ¬(p ? ¬q) F V F F V F V V Para dos variables, como en este caso, se necesitan 4 filas.

Para 3 variables se necesitan 8 filas y, en general, para n variables se requieren 2n filas. Proposiciones y tablas de verdad La tabla de verdad de la proposicion anterior ¬(p ? ¬q) Consiste solamente en las columnas encabezadas por las variables y la columna encabezada por la proposicion asi: proposicion, p V V F F q V F V F ¬(p ? ¬q) V F V V Otra manera de construir las tablas de verdad p V V F F Paso q V F V F ¬ V F V V (p ^ F V F F ¬ F V F V q) 4 1 3 2 1 La tabla de verdad de la proposicion queda formada por las columnas encabezadas por las variables y por la p p ultima columna completada en el ultimo paso.

Ejercicios 4. H ll la bl de l de las i i 4 Halle l tabla d valor d l siguientes proposiciones: ii (1) (2) (3) (4) ¬p ? q ¬(p >¬q) (p ? q) > (p V q) ¬(p ) ¬( ? q) V ¬(p ¬( – q) ) Soluciones (1) ¬p ? q p V V F F q V F V F ¬p ¬p F F V V ? q p q ¬ p V V F F 1 ? q V F V F 1 F F V F V V F V F F F V V F F V Paso 2 F F V F 3 Soluciones (2) p V V F F q ¬q V F V F F V F V ¬(p >¬q) p V q ¬ (p > ¬ V V V F V F F F F 4 1 F V V V 3 F V F V 2 q) V F V F 1 p >¬q ¬(p >¬q) F V V F V F V F V F F V F F Paso Soluciones (3) (p ? q) > (p V q) p q (p V V V F F V F F Paso P V V F F 1 ? p q p ? q p V q (p ? > p V q) VV V V V V F F V V F V F V V F F F F V q) > (p V F V F 1 V V V V 3 V V F F 1 v q) V F V F 1 V F F F 2 V V V F 2 Es una t t l gi porque sus valores de verdad resultantes de la tautologia proposicion son siempre verdaderos, sin importar si los enunciados sencillos que componen la proposicion son o no verdaderos. d d Soluciones (4) p V V F F q p? q V V F F V F F F p q q-p V F F V ¬ F V V V 3 (p V V F F 1 ¬(p ? q) ¬(p ? q) F V V V ? V ¬(p – q) ¬(p ¬(p ? q) ( V ¬(p ¬(p – q) ( F V V F V ¬(p ¬(p – q) ( F V V V (q V F V F 1 – V F F V 2 p) V V F F 1 q) V F V F 1 ¬ F V V F 3 V V V F F V F F Paso

V F F F 2 F V V V 4 Ejercicios 5. H ll la bl de l de las 5 Halle l tabla d valor d l siguientes proposiciones, utilizando el segundo metodo: (1) (p >q) V ¬(p – ¬q) Para dos variables, como en este caso, se necesitan 4 filas. (2) [p >(¬q V r )] ? ¬[q V (p – ¬r)] Para 3 variables se necesitan 8 filas y en y, general, para n variables se requieren 2n filas. Soluciones (1) p q V V V F F V F F Paso (p >q) V V ¬(p – ¬q) (p V V F F 1 (p > q) V V F F 1 V F V V 2 V F V F 1 ¬ V F F V 4 – F V V F 3 ¬ F V F V 2 p) V F V F 1 V F V V 5 Soluciones (2) p q V V V V F F F F r [p >(¬q V r )] ? ¬[q V V (p – ¬r)]

V [p > ¬ q) V V V V F F F F 1 V F V V V V V V 4 F F V V F F V V 2 V V F F V V F F 1 r] ^ ¬ [q V F F F F F V V V F F F V F F F F F V F F F V V 1 6 5 V V F F V V F F 1 (p – V V V V F F F F 1 F V F V V F V F 3 ¬ F V F V F V F V 2 r) V F V F V F V F 1 V V V F F V F F V V V F F V F F Paso V F V V V F V V 3 V V F V V V V F 4 Tautologias y contradiccion Algunas proposiciones P(p, q. . . ) tienen solo V en l l l la ultima columna de sus tablas de verdad. Es decir que la proposicion P( q. . . ) sera siempre un enunciado i io P(p, ) a i id verdadero sean cuales fueren los enunciados p0, q0,. . . erdaderos o falsos por los que se sustituyan las erdaderos ue sustitu an variables. Estas proposiciones se llaman tautologias. Definicion 2: p p p q Una proposicion P(p, q. . . ) es una tautologia si P(p0, q0, . . . ) es verdadera para dd cualesquiera enunciados p0, q0 . . . 0, Ejemplo 8-1: p p p p La proposicion “p o no p” es una tautologia, cosa que se verifica al construir una tabla de d d d verdad p ¬p p v ¬p p V F F V V V Tautologias y contradiccion De manera analoga al Definicion 3: Una proposicion P(p, q. . . ) es una contradiccion si P(p0, q0, . . . ) es falsa para cualesquiera enunciados p0, q0,. . O sea que una contradiccion solo contiene F en la ultima columna de su tabla de verdad. Ejemplo 8-2: La proposicion “p y no p” p p es una contradiccion, lo cual se ve por la tabla p V F ¬p p F V p ? ¬p V V Ejemplo 8-3: Un principio fundamental del g , y g que razonamiento logico, la “ley del silogismo” dice q “si p implica q y q implica r, entonces p implica r” Asi: [(p >q)] ? [q > r)] > (p >r) es una tautologia. p V V V V F F F F r [(p > [(p V V V V V F V V F V V F F F V F V V F V V F F V F V F V F F F V Paso 1 2 q q) V V F F V V F F 1 ? (q V V F F V V F F 1 > r)] > (p > r)

V F V V V F V V 2 V F V F V F V F 1 V V V V V V V V 4 V V V V F F F F 1 V F V F V V V V 2 V F V F V F V F 1 V F F F V F V V 3 Como una tautologia es siempre verdadera, la negacion verdadera de una tautologia sera siempre falsa, o sea que se trata ; de una contradiccion; y viceversa. Observacion 2: (p, q ) g , (p ) Si P(p, q. . . ) es una tautologia, entonces ¬P(p0, q0, . . . ) es una contradiccion, y viceversa. q ), q ), p Sean ahora P1(p, q. . . ), P1(p, q. . . ), . . . Proposiciones cualesquiera y sea P(p, q. . . ) una tautologia. Entonces P(p, q. . . ) no depende de los valores particulares de verdad d p, q. . P t t si se sustituye p por P1, q d d de Por tanto, i tit por P2 en la P(p, q. . . ) se tiene aun una tautologia. Teorema (principio de sustitucion: Si P(p, q. . . ) es una tautologia, entonces P(P1, P2, . . . ) es tambien una tautologia para cualesquiera proposiciones P1, P2, . . . Tautologias y contradiccion Dos proposiciones P(p q . .) y Q(p q . .) se dicen P(p, q. ) Q(p, q. ) logicamente equivalentes si sus tablas de verdad son . q g (p, identicas. Se denota la equivalencia logica de P(p, q. . . ) y Q(p, q. . . ) por P(p, q. . . ) (p, q ) Q(p, q. . . ) q ) Ejemplo 9-1: Las tablas de verdad de: (p >q) ? q > p) y p – q p V V F F q p >q q > p p >q V V V F F V V V F F V V Por lo tanto: (p >q) ? Equivalencia logica q>p p V V F F q V F V F V F V V ? p – q V F F V (q > p) p – q Equivalencia logica Ejemplo 9-2: Las tablas de verdad de: p >q y que son logicamente equivalentes. p V V F F q V F V F p > q V F V V p V V F F ¬p v q p muestran q ¬p ¬p v q V F V F F F V V V F V V ¬q v q q Por lo tanto: (p >q) Equivalencia logica Teorema 1: p p por La relacion entre proposiciones definida p P(p, q. . . ) ? Q(p, q. . . ) es una relacion de equivalencia, es decir: q , (1) para todo P(p, q. . . ), P(p, q. . . ) ? P(p, q. . ); (2) si P(p, q. . . ) ? Q(p, q. . . ), entonces Q(p, q. . . ) ? P(p, q. . . ); (p, (3) si P(p, q. . . ) ? Q(p, q. . . ) y Q(p, q. . . ) ? R(p, q. . . ), entonces P(p, q. . . ) ? R(p, q. . . ). Equivalencia logica Teorema 2: P(p, q. . . ) ? Q(p, q. . . ) es una tautologia si, y (p, q ) q ) g , solamente si, la proposicion P(p, q. . . ) – Q(p, q. . . ) (p, q ) q ) es tambien una tautologia. Teorema 3: Si P( q. . . ) y Q( q. . . ) son ambas tautologias o bi P(p, ) Q(p, ) b l i bien ambas contradicciones, entonces P(p, q,. . . ) ? Q(p, p,. . . ), Equivalencia logica Corolario 1: C l i 1 Si P(p, q. . . ) ?

Q(p, q. . . ), entonces p q p q P(P1, P2,. . . ) ? Q(P1, P2,. . . ), para cualesquiera proposiciones P1, P2,. . . l i ii Este corolario es una consecuencia del principio de sustitucion en las tautologias y del Teorema 2 anterior. Es d i E decir, que si se sustituyen por proposiciones las i tit ii l variables en proposiciones equivalentes, las proposiciones que resultan son t bie equivalentes. ii lt tambien i l t Teorema 4: (1a) (2a) (3a) ( ) (5a) Algebra de proposiciones p? p? p (2b) (p ? q) ? r ? p ? (q ? r) (3b) p ? q ? q ? p (4b) p ? (q V r) ? (p ? q) ? (p V r) ( ) (5b) p ? v ? p (6b) p ? f ? f p (7b) p ? p ? f (8b) ¬v ? f, ¬f ? v (9b) ¬(p ^ q) ? ¬p v ¬q (1b) pVp? p (p V q) V r ? p V (q V r) pVq? qVp (4a) p V (q ? r) ? (p V q) ? (p V r) pVf? f (6a) p V v ? v p (7a) p V ¬p ? v (8a) ¬¬p ? p (9a) (9 ) ¬(p v q) ? ¬p ^ ¬q Este teorema se puede demostrar construyendo las tablas de verdad correspondientes. A i v y f d d Aqui denotan variables que estan bl a restringidas respectivamente a enunciados verdaderos y falsos. Leyes del algebra de proposiciones (1a) Leyes de idempotencia PVP? P (1b) P ? P ? P (2a) Leyes asociativas (P V Q) V R ? P V (Q V R) (2b) (P ? Q) ? R ? P ? (Q ? R) Leyes conmutativas P V Q ?

Q V P (3b) P ? Q ? Q ? P 3b Leyes distributivas (3a) 3 (4a) P V (Q ? R) ? (P V Q) ? (P v R) (4b) P ? (Q V R) ? (P ? Q) ? (P V R) Leyes del algebra de proposiciones (5a) (6a) Leyes de identidad PVF? F (5b) P ? V ? P PVV? V (6b) P ? F ? F Leyes del complemento P V ¬P ? V (7b) P ? ¬P ? F P P ¬¬P ? P (8b) ¬V ? F, ¬F ? V (7a) (8a) Leyes de Morgan (P P Q (9b) ¬(P ? Q) ? ¬P V ¬Q (P P Q (9a) ¬(P V Q) ? ¬P ? ¬Q Implicacion logica g Examinemos el siguiente teorema: Teorema 5: p q p q p p Si P(p, q. . . ) y Q(p, q. . . ) son proposiciones, las tres Condiciones que siguen son equivalentes: (1) ¬P(p, q. . ) V Q(p, q. . . ) es una tautologia, (2) P(p, q. . . ) ? ¬Q(p, q. . . ) es una contradiccion (3) P(p, q. . . ) > Q(p, q. . . ) es una tautologia Con b C base en el t l teorema anterior, se puede i t d i l t i d introducir la: Definicion 4: Se di S dice que una proposicion P( q. . . ) implica i io P(p, ) i li logicamente una proposicion Q(p, q. . . ), lo que se escribe P(p, q. . . ) Q(p, q. . . ) si se verifica una de las condiciones del teorema 5 5. Ejemplo 10-1: La proposicion “p implica q” implica logicamente la proposicion “p implica q”, pues como se muestra en el Ejemplo 8-3 Ej l 83 (p >q) ? (q > r)] > (p >r) es una tautologia. O lo que es lo mismo: (p >q) ? (q > r) p> r Implicacion logica Implicacion logica Ejemplo 10-2: Considerese la tabla de verdad de p q V V V F F V F F Paso (p V V F F 1 ? q) V F V F 1 ? ¬ F F F V 3 (p V V F F 1 V q) V F V F 1 V F F F 2 F F F F 4 V V V F 2 Observese que: (p ? q) ? ¬(p V q) es una contradiccion; luego p ? q p V q) Implicacion logica g Teorema 6: La relacion entre proposiciones definida por P(p, q. . . ) Q(p, q. . . ) Es reflexiva antisimetrica y transitiva es decir: reflexiva, transitiva, (1) P(p, q. . . ) P(p, q. . . . (2) Si P(p, q. . . ) Q(p, q. . . ) y Q(p, q. . . ) P(p, q. . . ), p q p q entonces P(p, q. . . ) ? Q(p, q. . . ). (3) P( q. . . ) Q( q. . . ) P(p, ) Q(p, ) y Q(p, q. . . ) R(p, q. . . ), entonces P(p, q. . . ) ? R(p, q. . . ). Implicacion logica Teorema 7: Si P(p, q. . . ) Q(p, q. . . ) Entonces, para cualesquiera proposiciones P1, P2,. . . P(P1, P2,. . . ) Q(P1, P2,. . . ) Es decir, si una proposicion implica logicamente otra, g y la relacion sigue siendo valida cuando se sustituyen las proposiciones arbitrarias en las proposiciones originales. originales Implicacion logica g

Observacion 3: Considerando los simbolos > y Observese que P(p, q. . . ) > Q(p, q. . . ) es precisamente una proposicion y que su tabla d i i io bl de verdad solo puede contener o bien V o bien F en la ultima l ulti columna. P Pero P(p, q. . . ) Q(p, q. . . ) p q p q define una relacion entre proposiciones compuestas, a saber, que la proposicion compuesta ,q p p p P(p, q. . . ) > Q(p, q. . . ) solo tiene V en la ultima columna de su tabla de verdad, o sea que es una tautologia. Observacion 4: Ob io 4 Considerando ahora los simbolos – y ? Observese que P( q. . . ) – Q( q. . . Ob e P(p, ) Q(p, ) es tambien precisamente una proposicion compuesta y que su tabla de verdad puede tener en la ultima columna tanto V como F. Pero P(p, q. ) Q(p, q. ) P(p q . .) ? Q(p q . .) define una relacion entre proposiciones compuestas q (p, q ) q ) estableciendo que P(p, q. . . ) y Q(p, q. . . ) tienen tablas de verdad identicas, o lo que es lo mismo, que P(p, q. . . ) – Q(p, q. . . ) (p q ) Q(p q ) solo tiene V en la ultima columna de su tabla de verdad. Siendo asi que, hablando en pura logica, no cabe distinguir di i i entre dos proposiciones equivalentes, hay d ii i l h autores que usan el signo = en vez del ?.

Implicacion logica Se dice que un enunciado es logicamente verdadero si se le puede derivar de una tautologia, es decir si el enunciado es de la forma P(p0, q0,. . . ), ) donde P(p, q,. . . ), es una tautologia Ejemplo 11-1: Sean los siguientes enunciados: (1) Esta lloviendo. lloviendo (2) Esta lloviendo o no esta lloviendo. El primer enunciado puede ser verdadero; su valor de verdad depende de condiciones extrinsecas al enunciado , , g mismo, es decir, del clima. El segundo enunciado es logicamente verdadero, ya que se puede derivar de la tautologia p V ¬p.

Su valor de verdad no depende de condiciones extrinsecas al enunciado mismo. di i ti l id i Implicacion logica Implicacion logica Asimismo, se dicen logicamente equivalentes los enunciados de la forma P(p0, q0,. . . ) y Q(p0, q0,. . . ) si (p , ) , ) las proposiciones P(p, q,. . . ) y Q(p, q,. . . ) son logicamente equivalentes. g q Ejemplo 11-2: Como ¬(p ? q) ? ¬p v ¬q, el enunciado “ es C ( ) l i d “no verdad que las rosas son rojas y que las violetas son azules” es logicamente equivalente al azules enunciado “Las rosas no son rojas o las violetas no son azules”