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".

Usa IA

Indice

1. 11 relazioni: Algebra di Boole, Clausola (logica), Complessità temporale, Componente fortemente connessa, Digrafo (matematica), Espressione booleana, Forma normale congiuntiva, Letterale, Logica matematica, Robert Tarjan, 2-satisfiability.

2. Algebra di Boole
3. Digrafi
4. Famiglie di grafi

Algebra di Boole

Lalgebra di Boole (anche detta algebra booleana, logica 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.

Vedere Grafo delle implicazioni e Algebra di Boole

Clausola (logica)

In logica, una clausola è una disgiunzione logica fra letterali. In genere una clausola è scritta come segue: dove i simboli l_i sono letterali.

Vedere Grafo delle implicazioni e Clausola (logica)

Complessità temporale

In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.

Vedere Grafo delle implicazioni e Complessità temporale

Componente fortemente connessa

Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso appartenenti.

Vedere Grafo delle implicazioni e Componente fortemente connessa

Digrafo (matematica)

In matematica, e in particolare in matematica discreta, per digrafo si intende la struttura relazionale di base, costituita da un insieme finito detto insieme dei nodi e da collegamenti orientati tra tali nodi.

Vedere Grafo delle implicazioni e Digrafo (matematica)

Espressione booleana

In informatica, 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).

Vedere Grafo delle implicazioni e Espressione booleana

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.

Vedere Grafo delle implicazioni e Forma normale congiuntiva

Letterale

Nella logica proposizionale, un letterale è una formula atomica o la sua negazione. Un letterale può essere di due tipi: positivo o negativo.

Vedere Grafo delle implicazioni e Letterale

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.

Vedere Grafo delle implicazioni e Logica matematica

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.

Vedere Grafo delle implicazioni e Robert Tarjan

2-satisfiability

In informatica, 2-satisfiability, 2-SAT o semplicemente 2SAT è un problema di soddisfacibilità booleana con clausole composte da coppie di letterali.

Vedere Grafo delle implicazioni e 2-satisfiability

Vedi anche

Algebra di Boole

• Algebra di Boole
• Algebra di Robbins
• Algebra di insiemi
• Algoritmo di Davis-Putnam
• Anello booleano
• Base di connettivi
• Booleano (informatica)
• Espressione booleana
• Forma canonica (algebra di Boole)
• Funzione booleana
• George Boole
• Grafo delle implicazioni
• Implicante
• Leggi di De Morgan
• Logica proposizionale
• Mappa di Karnaugh
• Matrice binaria
• Metodo di Petrick
• Metodo di Quine-McCluskey
• Operazione bit a bit
• Porta OR
• Ridondanza logica
• Sigma-algebra
• Soddisfacibilità booleana
• Tabella della verità
• Teorema del consenso
• Teorema di Shannon (elettronica)
• Unione (insiemistica)

Digrafi

• Componente fortemente connessa
• Digrafo (matematica)
• Digrafo aciclico
• Grafo delle attese
• Grafo delle implicazioni
• Grafo di de Bruijn
• Grafo trasposto
• Quiver
• St-connectivity

Famiglie di grafi

• Densità di un grafo
• Grafo bipartito
• Grafo cordale
• Grafo cubico
• Grafo delle implicazioni
• Grafo di Cayley
• Grafo planare
• Grafo regolare
• Rete a invarianza di scala
• Snark (teoria dei grafi)

Unionpedia è una mappa concettuale o rete semantica organizzata come un'enciclopedia o un dizionario. Esso fornisce una breve definizione di ogni concetto e le sue relazioni.

Si tratta di una mappa mentale in linea gigante che serve come base per gli schemi concettuali, immagini o sintesi sinaptica. E 'gratuito - liberi, liberi di usare e ogni elemento o documento può essere scaricato. E 'uno strumento, risorsa o di riferimento per lo studio, la ricerca, l'istruzione, la formazione o istruzione che gli insegnanti possono utilizzare, insegnanti, professori, educatori, alunni e studenti; o la scuola per il mondo accademico, a scuola, primaria, secondaria, di mezzo, università, laurea tecnica, college, università, laurea, master o dottorati; per documenti, relazioni, documenti, progetti, idee, documentazione, riassunti, sondaggi o tesi. Ecco la definizione, spiegazione, descrizione, o il significato di ogni significativo su cui avete bisogno di informazioni, e una lista o un elenco di concetti correlati come appare un glossario. Disponibile in italiano, inglese, spagnolo, portoghese, giapponese, cinese, francese, tedesco, polacco, olandese, russo, arabo, hindi, svedese, ucraino, ungherese, catalano, ceco, ebraico, danese, finlandese, indonesiano, norvegese, rumeno, turco, vietnamita, coreano, tailandese, greco, bulgaro, croato, slovacca, lituano, filippina, lettone, estone e sloveno. Altre lingue presto.

Le informazioni si basano su articoli di Wikipedia e altri progetti Wikimedia, e sono disponibili sotto la Licenza Creative Commons Attribuzione-Condividi allo stesso modo.

Unionpedia non è supportata o affiliata alla Wikimedia Foundation.

Google Play, Android e il logo di Google Play sono marchi di Google Inc.

Politica sulla riservatezza