Tutti i termini usati dalla calcolatrice, dalle guide e dagli esercizi, definiti in un unico posto.
Cerca un termine, guarda la sua notazione e apri l'esempio nella calcolatrice per vederlo all'opera. I termini definiti qui vengono evidenziati la prima volta che compaiono in una guida.
Tutti i 62 termini
Lo studio di quali conclusioni seguono davvero da quali assunzioni.
La logica studia la forma del ragionamento, non il suo contenuto. La logica formale sostituisce le frasi con simboli, così che se una conclusione segue si decide dalla sola forma dell'argomento e si verifica meccanicamente.
Un enunciato che è vero oppure falso, ma non entrambi.
Una proposizione è un enunciato dichiarativo con esattamente un valore di verità. «Sta piovendo» è una proposizione; una domanda o un comando no, perché in essi non c'è nulla che possa essere vero o falso.
Uno dei due valori che una proposizione può assumere: vero o falso.
La logica classica assegna a ogni proposizione esattamente uno di due valori di verità, scritti ⊤ e ⊥ (oppure 1 e 0). Ogni riga di una tavola di verità è un'assegnazione di valori alle variabili, con il risultato che la formula assume lì.
Una proposizione che non contiene alcun connettivo.
Una proposizione atomica non si scompone in proposizioni più piccole: non contiene negazione, congiunzione né altri connettivi. Tutto il resto è composto, costruito a partire dagli atomi, e il suo valore di verità dipende dal loro.
Una lettera come p o A che sta per una proposizione qualsiasi.
Una variabile proposizionale è un segnaposto per qualunque proposizione. La calcolatrice accetta le lettere singole come variabili e dà a ciascuna una colonna della tavola di verità, con una riga per ogni combinazione di valori possibili.
Nella calcolatricep → qUna stringa di simboli che la grammatica del linguaggio permette davvero.
Una formula ben formata si costruisce secondo le regole: una variabile lo è, e lo è anche ogni formula ottenuta da formule più piccole tramite un connettivo. «p ∧ ∨ q» non lo è, ed è per questo che la calcolatrice segnala un errore invece di indovinare.
Un'assegnazione di valori di verità a tutte le variabili di una formula.
Un'interpretazione dice quanto vale ogni variabile e fissa così il valore dell'intera formula. Una formula con n variabili ha 2ⁿ interpretazioni, che sono esattamente le righe della sua tavola di verità.
Un insieme di premesse offerte a sostegno di una conclusione.
Un argomento sostiene che la sua conclusione segue dalle premesse. Scrivilo nella calcolatrice con un tornello — premesse prima, conclusione dopo — e ogni riga verrà controllata alla ricerca di un caso in cui le premesse valgono e la conclusione fallisce.
Nella calcolatricep → q, p ⊨ qUn enunciato che un argomento assume per arrivare alla conclusione.
Le premesse sono il punto di partenza di un argomento. La validità chiede solo se la conclusione vale ovunque valgano tutte le premesse; se queste siano di fatto vere è un'altra questione, quella che aggiunge la fondatezza.
Nella calcolatricep → q, p ⊨ qL'enunciato che un argomento cerca di stabilire.
La conclusione è ciò che le premesse dovrebbero sostenere. Nella calcolatrice è l'espressione dopo il tornello, e un argomento è valido quando nessuna interpretazione rende vere le premesse e falsa la conclusione.
Nella calcolatricep → q, p ⊨ qUn simbolo che costruisce una proposizione composta da altre più semplici.
Un connettivo come ¬, ∧, ∨, → o ↔ combina proposizioni in una più grande il cui valore di verità dipende solo dai loro. È questa dipendenza che una tavola di verità registra, una riga per ogni combinazione di ingressi.
Inverte un valore di verità: ¬p è vera esattamente quando p è falsa.
La negazione è l'unico connettivo unario della logica proposizionale. Scritta ¬p, ~p o !p, trasforma il vero in falso e il falso in vero, così negare due volte restituisce la proposizione di partenza.
Nella calcolatrice¬pVera solo quando entrambe le parti sono vere: p ∧ q.
Una congiunzione afferma entrambe le sue parti, dette congiunti. È vera in esattamente una riga della sua tavola di verità — quella in cui entrambi i congiunti sono veri — il che la rende il più rigido dei connettivi binari.
Nella calcolatricep ∧ qVera quando almeno una parte è vera: p ∨ q.
In logica la disgiunzione è inclusiva: p ∨ q è vera quando è vera p, quando è vera q e quando lo sono entrambe. La lettura esclusiva di «o», vera solo se le parti differiscono, è un connettivo distinto.
Nella calcolatricep ∨ qVera quando esattamente una delle due proposizioni è vera.
La disgiunzione esclusiva, scritta ⊕ o XOR, vale quando le sue parti differiscono e fallisce quando coincidono. È la negazione del bicondizionale e si può scrivere come (p ∨ q) ∧ ¬(p ∧ q).
Nella calcolatrice(p ∨ q) ∧ ¬(p ∧ q)p → q, falso solo quando p è vera e q è falsa.
Il condizionale materiale non dice altro che «non accade: antecedente vero e conseguente falso», quindi vale automaticamente ogni volta che l'antecedente fallisce. Per questo p → q equivale a ¬p ∨ q.
Nella calcolatricep → qp ↔ q, vero quando le due parti hanno lo stesso valore di verità.
Il bicondizionale afferma ciascun lato a condizione dell'altro: è vero quando entrambe le parti sono vere e quando entrambe sono false. Un bicondizionale che è una tautologia esprime esattamente un'equivalenza logica.
Nella calcolatricep ↔ qLa parte «se» di un condizionale: la p in p → q.
L'antecedente è la condizione da cui dipende un condizionale. Quando è falso l'intero condizionale è vero qualunque sia il conseguente, ed è da lì che vengono quasi tutte le sorprese della tavola di →.
Nella calcolatricep → qLa parte «allora» di un condizionale: la q in p → q.
Il conseguente è ciò che un condizionale afferma debba seguire se il suo antecedente vale. Un conseguente vero rende vero il condizionale, ma non rende vero l'antecedente: dedurlo è una fallacia formale.
Nella calcolatricep → qIl condizionale con le due parti scambiate: q → p.
L'inverso di p → q è q → p, e i due non sono equivalenti: la calcolatrice trova una riga in cui l'uno vale e l'altro fallisce. Trattarli come intercambiabili è affermare il conseguente.
Nella calcolatriceq → p¬q → ¬p, che ha sempre lo stesso valore di verità di p → q.
La contronominale nega entrambe le parti di un condizionale e le scambia. A differenza dell'inverso è davvero equivalente all'originale, ed è ciò che rende legittima la dimostrazione per contrapposizione in matematica.
Nella calcolatrice(p → q) ≡ (¬q → ¬p)La negazione di una congiunzione: vera tranne quando entrambi gli ingressi lo sono.
NAND, scritto ↑, è ¬(p ∧ q). È funzionalmente completo: ogni altro connettivo può essere costruito con il solo NAND, ed è per questo un cardine della progettazione dei circuiti digitali.
Nella calcolatrice¬(p ∧ q)La negazione di una disgiunzione: vera solo se entrambi gli ingressi sono falsi.
NOR, scritto ↓, è ¬(p ∨ q). Come NAND è funzionalmente completo da solo, così che un circuito può essere costruito interamente con porte NOR e nient'altro.
Nella calcolatrice¬(p ∨ q)Quale connettivo si applica per primo quando mancano le parentesi.
La negazione lega più strettamente, poi la congiunzione, la disgiunzione, il condizionale e infine il bicondizionale. Così ¬p ∧ q ∨ r si legge ((¬p) ∧ q) ∨ r; le parentesi cambiano l'ordine quando la lettura voluta è diversa.
Nella calcolatrice¬p ∧ q ∨ rUna riga per ogni assegnazione di valori, con il valore della formula.
Una tavola di verità elenca tutte le 2ⁿ interpretazioni delle n variabili di una formula e ne calcola il valore in ciascuna. Essendo esaustiva risolve ogni questione semantica della logica proposizionale: equivalenza, validità, soddisfacibilità e le altre.
Nella calcolatricep → qUna formula vera sotto ogni interpretazione.
Una tautologia risulta vera in ogni riga della sua tavola di verità, quindi non dice nulla sul mondo: p ∨ ¬p è vera qualunque cosa sia p. Due formule sono equivalenti esattamente quando il bicondizionale fra loro è una tautologia.
Nella calcolatricep ∨ ¬pUna formula falsa sotto ogni interpretazione.
Una contraddizione come p ∧ ¬p è falsa in ogni riga della sua tavola di verità. Derivarne una da un insieme di assunzioni mostra che non possono valere tutte, ed è il motore della dimostrazione per assurdo.
Nella calcolatricep ∧ ¬pUna formula vera sotto alcune interpretazioni e falsa sotto altre.
Una formula contingente non è né tautologia né contraddizione: la sua tavola di verità ha almeno una riga vera e almeno una falsa. Quasi tutte le formule che qualcuno scrive sono contingenti, ed è ciò che le rende informative.
Nella calcolatricep ∧ qSe qualche interpretazione rende vera la formula.
Una formula è soddisfacibile quando almeno una riga della sua tavola di verità è vera, e quella riga ne è un modello. Decidere la soddisfacibilità è il problema centrale dei risolutori SAT e, tramite essi, di gran parte del ragionamento automatico.
Nella calcolatricep ∧ (p → q)Due formule con tavole di verità identiche.
Formule equivalenti concordano sotto ogni interpretazione, quindi ciascuna può sostituire l'altra ovunque senza cambiare ciò che si dice. Metti un segno di uguale fra due espressioni e la calcolatrice confronterà le loro colonne riga per riga.
Nella calcolatrice(p → q) ≡ (¬p ∨ q)La conclusione vale in ogni interpretazione in cui valgono le premesse.
Scritta Γ ⊨ φ, la conseguenza logica è ciò che un argomento valido pretende. Si verifica cercando un controesempio: un'interpretazione che renda vere tutte le premesse e falsa la conclusione. Se non ce n'è, la conseguenza vale.
Nella calcolatricep → q, p ⊨ qNessuna interpretazione rende vere le premesse e falsa la conclusione.
La validità è una proprietà della forma dell'argomento, non dei fatti: un argomento valido può avere premesse false e conclusione falsa. Ciò che non può avere sono premesse vere insieme a una conclusione falsa.
Nella calcolatricep → q, p ⊨ qUn argomento valido le cui premesse sono anche vere.
La fondatezza aggiunge un'affermazione di fatto a una formale: l'argomento è valido e le sue premesse valgono. La logica da sola risolve la prima metà; la seconda appartiene all'argomento di cui si parla.
Un'interpretazione che rende vere le premesse e falsa la conclusione.
Un controesempio prova che un argomento è invalido: basta una riga. La calcolatrice mostra quella che trova, trasformando «questo non segue» in un'assegnazione concreta da verificare a mano.
Nella calcolatricep → q ⊨ q → pQualche interpretazione rende veri tutti gli enunciati dell'insieme insieme.
Un insieme di premesse è coerente quando possono valere tutte insieme. Premesse incoerenti implicano qualsiasi cosa, così che un argomento costruito su di esse è tecnicamente valido e non vale nulla.
Nella calcolatricep → q, ¬q ⊨ ¬pUna variabile o la sua negazione, come p o ¬p.
I letterali sono gli atomi delle forme normali: una clausola è una disgiunzione di letterali e un mintermine una loro congiunzione. Un letterale è positivo quando la variabile compare nuda e negativo quando è negata.
Nella calcolatrice¬pUna disgiunzione di letterali, come p ∨ ¬q ∨ r.
Una clausola è uno dei gruppi fra parentesi con cui si costruisce una forma normale congiuntiva. Poiché una congiunzione è vera solo se lo è ogni sua parte, una formula in FNC vale esattamente quando valgono tutte le sue clausole.
Nella calcolatricep ∨ ¬q ∨ rUn OR di AND: una disgiunzione di congiunzioni di letterali.
Ogni formula ha una forma normale disgiuntiva, e si legge direttamente dalla tavola di verità: una congiunzione per ogni riga vera, unite da ∨. La calcolatrice fornisce anche una FND minimizzata, che dice la stessa cosa con meno letterali.
Nella calcolatrice(p ∧ q) ∨ (¬p ∧ r)Un AND di OR: una congiunzione di clausole.
La forma normale congiuntiva si legge dalle righe false della tavola di verità, una clausola per riga. È il formato di ingresso che i risolutori SAT si aspettano, il che rende la conversione in FNC un passo di routine del ragionamento automatico.
Nella calcolatrice(p ∨ q) ∧ (¬p ∨ r)Una congiunzione che individua esattamente una riga della tavola di verità.
Un mintermine nomina ogni variabile una volta, negata o no, così che una sola interpretazione lo soddisfi. Raccogliere i mintermini delle righe vere e unirli con ∨ dà la forma normale disgiuntiva della formula.
Nella calcolatricep ∧ ¬q ∧ rUna disgiunzione che esclude esattamente una riga della tavola di verità.
Un maxtermine nomina ogni variabile una volta ed è falso in una sola interpretazione. Prendere il maxtermine di ogni riga falsa e unirli con ∧ dà la forma normale congiuntiva della formula.
Nella calcolatricep ∨ ¬q ∨ rLa negazione trasforma ∧ in ∨ e ∨ in ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
Le leggi di De Morgan spingono una negazione all'interno di una congiunzione o di una disgiunzione, ribaltando il connettivo lungo la strada. È così che una formula viene portata verso una forma normale e così che si semplificano le negazioni nel codice e nei circuiti.
Nella calcolatrice¬(p ∧ q) ≡ ¬p ∨ ¬qNegare due volte restituisce l'originale: ¬¬p ≡ p.
La doppia negazione vale nella logica classica in entrambe le direzioni, quindi ¬¬p e p sono sempre scambiabili. La logica intuizionista conserva solo la direzione da p a ¬¬p, ed è lì che i due sistemi si separano.
Nella calcolatrice¬¬p ≡ pL'algebra di due valori, con ∧, ∨ e ¬ come operazioni.
L'algebra di Boole è la logica proposizionale scritta come aritmetica su 0 e 1, con leggi — commutatività, distributività, assorbimento, De Morgan — che permettono di riscrivere e semplificare le espressioni. È la matematica con cui si progettano i circuiti digitali.
Nella calcolatrice(p ∧ q) ∨ (p ∧ ¬q) ≡ pUna griglia della tavola di verità che rende visibili le semplificazioni.
Una mappa di Karnaugh dispone le righe in modo che le celle vicine differiscano per una variabile, e i bordi si richiudono. Si scrive anche mappa K, K-map o kmap. I gruppi rettangolari di 1 adiacenti di dimensione 1, 2, 4 o 8 si leggono allora come termini di un'espressione minima.
Nella calcolatrice(p ∧ q) ∨ (p ∧ ¬r)Un gruppo sulla mappa che non può più essere ingrandito.
Un implicante è una congiunzione di letterali che forza la formula a essere vera; è primo quando togliere un qualsiasi letterale glielo impedirebbe. Su una mappa di Karnaugh gli implicanti primi sono i rettangoli massimali di 1.
L'unico implicante primo che copre un certo 1.
Quando un 1 sulla mappa appartiene a un solo gruppo massimale, quel gruppo deve comparire in ogni copertura minima, quindi si prende per primo. Ciò che resta è la parte della copertura che va davvero cercata.
Un elemento di circuito che calcola un connettivo sui suoi ingressi.
Le porte AND, OR, NOT, NAND, NOR e XOR sono la controparte hardware dei connettivi. Una formula e un circuito sono lo stesso oggetto disegnato due volte, ed è per questo che la calcolatrice può mostrare un'espressione come schema di porte.
Nella calcolatrice(p ∧ q) ∨ ¬rUn passo consentito da formule già ottenute a una nuova.
Una regola di inferenza è uno schema come il modus ponens, applicabile ogni volta che sono disponibili formule della forma giusta. I sistemi di dimostrazione si costruiscono con una manciata di esse, scelte perché si possano derivare solo conclusioni che seguono.
Da p → q e p si inferisce q.
Il modus ponens è la regola base del condizionale: dati un condizionale e il suo antecedente, segue il conseguente. La sua validità si vede nella tavola di verità: l'unica riga con entrambe le premesse vere ha vera anche la conclusione.
Nella calcolatricep → q, p ⊨ qDa p → q e ¬q si inferisce ¬p.
Il modus tollens percorre un condizionale all'indietro: se il conseguente fallisce, l'antecedente non può aver valso. È la contronominale al lavoro ed è la forma di ogni argomento che confuta un'ipotesi mettendone alla prova le previsioni.
Nella calcolatricep → q, ¬q ⊨ ¬pDa p → q e q → r si inferisce p → r.
Il sillogismo ipotetico concatena condizionali, ed è ciò che rende possibili le derivazioni lunghe: ogni anello porta l'argomento un passo più avanti senza che nessuna premessa venga asserita.
Nella calcolatricep → q, q → r ⊨ p → rDa p ∨ q e ¬p si inferisce q.
Il sillogismo disgiuntivo elimina l'opzione esclusa: se vale una di due alternative e la prima no, deve valere la seconda. È la regola dietro il ragionamento per esclusione.
Nella calcolatricep ∨ q, ¬p ⊨ qDimostrare una conclusione applicando regole di inferenza passo dopo passo.
La deduzione naturale ricava una conclusione dalle premesse con regole di introduzione ed eliminazione per ciascun connettivo, permettendo assunzioni temporanee da scaricare in seguito. Dimostra ciò che una tavola di verità verifica, ma senza percorrere ogni riga.
Assumi il contrario, deriva una contraddizione, concludi l'originale.
Per dimostrare φ si assume ¬φ e si deriva qualcosa della forma ψ ∧ ¬ψ. Poiché nessuna interpretazione rende vera una contraddizione, l'assunzione non può valere e φ segue. È così che procedono di solito le dimostrazioni di irrazionalità e di infinità.
Nella calcolatricep ∧ ¬pIl passo invalido da p → q e q a p.
Un conseguente vero non stabilisce l'antecedente: potrebbe averlo prodotto qualcos'altro. La calcolatrice mostra il controesempio — p falsa, q vera — che è la riga che distingue questo dal modus ponens.
Nella calcolatricep → q, q ⊨ pIl passo invalido da p → q e ¬p a ¬q.
Un condizionale non dice nulla su cosa accade quando il suo antecedente fallisce, quindi escludere l'antecedente lascia aperto il conseguente. Il controesempio è la riga in cui p è falsa e q vera.
Nella calcolatricep → q, ¬p ⊨ ¬qLogica che guarda dentro le proposizioni, agli oggetti e alle loro proprietà.
La logica dei predicati aggiunge predicati, termini e quantificatori, così che «ogni primo maggiore di due è dispari» diventi una formula e non una singola lettera. È strettamente più espressiva di quella proposizionale, e nessuna tavola di verità può deciderla.
Un simbolo che dice di quanti oggetti vale un predicato.
I due quantificatori classici sono ∀ (tutti) e ∃ (almeno uno), e ciascuno è la negazione dell'altro con il corpo negato. La variabile che un quantificatore lega è ciò che distingue la logica dei predicati da quella proposizionale.
∀x φ: φ vale per ogni oggetto del dominio.
Un'affermazione universale è confutata da un solo controesempio e vale a vuoto su un dominio vuoto. ∀x φ equivale a ¬∃x ¬φ, che è la controparte delle leggi di De Morgan per i quantificatori.
∃x φ: φ vale per almeno un oggetto del dominio.
Un'affermazione esistenziale si stabilisce esibendo un testimone. ∃x φ equivale a ¬∀x ¬φ, così che ciascun quantificatore può essere definito a partire dall'altro e dalla negazione.
Logica estesa con «necessariamente» (□) e «possibilmente» (◇).
La logica modale valuta le formule in mondi possibili anziché in una sola interpretazione: □φ vale quando φ vale in ogni mondo accessibile, ◇φ quando vale in qualcuno. Variando il significato di «accessibile» si ottengono i diversi sistemi modali.
