決定可能性
(決定可能 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/12/11 08:41 UTC 版)
決定可能（けっていかのう、英: decidable）は、数理論理学または現代論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、英: decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。そうでなければ、決定不能である。
- ^ Enderton, Herbert (2001年), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
- ^ a b Monk, J. Donald (1976年), Mathematical Logic, Berlin, New York: Springer-Verlag
- ^ Cantone, D., E. G. Omodeo and A. Policriti, "Set Theory for Computing. From Decision Procedures to Logic Programming with Sets," Monographs in Computer Science, Springer, 2001.
[続きの解説]
「決定可能性」の続きの解説一覧
- 1 決定可能性とは
- 2 決定可能性の概要
- 3 決定不能な理論の例
- 4 関連項目
- 決定可能のページへのリンク
