UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

UNIDAD N° 01: SEMANA 01:

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

 Denominación: LÓGICA, MATEMÁTICA Y CONJUNTOS.  Contenido: Lógica Proposicional: Introducción. Proposiciones lógicas. Clases de Proposiciones Lógicas. Proposiciones Compuestas Básicas. Proposiciones Compuestas. Tautología, Contradicción y Contingencia. Proposiciones Lógicamente Equivalentes.  Objetivos: - Formalizar y simbolizar cualquier proposición simple o molecular. - Determinar la tabla de verdad, determinar los valores de verdad de las proposiciones simples o compuestas. - Identificar las proposiciones lógicamente equivalentes.

Sesión 01:

Tema: LÓGICA PROPOSICIONAL

I.

INTRODUCCIÓN: El ser humano, a través de su vida diaria, se comunica con sus semejantes a través de un lenguaje determinado (oral, escrito, etc.) por medio de las denominadas frases u oraciones. Estas pueden tener diferentes significados pero siempre van a resumirse a las formas de verdaderas o falsas, siendo éste el precedente fundamental para el desarrollo humano. Lo importante en el desarrollo de esta sesión es el hecho de que, a partir de los enunciados y de acuerdo a su significado es posible establecer una proposición y a partir de un conjunto de éstas podemos llegar a una conclusión o inferencia, siendo la lógica la ciencia encargada del estudio de éstas. La lógica proposicional es una rama de la lógica que permite representar hechos y/o expresiones del mundo real en un lenguaje representativo del conocimiento mediante propiedades elementales para estudiar a través de proposiciones o sentencias lógicas sus posibles evaluaciones de verdad. La lógica proposicional toma un rol muy importante en el desarrollo de la inteligencia artificial, y en otros aspectos de la informática.

II.

PROPOSICIONES LÓGICAS: Definición: Son aquellas expresiones u oraciones que pueden ser calificadas bien como VERDADERAS, o bien como FALSAS, sin ambigüedades. Las proposiciones lógicas serán denotadas con letras minúsculas generalmente: p, q, r, …, etc. A la veracidad o falsedad de un enunciado (proposición) se le denomina VALOR VERITATIVO o VALOR DE VERDAD. Ejemplos de proposiciones lógicas:

p : q : r :

Proposiciones lógicas Lima es la capital del Perú. 17 – 6 = 10. La UNAM es una universidad privada.

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

Valor de verdad Verdadera (V). Falso (F). Falso (F).

1

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Ejemplos de expresiones que no son proposiciones lógicas: Expresiones que no son proposiciones lógicas Buenos días. No faltes. ¿Quién llamo por teléfono?. ¡Ingrese a la universidad!.

Valor de verdad No posee/No esta definido. No posee/No esta definido. No posee/No esta definido. No posee/No esta definido.

Observación: En resumen, las Proposiciones Lógicas son expresiones de las que tienen sentido decir que son verdaderas o que son falsas. También se les denomina simplemente PROPOSICIONES.

III.

CLASES DE PROPOSICIONES LÓGICAS: PROPOSICIONES SIMPLES O ATÓMICAS: Son aquellas que se pueden representar por una sola variable, es decir, por una sola letra como: p: Pamela tiene 20 años. q: 5 x 5 = 25. PROPOSICIONES COMPUESTAS O MOLECULARES: Son aquellas que se pueden representar por lo menos por una variable y algún o algunos de los símbolos que representan a las palabras siguientes: Palabras:

no

implica

o

y

si y solo si

o bien “p” o bien “q”

Símbolo:

~











Ejemplo:

No aprobé el curso de Matemática I.

p

~ Hoy es sábado

y

mañana domingo.

q

p IV. PROPOSICIONES COMPUESTAS BÁSICAS LA NEGACIÓN:

Dada una proposición p, se denomina LA NEGACIÓN DE p, a otra proposición denotada por que le asigna el valor veritativo opuesto al de p.

~p,y

Su tabla de verdad es: p V F

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

~p F V

2

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Esta proposición ~ p es también leída como: “no p” “no es cierto que p” Ejemplos: Sean las proposiciones: Expresión simbólica p: q:

Proposiciones lógicas Lenguaje natural 3 x 4 = 12 Visual Basic 6.0 no es un lenguaje de programación.

Valor de verdad V F

Entonces sus negaciones son: Expresión simbólica ~ p: ~ q:

Proposiciones lógicas Lenguaje natural No es cierto que 3 x 4 = 12 (o sino, 3 x 4  12 ) Visual Basic 6.0 es un lenguaje de programación.

Valor de verdad F V

LA DISYUNCIÓN: Se le denota “p v q” y se lee “p o q”. Es una proposición compuesta por la proposición p y la proposición q, ambas relacionadas por la palabra “o”, y está definida por la siguiente condición: “La proposición p v q es FALSA únicamente en el caso en que p y q son ambas falsas; en cualquier otro caso es verdadera”. En su tabla de verdad se denota sus valores para todas las posibles combinaciones de valores veritativos de p y q como sigue: p V V F F

q V F V F

p v q V V V F

(*) Ver el ejemplo.

Por ejemplo: correspondiente a la combinación (*) de la tercera fila:

Expresión simbólica p: q: p v q

Proposiciones lógicas Lenguaje natural 8 es menor que 5 6 es mayor que 5 8 es menor que 5 o 6 es mayor que 5

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

Valor de verdad F V V

3

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

LA CONJUNCIÓN: Se le simboliza “p q”, y se lee como “p y q”. Se le define como una nueva proposición que resulta verdadera (V) en el único caso en que las proposiciones componentes p y q son ambas VERDADERAS (V). En todos los demás casos es FALSA (F). Su tabla de verdad es: p V V F F

p

q V F V F

q V F F F

(*) Ver el ejemplo.

Por ejemplo: correspondiente a la combinación (*) de la segunda fila:

Expresión simbólica p: q: p q

Proposiciones lógicas Lenguaje natural 9 es múltiplo de 3 10 + 7 = 12 9 es múltiplo de 3 y 10 + 7 = 12

Valor de verdad V F F

LA CONDICIONAL: Se le simboliza “p  q”, y se lee “Si p entonces q”. Es una nueva proposición compuesta que es falsa únicamente en le caso en que la proposición p es verdadera y la proposición q es falsa. Su tabla de verdad es: p V V F F

q V F V F

p

 q V F V V

La proposición “p” es llamada ANTECEDENTE y la proposición “q” CONSECUENTE. Esta proposición “p  q” también se lee de las siguientes maneras: “p implica q”. “p es una condición suficiente para que q”. “q a menos que ~p” “Es suficiente que p para que q”.

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

4

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Ejemplo: Explique porqué las condicionales siguientes tienen los valores veritativos indicados:

Expresión simbólica p  q p  q p  q

Proposiciones lógicas Lenguaje natural 2+ 3 = 8  5 < 6 3 - 1 = 4  2 < 1 Si 5 es primo, entonces 15 es un número par

Valor de verdad V V F

Estas condicionales tienen los valores de verdad indicados debido a que: a) p es falsa y q verdadera b) p es falsa y q falsa c) p es verdadera y q falsa

: : :

condicional verdadera. condicional verdadera. condicional falsa.

LA BICONDICIONAL: Se denota “p  q ”, y se lee “p si y solo si q”. Es aquella proposición compuesta que es VERDADERA en los casos en que ambas p y q tengan valores veritativos iguales (ambas verdaderas o ambas falsas); es FALSA en los casos en p y q tengan valores veritativos opuestos. Su tabla de verdad es: p V V F F

q V F V F

p



q

V F F V

También se lee como: “p si y solamente si q ”. “p es una condicional necesaria y suficiente para q”. Por ejemplo: Expresión simbólica p q p  q

Proposiciones lógicas Lenguaje natural 2 < 4 2 + 6 < 4 + 6 2 < 4 si y solo si

2+6 < 4 + 6

Valor de verdad V V V

LA DISYUNCIÓN EXCLUSIVA: Se denota “p q” , y se lee: “O bien p o bien q”. Es aquella proposición que es verdadera en los casos en que ambas proposiciones p y q tengan valores veritativos opuestos, y es falsa si ambas tienen idénticos valores de verdad.

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

5

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Su tabla de verdad es: P V V F F

p

q V F V F

q F V V F

Por ejemplo: Expresión simbólica p q p q

Proposiciones lógicas Lenguaje natural Vamos a Arequipa. Vamos a Tacna. O vamos a Arequipa o vamos a Tacna

Valor de verdad V / F F / V V

Sea la proposición: O vamos a Arequipa o vamos a Tacna. Queda claro que sólo podremos ir a uno de los dos lugares, y sólo a uno. Es decir que el enunciado es verdadero sólo si vamos a una de las dos ciudades. En caso de ir a ambas, o de no ir a ninguna, el enunciado es Falso.

V.

CONECTIVOS LÓGICOS -

Representación: Los conectivos lógicos se representan por los símbolos: Palabras:

No

implica

o

y

si y solo si

o bien “p” o bien “q”

Símbolo:

~











VI. PROPOSICIONES COMPUESTAS -

Utilizando los conectivos lógicos se pueden combinar cualquier número finito de proposiciones compuestas básicas para obtener otras cuyos valores de verdad pueden ser conocidos construyendo sus tablas de verdad; en tales tablas se indican los valores resultantes de estas proposiciones compuestas para todas las combinaciones posibles de valores de verdad de las proposiciones compuestas.

-

Por ejemplo, la tabla de verdad de la proposición compuesta siguiente: [ (~p) q ]  (r p ) , es: p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

~p F F F F V V V V

(~p)

q V V F F V V V V

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

r

p V F V F F F F F

[ (~p)

q ]

 (r

p)

V F V V F F F F 6

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Jerarquía de los conectivos lógicos: Cuando en una proposición compuesta se tiene varios conectivos lógicos, las operaciones se realizan luego de colocar los paréntesis adecuadamente comenzando de las proposiciones que se encuentren dentro de los paréntesis interiores. Siguen todas las negaciones y luego se avanza de izquierda a derecha. Los corchetes son considerados como paréntesis.

VII. TAUTOLOGÍA, CONTRADICCIÓN y CONTINGENCIA -

TAUTOLOGÍA: A toda proposición simple o compuesta cuyo valor es siempre VERDADERO para cualquier combinación de valores veritativos de sus componentes se le llama TAUTOLOGÍA y se le denota siempre por V. Ejemplo: La proposición [ ( (~p) p V V F F

-

q V F V F

~p F F V V

~q F V F V

(~p)

q)

q

 ~p , es una TAUTOLOGÍA. En efecto:

[ ( (~p)

V F V V

q) F F F V

~q ]

 ~p V V V V

F F V V

CONTRADICCIÓN: A toda proposición simple o compuesta cuyo valor es siempre FALSO para todas las combinaciones de valores veritativos de sus componentes se le llama CONTRADICCIÓN, y se le denota simplemente por F Ejemplo: La proposición [ ( p p V V F F

-

~q ]

q V F V F

~q F V F V

p

q

q)

(p

q ]

q)

V F F F

~q , es una CONTRADICCIÓN. En efecto:

q

[ (p

q)

q ]

V F V F

~q F F F F

CONTINGENCIA: Una proposición simple o compuesta cuya tabla de verdad contiene al menos un V y al menos un F recibe el nombre de CONTINGENCIA. Ejemplo: p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

~p F F F F V V V V

(~p)

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

q V V F F V V V V

r

p V F V F F F F F

[ (~p)

q ]

 (r

p)

V F V V F F F F

7

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

VIII. PROPOSICIONES LÓGICAMENTE EQUIVALENTES Dos proposiciones p y q se llaman EQUIVALENTES (o lógicamente equivalentes) si sus tablas de verdad son idénticas, en cuyo caso se simboliza: p  q Ejemplo: Las proposiciones ( p  q ) y [ (~q)  (~p) ] son EQUIVALENTES pues sus tablas de verdad resultantes son idénticas, como se puede ver en el cuadro: p V V F F

q V F V F

p

 q V F V V

~q F V F V

 ~p V F V V

F F V V

idéntica Por lo tanto: ( p

 q) 

[ (~q)

 (~p) ]

IX. EJERCICIOS PRÁCTICOS Identifique las proposiciones en las siguientes expresiones: a) El teclado es un dispositivo de entrada de datos. Respuesta: El teclado es un dispositivo de entrada de datos.

p p

: El teclado es un dispositivo de entrada de datos.

b) El curso de Física es teórico y práctico. Respuesta: El curso de Física es teórico y práctico.

p p q

q

: El curso de Física es teórico. : El curso de Física es práctico.

c) Ana y Pedro estudian en la UNAM, entonces son parte de la comunidad universitaria. Respuesta: Ana y Pedro estudian en la UNAM, entonces son parte de la comunidad universitaria.

p p q r

q

r

: Ana estudia en la UNAM. : Pedro estudia en la UNAM. : Son parte de la comunidad universitaria.

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

8

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

Construya proposiciones compuestas: Sea

p: 8 es un número par. q: 8 es el producto de dos enteros.

Traducir en símbolos cada una de las siguientes proposiciones: a) 8 es un número par o es un producto de dos enteros. b) 8 es impar y es un producto de de dos enteros. c) 8 es par y un producto de dos enteros o es un número impar y no un producto de dos enteros. Respuesta: a) p q b) (~p) q c) (p q) [ (~p)

(~q)]

Indicar que proposiciones son verdaderas o falsas: Sean p, q y r tres proposiciones tales que p es verdadera, q es falsa y r es falsa. Indicar cuáles de las siguientes proposiciones son verdaderas: a) (p b) (~p)

q)

r (q

r)

Solución: a) Esta proposición es VERDADERA, pues: (p

(V

q)

r

F)

F

V

F

V b) Esta proposición es FALSA, pues: (~p)

(q

r)

(F)

(F

F)

F

F

F Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

9

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

X.

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

PROBLEMAS PROPUESTOS Dadas dos sentencias proposicionales A y B, se cumple que AB es una tautología. Indicar cuáles de las siguientes opciones son válidas: a. A B es una tautología. b. A B es una tautología. c. A B es una tautología. d. B A es una tautología. e. A B es una tautología. f. A B es contradicción. g. A B es contradicción.

La sentencia “El caso no se resolverá a menos que el asesino decida confesar su crimen o aparezca por sorpresa un testigo relevante” puede formalizarse como: a. ~q → (q ∨ r) b. (q ∨ r) → ~p c. (q ∨ r) → p d. p → (q ∨ r) Dadas las premisas { p (q r), q r } ¿Cuál de las siguientes podría ser la consecuencia para que el razonamiento sea correcto? a.p r b.p r c.r p d.p r Dada la fórmula ((p q) (q r)) (p q), una fórmula equivalente puede ser: a.p q b.p c.p q r d.(p q) (p r)

XI. CONCLUSIONES -

Las PROPOSICIONES son aquellas expresiones u oraciones que pueden ser calificadas bien como VERDADERAS, o bien como FALSAS, sin ambigüedades. Las proposiciones lógicas serán denotadas con letras minúsculas generalmente: p, q, r, …, etc.

-

A la veracidad o falsedad de un enunciado (proposición) se le denomina VALOR VERITATIVO o VALOR DE VERDAD.

-

Las clases de proposiciones lógicas pueden ser PROPOSICIONES SIMPLES O ATÓMICAS y las PROPOSICIONES COMPUESTAS O MOLECULARES.

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

10

UNIVERSIDAD NACIONAL DE MOQUEGUA - UNAM FACULTAD DE INGENIERIA Carrera Profesional de Ingeniería en Sistemas e Informática

Periodo Académico: 2009 - I Curso: MATEMÁTICA DISCRETA

-

Proposiciones compuestas básicas son: la NEGACIÓN, la DISYUNCIÓN, la CONJUNCIÓN, la CONDICIONAL, la BICONDICIONAL y la DISYUNCIÓN EXCLUSIVA.

-

Las PROPOSICIONES COMPUESTAS se forman utilizando los conectivos lógicos, con los cuales se pueden combinar cualquier número finito de proposiciones compuestas básicas para obtener otras cuyos valores de verdad pueden ser conocidos construyendo sus tablas de verdad.

-

La TAUTOLOGÍA se da en toda proposición simple o compuesta cuyo valor es siempre VERDADERO y se le denota siempre por V.

-

La CONTRADICCIÓN se da en toda proposición simple o compuesta cuyo valor es siempre FALSO y se le denota simplemente por F

-

La CONTINGENCIA se da en toda proposición simple o compuesta cuya tabla de verdad contiene al menos un V y al menos un F.

-

Dos proposiciones p y q se llaman EQUIVALENTES (o lógicamente equivalentes) si sus tablas de verdad son idénticas, en cuyo caso se simboliza: p  q .

XII. BIBLIOGRAFÍA Libros: 1. R. Figueroa, Matemática Básica, Ed. Americana, Lima 1996 2. W. K.Grassmann, J.P. Tremblay, Matemática Discreta y Lógica. Ed. Prentice Hall 1997.

Direcciones electrónicas: 2. Tema: Lógica Proposicional Autor: Andrés J. Bilstein http://www.scribd.com/doc/3984030/Logica-Proposicional 3. Tema: Lógica Autores: Fernando Hernández Magadán, Jose E. Labra G., Daniel Fernández Lanvin Daniel Gayo Avello César Fernández Acebal. http://www.di.uniovi.es/~labra/Logica/Logica.html

Docente: Ing. Vaneza Flores Gutiérrez Celular: (052) 952864956 E-mail: [email protected]

11