funzionebooleanafunzionebooleanafunzione binaria a variabili binarie. È una funzione che è applicata a un insieme di variabili binarie che assumono ciascuna uno di due possibili valori, per esempio [...] 0 o 1. Per esempio, se x e y sono variabili binarie che possono assumere solo i valori 0 e 1, allora la funzione binaria definita da ƒ(x, y) = x ⋅ y è una funzionebooleana i cui valori sono ƒ(0, 0) = 0, ƒ(0, 1) = 0 , ƒ(1, 0) = 0, ƒ(1, 1) = 1. Al ...
Leggi Tutto
funzione logica
funzione logica detta anche funzione di verità oppure → funzionebooleana, associa a uno o più valori di verità in ingresso (vero V e falso F) un solo valore di verità in uscita. Un esempio [...] E.L. Post e va sotto il nome di teorema di completezza funzionale. Da ciò deriva che ogni funzione logica è una funzione calcolabile perché esiste una procedura algoritmica (rappresentata dalla tavola di verità dell’enunciato a essa associata) che ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] intere, la soddisfattibilità di un'espressione booleana, la possibilità di sequenziare un insieme arco (ni, nj), in G₂ esiste un arco (nπ(i), nπ(j)). Il protocollo funziona nel seguente modo:
V sceglie a caso i in {1,2} e una permutazione π;
calcola ...
Leggi Tutto
Calcolatori
GGianfranco Bilardi e Raffaele Tripiccione
Nicola Cabibbo
Mario Rasetti
Hardware, di Gianfranco Bilardi e Raffaele Tripiccione
Calcolatori paralleli, di Nicola Cabibbo
Calcolo quantistico, [...] tra il XIX e il XX secolo, è che una qualsiasi funzionebooleana si può realizzare componendo molte copie di un'unica funzione opportunamente scelta, ad esempio la cosiddetta funzione NAND, la quale elabora due bit per produrne un terzo che vale ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] pensa che non appartenga alla classe P della complessità ordinaria).
Complessità di un circuito
Il calcolo del valore di una funzionebooleana di n variabili dà luogo a un circuito: si tratta semplicemente di un grafo orientato aciclico con 2n nodi ...
Leggi Tutto
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] pensa che non appartenga alla classe P della complessità ordinaria.
Complessità di un circuito
Il calcolo del valore di una funzionebooleana di n variabili dà luogo a un circuito: si tratta semplicemente di un grafo orientato aciclico, con 2n nodi ...
Leggi Tutto
teorema
teorèma [Der. del lat. theorema, dal gr. theórema "ricerca, meditazione"] [FAF] (a) Nelle scienze deduttive (tipic., nella matematica), ogni enunciato che può essere dedotto logicamente dagli [...] ] T. di correttezza e di completezza della logica dei predicati: v. logica: III 485 c. ◆ [ELT] T. fondamentale di una funzionebooleana: v. circuiti logici: I 619 e. ◆ [FAF] T. invertibile e inverso: un t. invertibile e quello tale che, se si scambia ...
Leggi Tutto
percettrone
Mauro Cappelli
Modello base di rete neurale proposto nel 1958 dallo psicologo americano Frank Rosenblatt. Sebbene sia oggi considerato datato, rappresenta tuttavia il modello di partenza [...] come modello elementare di una più vasta rete neurale composta di numerosi neuroni. Le unità elementari di un percettrone possono rappresentare funzionibooleane di base (AND, OR, NOT), mentre una rete con più strati potrebbe rappresentare qualsiasi ...
Leggi Tutto
verita
verità [Der. del lat. veritas -atis, da verus "vero"] Tavola di v.: (a) [FTC] Modello, costituito dall'elenco di tutti i possibili stati di un sistema, per studiare l'affidabilità di esso: v. [...] ai valori di v. delle proposizioni semplici che compaiono nella funzione: v. logica: III 483 d; analogamente per una funzionebooleana: v. circuiti logici: I 619 b. ◆ [FAF] [ALG] Funzione di v.: nella logica proposizionale, v. logica: III 483 e ...
Leggi Tutto
maxtermine
maxtermine prodotto di somme di una tavola di verità relativa a una funzionebooleana. Si considerano le righe corrispondenti al valore della funzione uguale a 0; a ciascuna di esse corrisponde [...] logica di tutte le variabili in ingresso, prese in forma diretta se valgono 0 e in forma negata se valgono 1. Ogni espressione booleana può essere espressa come prodotto dei maxtermini relativi alle configurazioni delle variabili per le quali la ...
Leggi Tutto