aausimple.pdf

MATEMATICA FMM004Lgica y Conjuntos

Primer Semestre, 2013

Prof. Gabriel Aguilera C

Universidad Andrs Bello

Prof. Gabriel Aguilera C | MATEMATICA FMM004

2Lgica

La lgica es la base de todo el gran edificio llamado Matemtica. Sin lalgica, no podramos efectuar razonamientos matemticos.

Conceptos primitivosLos conceptos primitivos corresponden a ideas que no precisan definicin.En Lgica, los valores de verdad verdadero (V) y falso (F) son los conceptosprimitivos.

Ahora presentaremos nuestro primer concepto a definir:

DefinicinUna proposicin es una sentencia declarativa (que afirma o niega algo dealgn sujeto) que posee un nico valor de verdad, pudiendo ser verdadera(V) o bien ser falsa (F). Usualmente se denotan por letras minsculasp, q, r, s, etc.


3

EjemplosI Sea p :Hoy es Martes. p es una proposicin, pues podemos darle un

valor de verdad (V F) dependiendo de si hoy es martes o no.I q : Hola no es una proposicin, no podemos darle un valor de verdadI 5 = 5 es una proposicin, cuyo valor de verdad es F.I |0| = 0 es una proposicin V.


4Conectivos lgicos

DefinicinUn conectivo lgico es un operador que nos permite obtener nuevas pro-posiciones a partir de otras dadas. Los conectivos bsicos son:I negacin: (no)I conjuncin: (y)I disyuncin: ()I condicional: (si. . . entonces)I bicondicional: (si y slo si)

DefinicinUna proposicin se dice simple si no incluye conectivos lgicos. En casocontrario, se dice que la proposicin es compuesta.


5Valor de verdad de una proposicin compuesta

El valor de verdad de una proposicin compuesta depende de los valores deverdad de las proposiciones que la componen y de los conectivos empleados.Para analizar el valor de verdad de una proposicin compuesta, usamos lastablas de verdad.La tabla de verdad bsica, para dos proposiciones p y q tiene la forma:

p qV VV FF VF F

A esta tabla se van agregando columnas con las proposiciones compues-tas que queremos analizar. Para esto, necesitamos saber cul es el valorde verdad de una proposicin compuesta con cada uno de los conectoreslgicos.


6Conectivos lgicosNegacin ()

DefinicinDada una proposicin p, se llama negacin de p, y se escribe p, a laproposicin no p. Esto significa que p es V si p es F , y p es F si pes V .

La tabla de verdad para la negacin es:

p pV FF V


7Conectivos lgicosConjuncin ()

DefinicinDadas dos proposiciones p y q, su conjuncin es la proposicin p y q, lacual se escribe p q. La conjuncin es V si ambas proposiciones p, q sonverdaderas, y F si hay al menos una proposicin falsa.

La tabla de verdad para la conjuncin es:

p q p qV V VV F FF V FF F F


8Conectivos lgicosDisyuncin ()

DefinicinDadas dos proposiciones p y q, su disyuncin es la proposicin p q, lacual se escribe pq. La disyuncin es V si al menos una de las proposicionesp, q es verdadera, y F si ambas son falsas.

La tabla de verdad para la disyuncin es:

p q p qV V VV F VF V VF F F


9Conectivos lgicosCondicional ()

DefinicinDadas dos proposiciones p y q, el condicional de ellas es la proposicin sip entonces q, la cual se escribe p q. Aqu, p se llama antecedente y qel consecuente. Tambin, p q se lee p es condicin suficiente para q,o bien q es condicin necesaria para p. As, p q es F slo si p es V yq es F . En los dems casos es V .

La tabla de verdad para el condicional es:

p q p qV V VV F FF V VF F V


10Conectivos lgicosBicondicional ()

DefinicinDadas dos proposiciones p y q, el bicondicional de ellas es la proposicin p si y slo si q, la cual se escribe p q. Tambin se lee p es condicinnecesaria y suficiente para q p q es V cuando las proposiciones tienenel mismo valor de verdad. En los dems casos es F .

La tabla de verdad para el bicondicional es:

p q p qV V VV F FF V FF F V


11Tautologa y Contradiccin

DefinicinUna proposicin compuesta se dice que es una:I tautologa, si ella es siempre V , independiente de los valores de verdad

que tomen las proposiciones que la forman.I contradiccin, si ella es siempre F , independiente de los valores de

verdad que tomen las proposiciones que la forman.I contingencia, si no es ni tautologa ni contradiccin.


12Equivalencia lgica

DefinicinDadas dos proposiciones p y q, se dice que ellas son lgicamente equiva-lentes, si la proposicin p q es una tautologa. En tal caso se escribep q y se lee p es equivalente a q.


13Equivalencias importantesI ( p) p (doble negacin)I p q q p (conmutatividad de )I p q q p (conmutatividad de )I p q q p (conmutatividad de )I p (q r) (p q) r (asociatividad de )I p (q r) (p q) r (asociatividad de )I p (q r) (p q) r (asociatividad de )I p (q r) (p q) (p r)

(distributividad de con respecto a )I p (q r) (p q) (p r)

(distributividad de con respecto a )I (p q) p q (Ley de De Morgan para )I (p q) p q (Ley de De Morgan para )I p q p qI p q (p q) (q p)


14Cuantificadores

DefinicinUna funcin proposicional es una expresin p compuesta de variables, quese transforma en proposicin con valor de verdad cuando dichas variablesasumen ciertos valores.

EjemplosI Sea p : x es un pas de Europa. Esta es una funcin proposicional dex. Si x = Francia, la proposicin p es verdadera, pero si x = Uruguay,la proposicin que se obtiene es falsa.

I Sea q : x+ 6 = 11. Esta es una funcin proposicional de x. Si x = 5,la proposicin q es verdadera, pero si x = 4 , la proposicin que seobtiene es falsa.

DefinicinSe llama conjunto de validez de una funcin proposicional, al conjunto devalores que hacen que dicha proposicin sea verdadera.


15Cuantificadores

DefinicinI Para indicar que una funcin proposicional es verdadera para cualquier

elemento de un determinado conjunto U se usa el simbolo , el cualse llama cuantificador universal. El smbolo se lee: para todo,cualquiera sea, para cada.

I Para indicar que una funcin proposicional es verdadera para algnelemento de un determinado conjunto U se usa el simbolo , el cualse llama cuantificador existencial. El smbolo se lee: existe (un),existe al menos un, existe algn.

I Para indicar que una funcin proposicional es verdadera para un nicoelemento de un determinado conjunto U se usa el simbolo !, el cualse lee: existe un nico.


16CuantificadoresCuantificadores y funciones proposicionales

Sea A un conjunto y sea p una proposicin que depende de la variable x (eneste caso escribimos p(x)). Al usar los cuantificadores, podemos obtenerlas proposiciones siguientes:

I x A, p(x), lo cual se lee Para todo p en x, p(x) es una proposicinverdadera.

I x A, p(x), lo cual se lee Existe un p en x, tal que p(x) es unaproposicin verdadera.

Estas proposiciones pueden negarse segn las siguientes reglas:

I (x A, p(x)) (x A, p(x))I (x A, p(x)) (x A, p(x))


17

Ejemplos1. Sea p(x) : x es un pas de Sudamrica y sea A ={Chile, Uruguay, Bolivia, Paraguay, Brasil}. La proposicin x A, p(x), se leera

Todos los elementos de A son pases de Sudamricalo cual es verdadero.La negacin de p es (x A, p(x)) (x A, p(x)) y se leera

Existe algn elemento de A que no es un pas de Sudamricay es falsa (negacin de algo verdadero).

2. Sea A = R y sea p(x) : x A, 0x

= 0. Esta proposicin es falsa,porque si x = 0 no obtenemos cero al realizar la divisin. Por lo tanto,

su negacin p(x) : x A, 0x6= 0 es verdadera.


18Conjuntos

DefinicinI Llamaremos conjunto a cualquier coleccin bien determinada de ob-

jetos. Se denotan por letras maysculas: A,B,C, . . .. Los objetos losllamaremos elementos del conjunto, se denotan por a, b, c, . . .. Un ob-jeto a de A se dice que pertenece al conjunto y se escribe a A. Encaso contrario se escribe a / A.

I Dos conjuntos importantes son el conjunto vaco, que no contieneelementos y se denota por , y el conjunto universo, que contiene atodos los elementos y se denota por U .

I Los elementos x de un conjunto A se pueden caracterizar por una pro-piedad P (x) y definir el conjunto como A = {x U : P (x)}, llamadadefinicin por comprensin. Tambin se puede enumerar los elementosdel conjunto A = {a, b, c, ...}, llamada definicin por extensin.

I Un conjunto A est bien definido si dado un x U , puede decidirsesi el elemento est o no en A, es decir, puede decidirse si una de lasdos proposiciones: x A x / A es verdadera.


19Conjuntos

EjemplosAqu mostramos para dos casos, cmo definir un conjunto:1. Por extensin, vale decir mostrando los elementos de A.

N := { 1, 2, 3, . . .} ( Nmeros naturales)

2. Por comprensin, esto es dando una propiedad (o proposicin) quecaracterice a los elementos del conjunto.

Q : ={ab: a, b Z, b 6= 0

}( Nmeros racionales).


20Operaciones con conjuntos

Definicin (Subconjuntos)Dados dos conjuntos A y B, se dice que A es subconjunto de B o que Aest incluido o contenido en B, y se escribe A B, si todos los elementosde A estn tambin en B, esto es:

A B (x U : x A x B)

Propiedades de la inclusinDados A, B, C conjuntos, se tiene1. A U2. A A3. (A B B C) A C



Observacin

A 6 B x U : x A x / B

Definicin (Igualdad de conjuntos)Dados dos conjuntos A y B, se dice que A y B son iguales, y se escribeA = B, si los elementos de A y B coinciden, esto es:

A = B (A B) (B A).

Dicho de otro modo:

(x U : x A x B) (x U : x B x A).



Definicin (Diferencia)Sea U el conjunto universo, y sean A, B subconjuntos de U . La diferenciade A y B es el conjunto

AB = {x U : x A x 6 B }

que tambin se escribe A \B, y se representa grficamente como:

A B



Definicin (Complemento)El complemento de A con respecto a U , el cual se denota Ac (o bien A),es el conjunto U A, vale decir:

Ac := U A = {x U : x 6 A }

que se representa grficamente como:

A B



Propiedades de la diferencia y complemento1. x U : x A x Ac.2. c = U U c = .3. A Ac = U .4. (Ac)c = A.5. A Ac = 6. AB = A Bc



Definicin (Interseccin)Sea U el conjunto universo, y sean A, B subconjuntos de U . La interseccinde A y B, la cual se denota A B, es el conjunto de todos los elementoscomunes a A y B, esto es

A B := {x U : x A x B }


A B



Definicin (Unin)Sea U el conjunto universo, y sean A, B subconjuntos de U . La unin deA y B, la cual se denota AB, es el conjunto de todos los elementos queestn en A o en B, esto es

A B := {x U : x A x B }


A B


27

Propiedades de la unin e interseccin1. A A = A , A A = A (idempotencia)2. A B = B A , A B = B A (conmutatividad)3. A (B C) = (A B) C (asociatividad de )4. A (B C) = (A B) C (asociatividad de )5. A (B C) = (A B) (A C) (distributividad)6. A (B C) = (A B) (A C) (distributividad)7. (A B)c = Ac Bc (Ley de De Morgan)8. (A B)c = Ac Bc. (Ley de De Morgan)

DefinicinDos conjuntos A y B se dicen disjuntos si y slo si A B = .Por ejemplo, para A U , A y Ac son disjuntos pues A Ac = .


28Cardinalidad

DefinicinEl nmero de elementos de un conjunto finito A se llama cardinalidad de A y sedenota por Card(A) o por #A.

EjemploSi A = {x N : n es par yn < 10}, entonces su cardinalidad es

#(A) = #({2, 4, 6, 8}) = 4.

Propiedades1. Si A y B son conjuntos disjuntos, entonces #(A B) = #A+#B.2. Si A y B son conjuntos arbitrarios, entonces

#(A B) = #A+#B #(A B).3. Si A, B y C son conjuntos arbitrarios, entonces

#(ABC) = #A+#B+#C#(AB)#(AC)#(BC)+#(ABC)

aausimple.pdf

Documents