l'accesso più veloce di browser!
13 relazioni: Clausola (logica), Congiunzione logica, Disgiunzione logica, Espressione booleana, Forma normale congiuntiva, Grafo delle implicazioni, Letterale, NL (complessità), NP-completo, P (complessità), Robert Tarjan, Soddisfacibilità booleana, Teorema di Cook-Levin.
Clausola (logica)
In logica, una clausola è una disgiunzione logica fra letterali.
Nuovo!!: 2-satisfiability e Clausola (logica) · Mostra di più »
Congiunzione logica
In matematica, la congiunzione logica (simbolo \land che si legge e) è un connettivo logico attraverso il quale, a partire da due proposizioni A e B, si forma una nuova proposizione chiamata congiunzione di A e B o congiunzione di A et B, che si indica con A\land B, la quale è vera soltanto nel caso in cui A e B siano entrambe vere, mentre è falsa in tutti gli altri casi possibili.
Nuovo!!: 2-satisfiability e Congiunzione logica · Mostra di più »
Disgiunzione logica
In matematica, la disgiunzione inclusiva o disgiunzione logica (simbolo \vee, che si legge o, talvolta indicato come e/o), è un connettivo logico attraverso il quale, a partire da due proposizioni A e B, si forma una nuova proposizione A\vee B chiamata A o B oppure chiamata A vel B, la quale è vera solo nel caso in cui almeno una delle due proposizioni da cui è formata A e B è vera mentre è falsa quando tutte e due sono false.
Nuovo!!: 2-satisfiability e Disgiunzione logica · Mostra di più »
Espressione booleana
In algebra di Boole, un'espressione booleana è un'espressione che, quando valutata (ovvero, quando viene dato un valore ai letterali di cui è composta), produce un valore booleano (vero o falso).
Nuovo!!: 2-satisfiability e Espressione booleana · Mostra di più »
Forma normale congiuntiva
Nella logica booleana, una formula è in forma normale congiuntiva o congiunta (FNC), indicata anche come CNF (acronimo di Conjunctive Normal Form) se è una congiunzione di clausole, dove le clausole sono una disgiunzione di letterali.
Nuovo!!: 2-satisfiability e Forma normale congiuntiva · Mostra di più »
Grafo delle implicazioni
In logica matematica, un grafo delle implicazioni è un grafo orientato G(V, E) composto da un insieme di vertici V ed un insieme di archi E. Ogni vertice in V rappresenta l'assegnazione booleana di un letterale, ed ogni arco orientato da un vertice u ad un vertice v rappresenta l'implicazione materiale "Se il letterale u è vero allora lo è anche illetterale v".
Nuovo!!: 2-satisfiability e Grafo delle implicazioni · Mostra di più »
Letterale
Nella logica proposizionale, un letterale è una formula atomica o la sua negazione.
Nuovo!!: 2-satisfiability e Letterale · Mostra di più »
NL (complessità)
La classe NL è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con S_M(n).
Nuovo!!: 2-satisfiability e NL (complessità) · Mostra di più »
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.
Nuovo!!: 2-satisfiability e NP-completo · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: 2-satisfiability e P (complessità) · Mostra di più »
Robert Tarjan
Nel 1969 ha conseguito il Bachelor's degree in matematica dal California Institute of Technology e presso la Stanford University ha ottenuto nel 1971 il Master's degree in computer science e nel 1972 il Ph.D. in computer science e secondariamente in matematica, sotto la supervisione di Robert Floyd e Donald Knuth.
Nuovo!!: 2-satisfiability e Robert Tarjan · Mostra di più »
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Nuovo!!: 2-satisfiability e Soddisfacibilità booleana · Mostra di più »
Teorema di Cook-Levin
Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.
Nuovo!!: 2-satisfiability e Teorema di Cook-Levin · Mostra di più »
