| dbo:abstract
|
- 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 niž 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. (cs)
- En , la decidibilitat és una propietat dels sistemes formals quan, per a qualsevulla fórmula en el llenguatge del sistema, existeix un mètode efectiu per determinar si aquesta fórmula pertany o no al conjunt de les veritats del sistema. Per exemple, la lògica proposicional és decidible, perquè existeix un algoritme (taula de veritat) que en un nombre finit de passos pot decidir si la fórmula és vàlida o no. Quan una fórmula no pot ser provada vertadera ni falsa, es diu que la fórmula és independent, i que per tant el sistema és no decidible. L'única manera d'incorporar una fórmula independent a les veritats del sistema és postulant-la com a axioma. Dos exemples molt importants de fórmules independents són l'axioma de l'elecció en la teoria de conjunts, i el cinquè postulat d'Euclides. (ca)
- In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences 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. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them. (en)
- En metalógica, la decidibilidad es una propiedad de los sistemas formales cuando, para cualquier fórmula en el lenguaje del sistema, existe un para determinar si esa fórmula pertenece o no al conjunto de las verdades del sistema. Por ejemplo, la lógica proposicional es decidible, porque existe un algoritmo (la tabla de verdad) que en un número finito de pasos puede decidir si la fórmula es válida o no. Cuando una fórmula no puede ser probada verdadera ni falsa, se dice que la fórmula es independiente, y que por lo tanto el sistema es no decidible. La única manera de incorporar una fórmula independiente a las verdades del sistema es postulándola como axioma. Dos ejemplos muy importantes de fórmulas independientes son el axioma de elección en la teoría de conjuntos, y el quinto postulado de la geometría euclidiana. (es)
- 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. (fr)
- Il concetto di decidibilità si trova in logica matematica e in teoria della computabilità con accezioni differenti. (it)
- 논리학에서 결정가능성(decidability)은 참/거짓을 묻는 결정 문제가 가질 수 있는 성질의 하나로, 해답을 내어놓는 기계적인 절차가 존재하는 성질을 가리킨다. 대표적으로 정지 문제의 결정불가능성이 알론조 처치와 앨런 튜링에 의해 증명된 바 있다. (ko)
- 決定可能（けっていかのう、英: decidable）は、数理論理学または現代論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、英: decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。そうでなければ、決定不能である。 (ja)
- Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem. Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania sprzeczności. (pl)
- Em lógica, o termo decidível se refere a um problema de decisão, ou seja, a questão da existência de um método efetivo para determinar a pertinência em um conjunto de fórmulas. Sistemas lógicos, tais como a lógica proposicional, são decidíveis se a pertinência em seu conjunto de fórmulas logicamente válido pode ser efetivamente determinado. Uma teoria (conjunto de fórmulas fechada sob a consequência lógica) em um sistema lógico fixo é decidível se existe um algoritmo eficiente para determinar se fórmulas arbitrárias pertencem a ela. Muitos problemas importantes são indecidíveis. (pt)
- Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости. (ru)
- Алгоритмічна розв'язність — властивість формальної теорії володіти алгоритмом, який визначає за даною формулою, виводиться вона з множини аксіом даної теорії чи ні. Теорія називається розв'язною, якщо такий алгоритм існує, і нерозв'язною, в іншому випадку. Питання про виводимість у формальній теорії є частковим, але разом з тим найважливішим випадком більш загальної проблеми розв'язності. (uk)
|
| rdfs:comment
|
- 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 niž 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. (cs)
- In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences 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. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them. (en)
- 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. (fr)
- Il concetto di decidibilità si trova in logica matematica e in teoria della computabilità con accezioni differenti. (it)
- 논리학에서 결정가능성(decidability)은 참/거짓을 묻는 결정 문제가 가질 수 있는 성질의 하나로, 해답을 내어놓는 기계적인 절차가 존재하는 성질을 가리킨다. 대표적으로 정지 문제의 결정불가능성이 알론조 처치와 앨런 튜링에 의해 증명된 바 있다. (ko)
- 決定可能（けっていかのう、英: decidable）は、数理論理学または現代論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、英: decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。そうでなければ、決定不能である。 (ja)
- Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem. Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania sprzeczności. (pl)
- Em lógica, o termo decidível se refere a um problema de decisão, ou seja, a questão da existência de um método efetivo para determinar a pertinência em um conjunto de fórmulas. Sistemas lógicos, tais como a lógica proposicional, são decidíveis se a pertinência em seu conjunto de fórmulas logicamente válido pode ser efetivamente determinado. Uma teoria (conjunto de fórmulas fechada sob a consequência lógica) em um sistema lógico fixo é decidível se existe um algoritmo eficiente para determinar se fórmulas arbitrárias pertencem a ela. Muitos problemas importantes são indecidíveis. (pt)
- Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости. (ru)
- Алгоритмічна розв'язність — властивість формальної теорії володіти алгоритмом, який визначає за даною формулою, виводиться вона з множини аксіом даної теорії чи ні. Теорія називається розв'язною, якщо такий алгоритм існує, і нерозв'язною, в іншому випадку. Питання про виводимість у формальній теорії є частковим, але разом з тим найважливішим випадком більш загальної проблеми розв'язності. (uk)
- En , la decidibilitat és una propietat dels sistemes formals quan, per a qualsevulla fórmula en el llenguatge del sistema, existeix un mètode efectiu per determinar si aquesta fórmula pertany o no al conjunt de les veritats del sistema. Per exemple, la lògica proposicional és decidible, perquè existeix un algoritme (taula de veritat) que en un nombre finit de passos pot decidir si la fórmula és vàlida o no. (ca)
- En metalógica, la decidibilidad es una propiedad de los sistemas formales cuando, para cualquier fórmula en el lenguaje del sistema, existe un para determinar si esa fórmula pertenece o no al conjunto de las verdades del sistema. Por ejemplo, la lógica proposicional es decidible, porque existe un algoritmo (la tabla de verdad) que en un número finito de pasos puede decidir si la fórmula es válida o no. (es)
|
