Definiciones Logica
🇪🇸
In Spanish
In Spanish
Practice Known Questions
Stay up to date with your due questions
Complete 5 questions to enable practice
Exams
Exam: Test your skills
Test your skills in exam mode
Learn New Questions
Manual Mode [BETA]
Select your own question and answer types
Specific modes
Learn with flashcards
Complete the sentence
Listening & SpellingSpelling: Type what you hear
multiple choiceMultiple choice mode
SpeakingAnswer with voice
Speaking & ListeningPractice pronunciation
TypingTyping only mode
Definiciones Logica - Leaderboard
Definiciones Logica - Details
Levels:
Questions:
81 questions
🇪🇸 | 🇪🇸 |
Conjuntos coordinables | A y B conjuntos son COORDINABLES si existe f:A--->B biyectiva |
Sección Inicial | El conjunto In={1, 2, ..., n} |
Conjunto finito | Un conjunto es finito si es coordinable con una sección inicial o es vacío |
Conjunto infinito | Un conjunto es infinito si no es finito, es decir, si no se puede coordinar con ninguna sección inicial |
Cardinal | Es una "clase de equivalencia" de la relación de coordinables (~) |
Conjunto numerable | Un conjunto es numerable si es finito o si es coordinable con N |
#N | Aleph cero |
Alfabeto | Conjunto A no vacío |
Expresión | Una expresión en el alfabeto A es una sucesión finita de elementos de A |
Longitud | La longitud de una expresión es la cantidad de símbolos del alfabeto que posee la expresión |
A^n | El conjunto de todas las expresiones de longitud n |
A* | Todas las expresiones del alfabeto A |
Lenguaje | Un lenguaje en el alfabeto A es un conjunto Σ⊆A* |
Alfabeto de la lógica proposicional | Esta dado por: -los PARENTESIS -las VARIABLES -los CONECTIVOS |
Fórmulas | El conjunto de fórmulas FORM es el conjunto que cumple: -si pi∈Var ---> pi∈Form -si α∈Form ---> ¬α∈Form -si α,β∈Form ---> (α^β), (αvβ), (α->β) ∈Form |
Cadena de formación | Secuencia X1,...,Xn de expresiones proposicionales tal que para cada eslabón Xi: 1) Xi = pk para algun pk∈Var 2) Xi = ¬Xj para algun 1≤j<i 3)Xi = (Xj*Xk) con *∈{^,v,->} para algunos 1≤j,k<i |
Subcadena | Sea C=X1,...,Xn una cadena de formación. Xi1,...Xik es subcadena de C si: -es cadena de formación -Xik = Xn -respeta el orden creciente de C |
Cadena de formación minimal | Tiene una única subcadena que es si misma |
Complejidad | C(α) = #conectivos que aparecen en α |
Complejidad binaria | Cb(α) = #conectivos binarios (^,v,->) que aparecen en α |
Peso | P(α) = #parentesis que abren en α - #parentesis que cierran en α |
Subfórmulas | S(α) es el conjunto definido por: - Var(α)={pk/pk aparece en α} son subfórmulas - si α=¬β ---> s(α)={α} u s(β) - si α=(β1*β2) ---> s(α)={α} u s(β1) u s(β2) |
Valuación | Una valuación es una función v:Form--->{0,1} tal que: - v(¬β) = 1 - v(β) - v((β1^β2)) = min{v(β1); v(β2)} - v((β1vβ2)) = max{v(β1); v(β2)} - v((β1->β2)) = max{1-v(β1); v(β2)} |
Tautología | Α es tautología si v(α) = 1 para toda valuación |
Contradicción | Α es contradicción si v(α) = 0 para toda valuación |
Contingencia | Α es contingencia si NO es tautología ni contradicción |
Equivalentes | Dos formulas α y β se dicen equivalentes si v(α) = v(β) para toda v val α ≡ β |
Función booleana | Una función f:{0,1}^n ---> {0,1} |
Conectivos adecuados | C conjunto de conectivos es adecuado si ∀ α∈Form existe β∈Formc con α ≡ β |
Satisfacible | Un conjunto Γ es SATISFACIBLE si existe v val tal que v satisface a Γ v val SATISFACE a Γ si v(α)=1 ∀α∈Γ v val satisface a α si v(α)=1 |
Insatisfacible | Un conjunto Γ es insatisfacible si no existe ninguna v val tal que v satisfaga a Γ |
Consecuencia | Α es consecuencia de Γ si: ∀v val que satisface a Γ ---> v(α)=1 |
Finitamente satisfacible | Γ es f.s. si para cada conjunto finito Γ'⊆Γ, Γ' es satisfacible |
Axiomas | 1) ( α -> ( β -> α )) 2) (( α -> ( β -> γ )) -> (( α -> β ) -> ( α -> γ ))) 3) (( ¬α -> ¬β ) -> (( ¬α -> β ) -> α )) |
Prueba | Una prueba de α es una sucesión de fórmulas α1,...,αn con: - α = αn - αi tiene dos opciones: 1) es una instancia de axioma 2) existen αj, αk con j,k<i tal que αj = αk->αi. Entonces αi se obtiene por Modus Ponens de αj y αk |
Demostrable | Α es demostrable si existe una prueba de α |
Prueba a partir de Γ (Γ⊢α) | Α se prueba a partir de Γ si existe una prueba α1,...,αn tal que: - α = αn - αi tiene dos opciones: 1) αi es una instancia de axioma 2) αi ∈ Γ 3) αi se obtiene por MP de αj, αk con j,k<i |
Inconsistente | Un conjunto Γ es inconsistente si existe φ tal que Γ⊢φ y Γ⊢¬φ |
Consistente | Un conjunto Γ es consistente si no es inconsistente |
Maximal consistente | Γ es m.c. si: - Γ es consistente - ∀φ∈Form: φ∈Γ ó {φ}uΓ es inconsistente |
Independiente | Γ es independiente si ∀α∈Γ, α∉C(Γ-{α}) |
Dependiente | Γ es dependiente si ∃α∈Γ tal que α∈C(Γ-{α}) |
Base | Γ es base si y solo si: 1) Γ es independiente 2) Si ∃Σ conjunto independiente tal que Σ⊆Γ ---> Σ = Γ |
Valuación modificada | Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es v_xi=a (xj) = |
Alfabeto de la log de 1er orden | -Var -Paréntesis -Conectivos -Cuantificadores -Símbolos de constante -Símbolos de función -Símbolos de predicado |
Términos | El conjunto de términos de L leng de primer orden cumple: -Las var son términos -Los símbolos de cte son términos -Si fk es un símbolo de función y t1,...,tk son términos ---> fk(t1,...,tk) es término |
Fórmulas | El conjunto de fórmulas de L (leng de 1er orden) cumple: - Si Pk es un símbolo de predicado y t1,...,tk son términos ---> Pk(t1,...,tk) es una fórmula - Si α, β son fórmulas ---> (α^β), (αvβ), (α->β), ¬α son fórmulas -Si α es fórmula y xi∈Var ---> ∀xiα, ∃xiα son formulas |
Variable libre | Sea xi una variable que aparece en un término de α. Decimos que xi es libre si no es alcanzada por un cuantificador (∃ o ∀) en NINGUNA aparición |
Variable ligada | Sea xi una variable que aparece en un término de α. Decimos que xi es ligada si es alcanzada por un cuantificador (∃ o ∀) en TODAS sus apariciones |
Término cerrado | No tiene variables |
Sentencia/Enunciado | Fórmula en la cual todas las variables son ligadas |
Interpretación | Una interpretación I de un lenguaje de 1er orden L es: - un conjunto Ui no vacío (universo de la interpretación) - para cada c símbolo de cte, un elemento ci∈Ui - para cada fk símbolo de función, una funció n fik:Uik->Ui - para cada Pk símbolo de predicado, una relación Pik⊆Uik I=<Ui, {ci}, {fik}, {Pik}> |
Valuación en I | Una valuación en una interpretación I de L es una función v:Var->Ui Podemos extenderla de manera única a una funcion v':Term(L)->Ui |
Valuación modificada | Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es |
Valor de verdad | El valor de verdad de una fórmula es una funcion Vi,v : Form(L)->{0,1} tal que: - α=Pk(t1,...,tk): Vi,v(α)=|1 si (v'(t1),...,v'(tk))∈Pik | 0 si no - α=∀xi β : Vi,v(α) = |1 si ∀a∈Ui Vi,v_xi=a (β) = 1 |0 si no - α=∃xi β : Vi,v(α) = |1 si ∃a∈Ui / Vi,v_xi=a (β) = 1 |0 si no - α=(α1^α2): Vi,v(α) = min{Vi,v(α1); Vi,v(α2)} - α=(α1vα2): Vi,v(α) = max{Vi,v(α1); Vi,v(α2)} - α=(α1->α2): Vi,v(α) = max{1-Vi,v(α1); Vi,v(α2)} - α=¬α1: Vi,v(α) = 1-Vi,v(α1) |
Satisfacible | Α es satisfacible si existen I y v tal que I⊧α[v], es decir, tal que Vi,v(α)=1 |
Válida/verdadera | Α es válida o verdadera en I si ∀v valuación en I sucede que I⊧α (Vi(α)=1 para cualquier valuación) |
Universalmente válida | Α es universalmente valida si ∀I interpretacion ⊧α (V(α)=1) |
Consecuencia | Α es consecuencia de Γ si ∀I interpretación y ∀v val con I⊧γ[v] ∀γ∈Γ ---> I⊧α[v] Se escribe Γ⊧α |
Expresable | Un conjunto A es expresable por una fórmula α si α tiene una única variable libre y se cumple: a∈A ⇔ I⊧α[v_x=a] A={a∈U/α(a)} |
Distinguible | Un elemento u∈Ui es distinguible si {u} es expresable |
Modelo | Una interpretación I es un modelo de un conjunto Γ∈Form(L) si I⊧α ∀α∈Γ |
Isomorfismo | Sean I1 e I2 dos interpretaciones con universos Ui1 y Ui2 F:Ui1->Ui2 función de dice isomorfismo si cumple: 1) F es biyectiva 2) F(ci1)=ci2 3) F(fi1k(t1,...,tk))=fi2k(F(t1),...,F(tk)) 4) (t1,...,tk)∈Pi1k ⇔ (F(t1),...,F(tk))∈Pi2k |
Programa | Un programa es una lista de instrucciones I1,...,In |
Macro | Un macro es una pseudoinstrucción que es un reemplazo por un programa en S que ejecuta dicha pseudoinstrucción. Al proceso de cambiar la pseudoinstrucción por las instrucciones del programa se llama "expansión del macro" |
Estado | Un estado de un programa P es una lista de ecuaciones de la forma V=k (V variable que aparece en P) con k∈N |
Descripción instantanea (SNAPSHOT) | Dado P = I1,...,I2 es un par (i, σ) con 1≤i≤n+1 y σ un estado Si i=n+1 la descripción es terminal |
Computo | Un computo es una secuencia de descripciones d1, d2,...,dk donde dk es terminal y dj+1 es sucesor de dj con k>j≥1 |
Descripción inicial | Una descripción es inicial si d=(1, σ) y σ es estado con ecuación de todas las variables auxiliares y de salida V=0 |
Parcial computable | F:Nk -> N función es parcial computable si existe un programa P tal que |
Total computable | F:Nk -> N es total computable si es parcial computable y Dom(f)=Nk |
Recursión primitiva de tipo 1 | Sean h:N->N y g:N2->N. Decimos que h se obtiene de g por RP de tipo 1 o tiene un esquema recursivo de tipo 1 (ERP1) si cumple: -h(0) = k∈N -h(n+1) = g(n, h(n)) |
Recursión primitiva de tipo 2 | Sean g:Nn+2 -> N, f:Nn -> N funciones. Decimos que h:Nn+1 -> N se obtiene de recursión primitiva de tipo 2 de f y g (ERP2) si h cumple: -h(x1,...,xn,0) = f(x1,...,xn) -h(x1,...,xn,t+1) = g(x1,...,xn,t,h(x1,...,xn,t)) |
Funciones iniciales | Cero:N->N / cero(n)=0 suc:N->N / suc(n)=n+1 πin:Nn->N / πin(x1,...,xn)=xi (función proyección) |
Función recursiva primitiva | Una función es recursiva primitiva si se obtiene por finitos pasos de las funciones iniciales a partir de composición, ERP1 y ERP2 |
Predicado recursivo primitivo | Un predicado RP k-ario es una relación P⊆/Nk Le podemos asignar su función característica Cp(x1,...,xn) = |1 si (x1,...,xn)∈P |0 si no |
Codificación de pares (<,>) | La codificación de pares es la función <,>:NxN->N / <x,y> = 2^x (2+1) - 1 |
Numeración de Godel | Sea k∈/N |
Función |.| | Dado x = [a1,...,ak] |.|:N->N / ||x|=long[a1,...,ak]=k ||0| = 0 ||1| = 1 |
Función .[.] | .[.]:N->N / x[i] = v_pi(x) |