Diferència entre revisions de la pàgina «Decidibilitat»
De Wikisofia
(Es crea la pàgina amb «{{ConcepteWiki}} Propietat dels sistemes formals que disposen d'un procediment de decisió efectiu, o un algorisme|al...».) |
m (Text de reemplaçament - "reducible" a "reductible") |
||
| Línia 2: | Línia 2: | ||
Propietat dels [[sistema formal|sistemes formals]] que disposen d'un [[procediment de decisió|procediment de decisió]] efectiu, o un [[algorisme|algorisme]], que permet determinar si tota expressió bé formada del sistema és o no és deduïble dins del sistema. Als [[sistema formal|sistemes formals]] que gaudeixen d'aquesta propietat per a totes les seves fórmules o expressions se'ls anomena decidibles. Una expressió bé formada és deduïble si és un [[teorema|teorema]] del sistema. Al seu torn, una fómulaes decidible dins d'un sistema si ella o el seu [[negació|negació]] són teoremes del sistema. | Propietat dels [[sistema formal|sistemes formals]] que disposen d'un [[procediment de decisió|procediment de decisió]] efectiu, o un [[algorisme|algorisme]], que permet determinar si tota expressió bé formada del sistema és o no és deduïble dins del sistema. Als [[sistema formal|sistemes formals]] que gaudeixen d'aquesta propietat per a totes les seves fórmules o expressions se'ls anomena decidibles. Una expressió bé formada és deduïble si és un [[teorema|teorema]] del sistema. Al seu torn, una fómulaes decidible dins d'un sistema si ella o el seu [[negació|negació]] són teoremes del sistema. | ||
| − | Segons el [[teorema de Church|teorema de Church]], la [[lògica|lògica de predicats]] de primer ordre no disposa de tal [[procediment de decisió|procediment de decisió]]. Ho posseeix, en canvi, la [[lògica|lògica d'enunciats]]: les [[Lògica#Taules_de_veritat|taules de veritat]] (i les expressions monádicas de la lògica de predicats, | + | Segons el [[teorema de Church|teorema de Church]], la [[lògica|lògica de predicats]] de primer ordre no disposa de tal [[procediment de decisió|procediment de decisió]]. Ho posseeix, en canvi, la [[lògica|lògica d'enunciats]]: les [[Lògica#Taules_de_veritat|taules de veritat]] (i les expressions monádicas de la lògica de predicats, reductibles a expressions de lògica d'enunciats) |
{{Etiqueta | {{Etiqueta | ||
Revisió del 23:00, 8 març 2015
Propietat dels sistemes formals que disposen d'un procediment de decisió efectiu, o un algorisme, que permet determinar si tota expressió bé formada del sistema és o no és deduïble dins del sistema. Als sistemes formals que gaudeixen d'aquesta propietat per a totes les seves fórmules o expressions se'ls anomena decidibles. Una expressió bé formada és deduïble si és un teorema del sistema. Al seu torn, una fómulaes decidible dins d'un sistema si ella o el seu negació són teoremes del sistema.
Segons el teorema de Church, la lògica de predicats de primer ordre no disposa de tal procediment de decisió. Ho posseeix, en canvi, la lògica d'enunciats: les taules de veritat (i les expressions monádicas de la lògica de predicats, reductibles a expressions de lògica d'enunciats)