Enemmistötoiminto - Majority function

On Boolen logiikan , enemmistö toiminto (kutsutaan myös mediaani operaattori ) on Boolen funktio , joka on epätosi, kun puoli tai enemmän argumentit ovat vääriä ja totta muuten, eli funktion arvo on yhtä suuri kuin arvo enemmistö tuloista. Edustamalla todellisia arvoja 1 ja vääriä arvoja 0, voimme käyttää (reaaliarvoista) kaavaa:

${\ displaystyle \ langle p_ {1}, \ dots, p_ {n} \ rangle = \ operaattorinimi {Enemmistö} \ left (p_ {1}, \ dots, p_ {n} \ right) = \ left \ lfloor {\ frac {1} {2}}+{\ frac {\ left (\ sum _ {i = 1}^{n} p_ {i} \ right) -1/2} {n}} \ right \ rfloor.}$

Kaavan "−1/2" katkaisee siteet nollien hyväksi, kun argumenttien lukumäärä n on parillinen. Jos termi "−1/2" jätetään pois, kaavaa voidaan käyttää funktiolle, joka katkaisee siteet niiden hyväksi.

Useimmat sovellukset pakottavat tarkoituksella parittoman määrän tuloja, joten niiden ei tarvitse käsitellä kysymystä siitä, mitä tapahtuu, kun täsmälleen puolet tuloista on 0 ja täsmälleen puolet tuloista on 1. Muutamat järjestelmät, jotka laskevat enemmistöfunktion parillisella luvulla Tulot ovat usein puolueellisia kohti "0"-ne tuottavat "0", kun täsmälleen puolet tuloista on 0-esimerkiksi 4-tuloisella enemmistöportilla on 0-lähtö vain, kun sen tuloissa on kaksi tai useampia 0: ta. Joissakin järjestelmissä solmio voidaan katkaista satunnaisesti.

Boolen piirit

Enemmistö portti on looginen portti käytetään piirin monimutkaisuuden ja muita sovelluksia Boolen piirejä . Enemmistöportti palauttaa arvon tosi ja vain, jos yli 50% sen syötteistä on tosi.

Esimerkiksi täysi summain , siirtoulostulo löydetään soveltamalla enemmistöfunktiota kolmeen tuloon, vaikka usein tämä summaimen osa jaetaan useisiin yksinkertaisempiin loogisiin portteihin.

Monissa järjestelmissä on kolminkertainen modulaarinen redundanssi ; he käyttävät enemmistöfunktiota enemmistölogiikan dekoodaukseen virheenkorjauksen toteuttamiseksi .

Merkittävä tulos piirin monimutkaisuudessa väittää, että enemmistöfunktiota ei voida laskea alleeksponentiaalisen kokoisilla AC0 -piireillä.

Ominaisuudet

Mistään x , y , ja z , kolmiosaisessa mediaani operaattori ⟨ x , y , z ⟩ täyttää seuraavat yhtälöt.

• ⟨ X , y , y ⟩ = y
• ⟨ X , y , z ⟩ = ⟨ z , x , y ⟩
• ⟨ X , y , z ⟩ = ⟨ x , z , y ⟩
• ⟨⟨ x , w , y ⟩, w , z ⟩ = ⟨ x , w , ⟨ y , w , z ⟩⟩

Abstrakti järjestelmä, joka täyttää nämä aksioomina, on mediaanialgebra .

Monotoniset kaavat enemmistölle

Jos n = 1, mediaanioperaattori on vain yhtenäinen identiteettitoiminto x . Jos n = 3, kolmiosainen mediaanioperaattori voidaan ilmaista käyttämällä konjunktiota ja disjunktiota muodossa xy + yz + zx . Huomattavasti tämä lauseke tarkoittaa samaa toimintoa riippumatta siitä, tulkitaanko symboli + sisällyttäväksi vai poissulkevaksi tai .

Mielivaltaiselle n: lle on olemassa yksitoikkoinen kaava suurimmalle osalle kokoa O ( n ^5.3 ). Tämä todistetaan todennäköisyysmenetelmällä . Näin ollen tämä kaava ei ole rakentava.

On olemassa lähestymistapoja nimenomaiselle kaavalle suurimmalle osalle polynomikokoja:

• Ota mediaani lajittelujärjestelmästä , jossa jokainen vertailu- ja vaihtovaijeri on yksinkertaisesti TAI-portti ja JA-portti. Ajtai - Komlós - Szemerédi (AKS) rakentaminen on esimerkki.
• Yhdistä pienten enemmistöpiirien lähdöt.
• Derandomize Valiant -todistus yksitoikkoisesta kaavasta.

Huomautuksia

Viitteet

• Knuth, Donald E. (2008). Johdanto yhdistelmäalgoritmeihin ja Boolen funktioihin . Tietokoneohjelmoinnin taito . 4a . Upper Saddle River, NJ: Addison-Wesley. s. 64–74. ISBN 978-0-321-53496-5.

Katso myös

Media, joka liittyy Wikimedia Commonsin enemmistötoimintoihin

• Boolen algebra (rakenne)
• Boolen algebrat määritelty kanonisesti
• Boyer – Moore -enemmistöäänestysalgoritmi
• Enemmistöongelma (matkapuhelinautomaatti)