l'accesso più veloce di browser!
24 relazioni: Algoritmo, Aritmetica di Peano, Aritmetica di Robinson, Coerenza (logica matematica), Dimostrazione, Formula ben formata, Funzione indicatrice, Funzione ricorsiva, Insieme ricorsivo, Ipotesi del continuo, Linguaggio del primo ordine, Linguaggio formale, Logica matematica, Logica proposizionale, Negazione (matematica), Numero naturale, Rappresentabilità, Tabella della verità, Teorema di Goodstein, Teoremi di incompletezza di Gödel, Teoria assiomatica degli insiemi, Teoria degli insiemi di Zermelo-Fraenkel, Teoria del primo ordine, Teoria della calcolabilità.
Algoritmo
Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.
Nuovo!!: Decidibilità e Algoritmo · Mostra di più »
Aritmetica di Peano
L'aritmetica di Peano, denotata anche con l'acronimo PA (Peano Arithmetic) in logica matematica è una teoria del primo ordine che ha come assiomi propri una versione degli assiomi di Peano espressi nel linguaggio del primo ordine.
Nuovo!!: Decidibilità e Aritmetica di Peano · Mostra di più »
Aritmetica di Robinson
L'aritmetica di Robinson, denotata solitamente con Q in logica matematica, è una teoria del primo ordine, definita per la prima volta da Raphael M. Robinson nel 1950 che ha come assiomi propri una versione ridotta degli assiomi di Peano in cui è assente il principio di induzione e c'è l'aggiunta di un assioma che afferma che ogni numero naturale diverso da zero è successore di qualche altro numero (cosa che nell'aritmetica di Peano è dimostrabile per induzione).
Nuovo!!: Decidibilità e Aritmetica di Robinson · Mostra di più »
Coerenza (logica matematica)
In logica matematica, una teoria formale si dice coerente (o non contraddittoria, talvolta anche consistente, per assonanza con l'inglese consistent) se in essa è impossibile dimostrare una contraddizione.
Nuovo!!: Decidibilità e Coerenza (logica matematica) · Mostra di più »
Dimostrazione
La dimostrazione è una serie di ragionamenti logici che, partendo da una ipotesi, porta necessariamente a una tesi.
Nuovo!!: Decidibilità e Dimostrazione · Mostra di più »
Formula ben formata
Nella logica matematica si chiama formula ben formata o - brevemente - fbf di un sistema formale una stringa di simboli che, intuitivamente, rappresenti un'espressione sintatticamente corretta e che viene definita mediante le regole della grammatica del sistema formale stesso.
Nuovo!!: Decidibilità e Formula ben formata · Mostra di più »
Funzione indicatrice
In matematica, nel campo della teoria degli insiemi, se A è un sottoinsieme dell'insieme X, la funzione indicatrice, o funzione caratteristica di A è quella funzione da X all'insieme \ che sull'elemento x \in X vale 1 se x appartiene ad A, e vale 0 in caso contrario.
Nuovo!!: Decidibilità e Funzione indicatrice · Mostra di più »
Funzione ricorsiva
Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo.
Nuovo!!: Decidibilità e Funzione ricorsiva · Mostra di più »
Insieme ricorsivo
Nella teoria della calcolabilità un insieme ricorsivo è intuitivamente un insieme di numeri naturali, per cui è possibile costruire un algoritmo che in un tempo finito (ma a priori non predeterminato) sia in grado, dato un qualunque numero naturale, di stabilire se esso appartiene o no all'insieme.
Nuovo!!: Decidibilità e Insieme ricorsivo · Mostra di più »
Ipotesi del continuo
In matematica, l'ipotesi del continuo è un'ipotesi avanzata da Georg Cantor che riguarda le dimensioni possibili per gli insiemi infiniti.
Nuovo!!: Decidibilità e Ipotesi del continuo · Mostra di più »
Linguaggio del primo ordine
Nella logica matematica il linguaggio del primo ordine è un linguaggio formale che serve per gestire meccanicamente enunciati e ragionamenti che coinvolgono i connettivi logici, le relazioni e i quantificatori "per ogni..." (∀) ed "esiste..." (∃).
Nuovo!!: Decidibilità e Linguaggio del primo ordine · Mostra di più »
Linguaggio formale
Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.
Nuovo!!: Decidibilità e Linguaggio formale · Mostra di più »
Logica matematica
La logica matematica è il settore della matematica che studia i sistemi formali dal punto di vista del modo di codificare i concetti intuitivi della dimostrazione e di computazione come parte dei fondamenti della matematica.
Nuovo!!: Decidibilità e Logica matematica · Mostra di più »
Logica proposizionale
La logica proposizionale (o enunciativa) è un linguaggio formale con una semplice struttura sintattica, basata fondamentalmente su proposizioni elementari (atomi) e su connettivi logici di tipo vero-funzionale, che restituiscono il valore di verità di una proposizione in base al valore di verità delle proposizioni connesse (solitamente noti come AND, OR, NOT...). La semantica della logica proposizionale definisce il significato dei simboli e di qualsiasi proposizione che rispetti le regole sintattiche del linguaggio, basandosi sui valori di verità associati agli atomi.
Nuovo!!: Decidibilità e Logica proposizionale · Mostra di più »
Negazione (matematica)
In logica e in matematica con negazione si intende un'operazione logica unitaria, che restituisce il valore di verità inverso di una proposizione.
Nuovo!!: Decidibilità e Negazione (matematica) · Mostra di più »
Numero naturale
In matematica i numeri naturali sono quei numeri usati per contare e ordinare.
Nuovo!!: Decidibilità e Numero naturale · Mostra di più »
Rappresentabilità
Nella logica matematica il concetto di rappresentabilità di una funzione o di un predicato è relativo alle teorie formali dell'aritmetica, ovvero alle teorie del primo ordine che hanno come linguaggio il linguaggio dell'aritmetica del primo ordine e che quindi ammettono come modello la struttura dei numeri naturali dotati delle operazioni di addizione e moltiplicazione.
Nuovo!!: Decidibilità e Rappresentabilità · Mostra di più »
Tabella della verità
Le tabelle della verità (o tabelle logiche) sono tabelle usate nella logica per determinare se, attribuiti i valori di verità alle proposizioni che la compongono, una determinata proposizione è vera o falsa.
Nuovo!!: Decidibilità e Tabella della verità · Mostra di più »
Teorema di Goodstein
In matematica, il teorema di Goodstein è un teorema sui numeri naturali, relativamente semplice da enunciare, la cui particolarità consiste nel fatto di essere indecidibile dall'aritmetica di Peano ma dimostrabile nella teoria assiomatica degli insiemi.
Nuovo!!: Decidibilità e Teorema di Goodstein · Mostra di più »
Teoremi di incompletezza di Gödel
In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931.
Nuovo!!: Decidibilità e Teoremi di incompletezza di Gödel · Mostra di più »
Teoria assiomatica degli insiemi
La teoria degli insiemi è una branca della matematica sviluppata principalmente dal matematico tedesco Georg Cantor alla fine del XIX secolo.
Nuovo!!: Decidibilità e Teoria assiomatica degli insiemi · Mostra di più »
Teoria degli insiemi di Zermelo-Fraenkel
In matematica, e in particolare in logica matematica, la teoria degli insiemi di Zermelo-Fraenkel comprende gli assiomi standard della teoria assiomatica degli insiemi su cui, insieme con l'assioma di scelta, si basa tutta la matematica ordinaria secondo formulazioni moderne.
Nuovo!!: Decidibilità e Teoria degli insiemi di Zermelo-Fraenkel · Mostra di più »
Teoria del primo ordine
Nella logica matematica una teoria del primo ordine è un particolare sistema formale, cioè una teoria formale in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico.
Nuovo!!: Decidibilità e Teoria del primo ordine · Mostra di più »
Teoria della calcolabilità
La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico.
Nuovo!!: Decidibilità e Teoria della calcolabilità · Mostra di più »
Riorienta qui:
Enunciato indecidibile, Indecidibile, Problema decidibile, Problema indecidibile.
