Estructuras Discretas

UNIVERSIDAD CENTROOCIDENTAL ’LISANDRO ALVARADO’ DECANATO DE CIENCIAS Y TECNOLOG´ IA ´ DEPARTAMENTO DE MATEMATICAS

ESTRUCTURAS DISCRETAS

Por: Ronald Guti´rrez e

Barquisimeto 2009

´ Indice general
´ 1. CALCULO PROPOSICIONAL 1.1. Proposiciones . . . . . . . . . . . . . . . . 1.2. Operaciones veritativas . . . . . . . . . . . 1.3. Formas proposicionales . . . . . . . . . . . 1.4.Tautolog´ implicaciones y equivalencias ıas, 1.5. Circuitos l´gicos . . . . . . . . . . . . . . . o 1.6. Cuantificadores . . . . . . . . . . . . . . . 1.7. Ejercicios resueltos . . . . . . . . . . . . . 1.8. Ejercicios propuestos . . . . . . . . . . . . 1 1 4 8 12 15 19 22 24

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . ..

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

i

Cap´ ıtulo 1 ´ CALCULO PROPOSICIONAL
En este cap´ ıtulo estudiaremos las proposiciones, los diferentes elementos que intervienen ella (conectivos, cuantificadores) y los efectos de estos en la proposici´n. Uno de los temas principales que abordaremos ser´ el de formas o a proposicionales

1.1.Proposiciones

Definici´n 1.1.1 una proposici´n: es un juicio declarativo del que tiene o o sentido decir que es verdadero o falso pero no ambas simult´neamente a Ejemplo 1.1.1 Consideremos las siguientes expresiones 1. Barquisimeto es la capital del estado lara 2. 3 − 2 = 4 3. ¿ Hay clase hoy? 4. ¡ Vete ! 5. Todos los n´meros son positivos u 6. Esta proposici´n es falsa o 7. 4 · 8 = 32

1

Sonproposiciones 1,2,5 y 7 (verdadera, falsa, falsa, verdadera respectivamente). 3 y 4 no son proposiciones porque son juicio interrogativo e imperativo respectivamente. 6 es un juicio declarativo pero es contradictorio Definici´n 1.1.2 Si p es una proposici´n verdadera decimos que su valor o o l´gico, denotado por V L(p), es uno (V L(p) = 1), si p es falsa entonces o diremos que su valor l´gico es cero (VL(p) = 0) o Ejemplo 1.1.2 La expresi´n o ’EL trillonesimo digito de la expresi´n decimal de es 5’ o es una proposici´n. Aunque cuando no se sepa de antemano si es verdad o o no, es claro que solo es una de ella. Aunque sea muy dificil o casi imposible saber si un juicio declarativo es o no verdad, para que sea proposici´n lo importante es que se tenga la certeza de o que ser´ s´lo una de ellas a oOtra proposici´n de este tipo es por ejemplo o ’en Marte existen piedras de 2.42 kilogramos de peso’ Prestemos atenci´n a las siguientes expresiones o a) x + 1 > 0 b) Para todo n´mero real x se cumple que x + 1 > 0 u La primera expresi´n NO es proposici´n, pero la segunda SI lo es (falsa). o o Esto se debe a que en la primera no hay especificaci´n sobre x, depende de o que n´mero real x se coloquepara conocer si la expresi´n es verdadera o falsa u o (por ejemplo 2 + 1 > 0 es verdadero, −4 + 1 > 0 es falso) En cambio en la segunda, la expresi´n para todo n´ mero real x, es la o u que hace que tenga sentido decir que el juicio declarativo sea falso debido a que existen numeros para los cuales es verdad que el m´s uno es mayor que ´ a cero(2 por ejemplo), pero para otros no es as´ (por ejemplo-4) ı Definici´n 1.1.3 Una funci´n proposicional (o proposici´n abierta) o o o (A, P (x)), consta de un conjunto A y un juicio declarativo P (x) tal que 1. tiene variable (a saber x) 2

2. no es proposici´n o 3. se convierte en proposici´n cuando la variable es reemplazada por un o elemento del conjunto A Al conjunto de todos los elementos de A que hacen verdadera P(x) se le llama dominio deverdad de la funci´n proposicional. o Es costumbre decir la funci´n proposicional P (x) en lugar de la funci´n o o proposicional (A, P (x)) Ejemplo 1.1.3 Sea (A, P (x)) la funci´n proposicional donde o A = {−2, 0, 4, 5, 7}, P (x) : x + 3 < 4 El dominio de verdad de P (x) viene dado por {−2, 0} ya que 1. P (−2) : −2 + 3 < 4 (verdadero) 2. P (0) : 0 + 3 < 4 (verdadero) 3. P (4) : 4 + 3 < 4 (falso) 4....