Resumen de teoría de lógica
Quiz yourself by thinking what should be in
each of the black spaces below before clicking
on it to display the answer.
Help!
|
|
||||
|---|---|---|---|---|---|
| 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
🗑
|
Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
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
Normal Size Small Size show me how
Created by:
vit0
Popular Computers sets