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, [...] di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfattibilità di un'espressionebooleana, la possibilità di sequenziare un insieme di lavori su più macchine in modo da rispettare una data scadenza, la ...
Leggi Tutto
Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] polinomiale con una macchina di Turing non deterministica si riducono all'unico problema della soddisfattibilità di espressionibooleane. Negli anni seguenti si riconobbe che numerosissimi problemi ben posti e praticamente rilevanti sono equivalenti ...
Leggi Tutto
and
and uno degli operatori logici fondamentali dell’algebra di → Boole, detto anche prodotto logico e indicato con ×. Corrisponde al connettivo ∧ della congiunzione che, dati due enunciati A e B, ne [...] », 1 come «vero»):
L’operatore and gode della proprietà associativa; per estensione, la sua applicazione a un qualsiasi numero di espressionibooleane dà 1 solo se tutte hanno valore 1, mentre dà 0 se almeno una di esse ha valore 0. Nell’algebra di ...
Leggi Tutto
or
or uno degli operatori logici fondamentali dell’ algebra di → Boole, detto anche somma logica e indicato con +. Corrisponde al connettivo ∨ della → disgiunzione. Tale operatore binario, dati due enunciati [...] la seguente:
L’operatore or gode della proprietà associativa e, per estensione, la sua applicazione a un qualsiasi numero di espressionibooleane dà 1 se e solo se almeno una di esse ha valore 1 (è vera). Esso realizza quindi una funzione logica ...
Leggi Tutto
Premessa. - Gli sviluppi dell'a. nel quindicennio 1960-75 sono stati assai notevoli, sia dal punto di vista quantitativo sia da quello qualitativo. Prima di esaminare alcuni progressi in direzioni particolari, [...] creazione e allo studio di nuove strutture algebriche (a. booleane, reticoli; a. cilindriche, poliadiche, ecc.).
Mutamento della finito e ben determinato) per decidere se due espressioni polinomiali costruite applicando le operazioni F di una ...
Leggi Tutto
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] a⋂1=a, a⋃a′=1, a⋂a′=0.
Un esempio tipico di algebra booleana è l'insieme di tutti i sottoinsiemi di un dato insieme V, dove i (denotazione) in ciascuna di esse. Se X è un'espressione valida in tutti i modelli di un insieme di proposizioni S ...
Leggi Tutto
Imparare a generalizzare
Manfred Opper
(Neural Computing Research Group, Aston University Birmingham, Gran Bretagna)
Questo saggio fornisce un'introduzione alle teorie che mirano alla comprensione della [...] un perceptron che calcola output a valori binari dal segno dell'espressione [1].
Come studente scegliamo una rete con una funzione di P. Carnevali e S. Patarnello nelle cosiddette reti booleane, che possiedono unità elementari di calcolo diverse da ...
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. [...] di Kleene questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε denota la problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:
[2] ∀x∀y ...
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 [...] Kleene, questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε . Un tipico problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:
[2] ∀ x ∀ y(x ...
Leggi Tutto