Nel mondo di oggi, utilizziamo sempre più una varietà di auto e gadget. E non solo quando è necessario applicare una forza letteralmente disumana: spostare il carico, sollevarlo in altezza, scavare una trincea lunga e profonda, ecc. Le automobili oggi sono assemblate da robot, il cibo è preparato da multicucina e calcoli aritmetici elementari sono eseguito dai calcolatori. Sempre più spesso si sente l'espressione "algebra booleana". Forse è giunto il momento di capire il ruolo dell'uomo nella creazione di robot e la capacità delle macchine di risolvere problemi non solo matematici, ma anche logici.
Logica
Tradotto dal greco, la logica è un sistema di pensiero ordinato che crea relazioni tra determinate condizioni e consente di trarre conclusioni basate su premesse e ipotesi. Abbastanza spesso ci chiediamo: "È logico?" La risposta ricevuta conferma le nostre ipotesi o critica il corso del pensiero. Ma il processo non si ferma: continuiamo a ragionare.
A volte il numero di condizioni (introduttive) è così grande e le relazioni tra loro sono così intricate e complesse che il cervello umano non è in grado di "digerire" tutto in una volta. Potrebbe volerci più di un mese (settimana, anno) per capire cosa sta succedendo. Mala vita moderna non ci dà tali intervalli di tempo per prendere decisioni. E ricorriamo all'aiuto dei computer. Ed è qui che appare l'algebra della logica, con le sue leggi e proprietà. Scaricando tutti i dati iniziali, consentiamo al computer di riconoscere tutte le relazioni, eliminare le contraddizioni e trovare una soluzione soddisfacente.
Matematica e logica
Il famoso Gottfried Wilhelm Leibniz formulò il concetto di "logica matematica", i cui problemi erano comprensibili solo a una ristretta cerchia di scienziati. Questa direzione non suscitò particolare interesse e fino alla metà del XIX secolo pochi conoscevano la logica matematica.
Il grande interesse per la comunità scientifica ha provocato una disputa in cui l'inglese George Boole ha annunciato la sua intenzione di creare una branca della matematica che non ha assolutamente alcuna applicazione pratica. Come ricordiamo dalla storia, la produzione industriale si stava sviluppando attivamente a quel tempo, venivano sviluppati tutti i tipi di macchine ausiliarie e macchine utensili, cioè tutte le scoperte scientifiche avevano un focus pratico.
Guardando avanti, diciamo che l'algebra booleana è la parte più usata della matematica nel mondo moderno. Quindi Bull ha perso la sua argomentazione.
George Buhl
La stessa personalità dell'autore merita un'attenzione speciale. Anche considerando che in passato le persone sono cresciute prima di noi, è ancora impossibile non notare che all'età di 16 anni J. Buhl insegnò in una scuola del villaggio e all'età di 20 anni aprì la sua scuola a Lincoln. Il matematico parlava correntemente cinque lingue straniere e nel tempo libero leggeva opereNewton e Lagrange. E tutto questo riguarda il figlio di un semplice lavoratore!
Nel 1839 Boole presentò per la prima volta i suoi articoli scientifici al Cambridge Mathematical Journal. Lo scienziato ha 24 anni. Il lavoro di Boole interessò così tanto i membri della Royal Society che nel 1844 ricevette una medaglia per il suo contributo allo sviluppo dell'analisi matematica. Diversi altri lavori pubblicati, che descrivevano gli elementi della logica matematica, permisero al giovane matematico di assumere l'incarico di professore al Cork County College. Ricordiamo che lo stesso Buhl non aveva istruzione.
Idea
In linea di principio, l'algebra booleana è molto semplice. Esistono enunciati (espressioni logiche) che, dal punto di vista matematico, possono essere definiti solo con due parole: “vero” o “falso”. Ad esempio, in primavera gli alberi fioriscono - vero, in estate nevica - una bugia. Il bello di questa matematica è che non è necessario utilizzare solo i numeri. Qualsiasi affermazione con un significato inequivocabile è abbastanza adatta per l'algebra dei giudizi.
Quindi, l'algebra della logica può essere usata letteralmente ovunque: nella pianificazione e nella scrittura di istruzioni, nell'analisi di informazioni contrastanti sugli eventi e nella determinazione della sequenza di azioni. La cosa più importante è capire che è del tutto irrilevante come determiniamo la verità o la falsità dell'affermazione. Questi "come" e "perché" devono essere astratti. Conta solo l'affermazione di fatto: vero-falso.
Naturalmente, per la programmazione, sono importanti le funzioni dell'algebra della logica, che vengono scritte dal corrispondentesegni e simboli. E impararli significa padroneggiare una nuova lingua straniera. Niente è impossibile.
Concetti e definizioni di base
Senza approfondire, affrontiamo la terminologia. Quindi l'algebra booleana assume:
- dichiarazioni;
- operazioni logiche;
- funzioni e leggi.
Le dichiarazioni sono espressioni affermative che non possono essere interpretate in modo ambiguo. Sono scritti come numeri (5 > 3) o formulati con parole familiari (l'elefante è il mammifero più grande). Allo stesso tempo, anche la frase "la giraffa non ha collo" ha il diritto di esistere, solo l'algebra booleana la definirà "falsa".
Tutte le affermazioni devono essere prive di ambiguità, ma possono essere elementari e composte. Questi ultimi usano connettivi logici. Cioè, nell'algebra dei giudizi, gli enunciati composti si formano aggiungendo enunciati elementari mediante operazioni logiche.
Operazioni di algebra booleana
Ricordiamo già che le operazioni nell'algebra dei giudizi sono logiche. Proprio come l'algebra dei numeri usa l'aritmetica per sommare, sottrarre o confrontare numeri, gli elementi della logica matematica consentono di fare affermazioni complesse, negare o calcolare il risultato finale.
Le operazioni logiche per la formalizzazione e la semplicità sono scritte da formule a noi familiari in aritmetica. Le proprietà dell'algebra booleana consentono di scrivere equazioni e calcolare incognite. Le operazioni logiche vengono solitamente scritte utilizzando una tabella di verità. Le sue colonnedefinire gli elementi del calcolo e l'operazione che viene eseguita su di essi, e le righe mostrano il risultato del calcolo.
Azioni logiche di base
Le operazioni più comuni nell'algebra booleana sono la negazione (NOT) e AND e OR logici. Quasi tutte le azioni nell'algebra dei giudizi possono essere descritte in questo modo. Esaminiamo ciascuna delle tre operazioni in modo più dettagliato.
La negazione (non) si applica a un solo elemento (operando). Pertanto, l'operazione di negazione è chiamata unaria. Per scrivere il concetto di "non A" utilizzare i seguenti simboli: ¬A, A¯¯¯ o !A. In forma tabellare si presenta così:
La funzione di negazione è caratterizzata dalla seguente affermazione: se A è vero, allora B è falso. Ad esempio, la Luna gira intorno alla Terra - vero; La terra gira intorno alla luna - false.
Moltiplicazione logica e addizione
L'AND logico è chiamato operazione di congiunzione. Cosa significa? In primo luogo, che può essere applicato a due operandi, cioè And è un'operazione binaria. In secondo luogo, che solo nel caso della verità di entrambi gli operandi (sia A che B) l'espressione stessa è vera. Il proverbio "La pazienza e il lavoro macineranno tutto" suggerisce che solo entrambi i fattori aiuteranno una persona a far fronte alle difficoltà.
Simboli usati per scrivere: A∧B, A⋅B o A&B.
La congiunzione è simile alla moltiplicazione in aritmetica. A volte lo dicono: moltiplicazione logica. Se moltiplichiamo gli elementi della tabella riga per riga, otteniamo un risultato simile al ragionamento logico.
La disgiunzione è un'operazione logica OR. Ci vuole il valore della veritàquando almeno una delle affermazioni è vera (A o B). Si scrive così: A∨B, A+B o A||B. Le tabelle di verità per queste operazioni sono:
La disgiunzione è come l'addizione aritmetica. L'operazione di addizione logica ha una sola limitazione: 1+1=1. Ricordiamo però che nel formato digitale la logica matematica è limitata a 0 e 1 (dove 1 è vero, 0 è falso). Ad esempio, l'affermazione "in un museo puoi vedere un capolavoro o incontrare un interlocutore interessante" significa che puoi vedere opere d'arte o puoi incontrare una persona interessante. Allo stesso tempo, non è esclusa la possibilità che entrambi gli eventi si verifichino contemporaneamente.
Funzioni e leggi
Quindi, sappiamo già quali operazioni logiche utilizza l'algebra booleana. Le funzioni descrivono tutte le proprietà degli elementi della logica matematica e consentono di semplificare complesse condizioni composte di problemi. La proprietà più comprensibile e semplice sembra essere il rifiuto delle operazioni derivate. I derivati sono OR esclusivi, implicazione ed equivalenza. Poiché abbiamo studiato solo le operazioni di base, considereremo anche le proprietà solo di esse.
Associatività significa che in affermazioni come "e A, e B e C", l'ordine degli operandi non ha importanza. La formula è scritta così:
(LA∧B)∧V=LA∧(B∧V)=LA∧B∧V, (LA∨B)∨C=LA∨(B∨C)=LA∨B∨C.
Come puoi vedere, questo è caratteristico non solo della congiunzione, ma anche della disgiunzione.
Commutatività afferma che il risultatocongiunzione o disgiunzione non dipende da quale elemento è stato considerato per primo:
LA∧B=B∧A; A∨B=B∨A.
La distribuzione consente di espandere le parentesi in espressioni logiche complesse. Le regole sono simili all'apertura delle parentesi in moltiplicazione e addizione in algebra:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Le proprietà di uno e zero, che possono essere uno degli operandi, sono simili anche alla moltiplicazione algebrica per zero o uno e addizione con uno:
LA∧0=0, LA∧1=LA; LA∨0=LA, LA∨1=1.
L'idempotenza ci dice che se, rispetto a due operandi uguali, il risultato di un'operazione risulta essere simile, allora possiamo “buttare via” gli operandi extra che complicano il corso del ragionamento. Sia la congiunzione che la disgiunzione sono operazioni idempotenti.
B∧B=B; B∨B=B.
L'assorbimento ci permette anche di semplificare le equazioni. L'assorbimento afferma che quando un' altra operazione con lo stesso elemento viene applicata a un'espressione con un operando, il risultato è l'operando dell'operazione di assorbimento.
LA∧B∨B=B; (LA∨B)∧B=B.
Sequenza delle operazioni
La sequenza delle operazioni non ha poca importanza. In re altà, come per l'algebra, c'è una priorità di funzioni che usa l'algebra booleana. Le formule possono essere semplificate solo se si osserva il significato delle operazioni. Classificando dal più significativo al meno, otteniamo la seguente sequenza:
1. Negazione.
2. Congiunzione.
3. Disgiunzione, esclusivoO.
4. Implicazione, equivalenza.
Come puoi vedere, solo la negazione e la congiunzione non hanno uguale precedenza. E la priorità di disgiunzione e XOR sono uguali, così come le priorità di implicazione ed equivalenza.
Funzioni di implicazione ed equivalenza
Come abbiamo già detto, oltre alle operazioni logiche di base, la logica matematica e la teoria degli algoritmi utilizzano le derivate. I più comunemente usati sono l'implicazione e l'equivalenza.
L'implicazione, o conseguenza logica, è un'affermazione in cui un'azione è una condizione e l' altra è una conseguenza della sua attuazione. In altre parole, questa è una frase con le preposizioni "se … allora". "Se ti piace andare in bicicletta, ami portare le slitte." Cioè, per sciare, devi stringere la slitta su per la collina. Se non c'è voglia di scendere dalla montagna, allora non devi portare la slitta. Si scrive così: A→B o A⇒B.
Equivalenza presuppone che l'azione risultante avvenga solo quando entrambi gli operandi sono veri. Ad esempio, la notte si trasforma in giorno quando (e solo quando) il sole sorge all'orizzonte. Nel linguaggio della logica matematica, questa affermazione è scritta come segue: A≡B, A⇔B, A==B.
Altre leggi dell'algebra booleana
L'algebra dei giudizi si sta sviluppando e molti scienziati interessati hanno formulato nuove leggi. I postulati del matematico scozzese O. de Morgan sono considerati i più famosi. Notò e definì proprietà come stretta negazione, complemento e doppia negazione.
Chiudi negazione significa che non c'è negazione prima della parentesi:non (A o B)=non A o NON B.
Quando un operando viene negato, indipendentemente dal suo valore, si parla di complemento:
B∧¬B=0; B∨¬B=1.
E infine, la doppia negazione si compensa da sola. Quelli. o la negazione scompare prima dell'operando, oppure ne rimane solo uno.
Come risolvere i test
La logica matematica implica la semplificazione di equazioni date. Proprio come in algebra, devi prima rendere la condizione il più semplice possibile (sbarazzarti di input e operazioni complessi con essi), quindi iniziare a cercare la risposta giusta.
Cosa si può fare per semplificare? Converti tutte le operazioni derivate in operazioni semplici. Quindi apri tutte le parentesi (o viceversa, toglilo dalle parentesi per accorciare questo elemento). Il passo successivo dovrebbe essere l'applicazione pratica delle proprietà dell'algebra booleana (assorbimento, proprietà di zero e uno, ecc.).
In definitiva, l'equazione dovrebbe consistere nel numero minimo di incognite combinate da semplici operazioni. Il modo più semplice per trovare una soluzione è ottenere un gran numero di negativi ravvicinati. Quindi la risposta apparirà come da sola.
