BOOLEAANSE ALGEBRA: GESCHIEDENIS, STELLINGEN EN POSTULATEN, VOORBEELDEN - WISKUNDE - 2024

De Booleaanse algebra of Booleaanse algebra is een algebraïsche notatie die wordt gebruikt voor de behandeling van binaire variabelen. Het omvat de studies van elke variabele die slechts twee mogelijke uitkomsten heeft, complementair en wederzijds exclusief. Variabelen waarvan de enige mogelijkheid waar of onwaar is, juist of onjuist, aan of uit, vormen bijvoorbeeld de basis van de studie van Booleaanse algebra.

Booleaanse algebra vormt de basis van digitale elektronica, waardoor het tegenwoordig behoorlijk aanwezig is. Het wordt beheerst door het concept van logische poorten, waar bekende bewerkingen in traditionele algebra met name worden beïnvloed.

Bron: pexels.com

Geschiedenis

Booleaanse algebra werd in 1854 geïntroduceerd door de Engelse wiskundige George Boole (1815 - 1864), een autodidactische geleerde van die tijd. Zijn bezorgdheid kwam voort uit een bestaand geschil tussen Augustus De Morgan en William Hamilton, over de parameters die dit logische systeem definiëren.

George Boole stelde dat de definitie van de numerieke waarden 0 en 1 op het gebied van logica overeenkomt met respectievelijk de interpretatie Niets en Universe.

George Boole's bedoeling was om, door middel van de eigenschappen van algebra, de uitdrukkingen van propositielogica te definiëren die nodig zijn om met variabelen van het binaire type om te gaan.

In 1854 werden de belangrijkste delen van de Booleaanse algebra gepubliceerd in het boek "Een onderzoek naar de wetten van het denken waarop de wiskundige theorieën over logica en waarschijnlijkheid zijn gebaseerd".

Deze merkwaardige titel zou later worden samengevat als "De wetten van het denken" ("De wetten van het denken"). De titel werd beroemd vanwege de onmiddellijke aandacht die het kreeg van de wiskundige gemeenschap van die tijd.

In 1948 paste Claude Shannon het toe op het ontwerp van bistabiele elektrische schakelcircuits. Dit diende als een inleiding op de toepassing van Booleaanse algebra binnen het gehele elektronisch-digitale schema.

Structuur

De elementaire waarden in dit type algebra zijn 0 en 1, die respectievelijk overeenkomen met FALSE en TRUE. De fundamentele bewerkingen in Booleaanse algebra zijn 3:

- EN werking of combinatie. Vertegenwoordigd door een punt (.). Synoniem van het product.

- OF operatie of disjunctie. Vertegenwoordigd door een kruisje (+) Synoniem van de som.

- GEEN operatie of negatie. Vertegenwoordigd door het voorvoegsel NOT (NOT A). Het staat ook bekend als een aanvulling.

Als in een set A2 wetten van interne samenstelling worden gedefinieerd als product en som (. +), Wordt er gezegd dat de triple (A. +) een Booleaanse algebra is als en slechts als die triple voldoet aan de voorwaarde dat het een rooster is distributief.

Om een ​​distributief rooster te definiëren, moet aan de distributievoorwaarden worden voldaan tussen de gegeven bewerkingen:

. is distributief ten opzichte van de som + a. (b + c) = (a. b) + (a. c)

+ is distributief met betrekking tot het product. a + (b. c) = (a + b). (a + c)

De elementen waaruit set A bestaat, moeten binair zijn en dus universe- of ongeldige waarden hebben.

Toepassingen

Het belangrijkste toepassingsscenario is de digitale tak, waar het dient om de circuits te structureren die de betrokken logische bewerkingen vormen. De kunst van het vereenvoudigen van schakelingen ten gunste van het optimaliseren van processen is het resultaat van de juiste toepassing en praktijk van Booleaanse algebra.

Van het uitwerken van elektrische panelen, het doorgeven van gegevens, tot het komen tot programmeren in verschillende talen, we vinden Booleaanse algebra regelmatig terug in allerlei digitale toepassingen.

Booleaanse variabelen komen veel voor in de structuur van programmeren. Afhankelijk van de gebruikte programmeertaal, zullen er structurele bewerkingen in de code zijn die deze variabelen gebruiken. De voorwaarden en argumenten van elke taal laten Booleaanse variabelen toe om de processen te definiëren.

Postulaten

Er zijn stellingen die de structurele logische wetten van de Booleaanse algebra beheersen. Op dezelfde manier zijn er postulaten om de mogelijke resultaten in verschillende combinaties van binaire variabelen te kennen, afhankelijk van de uitgevoerde operatie.

Som (+)

De OR- operator waarvan het logische element de unie (U) is, wordt als volgt gedefinieerd voor binaire variabelen:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Product (.)

De AND- operator waarvan het logische element het snijpunt (∩) is, wordt als volgt gedefinieerd voor binaire variabelen:

0. 0 = 0

0. 1 = 0

een . 0 = 0

een . 1 = 1

Tegenover (NIET)

De NOT- operator waarvan het logische element het complement (X) 'is, wordt als volgt gedefinieerd voor binaire variabelen:

NIET 0 = 1

NIET 1 = 0

Veel van de postulaten verschillen van hun tegenhangers in conventionele algebra. Dit komt door het domein van de variabelen. Het toevoegen van universe-elementen in de Booleaanse algebra (1 + 1) kan bijvoorbeeld niet het conventionele resultaat 2 opleveren, omdat het niet tot de elementen van de binaire set behoort.

Stellingen

Regel van nul en eenheid

Elke eenvoudige bewerking waarbij een element met de binaire variabelen betrokken is, wordt gedefinieerd:

0 + A = A

1 + A = 1

0. A = 0

een . A = A

Gelijke krachten of onmacht

Bewerkingen tussen gelijke variabelen worden gedefinieerd als:

A + A = A

NAAR . A = A

Aanvulling

Elke bewerking tussen een variabele en zijn complement wordt gedefinieerd als:

A + NIET A = 1

NAAR . NIET A = 0

Involutie of dubbele ontkenning

Elke dubbele ontkenning wordt als de natuurlijke variabele beschouwd.

NIET (NIET A) = A

Commutatief

A + B = B + A; Commutativiteit van de som.

NAAR . B = B. NAAR ; Commutativiteit van het product.

Associatief

A + (B + C) = (A + B) + C = A + B + C; Associativiteit van de som.

NAAR . (B. C) = (A. B). C = A. B. C; Productassociativiteit.

Distributief

A + (B. C) = (A + B). (A + C); Distributiviteit van de som ten opzichte van het product.

NAAR . (B + C) = (A. B) + (A + C); Distributiviteit van het product ten opzichte van de som.

Wetten van absorptie

Er zijn veel absorptiewetten tussen meerdere referenties, waarvan enkele bekend zijn:

NAAR . (A + B) = EEN

NAAR . (NIET A + B) = A. B.

NIET A (A + B) = NIET A. B.

(A + B). (A + NIET B) = A

A + A. B = A

A + NIET A. B = A + B

NIET A + A. B = NIET A + B

NAAR . B + A. NIET B = A

Morgan's stelling

Het zijn transformatiewetten, die paren variabelen behandelen die interageren tussen de gedefinieerde bewerkingen van Booleaanse algebra (+.).

NIET (A. B) = NIET A + NIET B

NIET (A + B) = NIET A. NIET B

A + B = NIET (NIET A + NIET B)

NAAR . B = NIET (NIET A. NIET B)

Dualiteit

Alle postulaten en stellingen bezitten het vermogen van dualiteit. Dit houdt in dat door het uitwisselen van de variabelen en bewerkingen de resulterende propositie wordt geverifieerd. Dat wil zeggen, bij het uitwisselen van 0 voor 1 en AND voor OF of vice versa; er wordt een uitdrukking gemaakt die ook volledig geldig is.

Bijvoorbeeld als het postulaat wordt ingenomen

een . 0 = 0

En dualiteit wordt toegepast

0 + 1 = 1

Een ander volkomen geldig postulaat wordt verkregen.

Karnaugh kaart

De Karnaugh-kaart is een diagram dat in Booleaanse algebra wordt gebruikt om logische functies te vereenvoudigen. Het bestaat uit een tweedimensionale opstelling vergelijkbaar met de waarheidstabellen van propositionele logica. De gegevens van de waarheidstabellen kunnen direct op de Karnaugh-kaart worden vastgelegd.

De Karnaugh-kaart is geschikt voor processen van maximaal 6 variabelen. Voor functies met een groter aantal variabelen wordt het gebruik van software aanbevolen om het proces te vereenvoudigen.

Het werd in 1953 voorgesteld door Maurice Karnaugh en werd opgericht als een vast hulpmiddel op het gebied van Booleaanse algebra, omdat de implementatie het menselijk potentieel synchroniseert met de noodzaak om Booleaanse uitdrukkingen te vereenvoudigen, een belangrijk aspect in de vloeibaarheid van digitale processen.

Voorbeelden

Booleaanse algebra wordt gebruikt om logische poorten in een circuit te verminderen, waarbij de prioriteit is om de complexiteit of het niveau van het circuit naar de laagst mogelijke uitdrukking te brengen. Dit komt door de rekenvertraging die elke poort veronderstelt.

In het volgende voorbeeld zullen we de vereenvoudiging van een logische uitdrukking tot zijn minimumuitdrukking zien, met behulp van de stellingen en postulaten van de Booleaanse algebra.

NIET (AB + A + B). NIET (A + NIET B)

NIET. NIET (A + NIET B); Factoring A met een gemeenschappelijke factor.

NIET. NIET (A + NIET B); Volgens stelling A + 1 = 1.

NIET (A + B). NIET (A + NIET B); door stelling A. 1 = EEN

(NIET A. NIET B). ;

Volgens de stelling van Morgan NOT (A + B) = NOT A. NIET B

(NIET A. NIET B). (NIET A. B); Door dubbele negatiestelling NOT (NOT A) = A

NIET A. NIET B. NIET A. B; Algebraïsche groepering.

NIET A. NIET A. NIET B. B; Commutativiteit van product A. B = B. NAAR

NIET A. NIET B. B; Volgens stelling A. A = A

NIET A. 0; Volgens stelling A. NIET A = 0

0; Volgens stelling A. 0 = 0

NAAR . B. C + NIET A + A. NIET B. C

NAAR . C. (B + NIET B) + NIET A; Factoring (A. C) met een gemeenschappelijke factor.

NAAR . C. (1) + NIET A; Volgens stelling A + NIET A = 1

NAAR . C + NIET A; Volgens de regel van nulstelling en eenheid 1. A = A

NIET A + C ; Volgens de wet van Morgan A + NIET A. B = A + B

Voor deze oplossing moet de wet van Morgan worden uitgebreid om te definiëren:

NIET (NIET A). C + NIET A = NIET A + C

Omdat NOT (NOT A) = A door involutie.

Vereenvoudig de logische functie

NIET A. NIET B. NIET C + NIET A. NIET B. C + NIET A. NOT C tot zijn minimumuitdrukking

NIET A. NIET B. (NIET C + C) + NIET A. NIET C; Factoring (NIET A. NIET B) met gemeenschappelijke factor

NIET A. NIET B. (1) + NIET A. NIET C; Volgens stelling A + NIET A = 1

(NIET A. NIET B) + (NIET A. NIET C); Volgens de regel van nulstelling en eenheid 1. A = A

NIET A (NIET B + NIET C); Factoring NOT A met een gemeenschappelijke factor

NIET A. NIET (B. C); Volgens de Morgan-wetten NIET (A. B) = NIET A + NIET B

NIET volgens de wetten van Morgan NIET (A. B) = NIET A + NIET B

Elk van de 4 vetgedrukte opties vertegenwoordigt een mogelijke oplossing om het niveau van het circuit te verlagen

Vereenvoudig de logische functie tot zijn eenvoudigste vorm

(A. NIET B. C + A. NIET B. B. D + NIET A. NIET B). C

(A. NIET B. C + A. 0. D + NIET A. NIET B). C; Volgens stelling A. NIET A = 0

(A. NIET B. C + 0 + NIET A. NIET B). C; Volgens stelling A. 0 = 0

(A. NIET B. C + NIET A. NIET B). C; Volgens stelling A + 0 = A

NAAR . NIET B. C. C + NIET A. NIET B. C; Door distributiviteit van het product ten opzichte van de som

NAAR . NIET B. C + NIET A. NIET B. C; Volgens stelling A. A = A

NIET B. C (A + NIET A) ; Factoring (NIET B. C) met gemeenschappelijke factor

NIET B. C (1); Volgens stelling A + NIET A = 1

NIET B. C; Volgens de regel van nulstelling en eenheid 1. A = A

Referenties

1. Booleaanse algebra en zijn toepassingen J. Eldon Whitesitt. Continental Publishing Company, 1980.
2. Wiskunde en techniek in de informatica. Christopher J. Van Wyk. Instituut voor Computerwetenschappen en Technologie. Nationaal Bureau of Standards. Washington, DC 20234
3. Wiskunde voor informatica. Eric Lehman. Google Inc.
   V Thomson Leighton Afdeling Wiskunde en Computerwetenschappen en AI-laboratorium, Massachussetts Institute of Technology; Akamai Technologies.
4. Elementen van abstracte analyse. Mícheál O'Searcoid PhD. Afdeling wiskunde. Hogeschool Dublin, Beldfield, Dublind.
5. Inleiding tot de logica en de methodologie van de deductieve wetenschappen. Alfred Tarski, New York Oxford. Oxford Universiteit krant.