Diferència entre revisions de la pàgina «Indecibilitat»
De Wikisofia
m (bot: -per poder +per a poder) |
m (bot: - per determinar, + per a determinar,) |
||
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 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). | + | Un [[sistema formal|sistema formal]] és indecidible si no disposa d'un [[algorisme|algorisme]] o [[procediment de decisió|procediment de decisió]] per a 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ó de 10:13, 13 oct 2017
Un sistema formal és indecidible si no disposa d'un algorisme o procediment de decisió per a 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).