Diferència entre revisions de la pàgina «Indecibilitat»
De Wikisofia
m (bot: -per poder +per a poder) |
|||
| Línia 1: | Línia 1: | ||
{{ConcepteWiki}} | {{ConcepteWiki}} | ||
| − | Un [[sistema formal|sistema formal]] és indecidible si no disposa d'un [[algorisme|algorisme]] o [[procediment de decisió|procediment de decisió]] per determinar, en un nombre finit de passos, si un enunciat o fórmula d'aquest sistema és un [[teorema|teorema]] seu. La [[lògica|lògica d'enunciats]] és decidible, atès que disposa d'un medi mecànic, les [[lògica|taules de veritat]], per poder determinar, per a qualsevol fórmula donada, si és o no una [[veritat lògica|veritat lògica]], una [[contradicció|contradicció]] o una [[contingència|contingència]]. La [[lògica|lògica de predicats]] de primer ordre, en canvi, no ho és, segons el [[teorema de Church|teorema de Church]] (1936). | + | Un [[sistema formal|sistema formal]] és indecidible si no disposa d'un [[algorisme|algorisme]] o [[procediment de decisió|procediment de decisió]] per determinar, en un nombre finit de passos, si un enunciat o fórmula d'aquest sistema és un [[teorema|teorema]] seu. La [[lògica|lògica d'enunciats]] és decidible, atès que disposa d'un medi mecànic, les [[lògica|taules de veritat]], per a poder determinar, per a qualsevol fórmula donada, si és o no una [[veritat lògica|veritat lògica]], una [[contradicció|contradicció]] o una [[contingència|contingència]]. La [[lògica|lògica de predicats]] de primer ordre, en canvi, no ho és, segons el [[teorema de Church|teorema de Church]] (1936). |
{{Etiqueta | {{Etiqueta | ||
Revisió del 23:37, 31 ago 2017
Un sistema formal és indecidible si no disposa d'un algorisme o procediment de decisió per determinar, en un nombre finit de passos, si un enunciat o fórmula d'aquest sistema és un teorema seu. La lògica d'enunciats és decidible, atès que disposa d'un medi mecànic, les taules de veritat, per a poder determinar, per a qualsevol fórmula donada, si és o no una veritat lògica, una contradicció o una contingència. La lògica de predicats de primer ordre, en canvi, no ho és, segons el teorema de Church (1936).