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 [...] IP è quello del non-isomorfismo dei grafi. Il verificatore sceglie a caso un indice i∈{1,2} e una permutazione π, e invia al dimostratore il grafo H=π(Gi). Il verificatore trova j∈{1,2} tale che Gj e H sono isomorfi e accetta se i=j. Joseph Shamir ...
Leggi Tutto
sintassi
sintassi [Der. del gr. sy´ntaxis "organizzazione", comp. di sy´n "insieme" e táxis "sistemazione"] [ALG] [FAF] Nella logica matematica, lo studio delle proprietà e delle relazioni formali di [...] e come si deve operare sui simb. e sulle formule stesse (calcolo logico); in partic., rientrano nella s. i concetti di dimostrazione e di teorema, in quanto le regole per essi prescindono da casi o signif. specifici. ◆ [ELT] [INF] Nella tecnica dei ...
Leggi Tutto
teorema In matematica e nelle scienze deduttive, ogni enunciato (o formula o proprietà) che può essere dimostrato, cioè che può essere dedotto logicamente dagli enunciati primitivi, detti assiomi o postulati. [...] t. si distinguono in genere l’ipotesi (proprietà che si suppongono valide fin dall’inizio) e la tesi (proprietà che s’intende dimostrare); si parla poi di t. invertibile, se, scambiando nell’enunciato l’ipotesi con la tesi, si ottiene un nuovo t. (t ...
Leggi Tutto
sofisma Termine greco che inizialmente significò ogni manifestazione concreta della σοϕία, cioè della sapienza dell’uomo; più tardi venne usato per designare, in generale, ogni argomentazione speciosa, [...] a una revisione dei procedimenti e delle ipotesi, e quindi a un reale progresso di conoscenza.
Un esempio di s. matematico è la dimostrazione che tutti i numeri sono uguali: dati due numeri qualunque a, b, si ponga a+b=2c (c è la media aritmetica di ...
Leggi Tutto
realtà Qualità e condizione di ciò che esiste effettivamente e concretamente.
Filosofia
La nozione di r. è legata al problema tipicamente moderno dell'esistenza del mondo esterno. A partire da R. Descartes [...] reale? Più in generale, chi ci garantisce che la realtà esterna esista? Descartes risolse il problema ricorrendo alla dimostrazione dell'esistenza di Dio, che faceva da 'garante' sulla verità delle nostre rappresentazioni. G. Berkeley, invece, si ...
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, [...] che ogni strada abbia un vigile ad almeno una delle due estremità. Sfruttando le tecniche di riduzione viste precedentemente si può dimostrare che questo problema è risolubile in modo ottimo in tempo polinomiale se e solo se risulta P=NP. Ebbene, è ...
Leggi Tutto
Identificazione
Red.
Lucio Pinkus
Il termine identificazione indica sia l'attività diretta a stabilire l'identità di una persona sia il processo psicologico per cui un individuo si sente o si considera [...] , e danno luogo a modificazioni dell'Io.
L'identificazione in ambito giudiziario
Il riconoscimento e la dimostrazione dei dati costitutivi di un determinato individuo, considerati nel loro complesso o singolarmente, hanno grande importanza ...
Leggi Tutto
Affermazione, proposizione, tesi, opinione che, per il suo contenuto o per la forma in cui è espressa, appare contraria all’opinione comune o alla verosimiglianza e riesce perciò sorprendente o incredibile. [...]
P. del liberale paretiano Teorema presentato dall’economista indiano A.K. Sen (1970) con il quale si vuole dimostrare come, nell’ambito della teoria delle scelte collettive, sia impossibile trovare regole capaci di soddisfare simultaneamente sia il ...
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, [...] in gioco sono il numero N di cui si deve stabilire la natura e un secondo numero R indipendente da N ed estratto a caso. Come dimostrato da Gary L. Miller e Michael O. Rabin, si ha:
esiste un predicato Z(N,R), con 2〈R〈N, tale che se N è primo ...
Leggi Tutto
bufala mediatica
bùfala mediàtica locuz. sost. f. – Notizia falsa che viene ripresa e amplificata dai media. Il saper riconoscere una notizia non rispondente al vero è una delle basi del giornalismo, [...] . Essa può anche mettere in luce le debolezze e la scarsa affidabilità del sistema dei media, nonché le imprevedibili conseguenze, dato che la successiva dimostrazione della non veridicità di una notizia non necessariamente ne arresta la diffusione. ...
Leggi Tutto
dimostrazione
dimostrazióne s. f. [dal lat. demonstratio -onis]. – 1. a. Ogni atto, fatto, comportamento, parola o discorso che mostra o dimostra o rivela qualche c0sa, che cioè rende o con cui si rende manifesto, conosciuto, chiaro o certo...