In logic, the term decidable refers to the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of formulas closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.

PropertyValue
dbpprop:abstract
  • In logic, the term decidable refers to the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of formulas closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.
  • Rozhodnutelnost je matematický pojem z oblasti matematické logiky. Vyjadřuje, zda existuje konečný algoritmus, který pro každou formuli určí, zda je v dané teorii dokazatelná nebo není. Teorie, pro níž takový algoritmus existuje, se nazývá rozhodnutelná, v opačném případě pak nerozhodnutelná. Problematika rozhodnutelnosti úzce souvisí s Gödelovými větami o neúplnosti.
  • Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema. Por otra parte, una teoría decidible semánticamente, es un sistema axiomático donde existe un método para evidenciar que toda proposicion verdadera en un modelo es decidible o no en el sistema en concreto. Ejemplo: La Lógica proposicional es decidible, porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula que combina M formulas atómicas, hay un número máximo N = 2 de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad. La lógica de primer orden es sintácticamente decidible si se limita a predicados con un solo argumento. Si se incluyen predicados con dos o más argumentos, no es decidible. Toda teoría completa recursivamente enumerable es decidible sintácticamente. Por otro lado, toda teoría que incluya aritmética básica es no decidible sintácticamente.
  • En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L'indécidabilité est la négation de la décidabilité. Dans les deux cas il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique.
  • 決定可能（けっていかのう、英: decidable）は、論理学において、論理式の集合のメンバーシップの決定をする実効的方法が存在することを指す。決定可能性（けっていかのうせい、英: decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。
  • Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić czy dana odpowiedź na pytanie stawiane przez problem jest poprawna. Na przykład pytanie czy w dziedzinie liczb rzeczywistych dwa wyrażenia złożone z liczb, zmiennych i plusów mają równą wartość jest rozstrzygalne: np. <math>x + 2 + 3</math> i <math>5 + x</math> są równoważne, natomiast <math>4 + x</math> i <math>4 + y</math> już nie. Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania paradoksów.
  • В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем, важнейшим случаем более общей проблемы разрешимости.
dbpprop:hasPhotoCollection
rdfs:comment
  • In logic, the term decidable refers to the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of formulas closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.
  • Rozhodnutelnost je matematický pojem z oblasti matematické logiky. Vyjadřuje, zda existuje konečný algoritmus, který pro každou formuli určí, zda je v dané teorii dokazatelná nebo není. Teorie, pro níž takový algoritmus existuje, se nazývá rozhodnutelná, v opačném případě pak nerozhodnutelná. Problematika rozhodnutelnosti úzce souvisí s Gödelovými větami o neúplnosti.
  • Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
  • En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L'indécidabilité est la négation de la décidabilité. Dans les deux cas il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique.
  • Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić czy dana odpowiedź na pytanie stawiane przez problem jest poprawna. Na przykład pytanie czy w dziedzinie liczb rzeczywistych dwa wyrażenia złożone z liczb, zmiennych i plusów mają równą wartość jest rozstrzygalne: np.
  • В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет.
rdfs:label
  • Decidability (logic)
  • Rozhodnutelnost
  • Decidibilidad
  • Décidabilité et indécidabilité
  • 決定可能性
  • Rozstrzygalność
  • Разрешимость
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of