click below
click below
Normal Size Small Size show me how
Logica
Resumen de teoría de lógica
Question | Answer |
---|---|
Proposición | Frase declarativa de la que tiene sentido preguntarse si es cierta o no |
(Proposiciones): Átomo | Proposición que no se puede descomponer en más proposiciones más simples |
Lenguaje proposicional | Sea σ(sigma), un conjunto finito de átomos, definimos el lenguaje de las σ-fórmulas como el conjunto de elementos generados por las reglas: 1- un átomo es una fórmula; 2- si φ es fórmula, ¬φ también lo es; 3- φ,Ψ fórmulas, ∨∧→⇔ también |
σ-interpretación(proposiciones) | Asignación de valores de verdad a elementos de σ |
Una fórmula es tautología, satisfactible, contradicción | cierta en todas interpretaciones; cierta en alguna interpretación; falsa en todas interp. |
(Proposiciones): Dos fórmulas φ,Ψ son lógicamente equivalentes | Si ∀I, I(φ)=V <=> I(Ψ) = V |
(Proposiciones): Literal | Un átomo o la negación de un átomo |
(Proposiciones): Cláusula | Disyunción de literales, podria estar vacía |
(Proposiciones): φ es consecuencia lógica de φ1,φ2...,φn | Si (φ1^...^φn)->φ es tautología |
Objetivo de la Demostración automática | Encontrar métodos para validar razonamiento con PC |
Resolvente de 2 cláusulas | Para 2 cláusulas φ1,φ2, hay un literal Ψ1 en φ1, que es complementario de un literal Ψ2 en φ2. Se borra Ψ1 Ψ2 de φ1 φ2 y se construye la resolvente. |
Ʃ* | Lenguaje de todas las palabras |
Teorema de resolución | Sea φ1,...,φn, φ fórmulas, Ψ1^...^Ψn FNC de φ1^...^φn^¬φ , entonces: {φ1,...φn}|=φ <=> {Ψ1...Ψn}|- ℿ El que φ sea consecuencia lógica de {φ1,...φn}, es equivalente a que la cláusula vacía es teorema(es deducible) a partir de {Ψ1...Ψn} |
F.N.C | Una formula esta en FNC si es una conjuncion de disyunciones de literales: (L11 ∨ L12 ∨ ... ∨ L1k1) ∧ (L21 ∨ ... ∨ L2k2) ∧ ... ∧ (Ln1 ∨ ... ∨ Lnkn) |
a|=b | b es consecuencia lógica de a |
a |- b | b es teorema a partir de a |
(logica Predicados): Aridad | Número de argumentos que tiene un predicado |
(logica Predicados): σ vocabulario | Conjunto finito de símbolos de constante, función, predicado. |
(logica Predicados): σ término | Expresión generada por: (1) toda variable es un término; (2) todo símbolo cte de σ es un término; (3) si f^n € σ y t1,...tn son términos, f(t1,...,tn) es término |
(logica Predicados): Lenguaje de σ fórmulas(L(σ)) | Conjunto de elementos generados por: 1-Si φ^n € σ y t1..tn términos, φt1...tn es fórmula 2- φ fórmula, ¬φ también 3- φ v Ψ ∧ → ⇔ 4- φ fórmula, x variable, Ǝxφ, ∀xφ son fórmulas |
(logica Predicados): Subformulas de la fórmula φ | Son fórmulas que aparecen en el árbol genealógico de φ |
(logica Predicados):Radio de acción de un cuantificador | Es la fórmula a la que precede |
(logica Predicados):Variable libre | Si x no está en radio de acción de ningún cuantificador. Si lo está, es ligada |
(logica Predicados): Fórmula cerrada | Fórmula sin variables libres |
(logica Predicados): Función de n argumentos sobre un conjunto no vacío D | Es una función cuyo dominio es D^n y rango D |
Predicado de n argumentos sobre un conjunto no vacío D | Es un subconjunto de D^n |
(logica Predicados): σ interpretación | Es una estructura que consta de : un conjunto no vacío D - dominio de la interpretación, una aplicación I de dominio σ |
Prolog: id | Una tira de carácteres formada por letras aA, dígitos y carácteres de subrayado de manera que el carácter no es un dígito. |
Prolog: variable | id que empieza por "_" |
Prolog: átomo | es un id que empieza por minúscula o una tira de carácteres encerrada entre comillas simples |
Prolog: cte | es un átomo, o un entero, o un decimal |
Prolog: Fórmula | es o bien una fórmula atómica de lenguaje de predicados o bien una fórmula de la forma( φ1^...^φn)->φ donde φ1..φn,φ son formulas de un lenguaje de predicados |
Prolog: Programa | secuencia finita de fórmulas de prólog |
Prolog: Objetivo | fórmula φ1...φn donde φ1...φn son fórmulas atómicas |
Lenguaje regular(L) | Lenguaje reconocido por autómatas sin pila. Existe un AD M tal que el lenguaje de M es el lenguaje regular. |
Lenguaje regular: Alfabeto Ʃ | Conjunto finito de símbolos |
Lenguaje regular: Palabra sobre Ʃ | Secuencia finita de símbolos de Ʃ |
Lenguaje regular: Longitud de una palabra x | Es el número de símbolos que la componen con repetición |
Lenguaje | Conjunto de palabras sobre un alfabeto |
Lenguajes regulares: Autómata determinista | Es una estructura M=(K,Ʃ, δ, q0, F) donde K es un conjunto finito de estados; Ʃ es un alfabeto; δ es la función de KxƩ en K; q0 es el estado inicial; F:conjunto de estados aceptadores |
Lenguajes regulares: Símbolo actual | Símbolo accesible a través del cabezal en un instante dado. |
Lenguajes regulares: Relación de cómputo de un paso | Sea M un AD: a) una configuración de M es una palabra Px€KƩ* b) Si px, qy son configuraciones de M , decimos que px produce qy en un paso de cómputo, en símbolos px |- qy, si podemos pasar de px a qy aplicando una vez[o número finito vez] la función δ |
px |- p' [*, M] | Si desde p con x llegas a un estado p' |
Lenguajes regulares: Reconocido | a)Sea x Є Ʃ* . Decimos que x es reconocido(ó aceptado) por M, si Ǝq Є F tq podemos llegar de q0 a q con x; b) L(M) = { x Є Ʃ* : x es reconocida por M} |
Lenguajes regulares: Reconocedor | Un programa que recibe como entrada un string y determina si satisface una condición |
Lenguajes regulares: Minimización AD | Dos autómatas M1,M2 son equivalentes si lo son sus lenguajes L(M1)<=>L(M2) |
Lenguajes regulares: Estado inaccesible | Un estado q€K es inaccesible si no hay ninguna palabra x € Ʃ* tq se pueda llegar desde q0 a q con x. Ese estado se puede eliminar |
Lenguajes regulares: Estados p y q equivalentes | Si para toda palabra x € Ʃ*, si desde p con x se llega a p' y desde q con x se llega a q', entonces o bien p',q' son estados finales o bien no lo son [[[[o que siempre llegas a una aceptador desde los dos o nunca llegas a un aceptador desde los dos]]] |
Autómata indeterminista | Es una estructura M=(K,Ʃ,Δ , q0, F) donde Δ es un subconjunto de Kx(Ʃ U {λ})x K ---Posee almenos un estado q€K tq para un símbolo a del alfabeto, existe más de una transición posible. |
Lamda cierre (q) | Conjunto de todos los estados a lo que se puede llegar desde q con la palabra vacía |
Lenguaje incontextual L(G) | Existe G(gramática incontextual) tal que L(G) = L. "L es un lenguaje de alguna gramática incontextual" |
L(G) | Lenguaje de la gramática. Toda gramática tiene un lenguaje |
Configuración de M(con pila) | Es una palabra de la forma α Px € Γ*KƩ*. Alfa indica el contenido de la pila. P el estado en el que estas. X lo que queda en la cinta. |
Lenguaje de un autómata L(M) | L(M) = {x € Ʃ*, x es reconocido por M} |
Autómata con pila | Estructura M=(K,Ʃ,Γ ,Δ , q0, F) donde Γ es el alfabeto de la pila. Δ un conjunto finito de elementos de la forma ((p,x,α),(q,β)) donde p,q son estados. x una palabra de alfabeto. α,β € Γ* |
Gramática ambigua | Si hay una palabra en su lenguaje que tiene dos árboles de derivación distintos |
Analizador léxico | Agrupa los símbolos que va leyendo del archivo de entrada en categorías sintácticas y pasa esa información al analizador sintáctico. |
Para que una palabra sea reconocida por AP | Debe haber un cómputo que cumpla 3 condiciones: 1- cómputo acaba en un estado aceptador, 2- se lea toda la palabra de entrada, 3- pila queda vacía al final de ese cómputo. |
Gramática Incontextual (Gi) | Es una estructura G=(V,Ʃ,P,S) donde V es el alfabeto con símbolos siendo variables. Ʃ el alfabeto disjunto de V con símbolos siendo terminales. P es un conjunto finito de Vx(VUƩ)* con elementos siendo reglas y S es la variable inicial. |
Lógica predicados: fórmulas átomicas: | símbolos de predicado seguido de tantos términos como su aridad |