10/03
67

¿qué es la lógica?

• la capacidad de determinar razonamientos correctos
• estudio del razonamiento formal
• una secuencia de sentencias verificables
• razonamiento
• deducir conclusiones a partir de premisas
  todas son correctas!

Deducción -> Aristóteles

discurso en el cual, habiendo hecho algunos supuestos, algo diferente se obtiene en consecuencia de la validez de los supuestos.

• Bool y demorgan definen algebra para la logica(aristotelica)

• leigniz presenta la idea de demostraciones constructivas

• frege dice que toda la matematica es logica

• russel rompe la logica y la matematica

• russel publica principia mathematica

• zermelo y fraenkel publica los axiomas ZF ©

• godel demuestra el teorema de incompletitud

• entscheidungs probem. dado un programa, ¿Podemos saber si termina?
  |-> Alan Turing : No.

12/03
conjunto: coleccion bieen definida de objetos(elementos)
|-> determinar sin ambiguedades si el elemento pertenece al conjunto.

por extension: doy 1 por 1 los elementos del conjunto
por comprension: doy reglas que cumplen los elementos del conjunto.

cardinal : sea A un conjunto, la cantidad de elementos del conjunto A se denomina cardinal de A -> |A| o # A
subconjuntos: sean A y B conjuntos
B es subconjunto de A si $\forall x \in B, x \in A \to B$

26/03/26

$\text{Sea } A \setminus |A| = n, \text{la cantidad de subconjuntos e} A \text{de tamaño }k(k\leq n):$

$$\frac{n!}{k!(n-k)!}$$

El conjunto de todos los elementos es el ocnjunto Universal ($\mho$)

conjuntos disjuntos: conjuntos con interseccion vacia: $A \cap B =\emptyset$

Propiedades de Conjuntos

Sean $A, B, C$ subconjuntos del conjunto universal $\mho$.

Leyes de De Morgan

$$\overline{A \cup B} = \overline{A} \cap \overline{B}$$

$$\overline{A \cap B} = \overline{A} \cup \overline{B}$$

Ley de Doble Complemento

$$\overline{\overline{A}} = A$$

Leyes de Idempotencia

$$A \cup A = A$$

$$A \cap A = A$$

Leyes de Identidad

$$A \cup \emptyset = A$$

$$A \cap \mho = A$$

$$A \cup \mho = \mho$$

$$A \cap \emptyset = \emptyset$$

Leyes de Absorción

$$A \cup (A \cap B) = A$$

$$A \cap (A \cup B) = A$$

Leyes Conmutativas

$$A \cup B = B \cup A$$

$$A \cap B = B \cap A$$

Leyes Asociativas

$$(A \cup B) \cup C = A \cup (B \cup C)$$

$$(A \cap B) \cap C = A \cap (B \cap C)$$

Leyes Distributivas

$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$

Ejemplo: Simplificación paso a paso

Simplificar: $\overline{\overline{((A\cup B)\cap C)} \cup \overline{B}}$

Paso 1: Aplicar De Morgan al complemento exterior

$$\overline{\overline{((A\cup B)\cap C)} \cup \overline{B}} = \overline{\overline{((A\cup B)\cap C)}} \cap \overline{\overline{B}}$$

Paso 2: Aplicar doble complemento

$$= ((A\cup B)\cap C) \cap B$$

Paso 3: Aplicar asociatividad

$$= (A\cup B) \cap (C \cap B)$$

Paso 4: Aplicar conmutatividad

$$= (A\cup B) \cap (B \cap C)$$

Paso 5: Aplicar asociatividad nuevamente

$$= ((A\cup B) \cap B) \cap C$$

Paso 6: Aplicar absorción: $(A\cup B) \cap B = B$

$$= B \cap C$$

Resultado final:

$$\boxed{B \cap C}$$

plancha 1 resolucion

14-04

Producto Cartesiano

Sean $A$ y $B$ conjuntos, definimos el producto cartesiano como:

$$A \times B = \{ (a,b) \mid a \in A \land b \in B \}$$

Si $x \in A \times B$, entonces $x$ es un par ordenado.
El cardinal del producto cartesiano es el producto de los cardinales:

$$|A \times B| = |A| \cdot |B|$$

Generalización:
Sean $A_0, \dots, A_n \subseteq \mho$.

$$A_0 \times \dots \times A_n = \{ (a_0, \dots, a_n) \mid a_i \in A_i, \text{ para } 0 \leq i \leq n \}$$

Relaciones

Sean $A, B \subseteq \mho$. Una relación $R$ es un subconjunto del producto cartesiano $A \times B$:

$$R \subseteq A \times B$$

Ejemplo 1

Sean los conjuntos:

$$A = \{ 1, 7, 9 \}$$

$$B = \{ 2, 42 \}$$

Posibles relaciones de $A$ en $B$:

• $R_1 = \emptyset$
• $R_2 = \{ (7,42), (9,42), (1,42) \}$
• $R_3 = \{ (9,2) \}$
• $R_4 = A \times B$

Nota: Todos los $R_i$ mencionados son relaciones de $A \times B$ (ya que son subconjuntos válidos del producto cartesiano).

Ejemplo 2: “y divide a x”

Sean:

$$A = \{ 2, 6, 9 \}$$

$$B = \{ 2, 3 \}$$

Definimos la relación $R \subseteq A \times B$ como:

$$R = \{ (x,y) \mid y \text{ divide a } x \}$$

Calculamos los pares ordenados donde $y$ divide a $x$:

• Para $y=2$: divide a $2$ y a $6$ → $(2,2), (6,2)$
• Para $y=3$: divide a $6$ y a $9$ → $(6,3), (9,3)$

Por lo tanto:

$$R = \{ (2,2), (6,2), (6,3), (9,3) \}$$

Ejemplo 3: Relaciones de orden y suma

Sean:

$$A = \{ 1, 2, 3, 4, 5 \}$$

$$B = \{ 2, 4, 6, 8 \}$$

Relación $R_1$: $x \leq y$

$$R_1 = \{ (x,y) \mid x \leq y \}$$

Por lo tanto:

$$R_1 = \{ (1,2), (1,4), (1,6), (1,8), (2,2), (2,4), (2,6), (2,8), (3,4), (3,6), (3,8), (4,4), (4,6), (4,8), (5,6), (5,8) \}$$

Relación $R_2$: $x + y = 6$

$$R_2 = \{ (x,y) \mid x + y = 6 \}$$

Buscamos pares donde la suma sea 6:

Por lo tanto:

$$R_2 = \{ (2,4), (4,2) \}$$

Relación Binaria

Sea $A$ un conjunto. Una relación binaria sobre $A$ es una relación de $A$ en $A$:

$$R \subseteq A \times A$$

Representación como Grafo Dirigido

Toda relación binaria se puede representar como un grafo dirigido:

1. Cada elemento de $A$ es un vértice
2. Por cada par $(a,b) \in R$, dibujamos una flecha (arco dirigido) que parte de $a$ y llega a $b$

Ejemplo: Relación de orden $\leq$

Sea:

$$X = \{ 1, 2, 3, 4 \}$$

Definimos la relación $R \subseteq X \times X$ como:

$$R = \{ (a,b) \mid a \leq b \}$$

Calculemos los pares ordenados:

• Para $a=1$: $b \in \{1,2,3,4\}$ → $(1,1), (1,2), (1,3), (1,4)$
• Para $a=2$: $b \in \{2,3,4\}$ → $(2,2), (2,3), (2,4)$
• Para $a=3$: $b \in \{3,4\}$ → $(3,3), (3,4)$
• Para $a=4$: $b \in \{4\}$ → $(4,4)$

Por lo tanto:

$$R = \{ (1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4) \}$$

Representación como grafo:

1 ----> 2 ----> 3 ----> 4
↓       ↓       ↓       ↓
1       2       3       4  (bucles)

Donde:

• Hay un bucle en cada vértice (reflexividad: $(1,1), (2,2), (3,3), (4,4)$)
• Hay flechas de menor a mayor (antisimetría y transitividad)

Propiedades de las Relaciones

Sea $R \subseteq A \times A$ una relación binaria sobre $A$.

1. Reflexividad — “Todo elemento se relaciona consigo mismo”

$R$ es reflexiva si todo elemento está relacionado consigo mismo:

$$\forall x \in A : (x,x) \in R$$

Ejemplo: La relación $\leq$ es reflexiva porque $x \leq x$ para todo $x$.

2. Simetría — “Si xRy entonces yRx”

$R$ es simétrica si cuando $x$ está relacionado con $y$, entonces $y$ está relacionado con $x$:

$$\forall x,y \in A : (x,y) \in R \implies (y,x) \in R$$

Ejemplo: La relación “es paralelo a” en rectas es simétrica.

3. Antisimetría — “Solo hay ida y vuelta si x=y”

$R$ es antisimétrica si el único caso en que $(x,y)$ y $(y,x)$ están en $R$ es cuando $x = y$:

$$\forall x,y \in A : \big( (x,y) \in R \land (y,x) \in R \big) \implies x = y$$

Equivalentemente:

$$\forall x,y \in A : \big( (x,y) \in R \land x \neq y \big) \implies (y,x) \notin R$$

Ejemplo: La relación $\leq$ es antisimétrica: si $x \leq y$ e $y \leq x$, entonces $x = y$.

4. Transitividad — “Si xRy y yRz entonces xRz”

$R$ es transitiva si cuando $x$ está relacionado con $y$, y $y$ con $z$, entonces $x$ está relacionado con $z$:

$$\forall x,y,z \in A : \big( (x,y) \in R \land (y,z) \in R \big) \implies (x,z) \in R$$

Ejemplo: La relación “es ancestro de” es transitiva.

Tipos de Relaciones

16-04

solucion ej 3 p2

sea $A \neq \emptyset,$ y $R=A\times\emptyset$ ¿cuanto vale |R|?
$R=\{ (x,y)\mid x \in A,y \in \emptyset \}$ Sea |A| = n, n>0 Pues $A\neq \emptyset$
Si $(x,y) \in R, x \in A, y \in \emptyset$. Pero $\forall \times,x \in \emptyset$
luego, $A\times\emptyset$ no tiene elementos

si una relacion es reflexiva, antisimetrica y transitiva se le llama orden parcial
para que sea total, todo elemento se relaciona con al menos un y
“el mas grande es el ultimo que puedo llegar, el maschico es el que arranco”

23-04

Sean X,Y conjuntos. Sea $R\subseteq x \times Y$
Decimos que R es una funcion de X en Y si:

$$\text{"Para cada } x \in X \text{ existe un unico elemento } y \in Y \text{ tal que } xRy\text{"}$$

$R: x\to y$. por la propiedad, podemos escribir $R(x)=y$

Ejemplo: ¿Función o no función?

Sean:

$$X = \{ 1, 2, 3 \}$$

$$Y = \{ a, b, c \}$$

Ejemplo 1: SÍ es función ✅

$$R_1 = \{ (1,a), (2,b), (3,c) \}$$

¿Es función? Sí, porque:

• Cada $x \in X$ aparece exactamente una vez como primer elemento
• $R_1(1) = a$, $R_1(2) = b$, $R_1(3) = c$
• Todo elemento de X tiene una única imagen en Y

Ejemplo 2: SÍ es función (mismo destino permitido) ✅

$$R_2 = \{ (1,a), (2,a), (3,a) \}$$

¿Es función? Sí, porque:

• Cada $x \in X$ tiene exactamente un $y \in Y$ asociado
• Varios elementos pueden ir al mismo destino (constante)
• $R_2(1) = R_2(2) = R_2(3) = a$

Ejemplo 3: NO es función (uno va a dos lugares) ❌

$$R_3 = \{ (1,a), (1,b), (2,c), (3,c) \}$$

¿Es función? No, porque:

• El elemento $1 \in X$ está relacionado con dos elementos: $a$ y $b$
• No hay un único $R_3(1)$ —¿sería $a$ o sería $b$?

Ejemplo 4: Función PARCIAL (no total) ⚠️

$$R_4 = \{ (1,a), (2,b) \}$$

¿Es función? Es función parcial, pero no es función total:

• Está definida solo para $1$ y $2$, no para $3$
• Para que sea función total, debe estar definida para todo $x \in X$

Diferencia clave:

• Función parcial: definida en un subconjunto del dominio
• Función total: definida en TODO el dominio $X$

En la mayoría de los cursos, cuando decimos “función” sin calificar, nos referimos a funciones totales.

Sea F: x->y

• x es el dominio de F
• y es el codominio de F
• $\{ y \mid (x,y) \in F \}$ es el rango o imagen de F

Propiedades de F

• Inyectiva: Cada elemento de y aparece como maximo 1 vez como imagen de algun elemento x.
• Sobreyectiva: Ran(F) = y (todos los elementos del codominio son imagen de alguno)
• Biyectiva: es sobreyectiva e inyectiva (hay “emparejamiento perfecto” entre dominio y codominio)

Ejemplo: Funciones con conjuntos numéricos

Sean:

$$A = \{ 2, 4, 6, 8 \}$$

$$B = \{ 1, 3, 5, 7 \}$$

Ejemplo 5: Función INYECTIVA

$$f_1 = \{ (2,1), (4,3), (6,5), (8,7) \}$$

Propiedades:

• ✅ Función total: todo elemento de A tiene imagen única
• ✅ INYECTIVA: cada $y \in B$ aparece como imagen de a lo sumo un $x \in A$
  • $f_1(2)=1$, $f_1(4)=3$, $f_1(6)=5$, $f_1(8)=7$
  • Ningún elemento de B tiene dos preimágenes
• ❌ No es sobreyectiva: $Ran(f_1) = \{1,3,5,7\} = B$, ¡sí es sobreyectiva!
• ✅ Es biyectiva (inyectiva + sobreyectiva = biyectiva)

Ejemplo 6: Función SOBREYECTIVA

$$f_2 = \{ (2,1), (4,1), (6,3), (8,5) \}$$

Propiedades:

• ✅ Función total
• ❌ NO inyectiva: $f_2(2) = f_2(4) = 1$ (dos elementos van al mismo lugar)
• ❌ NO sobreyectiva: $Ran(f_2) = \{1,3,5\} \neq B$ (el 7 no es imagen de nadie)
• Por tanto, no es biyectiva

Ejemplo 7: Función SOBREYECTIVA pero no inyectiva

$$f_3 = \{ (2,1), (4,3), (6,5), (8,7) \}$$

Esta es la misma que $f_1$ — biyectiva.

Probemos una diferente:

$$f_4 = \{ (2,3), (4,3), (6,5), (8,5) \}$$

• ✅ Función total
• ❌ NO inyectiva: tanto 2 como 4 van a 3; tanto 6 como 8 van a 5
• ❌ NO sobreyectiva: $Ran(f_4) = \{3,5\} \neq B$

Ejemplo 8: Función que NO es función (no total)

$$f_5 = \{ (2,1), (4,3) \}$$

• ❌ NO es función total: 6 y 8 no tienen imagen
• ✅ Es función parcial: está bien definida para el subconjunto $\{2,4\} \subseteq A$

Si R es biyectiva, puedo definir $R^{-1} = \{ (y,x) \mid (x,y) \in R \}$

notaciones pre prueba
$A\Delta B=A \cup B -(A\cap B)$

Navegación

Resoluciones de Prácticas

• Plancha1Resolucion - Conjuntos
• Plancha2Resolucion - Relaciones
• Plancha3Resolucion - Funciones

Teoría y Referencias

• propiedades de conjuntos - Propiedades algebraicas
• ResumenConceptosClave - Guía de conceptos importantes
• demostracion_potencia_induccion - Demostración |P(A)| = 2^|A|
• resumenLogica - Apuntes generales

Ejercicios y Enunciados

• Plancha1Conjuntos
• Plancha2Logica