Save
Busy. Please wait.
Log in with Clever
or

show password
Forgot Password?

Don't have an account?  Sign up 
Sign up using Clever
or

Username is available taken
show password


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.
Your email address is only used to allow you to reset your password. See 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.
focusNode
Didn't know it?
click below
 
Knew it?
click below
Don't Know
Remaining cards (0)
Know
0:00
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
Popular Computers sets

 

 



Voices

Use these flashcards to help memorize information. Look at the large card and try to recall what is on the other side. Then click the card to flip it. If you knew the answer, click the green Know box. Otherwise, click the red Don't know box.

When you've placed seven or more cards in the Don't know box, click "retry" to try those cards again.

If you've accidentally put the card in the wrong box, just click on the card to take it out of the box.

You can also use your keyboard to move the cards as follows:

If you are logged in to your account, this website will remember which cards you know and don't know so that they are in the same box the next time you log in.

When you need a break, try one of the other activities listed below the flashcards like Matching, Snowman, or Hungry Bug. Although it may feel like you're playing a game, your brain is still making more connections with the information to help you out.

To see how well you know the information, try the Quiz or Test activity.

Pass complete!
"Know" box contains:
Time elapsed:
Retries:
restart all cards