Busy. Please wait.
or

show password
Forgot Password?

Don't have an account?  Sign up 
or

Username is available taken
show password

why


Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account.
We do not share your email address with others. It is only used to allow you to reset your password. For details read our Privacy Policy and Terms of Service.


Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.

Remove ads
Don't know
Know
remaining cards
Save
0:01
To flip the current card, click it or press the Spacebar key.  To move the current card to one of the three colored boxes, click on the box.  You may also press the UP ARROW key to move the card to the "Know" box, the DOWN ARROW key to move the card to the "Don't know" box, or the RIGHT ARROW key to move the card to the Remaining box.  You may also click on the card displayed in any of the three boxes to bring that card back to the center.

Pass complete!

"Know" box contains:
Time elapsed:
Retries:
restart all cards




share
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

  Normal Size     Small Size show me how

Logica

Resumen de teoría de lógica

QuestionAnswer
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
Created by: vit0