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
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
spazio Sostantivo polisenso che designa in generale un’estensione compresa tra due o più punti di riferimento. Può essere variamente interpretato a seconda che lo si consideri dal punto di vista filosofico, [...] σ-algebra di sottoinsiemi, cioè un’algebra booleana di sottoinsiemi chiusa non solo per le ; si verifica che le forme lineari definite in V, e a valori in K, cioè le funzioni f:V→K tali che f(k1v1+k2v2)=k1f(v1) + k2f(v2), formano a loro volta ...
Leggi Tutto
Nel linguaggio scientifico, in presenza di fenomeni casuali (o aleatori), p. di un evento è il numero, compreso fra 0 e 1, che esprime il grado di possibilità che l’evento si verifichi, intendendo che [...] assiomi di normalizzazione e finita additività siano soddisfatti. Se la famiglia ℬ di tutti gli eventi è una σ-algebra booleana e la funzione P soddisfa il postulato di numerabile additività, la terna (S, ℬ, P) è detta uno spazio di probabilità. Per ...
Leggi Tutto
In elettronica, dispositivi che attuano operazioni di algebra logica binaria.
Operazioni logiche binarie
Per la schematizzazione di circuiti l. elettronici, detti circuiti di commutazione, e per la determinazione [...] proposte da G. Boole (algebra booleana; ➔ Boole, George), non solo 0; x ∙ 1 = x; x ∙ x = x; x ∙ x̄ = 0.
Una funzione logica di n variabili indipendenti può essere definita mediante una relazione analitica nella quale alle n variabili sono applicate ...
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⋃a′=1, a⋂a′=0.
Un esempio tipico di algebra booleana è l'insieme di tutti i sottoinsiemi di un dato insieme V, gt;ε, se 0>∣h∣>δ. Sia ora f(x) una qualsiasi funzione reale di una variabile reale e, per ogni x=ξ all'interno del suo intervallo ...
Leggi Tutto
LOGICA E INFORMATICA
Carlo Cellucci
I. McCarthy (1963) afferma che è ragionevole sperare che le relazioni tra l'i. e la l. matematica nel prossimo secolo saranno altrettanto fruttuose di quelle tra [...] M. Per es. λx·x(xy) rappresenta l'operazione di applicare una funzione due volte a un particolare argomento y, sicché per tutti i termini N l scoprire nuovi teoremi in vari campi, dall'algebra booleana ternaria alla teoria dei nodi) nonché di varie ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1941-1950
1941-1950
1941
Le successioni esatte. Introdotte in una nota sui gruppi di coomologia (priva di dimostrazioni) dal polacco Witold Hurewicz ed estensivamente [...] basilari del cervello umano alla logica simbolica booleana. Il modello suggerisce che tali meccanismi fisiologici più semplice, afferma che il numero dei primi p≤x è asintotico alla funzione x/log x. Il norvegese Atle Selberg e l'ungherese Pál Erdős, ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] le assegnazioni di valori di verità alle variabili della formula booleana) è esponenziale, mentre la verifica del fatto che la versione quantistica del bit. Lo stato di un qubit è espresso dalla funzione ∣ψ>=α∣0>+β∣1> in cui le ampiezze α ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] . Nel caso di insiemi, basterà considerare n=1 e per funzioni prendere il grafo come relazione n+1-aria. Diremo poi che Zarinski, in cui i sottoinsiemi definibili di DMn sono combinazioni booleane di elementi di una topologia su DM che simula quelle ...
Leggi Tutto