Nel Capitolo 8 sono stati considerati tipi di oggetti di natura non numerica come gli insiemi fuzzy e casuali. Lo scopo di questa appendice è quello di studiare più a fondo le proprietà degli insiemi fuzzy e mostrare che la teoria degli insiemi fuzzy in un certo senso si riduce alla teoria degli insiemi casuali. Per raggiungere questo obiettivo, viene formulata e dimostrata una catena di teoremi.

In quanto segue, si assume che tutti gli insiemi fuzzy considerati siano sottoinsiemi dello stesso insieme Y.

P2-1. Le leggi di De Morgan per gli insiemi fuzzy

Come è noto, le seguenti identità dell'algebra degli insiemi sono dette leggi di Morgan

Teorema 1.Per i set sfocati, le identità

(3)

La dimostrazione del Teorema 1 consiste in una verifica diretta della validità delle relazioni (2) e (3) calcolando i valori delle funzioni di appartenenza degli insiemi fuzzy che partecipano a tali relazioni in base alle definizioni date nel Capitolo 8.

Verranno chiamate le identità (2) e (3). leggi di de Morgan per gli insiemi fuzzy. Contrariamente al caso classico delle relazioni (1), esse sono costituite da quattro identità, una coppia delle quali si riferisce alle operazioni di unione e intersezione, e la seconda coppia alle operazioni di prodotto e somma. Come la relazione (1) nell'algebra degli insiemi, le leggi di de Morgan nell'algebra degli insiemi fuzzy consentono di trasformare espressioni e formule, che includono operazioni di negazione.

P2-2. Legge distributiva per insiemi fuzzy

Alcune proprietà delle operazioni sugli insiemi non valgono per gli insiemi fuzzy. Sì, tranne quando MA- set "clear" (cioè la funzione di appartenenza assume solo i valori 0 e 1).

La legge distributiva è vera per gli insiemi fuzzy? La letteratura a volte afferma vagamente che "non sempre". Mettiamolo in chiaro.

Teorema 2.Per tutti gli insiemi fuzzy A, B e C

Allo stesso tempo, l'uguaglianza

è vero se e solo se, per tutti

Prova. Risolviamo un elemento arbitrario. Per abbreviare la notazione, indichiamo Per dimostrare l'identità (4), è necessario mostrarlo

Considera diversi ordinamenti di tre numeri a, b, c. Sia prima Allora il lato sinistro della relazione (6) è e il lato destro cioè vale l'uguaglianza (6).

Sia quindi in relazione (6) sta a sinistra e a destra, cioè la relazione (6) è di nuovo un'uguaglianza.

Se poi in relazione (6) sta a sinistra e a destra, cioè entrambe le parti corrispondono di nuovo.

Altri tre ordinamenti di numeri a, b, c non c'è bisogno di smontare, poiché in relazione (6) i numeri B e C entrare simmetricamente. L'identità (4) è dimostrata.

La seconda affermazione del Teorema 2 segue dal fatto che, in accordo con le definizioni delle operazioni sugli insiemi fuzzy (vedi Capitolo 8)

Queste due espressioni coincidono se e solo se, quando ciò che doveva essere dimostrato.

Definizione 1.Il vettore dell'insieme fuzzy A è la raccolta di tutti i punti , per cui

Corollario del Teorema 2.Se i supporti degli insiemi fuzzy B e C coincidono con Y, allora l'uguaglianza (5) vale se e solo se A è un insieme "chiaro" (cioè ordinario, classico, non fuzzy).

Prova. Per condizione con tutto . Quindi segue dal Teorema 2 che quelli. o , il che significa che MA- set chiaro.

P2-3. Insiemi fuzzy come proiezioni di insiemi casuali

Fin dall'inizio dell'apparizione teoria moderna fuzziness negli anni '60 iniziò una discussione sulla sua relazione con la teoria della probabilità. Il fatto è che la funzione di appartenenza di un insieme fuzzy assomiglia a una distribuzione di probabilità. L'unica differenza è che la somma delle probabilità su tutti i possibili valori della variabile casuale (o dell'integrale, se l'insieme dei possibili valori non è numerabile) è sempre uguale a 1, e la somma S i valori della funzione di appartenenza (nel caso continuo - l'integrale della funzione di appartenenza) possono essere qualsiasi numero non negativo. C'è la tentazione di normalizzare la funzione di appartenenza, ad es. dividere tutti i suoi valori per S(a S 0) per ridurlo a una distribuzione di probabilità (o densità di probabilità). Tuttavia, gli specialisti in fuzziness giustamente si oppongono a tale riduzione "primitiva", poiché viene eseguita separatamente per ogni fuzziness (set fuzzy) e le definizioni delle operazioni ordinarie sugli insiemi fuzzy non possono essere concordate con essa. L'ultima affermazione significa quanto segue Siano le funzioni di appartenenza degli insiemi fuzzy MA e IN. Come vengono trasformate le funzioni di appartenenza in questo caso? Installalo impossibile in linea di principio. L'ultima affermazione diventa abbastanza chiara dopo aver considerato diversi esempi di coppie di insiemi fuzzy con le stesse somme di valori delle funzioni di appartenenza, ma risultati diversi delle operazioni di teoria degli insiemi su di esse e le somme di valori delle corrispondenti funzioni di appartenenza per questi risultati di operazioni di teoria degli insiemi, ad esempio, anche per le intersezioni di insiemi sono diversi.

Nei lavori sugli insiemi fuzzy, è abbastanza spesso affermato che la teoria della fuzziness è una branca indipendente della matematica applicata e non ha nulla a che fare con la teoria della probabilità (vedi, ad esempio, la rassegna della letteratura nelle monografie). Gli autori che hanno confrontato la teoria fuzzy e la teoria della probabilità hanno solitamente enfatizzato la differenza tra queste aree di ricerca teorica e applicata. Solitamente si confrontano gli assiomatici e si confrontano le aree di applicazione. Va subito notato che le argomentazioni del secondo tipo di comparazione non hanno valore probatorio, in quanto esistono opinioni divergenti sui limiti di applicabilità anche di un campo scientifico così antico come i metodi probabilistico-statistici. Ricordiamo che il risultato del ragionamento di uno dei più famosi matematici francesi, Henri Lebesgue, sui limiti di applicabilità dell'aritmetica è il seguente: "L'aritmetica è applicabile quando è applicabile" (vedi la sua monografia).

Quando si confrontano vari assiomi della teoria fuzzy e della teoria della probabilità, è facile vedere che gli elenchi di assiomi differiscono. Da ciò, tuttavia, non ne consegue affatto che tra queste teorie sia impossibile stabilire una connessione, come la ben nota riduzione della geometria euclidea sul piano all'aritmetica (più precisamente, alla teoria di un sistema numerico - cfr. , ad esempio, la monografia). Ricordiamo che queste due assiomatiche - geometria euclidea e aritmetica - a prima vista sono molto diverse.

Si può comprendere il desiderio degli entusiasti della nuova tendenza di sottolineare la fondamentale novità del proprio apparato scientifico. Tuttavia, è altrettanto importante stabilire collegamenti tra il nuovo approccio e quelli precedentemente noti.

Come si è scoperto, la teoria degli insiemi fuzzy è strettamente correlata alla teoria degli insiemi casuali. Già nel 1974, è stato dimostrato nel lavoro che è naturale considerare gli insiemi fuzzy come "proiezioni" di insiemi casuali. Consideriamo questo metodo per ridurre la teoria degli insiemi fuzzy alla teoria degli insiemi casuali.

Definizione 2.Lascia stare - un sottoinsieme casuale di un insieme finito Y. Un insieme fuzzy B definito su Y è chiamato proiezione A ed è indicato con Proj A se

(7)

per tutti

Ovviamente, ogni set casuale MA può essere messo in corrispondenza con l'ausilio della formula (7) fuzzy set B = Progetto A. Si scopre che è vero anche il contrario.

Teorema 3. Per ogni sottoinsieme fuzzy B di un insieme finito Y, esiste un sottoinsieme casuale A dell'insieme Y tale che B = Proj A.

Prova.È sufficiente specificare la distribuzione dell'insieme casuale MA. Lascia stare 1- vettore IN(vedi definizione 1 sopra). Senza perdita di generalità, possiamo presumerlo a un certo m ed elementi 1 numerato in modo tale che

Introduciamo gli insiemi

Per tutti gli altri sottoinsiemi X imposta In mettiamo P(A=X)=0. Dal momento che l'elemento e t incluso nel set Y(1), Y(2),…, Y(t) e non è incluso in imposta Y(t+1),…, Y(m), poi dalle formule di cui sopra ne consegue che Se allora, ovviamente, il Teorema 3 è dimostrato.

La distribuzione di un insieme casuale con elementi indipendenti, come risulta dalle considerazioni del Capitolo 8, è completamente determinata dalla sua proiezione. Per un insieme casuale finito vista generale questo non è vero. Per chiarire quanto detto abbiamo bisogno del seguente teorema.

Teorema 4. Per un sottoinsieme casuale A di un insieme Y da un finito numero di elementi insiemi di numeri e si esprimono l'uno attraverso l'altro.

Prova. Il secondo insieme è espresso in termini del primo come segue:

Gli elementi del primo insieme possono essere espressi nei termini del secondo utilizzando la formula delle inclusioni ed esclusioni dalla logica formale, secondo la quale

In questa formula, nella prima somma a attraversa tutti gli elementi del set Y\X, nella seconda somma, le variabili di somma 1 e alle 2 non coincidono e attraversano anche questo set, e così via. Il riferimento alla formula di inclusione ed esclusione completa la dimostrazione del Teorema 4.

Secondo il Teorema 4, un insieme casuale A può essere caratterizzato non solo da una distribuzione, ma anche da un insieme di numeri In questo insieme a non ci sono altre relazioni del tipo di uguaglianza. Questo set include numeri, quindi fissare la proiezione di un set casuale equivale a correggere k = Carta(Y) parametri da (2k-1) parametri che specificano la distribuzione di un insieme casuale MA generalmente.

Sarà utile il seguente teorema.

Teorema 5. Se Proj A = B, poi

Per dimostrarlo è sufficiente utilizzare l'identità della teoria degli insiemi casuali, la formula per la probabilità di copertura del Capitolo 8, la definizione della negazione di un insieme fuzzy e il fatto che la somma di tutti P(A= X) è uguale a 1.

P2-4. Intersezioni e prodotti di insiemi fuzzy e random

Scopriamo come le operazioni sugli insiemi casuali sono correlate alle operazioni sulle loro proiezioni. In virtù delle leggi di de Morgan (Teorema 1) e del Teorema 5, basta considerare l'operazione di intersezione di insiemi casuali.

Teorema 6. Se sottoinsiemi casuali A 1 e A 2 di un insieme finito sono indipendenti, quindi l'insieme fuzzy è un prodotto set sfocati Proj A 1 e Proj A 2 .

Prova. Dobbiamo dimostrarlo per chiunque

Secondo la formula per la probabilità di coprire un punto con un insieme casuale (Capitolo 8)

Come è noto, la distribuzione di intersezione degli insiemi casuali può essere espressa in termini di distribuzione congiunta come segue:

Dalle relazioni (9) e (10) consegue che la probabilità di copertura per l'intersezione di insiemi casuali può essere rappresentata come una doppia somma

Si noti ora che il lato destro della formula (11) può essere riscritto come segue:

(12)

Infatti, la formula (11) differisce dalla formula (12) solo in quanto contiene termini in cui l'intersezione delle variabili di somma assume valore costante. Utilizzando la definizione dell'indipendenza degli insiemi casuali e la regola della moltiplicazione delle somme, otteniamo che da (11) e (12) segue l'uguaglianza

Per completare la dimostrazione del Teorema 6 è sufficiente fare riferimento ancora una volta alla formula della probabilità che un punto sia coperto da un insieme casuale (Capitolo 8).

Definizione 3. Il vettore di un insieme casuale C è la raccolta di tutti quegli elementi per cui

Teorema 7.Uguaglianza

è vero se e solo se l'intersezione di supporti di insiemi casuali e vuoto.

Prova.È necessario scoprire le condizioni in cui

Quindi l'uguaglianza (13) si riduce alla condizione

È chiaro che la relazione (14) è soddisfatta se e solo se R 2 R 3=0 per tutti cioè non vi è alcun elemento tale che allo stesso tempo e , e questo equivale al vuoto dell'intersezione di supporti di insiemi casuali e . Il teorema 7 è dimostrato.

P2-5. Riduzione di una sequenza di operazioni su insiemi fuzzy

a una sequenza di operazioni su insiemi casuali

Sopra, si ottengono alcune connessioni tra insiemi fuzzy e casuali. Vale la pena notare che lo studio di queste relazioni nel lavoro (questo lavoro è stato svolto nel 1974 e riportato al seminario "Multidimensional analisi statistica e la modellazione probabilistica dei processi reali "18 dicembre 1974 - vedi) iniziò con l'introduzione di insiemi casuali per sviluppare e generalizzare l'apparato degli insiemi fuzzy L. Zadeh. Il fatto è che l'apparato matematico degli insiemi fuzzy non consente di tenere in considerazione varie opzioni le dipendenze tra concetti (oggetti) modellati con il suo aiuto non sono sufficientemente flessibili. Quindi, per descrivere la "parte comune" di due insiemi fuzzy, ci sono solo due operazioni: prodotto e intersezione. Se viene utilizzato il primo di questi, si presume che gli insiemi si comportino effettivamente come proiezioni di insiemi casuali indipendenti (si veda il Teorema 6 sopra). L'operazione di intersezione impone anche restrizioni ben definite sul tipo di dipendenza tra insiemi (vedi Teorema 7 sopra), e in questo caso si trovano anche condizioni necessarie e sufficienti. È auspicabile avere maggiori opportunità per modellare la dipendenza tra insiemi (concetti, oggetti). Utilizzo apparato matematico gli insiemi casuali offrono tali opportunità.

Lo scopo della riduzione degli insiemi fuzzy a quelli casuali è quello di vedere dietro qualsiasi costruzione da insiemi fuzzy una costruzione da insiemi casuali che determina le proprietà del primo, proprio come vediamo una variabile casuale dalla densità della distribuzione di probabilità. In questa sottosezione, presentiamo i risultati sulla riduzione dell'algebra degli insiemi fuzzy all'algebra degli insiemi casuali.

Definizione 4.Spazio di probabilità { w, G, P)chiamiamo divisibile se per qualsiasi insieme misurabile X G e qualsiasi numero positivo , minore di P(X), si può specificare un insieme misurabile tale che

Esempio. Sia il cubo unitario di una dimensione finita spazio lineare, Gè la sigma-algebra degli insiemi di Borel, e Pè la misura di Lebesgue. Quindi { w, G, P)- spazio di probabilità divisibile.

Pertanto, uno spazio di probabilità divisibile non è esotico. Il cubo regolare è un esempio di tale spazio.

La dimostrazione dell'asserzione formulata nell'esempio viene effettuata con metodi matematici standard basati sul fatto che un insieme misurabile può essere approssimato arbitrariamente accuratamente insiemi aperti, queste ultime sono rappresentate come somma di non più di un numero numerabile di palle aperte, e per le palle la divisibilità è verificata direttamente (il corpo di volume è separato dalla palla X da un piano corrispondente).

Teorema 8.Sia dato un insieme casuale A su uno spazio di probabilità divisibile (w, G, P) con valori nell'insieme di tutti i sottoinsiemi dell'insieme Y di un numero finito di elementi e un insieme fuzzy D su Y. Quindi ci sono insiemi casuali ~ 1, Da 2, Da 3, C 4 sullo stesso spazio di probabilità tale che

dove B = ProjA.

Prova. A causa della validità delle leggi di de Morgan per fuzzy (vedi Teorema 1 sopra) e per insiemi casuali, così come per il Teorema 5 sopra (sulle negazioni), è sufficiente dimostrare l'esistenza di insiemi casuali Da 1 e Da 2 .

Considera la distribuzione di probabilità nell'insieme di tutti i sottoinsiemi dell'insieme In, corrispondente a un insieme casuale DA tale che Progetto C = D(esiste in virtù del Teorema 3). Costruiamo un set casuale C 2 Escludere l'elemento solo per dello stesso insieme Y tale che

e, inoltre, i risultati delle operazioni teoriche degli insiemi sono correlati da relazioni simili

dove il segno significa che il luogo in esame è il simbolo dell'intersezione di insiemi casuali, se la definizione di B m contiene il simbolo dell'intersezione o il simbolo del prodotto di insiemi fuzzy e, di conseguenza, il simbolo dell'unione di insiemi casuali, se B m contiene il simbolo dell'unione o il simbolo della somma degli insiemi fuzzy.

Le leggi di De Morgan lo sono regole logiche, stabilito dal matematico scozzese Augustus de Morgan, che collega coppie di operazioni logiche usando la negazione logica.

Augustus de Morgan ha notato che le seguenti relazioni sono vere nella logica classica:

not (A e B) = (non A) o (non B)

not (A o B) = (non A) e (non B)

In una forma per noi più familiare, questi rapporti possono essere scritti nella forma seguente:

Le leggi di De Morgan possono essere formulate come segue:

La legge di I de Morgan: La negazione della disgiunzione di due enunciati semplici equivale alla congiunzione delle negazioni di questi enunciati.

II legge di Morgan: La negazione della congiunzione di due semplici enunciati equivale alla disgiunzione delle negazioni di questi enunciati.

Si consideri l'applicazione delle leggi di de Morgan su esempi specifici.

Esempio 1 Trasforma la formula in modo che non ci siano negazioni di affermazioni complesse.

Usiamo la prima legge di de Morgan, otteniamo:

applichiamo la seconda legge di de Morgan alla negazione della congiunzione di semplici enunciati B e C, otteniamo:

,

così:

.

Di conseguenza, abbiamo ottenuto un'affermazione equivalente in cui non ci sono negazioni di affermazioni composte e tutte le negazioni si riferiscono solo ad affermazioni semplici.

Puoi verificare la validità della soluzione usando le tavole di verità. Per fare ciò, compiliamo tabelle di verità per l'affermazione originale:

e per l'affermazione ottenuta a seguito di trasformazioni effettuate secondo le leggi di de Morgan:

.

Tabella 1.

			AVANTI CRISTO	A\/B/\C

Come si vede dalle tabelle, l'enunciato logico originario e l'enunciato logico ottenuto con l'aiuto delle leggi di de Morgan sono equivalenti. Ciò è dimostrato dal fatto che nelle tavole di verità abbiamo gli stessi insiemi di valori.

Formule e leggi della logica

Sul lezione introduttiva dedicato a fondamenti della logica matematica, abbiamo familiarizzato con i concetti di base di questa sezione della matematica e ora l'argomento sta ricevendo una naturale continuazione. Oltre al nuovo materiale teorico, o meglio nemmeno teorico - ma didattico generale, ci aspettano compiti pratici, e quindi se sei arrivato a questa pagina da un motore di ricerca e/o sei poco orientato nel materiale, ti preghiamo di seguire il link sopra e partire dall'articolo precedente. Inoltre, per la pratica abbiamo bisogno di 5 tavole di verità operazioni logiche che io altamente raccomandato riscrivere a mano.

NON ricordare, NON stampare, vale a dire, ancora una volta comprendi e riscrivi su carta con la tua stessa mano - in modo che siano davanti ai tuoi occhi:

– tavolo NON;
- tavola I;
– tavolo operatorio;
– tabella delle implicazioni;
- Tabella delle equivalenze.

È molto importante. In linea di principio, sarebbe conveniente numerarli "Tabella 1", "Tabella 2", ecc., ma ho ripetutamente sottolineato il difetto di questo approccio - come si suol dire, in una fonte la tabella sarà la prima e nell'altra - cento e prima. Pertanto, useremo nomi "naturali". Continuiamo:

In effetti, hai già familiarità con il concetto di formula logica. Darò uno standard, ma piuttosto spiritoso definizione: formule le algebre proposizionali si chiamano:

1) eventuali affermazioni elementari (semplici);

2) se e sono formule, allora anche le formule sono espressioni della forma
.

Non ci sono altre formule.

In particolare, una formula è qualsiasi operazione logica, come la moltiplicazione logica. Presta attenzione al secondo punto: lo consente ricorsivo modo per "creare" una formula arbitrariamente lunga. Nella misura in cui sono formule, allora è anche una formula; poiché e sono formule, quindi - anche una formula, ecc. Qualsiasi affermazione elementare (sempre per definizione) può inserire la formula più di una volta.

Formula nonè, ad esempio, un record - e qui c'è un'ovvia analogia con "spazzatura algebrica", da cui non è chiaro se i numeri debbano essere aggiunti o moltiplicati.

La formula logica può essere pensata come funzione logica. Scriviamo la stessa congiunzione in forma funzionale:

Le affermazioni elementari in questo caso svolgono anche il ruolo di argomenti (variabili indipendenti), che nella logica classica possono assumere 2 valori: vero o Falso. In quanto segue, per comodità, chiamerò a volte semplici affermazioni variabili.

La tabella che descrive la formula logica (funzione) è chiamata, come già accennato, tavola di verità. Per favore - un'immagine familiare:

Il principio di formazione della tavola della verità è il seguente: "all'input" è necessario elencare tutte le combinazioni possibili verità e bugie che le proposizioni elementari (argomenti) possono accettare. In questo caso, la formula include due affermazioni ed è facile scoprire che esistono quattro di queste combinazioni. "All'uscita", otteniamo i corrispondenti valori logici dell'intera formula (funzione).

Devo dire che l'“uscita” qui si è rivelata “in un solo passaggio”, ma nel caso generale la formula logica è più complessa. E in tali "casi difficili" è necessario osservare ordine di esecuzione delle operazioni logiche:

- si esegue prima la negazione;
- secondo - congiunzione;
- quindi - disgiunzione;
- poi l'implicazione;
- e, infine, la priorità più bassa ha l'equivalente.

Quindi, ad esempio, la voce implica che devi prima eseguire la moltiplicazione logica, quindi - addizione logica:. Proprio come nell'algebra "ordinaria": "prima moltiplichiamo e poi aggiungiamo".

L'ordine delle azioni può essere modificato nel solito modo - parentesi:
- qui si esegue innanzitutto la disgiunzione e solo successivamente un'operazione più “forte”.

Probabilmente tutti lo capiscono, ma per ogni evenienza un pompiere: e questo due diversi formule! (sia formalmente che sostanzialmente)

Facciamo una tabella di verità per la formula. Questa formula include due affermazioni elementari e "all'input" dobbiamo elencare tutte le possibili combinazioni di uno e zero. Per evitare confusione e incongruenze, accettiamo di elencare le combinazioni rigorosamente in quest'ordine (che in realtà uso di fatto fin dall'inizio):

La formula include due operazioni logiche e, in base alla loro priorità, prima di tutto, è necessario eseguire negazione dichiarazioni. Bene, neghiamo la colonna "pe": trasformiamo le unità in zeri e gli zeri in unità:

Nella seconda fase, esaminiamo le colonne e le applichiamo O operazione. Guardando un po' avanti, dirò che la disgiunzione è permutabile (e sono la stessa cosa), e quindi le colonne possono essere analizzate nel solito ordine, da sinistra a destra. Quando si esegue l'addizione logica, è conveniente utilizzare il seguente ragionamento applicato: “Se ci sono due zeri mettiamo zero, se almeno un'unità ne mettiamo uno”:

Il tavolo della verità è costruito. E ora ricordiamo la buona vecchia implicazione:

…con attenzione-attenzione…guarda le colonne finali…. In algebra proposizionale, tali formule sono chiamate equivalente o identico:

(tre linee orizzontali sono l'icona dell'identità)

Nella prima parte della lezione, ho promesso di esprimere l'implicazione attraverso operazioni logiche di base, e il compimento della promessa non si è fatto attendere! Coloro che lo desiderano possono dare un significato significativo all'implicazione (es. "Se piove, fuori è umido") e analizzare indipendentemente l'affermazione equivalente.

Formuliamo definizione generale : si chiamano le due formule equivalente (identico), se assumono gli stessi valori per qualsiasi insieme di valori incluso in queste formule variabili (dichiarazioni elementari). Lo dicono anche "le formule sono equivalenti se le loro tavole di verità sono le stesse", ma questa frase non mi piace molto.

Esercizio 1

Crea una tabella di verità per la formula e assicurati che l'identità che conosci sia vera.

Ripetiamo la procedura per risolvere il problema:

1) Poiché la formula include due variabili, ci saranno 4 possibili insiemi di zeri e uno in totale. Li scriviamo nell'ordine sopra specificato.

2) Le implicazioni sono "più deboli" delle congiunzioni, ma si trovano tra parentesi. Compiliamo la colonna, mentre è conveniente utilizzare il seguente ragionamento applicato: "se zero segue da uno, allora mettiamo zero, in tutti gli altri casi - uno". Quindi, compila la colonna per l'implicazione e, allo stesso tempo, Attenzione!– colonne e dovrebbero essere analizzati “da destra a sinistra”!

3) E nella fase finale, compila la colonna finale. E qui è conveniente argomentare così: "se ce ne sono due nelle colonne, ne mettiamo uno, in tutti gli altri casi - zero".

E infine, controlliamo la tabella della verità equivalenze .

Equivalenze di base dell'algebra proposizionale

Ne abbiamo appena conosciuti due, ma la questione, ovviamente, non si limita a loro. Ci sono parecchie identità e ne elencherò le più importanti e famose:

Commutatività della congiunzione e commutatività della disgiunzione

commutativitàè una permutazione:

Familiarità dalle regole di prima elementare: “Da un riarrangiamento di fattori (termini), il prodotto (somma) non cambia”. Ma nonostante tutta l'apparente elementarietà di questa proprietà, è tutt'altro che sempre vero, in particolare non è commutativo moltiplicazione matriciale (in generale, non possono essere riorganizzati), ma prodotto incrociato di vettori– in modo anticommutativo (la permutazione dei vettori comporta un cambio di segno).

E inoltre, anche qui voglio sottolineare il formalismo della logica matematica. Quindi, per esempio, le frasi "Lo studente ha superato l'esame e ha bevuto" e "Lo studente ha bevuto e superato l'esame" diversa dal punto di vista del contenuto, ma indistinguibile dal punto di vista della verità formale. ... Ognuno di noi conosce questi studenti e per motivi etici non nomineremo nomi specifici =)

Associatività della moltiplicazione logica e dell'addizione

Oppure, se "stile scolastico" è una proprietà associativa:

Proprietà di distribuzione

Tieni presente che nel 2° caso non sarà corretto parlare di "aprire le parentesi", in un certo senso, ecco una "finzione" - dopotutto, possono essere rimosse del tutto: la moltiplicazione è un'operazione più forte.

E ancora: queste proprietà apparentemente "banali" sono lontane dall'essere soddisfatte in tutto sistemi algebrici, e, inoltre, richiedono una prova (di cui parleremo molto presto). A proposito, la seconda legge distributiva non vale nemmeno nella nostra algebra “ordinaria”. E senza dubbio:

Legge di idempotenza

Cosa fare, latino....

Solo qualche principio di una psiche sana: "Io e io siamo me", "Io o io sono anche me" =)

Ed ecco alcune identità simili:

... beh, qualcosa che ho anche riattaccato ... così domani puoi svegliarti con un dottorato di ricerca =)

La legge della doppia negazione

Bene, qui l'esempio con la lingua russa si suggerisce già: tutti sanno benissimo che due particelle "non" significano "sì". E per esaltare la colorazione emotiva della negazione, vengono spesso usati tre “non”:
- anche con una piccola prova ha funzionato!

Leggi di assorbimento

- Era un ragazzo? =)

Nella giusta identità, le parentesi possono essere omesse.

Le leggi di De Morgan

Supponiamo un insegnante severo (di cui conosci anche il nome :)) fa un esame se - Lo studente ha risposto alla prima domanda e – Lo studente ha risposto alla seconda domanda. Poi la dichiarazione che lo afferma Alunno non passato l'esame, sarà equivalente alla dichiarazione - Alunno non ha risposto alla prima domanda o alla 2a domanda.

Come notato sopra, le equivalenze sono soggette a prova, che viene normalmente eseguita utilizzando tabelle di verità. Infatti, abbiamo già dimostrato le equivalenze che esprimono l'implicazione e l'equivalenza, ed ora è il momento di fissare la tecnica per risolvere questo problema.

Proviamo l'identità. Poiché include una singola istruzione, sono possibili solo due opzioni "all'input": uno o zero. Successivamente, assegniamo una singola colonna e applichiamo ad essa regola E:

Di conseguenza, "all'uscita" si ottiene una formula la cui verità coincide con la verità dell'affermazione. L'equivalenza è stata dimostrata.

Sì, questa dimostrazione è primitiva (e qualcuno dirà che è "stupido"), ma un tipico insegnante di logica di matematica scuoterà la sua anima per lui. Pertanto, anche cose così semplici non dovrebbero essere trattate con disprezzo.

Ora assicuriamoci, ad esempio, della validità della legge di de Morgan.

Per prima cosa, creiamo una tabella di verità per il lato sinistro. Poiché la disgiunzione è tra parentesi, prima di tutto la eseguiamo, dopodiché annulliamo la colonna:

Successivamente, compiliamo una tabella di verità per il lato destro. Anche qui tutto è trasparente: prima di tutto eseguiamo negativi più "forti", quindi applichiamo alle colonne regola E:

I risultati combaciavano, quindi l'identità è provata.

Qualsiasi equivalenza può essere rappresentata come formula identicamente vera. Significa che PER QUALSIASI insieme iniziale di zeri e uno"all'uscita" si ottiene rigorosamente l'unità. E c'è una spiegazione molto semplice per questo: poiché le tavole di verità e coincidono, allora, ovviamente, sono equivalenti. Uniamo, ad esempio, le parti sinistra e destra dell'identità di de Morgan appena dimostrata per equivalenza:

Oppure, in modo più compatto:

Compito 2

Dimostra le seguenti equivalenze:

B)

Breve soluzione alla fine della lezione. Non siamo pigri! Cerca non solo di creare tabelle di verità, ma anche chiaramente formulare conclusioni. Come ho notato di recente, trascurare le cose semplici può essere molto, molto costoso!

Continuiamo a conoscere le leggi della logica!

Sì, assolutamente giusto - stiamo già lavorando con loro con potenza e main:

Vero a , è chiamato formula identicamente vera o la legge della logica.

In virtù del precedente giustificato passaggio dall'equivalenza alla formula identicamente vera, tutte le identità sopra elencate sono leggi della logica.

Formula che assume un valore Menzogna a qualsiasi insieme di valori delle variabili in esso incluse, è chiamato formula identicamente falsa o contraddizione.

Un caratteristico esempio di contraddizione degli antichi greci:
Nessuna affermazione può essere vera e falsa allo stesso tempo.

La dimostrazione è banale:

"Output" ha ricevuto esclusivamente zeri, quindi la formula è davvero identico falso.

Tuttavia, ogni contraddizione è anche una legge della logica, in particolare:

È impossibile trattare un argomento così vasto in un solo articolo, e quindi mi limiterò a poche leggi in più:

Legge del mezzo escluso

- nella logica classica, qualsiasi affermazione è vera o falsa e non esiste una terza via. “Essere o non essere” – questo è il dilemma.

Crea la tua tabella della verità e assicurati che lo sia identicamente vero formula.

Legge di contrapposizione

Questa legge è stata attivamente esagerata quando abbiamo discusso l'essenza condizione necessaria, ricordare: "Se fuori è umido durante la pioggia, ne consegue che se fuori è asciutto, sicuramente non ha piovuto".

Ne consegue anche da questa legge che se è giusto è dritto teorema, quindi l'istruzione, che a volte viene chiamata opposto teorema.

Se è vero inversione teorema, allora in virtù della legge di contrapposizione vale anche il teorema, rovescio opposto:

E torniamo ai nostri esempi significativi: per le affermazioni - un numero è divisibile per 4, - un numero è divisibile per 2 giusto dritto e opposto teoremi, ma falsi inversione e rovescio opposto teoremi. Per la formulazione "adulta" del teorema di Pitagora, tutte e 4 le "direzioni" sono vere.

Legge del sillogismo

Anche un classico del genere: “Tutte le querce sono alberi, tutti gli alberi sono piante, quindi tutte le querce sono piante”.

Ebbene, anche qui vorrei sottolineare il formalismo della logica matematica: se il nostro severo Insegnante pensa che un certo Allievo sia una quercia, allora dal punto di vista formale questo Allievo è certamente una pianta =) ... anche se, se pensaci, può essere anche informale = )

Facciamo una tabella di verità per la formula. In conformità con la priorità delle operazioni logiche, aderiamo al seguente algoritmo:

1) eseguire le implicazioni e . In generale, puoi eseguire immediatamente la 3a implicazione, ma è più conveniente con essa (e consentito!) scoprilo un po' più tardi

2) si applicano alle colonne regola E;

3) ora eseguiamo;

4) e nel passaggio finale applicare l'implicazione alle colonne E .

Sentiti libero di controllare il processo con l'indice e il medio :))


Dall'ultima colonna, penso che tutto sia chiaro senza commenti:
, che doveva essere dimostrato.

Compito 3

Scopri se è una legge della logica seguente formula:

Breve soluzione alla fine della lezione. Sì, e quasi dimenticavo: accettiamo di elencare gli insiemi iniziali di zeri e uno esattamente nello stesso ordine della dimostrazione della legge del sillogismo. Naturalmente, le linee possono essere riorganizzate, ma questo renderà molto difficile riconciliarsi con la mia soluzione.

Conversione di formule booleane

Oltre al loro scopo "logico", le equivalenze sono ampiamente utilizzate per trasformare e semplificare le formule. In parole povere, una parte dell'identità può essere scambiata con un'altra. Quindi, ad esempio, se ti imbatti in un frammento in una formula logica, allora, secondo la legge dell'idempotenza, puoi (e dovresti) scrivere semplicemente invece di esso. Se vedi , allora, secondo la legge di assorbimento, semplifica la notazione in . Eccetera.

Inoltre, c'è un'altra cosa importante: le identità sono valide non solo per proposizioni elementari, ma anche per formule arbitrarie. Per esempio:

, dove ce ne sono (complesso quanto vuoi) formule.

Trasformiamo, ad esempio, l'implicazione complessa (1a identità):

Applichiamo, inoltre, allo scaglione la legge “complessa” de Morgan, mentre, per la priorità delle operazioni, è la legge, dove :

Le parentesi possono essere rimosse, perché all'interno c'è una congiunzione più “forte”:

Bene, con la commutatività, in generale, tutto è semplice: non è nemmeno necessario designare nulla ... qualcosa è affondato nella mia anima la legge del sillogismo :))

Pertanto, la legge può essere riscritta in una forma più complessa:

Parla ad alta voce la catena logica “con una quercia, un albero, una pianta”, e capirai che il significato sostanziale della legge non è affatto cambiato dal riordino delle implicazioni. È che la formulazione è diventata più originale.

Come allenamento, semplifichiamo la formula.

Da dove cominciare? Innanzitutto, per capire l'ordine delle azioni: qui la negazione è applicata a un'intera parentesi, che è "fissata" con l'affermazione da una congiunzione "leggermente più debole". In sostanza, abbiamo davanti a noi il prodotto logico di due fattori: . Delle due operazioni rimanenti, l'implicazione ha la priorità più bassa, e quindi l'intera formula ha la seguente struttura: .

Di norma, al primo passaggio (passi) eliminare l'equivalenza e l'implicazione (se sono) e ridurre la formula a tre operazioni logiche di base. Cosa posso dire…. Logicamente.

(1) Usiamo l'identità . E nel nostro caso.

Questo è solitamente seguito da "smontaggio" con staffe. Prima l'intera soluzione, poi i commenti. Per non ottenere "olio di burro", userò le "solite" icone di uguaglianza:

(2) Applichiamo la legge di de Morgan alle parentesi esterne, dove .

Teorema di assorbimento scritto in due forme: disgiuntivo e

congiuntivo, rispettivamente:

A + AB \u003d A (16)

A(LA + B)=A (17)

Dimostriamo il primo teorema. Prendiamo la lettera A tra parentesi:

MA + AB \u003d A (1 + B)

Secondo il teorema (3) 1 + B = 1, quindi

LA(1 + B) = LA 1 = LA

Per dimostrare il secondo teorema, espandiamo le parentesi:

A(LA + B) = LA A + AB = LA + AB

Il risultato è un'espressione che è stata appena dimostrata.

Consideriamo diversi esempi di applicazione del teorema di assorbimento per

semplificazione delle formule booleane.

Teorema di incollaggio ha anche due forme: disgiuntiva e

congiuntivale:

Dimostriamo il primo teorema:

poiché secondo i teoremi (5) e (4)

Per dimostrare il secondo teorema, apriamo le parentesi:

Secondo il teorema (6), quindi:

Secondo il teorema di assorbimento (16) A + AB \u003d A

Il teorema di assorbimento, come il teorema di incollaggio, viene applicato durante la semplificazione

formule booleane, ad esempio:

Il teorema di De Morgan collega tutte e tre le operazioni di base dell'algebra booleana

Disgiunzione, congiunzione e inversione:

Il primo teorema si legge come segue: l'inversione di una congiunzione è una disgiunzione

inversioni. In secondo luogo, l'inversione di una disgiunzione è la congiunzione di inversioni. Puoi dimostrare i teoremi di Morgan usando le tabelle di verità per i lati sinistro e destro.

Vale anche il teorema di De Morgan di più variabili:

Lezione 5

Invertire espressioni complesse

Il teorema di De Morgan si applica non solo alle singole congiunzioni

o disgiunzioni, ma anche ad espressioni più complesse.

Troviamo l'inverso dell'espressione AB + CD , rappresentato come una disgiunzione di congiunzioni. L'inversione sarà considerata completa se i segni negativi sono solo al di sopra delle variabili. Introduciamo la notazione: AB = X;

CD=Y poi

Trova e sostituisci nell'espressione (22):

In questo modo:

Consideriamo un'espressione presentata in forma congiuntiva:

(LA + B) (C + RE)

Troviamo la sua inversione nella forma

Introduciamo la notazione: A + B = X; C + D \u003d Y, poi

Trovali e sostituiscili nell'espressione

In questo modo:

Quando si invertono espressioni complesse, è possibile utilizzare la regola seguente. Per trovare l'inversione, è necessario sostituire i segni di congiunzione con segni di disgiunzione e i segni di disgiunzione con segni di congiunzione e inserire inversioni su ciascuna variabile:

Il concetto di funzione booleana

IN nel caso generale, una funzione (lat. functio - performance, compliance,

mappatura) è una certa regola (legge), secondo la quale ogni elemento dell'insieme X, che è l'intervallo della variabile indipendente X, viene assegnato un determinato elemento dell'insieme F,

che è inteso come l'intervallo di valori della variabile dipendente F . Nel caso di funzioni booleane X=F = (0,1). La regola con cui viene specificata la funzione può essere qualsiasi formula booleana, ad esempio:

Simbolo F ecco una funzione che, come gli argomenti di A, AVANTI CRISTO, variabile binaria.

Gli argomenti sono variabili indipendenti, possono assumere qualsiasi valore - 0 o 1. La funzione F - variabile dipendente. Il suo significato è completamente determinato dai valori delle variabili e dalle connessioni logiche tra di esse.

La caratteristica principale di una funzione è che per determinarne il valore, nel caso generale, è necessario conoscere i valori di tutti gli argomenti da cui dipende. Ad esempio, la funzione precedente dipende da tre argomenti A, V, S. Se prendiamo A = 1, otteniamo

cioè si ottiene una nuova espressione, diversa da zero o

unità. Lascia ora IN= 1. Allora

cioè, in questo caso, non è noto se la funzione è uguale a zero o uno.

Infine, prendiamo DA= 0. Quindi otteniamo: F = 0. Quindi, se prendiamo A = 1 nell'espressione originale, IN= 1, DA = 0, la funzione assumerà un valore zero: f= 0.

Ritenere nozione di insieme di valori variabili .

Se a tutti gli argomenti da cui dipende la funzione vengono assegnati determinati valori, allora si parla di un insieme di valori di argomento che possono essere

chiamalo semplicemente un set. L'insieme dei valori degli argomenti è una sequenza di zeri e uno, ad esempio 110, dove la prima cifra corrisponde al primo argomento, la seconda al secondo e la terza al terzo. Ovviamente, è necessario concordare in anticipo quale sia il primo, il secondo o, diciamo, il quinto argomento. Per fare ciò, è conveniente utilizzare la disposizione alfabetica delle lettere.

Ad esempio, se

quindi secondo l'alfabeto latino il primo argomento è R, secondo -

Q, Terzo - X, quarto - U. Quindi, dall'insieme dei valori degli argomenti, è facile

trova il valore della funzione. Sia dato, per esempio, l'insieme 1001. Secondo il suo

voci cioè sul set 1001 data funzioneè uguale a uno.

Si noti ancora che l'insieme dei valori degli argomenti è l'insieme

zeri e uno. I numeri binari sono anche insiemi di zeri e uno.

Ciò solleva la domanda: gli insiemi possono essere considerati binari

numeri? È possibile, e in molti casi è molto conveniente, soprattutto se binario

convertire il numero in decimale. Ad esempio, se

A = 0, B = 1, C = 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

cioè, l'insieme dato ha il numero 6 in decimale.

Se vuoi trovare i valori degli argomenti per numero decimale, allora

Noi entriamo sequenza inversa: prima convertiamo il numero decimale in binario, quindi aggiungiamo tanti zeri a sinistra in modo che il numero totale di cifre sia uguale al numero di argomenti, dopodiché troviamo i valori degli argomenti.

Sia, ad esempio, necessario trovare i valori degli argomenti A, B, C, D, E, F dall'insieme con il numero 23. Convertiamo il numero 23 nel sistema binario usando il metodo

dividendo per due:

Di conseguenza, otteniamo 23 10 = 10111 2 . Questo è un numero di cinque cifre e in totale

ci sono sei argomenti, quindi uno zero deve essere scritto a sinistra:

23 10 = 010111 2 . Da qui troviamo:

A = 0, B = 1, C = 0, D = 1, E = 1, F = 1.

Quanti set ci sono se il numero è noto P argomenti? Ovviamente, tanti quanti sono i numeri binari di n bit, cioè 2 n

Lezione 6

Impostazione di una funzione booleana

Conosciamo già un modo. È analitico, cioè sotto forma di un'espressione matematica che utilizza variabili binarie e operazioni logiche. Oltre ad esso, ci sono altri modi, il più importante dei quali è tabulare. La tabella elenca tutto possibili insiemi valori degli argomenti e per ogni insieme viene indicato il valore della funzione. Tale tabella è chiamata tabella di corrispondenza (verità).

Sull'esempio della funzione

Scopriamo come creare una tabella di ricerca per esso.

La funzione dipende da tre argomenti A, B, C. Pertanto, nella tabella

fornire tre colonne per argomenti A,B,C e una colonna per i valori della funzione f. A sinistra della colonna A, è utile posizionare un'altra colonna. In esso scriveremo numeri decimali, che corrispondono agli insiemi se visti come numeri binari a tre cifre. Questo decimale

la colonna viene introdotta per comodità di lavorare con la tabella, quindi, in linea di principio,

può essere trascurato.

Compiliamo la tabella. La riga con il numero LLC recita:

A = B = C = 0.

Definiamo il valore della funzione su questo insieme:

Nella colonna f scriviamo zero nella riga con l'insieme 000.

Successivo set: 001, cioè e.A = B = 0, C = 1. Trova il valore della funzione

su questo set:

Sul set 001 la funzione è uguale a 1, quindi nella colonna f della riga con

numero 001 annotiamo l'unità.

Allo stesso modo, calcoliamo i valori delle funzioni su tutti gli altri insiemi e

completare l'intera tabella.