RESUMEN DE LA UNIDAD I

(LENGUAJES Y AUTÓMATAS)

Proposición o Sentencia

Es una frase de la cual se puede determinar si es verdadera o falsa. Existen dos tipos de proposiciones mas que son:

La proposición simple: es aquel enunciado que esta compuesto de un sujeto, un verbo y un complemento.

La proposición compuesta: es un enunciado que esta formado por dos o más sub - enunciados, para integrarlos o unirlos usando conectivos.

Los conectivos pueden ser conjunción:

Conectivo	Palabra o Leg	Símbolo	Ejemplo
Conjunción	Y	^	Venezuela exporta e importa a México
Disyunción	O	V	Venezuela exporta o importa a México
Condición	Sí entonces	®	Si Venezuela importa entonces México exporta
Bicondición	Sí y solo sí	«	Venezuela exporta si y solo si México compra

Equivalente

Si P y Q son proposiciones, se dice que P es equivalente a Q si para todos los casos tienen el mismo valor de verdad.

Ejemplo: si las frases “3<5” y “Pi es irracional” son equivalentes, como lo son las frases “½ es un entero” y “4<3” puesto que sus valores de verdad son los mismos.

Conjunción

Son dos enunciados cualesquiera unidos por la palabra “Y” se simboliza por P^Q. Esta será verdadera únicamente cuando todas sus proposiciones sean verdaderas. La tabla de verdad es la siguiente:

P	Q	P^Q
F	F	F
F	V	F
V	F	F
V	V	V

Ejemplo con respecto a la tabla anterior

1) París esta en Asia y 2+2=5

2) París esta en Asia y 2+2=4

3) París esta en Europa y 2+2=5

4) París esta en Europa y 2+2=4

Disyunción

Son dos enunciados cualesquiera unidos por la palabra “O” se simboliza por PvQ.

Esta será falsa únicamente cuando todas sus proposiciones sean falsas. La tabla de verdad es la siguiente:

P	Q	PvQ
F	F	F
F	V	V
V	F	V
V	V	V

Ejemplo con respecto a la tabla anterior:

1) El número 3 es negativo o el número 4 es negativo

2) El número 3 es negativo o el número 4 es par

3) El número 3 es positivo o el número 4 es negativo

4) El número 3 es positivo o el número 4 es par

Negación

Es un enunciado no P llamado la negación de P, sus significados son “es falso que”, “no es cierto que”, “no tiene”, “no esta” y se simboliza por ~P, ךP, P’.

La negación es solo lo contrario a lo que se afirme. La tabla de verdad de ~P es la siguiente:

P	~P
F	V
V	F

Ejemplo con respecto a la tabla anterior:

1) El triángulo equilátero tiene 4 lados iguales / El triángulo equilátero tiene 3 lados iguales

2) El triángulo equilátero tiene 3 lados iguales / El triángulo equilátero tiene 4 lados iguales

Condicional

Es aquel enunciado que tiene la forma “si P entonces Q” y se representa por ®

Esta proposición es falsa solo cuando P es verdadera y Q falsa. La tabla de verdad es la siguiente:

P	Q	P® Q
F	F	V
F	V	V
V	F	F
V	V	V

Ejemplo con respecto a la tabla anterior:

1) El sol no brilla y no hace calor

2) El sol no brilla y hace calor

3) El sol brilla y no hace calor

4) El sol brilla y hace calor

En la condicional P se conoce como hipótesis, condición o antecedente y Q se llama conclusión o consecuente.

Bicondicional

Es aquel enunciado que tiene la forma “es P si y solo si Q es” y se representa por «

Esta proposición es verdadera solo cuando ambas proposiciones son iguales. La tabla de verdad es la siguiente:

P	Q	P« Q
F	F	V
F	V	F
V	F	F
V	V	V

Ejemplo con respecto a la tabla anterior:

1) Juan es hermano de José si y solo si José es hijo de los padres de Juan

2) Juan es hermano de José si y solo si José tiene los mismos apellidos de Juan

3) Juan y José son hermanos si y solo si tienen los mismos apellidos

4) Juan y José son hermanos si y solo si son hijos de los mismos padres

Reciproca

De la condicional P®Q es la proposición Q®P

Contrapuesta

De P®Q es (-Q) ® (-P). Tome en cuenta que P®Q y su contraposición son equivalentes puesto que tienen los mismos valores de verdad para todos los casos, como se muestra a continuación.

P	Q	P®Q	~Q	~P	~Q®~P
V	V	V	F	F	V
V	F	F	V	F	F
F	V	V	F	V	V
F	F	V	V	V	V

Tautología

Es cuando una proposición es siempre verdadera. Ejemplo: checa la siguiente tabla

P Q	P®Q	(P®Q)^Q	Resultado
F F	V	F	V
F V	V	V	V
V F	F	F	V
V V	V	V	V

Contradicción

Es cuando una proposición es siempre falsa. La negación de una tautología es también una contradicción.

P Q	P®Q	(P®Q)^Q	Resultado	~	Nuevo Resultado
F F	V	F	V	F	F
F V	V	V	V	F	F
V F	V	F	V	F	F
V V	V	V	V	F	F

Frase abierta o función proporcional

Proposición que contiene una variable. Ejemplo “X son las materias de Ingeniería en sistemas computacionales”

Conjunto de significados de esa variable

Es la colección de objetos que puede ser sustituidos por una variable en una frase abierta.

Conjunto verdad de la Frase abierta

Es el conjunto perteneciente al conjunto se significados para los cuales la frase abierta se convierte en una proposición verdadera al sustituir la variable por ellos.

Ejemplo: si se considera que el conjunto de significados para la frase abierta X²+2X+16=0 es de números reales, el conjunto de verdad es vacío, pero si incluye –1 ± i √15 entonces ya tiene elementos.

Frase universalmente cuantificada

Indica que el conjunto de verdad P(x) esta compuesto por todos los objetos pertenecientes al conjunto de significados de x. Es la frase de la forma “para todo x del conjunto de significados P(x) es verdadera”. Su símbolo es"x P(x)

Ejemplo: si P(x) es la frase abierta “x+1>x” y el conjunto de significados es la colección de todos los números reales, entonces "x P(x) es una proposición verdadera

Frase cuantificada existencialmente

Indica que algún elemento del conjunto de significados es un valor que al sustituirlo hace que P(x) sea verdadera. Es la frase de la forma “existe un x en el conjunto de significados para el cual P(x) es verdadera. Su símbolo es $x P(x).

Contra ejemplo

Para "x P(x) es un elemento t, del conjunto de significados de forma que P(t) sea falsa. Demostrando que “Si para cada x P(x), entonces Q(x)” probando que "x (P (x)® Q(x)) es verdadera.

Ejemplo: si la proposición “n es primo entonces “n-1 es primo” puede ser refutada si el contra ejemplo tal como 11.

Conjuntos

Un Conjunto es cualquier colección de objetos el cual pueden ser tratado como una entidad, y un objeto de la colección se dice que es un elemento o miembro del conjunto.

Dado un objeto x y un conjunto S, si x es un elemento del conjunto S, lo podemos escribir como x Î S; si x no es un elemento del conjunto S, podemos escribirlo como Ø(x Î S) o también x Ï S.

Los términos de conjunto, colección y clase son usados como sinónimos, así como también los términos elemento o miembro.

Ejemplo: un conjunto de números o un conjunto de símbolos.

Existen dos formas de determinar los elementos de un conjunto:

a) Por extensión (o numeración): escribiendo una lista de todos los elementos o su inicial y encerrando la lista entre una llave.

b) Por comprensión o descripción: indicando la propiedad común que caracteriza a todos los elementos de la lista

Ejemplo: Forma por extensión los siguientes conjuntos y encuentre la cardinalidad.

1) A= {Países que limitan con México}

# 3

2) C= {materias de primer semestre de informática}

# 5

Ejemplo: Forma por comprensión los siguientes conjuntos.

1) A= {2,4,6,8,10}

a {números de pares del 2 al 10}

2) C= {tallo, flores, fruto, raíz, hojas}

c {partes de una planta}

Subconjuntos

Es un conjunto de a, cuyos elementos se encuentran en otro conjunto b. El símbolo de subconjuntos se representa por “Ì”

Ejemplo:

A= {1,3,4,5,8,9} B= {1,2,3,5,7} c= {1,5}

A Ë B A Ë C B Ë A B Ë C C Ì A C Ì B

Reglas de Subconjuntos

a) Para todo conjunto, se tiene que el conjunto vacío es subconjunto de A (0ÌA)

b) Para todo conjunto A, se tiene que A esta incluido en sí mismo (AÌA)

c) Si a es subconjunto B y B es subconjunto C, entonces A se subconjunto de C (AÌB, BÌC tal que AÌC)

d) Si A es subconjunto de B y B es subconjunto de A, entonces A es igual a B (AÌB, BÌA tal que A=B)

Elementos

También llamados miembros del conjunto a los objetos que forman al conjunto.

Colección

Es una agrupación que está determinada por una propiedad enunciada por medio de un lenguaje preciso. Todo conjunto es una colección de objetos, pero no toda colección de objetos es un conjunto.

Familia indexada de conjuntos

Son familia de conjuntos consecutivos. Supongamos que L es un conjunto. Si para todo ÎaL tenemos que Aa es un conjunto, entonces {AÎa½aL}

Conjunto Vacío

Es un conjunto que carece de elementos. Se suele llamarle conjunto nulo, y se le denota por el símbolo ø o { }.

Ejemplo:

A = { Los perros que vuelan }	A = { }	A = Ø
B = { x / xes un mes que tiene 53 días}	B = { }	B = Ø
C = { x / x³ = 8 y x es impar }	C = { }	C = Ø
D = { x / xes un día de 90 horas }	D = { }	D = Ø

Conjunto Potencia

La familia de todos los subconjuntos de un conjunto M se llama Conjunto Potencia de M. Se le denota como 2^M.

Ejemplo:

a)	M = { 1, 2 }	El conjunto M tiene 2 elementos
	2^M = { {1}, {2}, {1, 2}, ø}	entonces 2² = 4 elementos

b)	M = { 1, 2, 3 }	El conjunto M tiene 3 elementos
	2^M = { {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, ø}	entonces 2³= 8 elementos

Si un conjunto M es finito con "n" elementos, entonces su conjunto potencia 2^M tendrá 2ⁿ elementos.

Igualdad de Conjuntos

Se dice que 2 conjuntos A y B son iguales cuando ambos tienen los mismos elementos, es decir si cada elemento de A pertenece a B y si cada elemento que pertenece a B pertenece también a A. La igualdad se denota A = B.

En la igualdad, el orden de los elementos de cada conjunto no importa.

Ejemplo:

A = {1, 2, 3, 4}

C = {1, 2, 3, 3, 4, 1}

E = {vocal de la palabra mundo}

B = {3, 4, 1, 2}

D = {1, 2, 2, 3, 4, 4,}

F = {u, o}

A = B

C = D

E = F

OPERACIONES CON CONJUNTOS

Unión de Conjuntos

La unión de los conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A o a B o a ambos. Se denota: A U B. La unión de conjuntos se define como: A U B = {x / x A o x B}

En forma gráfica:


Cuando no tienen	Cuando tienen algunos	Cuando todos los elementos de un
elementos comunes	elementos comunes	conjunto pertenecen a otro conjunto

Ejemplo:

1. Dados los conjuntos: A = { 0, 1, 2, 3, 4, 5 }, B = { 0, 2, 4 } y C = { 5, 6, 8 }, efectuar y construir los diagramas respectivos:

A U C

B U C

A U B

Tenemos:

a) A = { 0, 1, 2, 3, 4, 5 } y C = { 5, 6, 8 }

						A U C = { 0, 1, 2, 3, 4, , 6, 8 }

						Representación gráfica de la unión de conjuntos A y C

b) B = { 0, 2, 4 } y C = { 5, 6, 8 }

						B U C = { 0, 2, 4, 5, 6, 8 }

						Representación gráfica de la unión de conjuntos B y C

c) A = { 0, 1, 2, 3, 4, 5 } y B = { 0, 2, 4 }

				A U B = { , 1, , 3, , 5 }

				Representación gráfica de la unión de conjuntos A y B

Diferencia de Conjuntos

Se denomina diferencia de dos conjuntos A y B al conjunto formado por todos los elementos de A pero que no pertenecen a B.

La diferencia se denota por: A - B que se lee: A diferencia B o A menos B. Se define la diferencia de dos conjuntos también como:

A - B = {x / x A y x B}

Mediante un diagrama de Venn - Euler:


Cuando no tienen	Cuando tienen	Cuando todos los elementos de un
elementos comunes	Elementos comunes	Conjunto pertenecen a otro conjunto

Ejemplo:

1. Dados los conjuntos: A = { a, b, c, d, e }, B = { a, e } y C = { d, f, g }, efectuar y construir los diagramas respectivos:

A - C

B - C

A – B

Tenemos:

a) A = { a, b, c, d, e } y C = { d, f, g }

				A - C = { a, b, c, e }

				Representación gráfica de la diferencia de conjuntos A y C

b) B = { a, e } y C = { d, f, g }

				B - C = { a, e }

				Representación gráfica de la diferencia de conjuntos B y C

c) A = { a, b, c, d, e } y B = { a, e }

				A - B = { b, c, d }

				Representación gráfica de la diferencia de conjuntos A y B

Complemento de un Conjunto

Si un conjunto A es subconjunto de otro conjunto universal U, al conjunto A' formado por todos los elementos de U pero no de A, se llama complemento de A con respecto a U. Simbólicamente se expresa:

A' = { x/x U y x A }

Ejemplo:

a)	Sean U = { m, a, r, t, e }		y		A = { t, e }
	Su complemento de A es:				A' = { m, a, r }

	En forma gráfica:

b)	Sean U = { letras de la palabra aritmética}	y	B = { vocales de la palabra vida }
	Determinado por extensión tenemos
	U = { a, r, i, t, m, e, c }		B = { i, a }
	Su complemento de B es:		B' = { r, t, m, e, c }

	En forma gráfica:

Producto Cartesiano (Conjunto Producto)

Se forma con todos los pares ordenados que es posible obtener con elementos de dos a mas conjuntos, de manera que el primer comprende de dicho par ordenado pertenezca siempre al primer conjunto, y el segundo componente al segundo conjunto

Ejemplo:

A={0,1,2} B={3,4} c={3,4} B⁵= B*B*B*B*B Hallar lo siguiente:

a) A*B b) B*A c) A² d) B² e) A²*B

a) A*B= {(0,3)(0,4)(1,3)(1,4)(2,3)(2,4)}

#6 elementos

b) B*A ={(3,0)(3,1)(3,2)(4,0)(4,1)(4,2)}

#6 elementos

c) A² = A*A {(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)}

#9 elementos

d) B²= B*B {(3,3)(3,4)(4,4)(4,3)}

#4 elementos

e) A²*B= A*A*B= {(0,0,3,)(0,0,4)(0,1,3)(0,1,4)(0,2,3)(0,2,4)(1,0,3)(1,0,4)(1,13) (1,1,4)(2,0,3)(2,1,3)(2,2,3)(2,2,4)(2,3,3)}

#15 elementos

Relaciones

Cuadro que muestra la correspondencia de unos elementos con respecto a otros

Alumno	Materia
Carolina	Español
Rafael	Matemáticas
Samantha	Física

Dominio Contra dominio

R= {carolina, español}, {carolina, matemáticas}, {Rafael, Matemáticas}, {Samantha, física}, {Samantha, Matemáticas}

Relación Binaria

R de un conjunto X a un conjunto Y es un subconjunto del producto cartesiano X xY. Si (x,y) Î R se escribe xRy y se dice que x está relacionado con y. En el caso de X=Y se afirma que R es una relación (binaria) sobre x.

Dígrafo

Se usa para representar una relación sobre un conjunto.

Propiedades de las Relaciones

Reflexiva

Una relación R sobre un conjunto x recibe el nombre reflexiva si (x,x) Î R para todo xÎX.

Simétrica

Se conoce a una relación r sobre un conjunto A si para todo (x,y) Î R se tiene que (y,x) ÎR

Antisimetrica

Se le conoce a una relación R sobre un conjunto A si para todo (x,y) Î R con ¹ y se tiene que (y,x) Ï R.

Transitiva

Se le conoce a una relación R sobre un conjunto X si para todo (x,y), (y,z) Î R se tiene que (x,z) Î R

Relación de orden parcial R

Se le llama a una relación R en un conjunto X cuando esta es reflexiva, antisimétrica y transitiva.

Orden parcial débil

Se le llama a una relación si es reflexiva, antisimétrica y transitiva.

Orden parcial estricto

Se le llama a una relación si no es reflexiva, es antisimétrica y es transitiva.

Relación de equivalencia

Se llama a una relación si es reflexiva, simétrica y transitiva