Logo
Unionpedia
Comunicazione
Disponibile su Google Play
Nuovo! Scarica Unionpedia sul tuo dispositivo Android™!
Gratuito
l'accesso più veloce di browser!
 

Soddisfacibilità booleana

Indice Soddisfacibilità booleana

La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.

29 relazioni: Algebra di Boole, Algoritmo, BPP (complessità), Classe di complessità, Clausola di Horn, Cricca (teoria dei grafi), Disgiunzione esclusiva, DPLL, Electronic design automation, Espressione booleana, Field Programmable Gate Array, Forma normale congiuntiva, Forma normale disgiuntiva, GRASP, Informatica teorica, L (complessità), Logica proposizionale, Model checking, NP-completo, P (complessità), Quantificatore, Sharp-P, Tautologia, Teorema di Cook-Levin, Teoremi di De Morgan, Teoria della complessità, 1971, 2-satisfiability, 21 problemi NP-completi di Karp.

Algebra di Boole

L'algebra di Boole (anche detta algebra booleana o reticolo booleano), in matematica e logica matematica, è il ramo dell'algebra in cui le variabili possono assumere solamente i valori vero e falso (valori di verità), generalmente denotati rispettivamente come 1 e 0.

Nuovo!!: Soddisfacibilità booleana e Algebra di Boole · Mostra di più »

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.

Nuovo!!: Soddisfacibilità booleana e Algoritmo · Mostra di più »

BPP (complessità)

Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta.

Nuovo!!: Soddisfacibilità booleana e BPP (complessità) · Mostra di più »

Classe di complessità

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.

Nuovo!!: Soddisfacibilità booleana e Classe di complessità · Mostra di più »

Clausola di Horn

In logica, e in particolare nel calcolo proposizionale, una clausola di Horn è una disgiunzione di letterali in cui al massimo uno dei letterali è positivo.

Nuovo!!: Soddisfacibilità booleana e Clausola di Horn · Mostra di più »

Cricca (teoria dei grafi)

In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega.

Nuovo!!: Soddisfacibilità booleana e Cricca (teoria dei grafi) · Mostra di più »

Disgiunzione esclusiva

La disgiunzione esclusiva "o" (simboli usuali:\dot oppure XOR) è un connettivo (o operatore) logico che restituisce in uscita VERO (V) se e solo se gli ingressi sono diversi tra di loro.

Nuovo!!: Soddisfacibilità booleana e Disgiunzione esclusiva · Mostra di più »

DPLL

DPLL (Davis-Putnam-Logemann-Loveland) è un algoritmo completo, basato sul backtracking, utilizzato per decidere la soddisfacibilità booleana di formule di logica proposizionale in forma normale congiuntiva (CNF), i.e. per risolvere il problema CNF-SAT.

Nuovo!!: Soddisfacibilità booleana e DPLL · Mostra di più »

Electronic design automation

Electronic Design Automation (EDA) è la categoria di strumenti per progettare e produrre sistemi elettronici, dai circuiti stampati ai circuiti integrati, a volte chiamata ECAD (electronic computer-aided design).

Nuovo!!: Soddisfacibilità booleana e Electronic design automation · 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!!: Soddisfacibilità booleana e Espressione booleana · Mostra di più »

Field Programmable Gate Array

In elettronica digitale, un dispositivo Field Programmable Gate Array, solitamente abbreviato in FPGA, è un circuito integrato le cui funzionalità sono programmabili via linguaggi di descrizione dell'hardware (VHDL, Verilog, ecc.). Tali dispositivi consentono la realizzazione di funzioni logiche anche molto complesse, e sono caratterizzati da un'elevata scalabilità.

Nuovo!!: Soddisfacibilità booleana e Field Programmable Gate Array · 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!!: Soddisfacibilità booleana e Forma normale congiuntiva · Mostra di più »

Forma normale disgiuntiva

Nella logica booleana, una formula è in forma normale disgiuntiva o disgiunta (FND), indicata anche come DNF (acronimo di Disjunctive Normal Form) se è una disgiunzione di clausole, dove le clausole sono una congiunzione di letterali.

Nuovo!!: Soddisfacibilità booleana e Forma normale disgiuntiva · Mostra di più »

GRASP

GRASP (General Responsibility Assignment Software Patterns) è una collezione di pattern, usata nella progettazione object-oriented, che fornisce delle linee guida per l'assegnazione di responsabilità alle classi e agli oggetti.

Nuovo!!: Soddisfacibilità booleana e GRASP · Mostra di più »

Informatica teorica

L'informatica teorica è una branca dell'informatica che riguarda gli aspetti più astratti e matematici della computazione, come la teoria della computazione, la semantica della programmazione e la teoria della complessità computazionale.

Nuovo!!: Soddisfacibilità booleana e Informatica teorica · Mostra di più »

L (complessità)

Nella teoria della complessità computazionale, L è la classe di complessità che contiene i problemi di decisione che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria.

Nuovo!!: Soddisfacibilità booleana e L (complessità) · 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!!: Soddisfacibilità booleana e Logica proposizionale · Mostra di più »

Model checking

Il model checking è un metodo per verificare algoritmicamente i sistemi formali.

Nuovo!!: Soddisfacibilità booleana e Model checking · 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!!: Soddisfacibilità booleana 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!!: Soddisfacibilità booleana e P (complessità) · Mostra di più »

Quantificatore

Nella logica i quantificatori sono espressioni come "qualcosa" (quantificatore esistenziale) e "ogni cosa" (quantificatore universale) e le loro controparti simboliche.

Nuovo!!: Soddisfacibilità booleana e Quantificatore · Mostra di più »

Sharp-P

Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP.

Nuovo!!: Soddisfacibilità booleana e Sharp-P · Mostra di più »

Tautologia

Una tautologia (dal greco ταυτολογία, composto di ταὐτό lo stesso — τό lo e αὐτό stesso — e λογία per λόγος discorso), in logica, è un'affermazione vera per definizione, quindi fondamentalmente priva di valore informativo.

Nuovo!!: Soddisfacibilità booleana e Tautologia · 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!!: Soddisfacibilità booleana e Teorema di Cook-Levin · Mostra di più »

Teoremi di De Morgan

I teoremi di De Morgan, o leggi di De Morgan sono relativi alla logica booleana e stabiliscono relazioni di equivalenza tra gli operatori di congiunzione logica "and" e "or".

Nuovo!!: Soddisfacibilità booleana e Teoremi di De Morgan · Mostra di più »

Teoria della complessità

La teoria della complessità o teoria dei sistemi complessi o scienza dei sistemi complessi è una branca della scienza moderna che studia i cosiddetti sistemi complessi, venuta affermandosi negli ultimi decenni sotto la spinta dell'informatizzazione (uso di supercomputer) e grazie alla crescente inclinazione, nell'indagine scientifica, a rinunciare alle assunzioni di linearità nei sistemi dinamici per indagarne più a fondo il comportamento.

Nuovo!!: Soddisfacibilità booleana e Teoria della complessità · Mostra di più »

1971

Nessuna descrizione.

Nuovo!!: Soddisfacibilità booleana e 1971 · Mostra di più »

2-satisfiability

2-satisfiability (o 2-SAT) è un problema di soddisfacibilità booleana con clausole composte da coppie di letterali.

Nuovo!!: Soddisfacibilità booleana e 2-satisfiability · Mostra di più »

21 problemi NP-completi di Karp

Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi.

Nuovo!!: Soddisfacibilità booleana e 21 problemi NP-completi di Karp · Mostra di più »

Riorienta qui:

3-SAT, 3SAT, Boolean satisfiability problem, Problema di soddisfacibilità booleana, Soddisfacibilità.

UscenteArrivo
Ehi! Siamo su Facebook ora! »