Apuntes completos de Lógica y Matemática Computacional

UNIDAD I: Lógica de Proposiciones

Introducción

• Origen etimológico de “lógica”: proviene del griego "logos" (palabra, razón) + sufijo “ica” (relacionado con).
• Objeto de estudio: razonamiento válido a partir de proposiciones con valor de verdad ${0,1}$ (falso/verdadero).

Proposiciones

• Definición general: enunciados que solo admiten un valor de verdad.
  • Ejemplos verdaderos/falsos dados.
• Clasificación:
  • Atómicas (primitivas): no se descomponen. Ej.: “1 es primo”.
  • La Lógica Proposicional no asigna su valor: se presupone.
  • Compuestas: combinación de atómicas mediante conectivos lógicos.

Lenguaje Formal Proposicional (LPC)

• Componentes:
  • Alfabetos $\Sigma$: variables + conectivos ${¬,\wedge,\vee,\rightarrow,\leftrightarrow}$ + paréntesis.
  • Gramática (sintaxis): reglas recursivas de formación de fórmulas bien formadas (fbf).
• Fórmula bien formada (fbf)
  1. Una variable proposicional $p_i$ es fbf.
  2. Si $\theta$ es fbf, entonces $¬\theta$ es fbf.
  3. Si $\theta,\phi$ son fbfs, entonces $(\theta\wedge\phi), (\theta\vee\phi), (\theta\rightarrow\phi), (\theta\leftrightarrow\phi)$ son fbfs.
  4. El cierre por finita aplicación de (1)–(3).
• Lenguaje proposicional $L\equiv Form$: conjunto (infinito numerable) de todas las fbfs posibles sobre un $\Sigma$.

Semántica

• Interpretación $I:Var \to {0,1}$ asigna verdad/falsedad a cada átomo.
• Valuación $v_I:Form\to{0,1}$ definida recursivamente por las tablas de verdad de conectivos.
• Conceptos
  • Modelo: interpretación que hace verdadera a una fórmula $I\vDash \theta$.
  • Tautología: $\forall I,\; I\vDash\theta$. Se denota $\vDash \theta$.
  • Contradicción: $\forall I,\; I\nvDash \theta$.
  • Contingencia: satisfacible y no tautología.
  • Conjunto satisfacible: existe $I$ modelo de todas sus fórmulas.
  • Consecuencia lógica: $S\vDash\phi\iff (\forall I)(I\vDash S \Rightarrow I\vDash \phi).$

Tablas de Verdad de Conectivos

• Negación $¬\theta$: invierte el valor.
• Conjunción $\theta\wedge\phi$: solo verdadera si ambas verdaderas.
• Disyunción incluyente $\theta\vee\phi$: falsa solo si ambas falsas.
• Disyunción excluyente $\theta\,\underline{\vee}\, \phi$ (símbolo $v$): verdadera si valores distintos.
• Implicación $\theta\rightarrow\phi$: falsa únicamente en $T\rightarrow F$.
• Bicondicional $\theta\leftrightarrow\phi$: verdadera cuando valores iguales.

Implicaciones asociadas

• Directa $(\theta\rightarrow\phi)$, recíproca $(\phi\rightarrow\theta)$, contraria $(¬\theta\rightarrow¬\phi)$, contrarrecíproca $(¬\phi\rightarrow¬\theta)$.

Equivalencias lógicas fundamentales

• Identidad, dominación, idempotencia, doble negación, conmutativas, asociativas, distributivas, De Morgan, absorción, negación.
• Relacionadas con $\rightarrow$ y $\leftrightarrow$ (lista completa en texto original).

Conectivos adecuados & Prioridades

• Conjuntos adecuados: ${¬,\wedge,\vee},{¬,\wedge},{¬,\vee},{¬,\rightarrow}$.
• Prioridad: ¬ > \wedge > \vee > \rightarrow > \leftrightarrow.

Circuitos lógicos / Redes de conmutación

• Modelan conectivos con interruptores (series $\wedge$, paralelos $\vee$).
• Objetivo: simplificación de circuitos (minimizar interruptores) usando equivalencias.

Reglas de Inferencia (Razonamientos Válidos)

• Forma general: $(p<em>1\wedge\dots\wedge p</em>n)\rightarrow c$.
• Validez: condicional tautológico.
• Principales reglas (con ejemplos):
  • Modus Ponens $p\wedge(p\rightarrow q)\rightarrow q$.
  • Modus Tollens $(p\rightarrow q)\wedge¬q \rightarrow ¬p$.
  • Silogismo Hipotético $(p\rightarrow q)\wedge(q\rightarrow r)\rightarrow(p\rightarrow r)$.
  • Silogismo Disyuntivo (incluyente & excluyente).
  • Dilema Constructivo $((p\vee q)\wedge(p\rightarrow r)\wedge(q\rightarrow r))\rightarrow r$.
  • Dilema Destructivo $(p\rightarrow q)\wedge(r\rightarrow s)\wedge(¬q\vee¬s)\rightarrow(¬p\vee¬r).$

Teorema de Deducción

• $S\cup{\theta}\vDash\phi \iff S\vDash(\theta\rightarrow\phi).$
• Corolario: ${\theta}\vDash\phi \iff \vDash(\theta\rightarrow\phi).$
• Relación con insatisfacibilidad: $S\vDash\theta\iff S\cup{¬\theta}$ es insatisfacible.

UNIDAD II: Relaciones de Recurrencia

Sucesiones y Sumatorias

• Sucesión: función $a_n$ con dominio $\mathbb N$.
  • Finita vs infinita.
  • Notaciones $S:{a_n:n\in\mathbb N}$.

Relación de Recurrencia (RR)

• Forma general $a<em>n = F(a</em>{n-1},a<em>{n-2},\dots,a</em>{n-k})$.
• Condiciones iniciales: $a<em>0,\dots,a</em>k$.
• Término general: fórmula explícita de $a_n$.

Clasificación

1. Lineal vs no lineal.
2. Coeficientes constantes vs variables.
3. Homogénea $f(n)=0$ vs no homogénea $f(n)\neq0$.
4. Orden (primer, segundo, …).

Transformación de RR no lineal a lineal

• Sustitución $b<em>n=a</em>n^2$, etc.

Solución de RR lineales homogéneas con coef. constantes

• Ecuación característica $r^k+c<em>1r^{k-1}+\dots+c</em>k=0$.
• Casos de raíces reales distintas / repetidas (fórmulas para $a_n$).

UNIDAD III: Estructuras Algebraicas Finitas

Ley de Composición Interna

• Función $*:A\times A\to A$.
• Propiedades: cerradura, asociatividad, conmutatividad, neutro (único), inverso (único si existe), distributividad.

Estructuras

• Semigrupo: $(A,*)$ interna + asociativa.
• Semigrupo conmutativo: además conmutativa.
• Semigrupo con unidad: existe neutro.
• Monoide: semigrupo con unidad.
• Grupo: monoide donde todo elemento es inversible.
  • Abeliano: además conmutativo.
• Subgrupo: subconjunto no vacío cerrando *, conteniendo neutro e inversos.
• Anillo $(A,+,*)$:
  1. $(A,+)$ grupo abeliano.
  2. $(A,*)$ semigrupo.
  3. Distribución doble.
  • Conmutativo, con unidad, anillo de división, cuerpo ($+$ y $*$ grupos abelianos, unidad, todo no nulo invertible).

UNIDAD IV: Álgebra de Boole

Definición Formal

• Séxtupla $\langle S,+,*,',0,1\rangle$ cumpliendo leyes asociativas, conmutativas, distributivas, identidad y complemento.

Aplicaciones

• A conjuntos: $+\to\cup,\;*\to\cap,\;'\to\bar{\ }$.
• A proposiciones: $+\to\vee,\;*\to\wedge,\;'\to¬$.

Propiedades adicionales

• Idempotencia, acotación, absorción, involución, leyes de De Morgan, unicidad del complemento.
• Principio de dualidad (intercambiar $0\leftrightarrow1, +\leftrightarrow*$).

Puertas lógicas básicas

• AND, OR, NOT, NAND, NOR, XOR.

Funciones Booleanas & Formas Canónicas

• Minitérmino: producto de todas las variables (directas o negadas).
• Forma normal disyuntiva: suma de minitérminos.
• Maxitérmino & forma conjuntiva.
• Minimización: álgebra booleana, mapas de Karnaugh.

UNIDAD V: Grafos

Definición general

• Grafo $G=(V,E)$ con vértices y aristas; dirigido (pares ordenados) o no dirigido.
• Grado de vértice $\delta(v)$ (# aristas incidentes).
• Términos: bucle, aristas paralelas, grafo simple, ponderado.

Caminos y circuitos

• Camino x–y: secuencia alterna de vértices y aristas.
• Longitud = nº aristas.
• Circuito: camino cerrado; ciclo si vértices únicos salvo inicio/fin.

Conectividad

• Conexo vs disconexo.
• Multígrafo: aristas múltiples.

Circuitos de Euler

• Circuito euleriano: recorre cada arista una sola vez y retorna.
• Teorema: grafo conexo con todos vértices de grado par ↔ posee circuito de Euler; exactamente 0/2 vértices impares → posee recorrido euleriano.
• Algoritmo de Fleury para construir circuito.

Ciclos Hamiltonianos

• Ciclo que pasa por todos los vértices exactamente una vez.
• No existen condiciones sencillas como Euler.

Caminos de longitud mínima

• Grafos ponderados, algoritmo de Dijkstra (etiquetado mínimo).

Matrices

• Adyacencia $A$: $A{ij}$= nº aristas entre$vi,v_j$(bucles cuentan doble en diagonal).<ul> <li>$A^n$: nº caminos de longitud$n$.</li></ul></li> <li><strong>Incidencia</strong>: filas vértices, columnas aristas, 1 si incidente.</li> </ul> <hr /> <h4 id="unidadvirboles">UNIDAD VI: Árboles</h4> <h5 id="definicin">Definición</h5> <ul> <li>Árbol con raíz$(T,v0)$: único camino simple de$v0$a cualquier vértice.</li> <li>Propiedades: acíclico, único padre excepto raíz, etc.</li> <li>Conceptos: nivel, altura, padre, hijo, ancestro, hoja, rama, subárbol.</li> </ul> <h5 id="tipos">Tipos</h5> <ul> <li><strong>Árbol binario (2-árbol)</strong>; completo si todo nodo interno tiene 2 hijos.</li> <li>Árbol posicional: hijos etiquetados${1..n} o L/R.
• Árbol de búsqueda binaria: subárbol izquierdo < nodo < subárbol derecho.

Recorridos

• Preorden (raíz–izq–der) → forma prefija.
• Entreorden (izq–raíz–der) → notación infija.
• Postorden (izq–der–raíz) → forma sufija (polaca inversa).

Árboles no dirigidos

• Grafo conexo, acíclico, |E|=|V|-1$.</li> <li>Árbol de expansión (spanning tree); mínimo (peso mínimo).</li> <li>Algoritmos: Prim, Kruskal.</li> </ul> <hr /> <h4 id="unidadviilenguajesformalesymquinasdeestadofinito">UNIDAD VII: Lenguajes Formales y Máquinas de Estado Finito</h4> <h5 id="lenguajesformales">Lenguajes Formales</h5> <ul> <li>Alphabet$\Sigma$: conjunto finito de símbolos.</li> <li>Palabras$\Sigma^$; lenguaje$L\subseteq\Sigma^$.</li> </ul> <h5 id="gramticasddgntpsigmadd">Gramáticas$G=(N,T,P,\sigma)$</h5> <ul> <li>Producciones$A\to\alpha$.</li> <li>Jerarquía de Chomsky:<ul> <li>Tipo 0 (sin restricciones)</li> <li>Tipo 1 (sensibles al contexto)</li> <li>Tipo 2 (libres de contexto)</li> <li>Tipo 3 (regulares)</li></ul></li> <li>Forma Backus-Naur (BNF):$::=\alpha|\beta|\dots$.</li> </ul> <h5 id="mquinasdeestadofinitomef">Máquinas de Estado Finito (MEF)</h5> <ul> <li>Sextupla$M=(I,O,S,f,g,\sigma)$.</li> <li>Diagramas de transición (estados = vértices, transiciones etiquetadas i/o).<ul> <li><strong>Mealy</strong>: salida en la transición.</li> <li><strong>Moore</strong>: salida asociada al estado.</li></ul></li> </ul> <h5 id="autmatasfinitosreconocimientodelenguajes">Autómatas Finitos (Reconocimiento de Lenguajes)</h5> <ul> <li>AEFD$M=(S,I,f,s_0,F)$determinista.</li> <li>AEFND: función de transición$f:S\times I\to \mathcal P(S)$$.
• Teorema de equivalencia: todo AEFND tiene AEFD equivalente (construcción de subconjuntos).
• Correspondencia con gramáticas regulares (Tipo 3).