Axioma lui Wolfram este rezultatul cercetărilor efectuate de Stephen Wolfram [1] în căutarea celei mai scurte axiome dintr-o ecuație, echivalentă cu axiomele algebrei booleene (sau logicii propoziționale ). Rezultatul [2] al căutării sale a fost o axiomă cu șase operații logice „NAND” (cunoscută și sub numele de stroke Schaeffer ) și trei variabile, care este echivalentă cu algebrei booleene:
((a | b) | c) | (a | ((a | c) | a)) = cSemnează | este indicată operația logică „NU-ȘI” ( stroke Scheffer ), iar propoziția X | Y înseamnă că X și Y nu sunt compatibile, adică nu sunt adevărate în același timp. Această funcție booleană este numită după Henry Schaeffer , care a demonstrat că logica restului operațiilor de algebră booleană („NU”, „ȘI”, „SAU”, etc.) poate fi exprimată folosind doar operația „NU-ȘI” ( stroke Schaeffer ), care formează o bază pentru spațiul funcțiilor booleene în două variabile.
Wolfram a selectat 25 de identități Schaeffer, constând din cel mult 15 elemente (excluzând imaginile în oglindă), care nu au modele necomutative de dimensiune mai mică sau egală cu 4 variabile [3] .
Cercetătorii știau despre existența unei axiome cu o singură ecuație echivalentă cu algebrei booleene, care poate fi exprimată în termeni de disjuncție, negație și primul Schaeffer. Wolfram a dovedit că nu există o înregistrare mai scurtă a unei astfel de axiome decât cea pe care a găsit-o. Dovada este dată în cartea sa „A New Kind of Science” și are două pagini. Astfel, axioma lui Wolfram este cea mai simplă (după numărul de operații și variabile) axiomă cu o ecuație necesară pentru a reproduce algebra booleană.
Identitățile lui Schaeffer au fost obținute independent în diferite moduri și publicate într-un memorandum tehnic [4] în iunie 2000, confirmând corespondența cu rezultatul lui Wolfram, care a găsit axioma în 1999 în timp ce își pregătea cartea. Raportul tehnic [5] oferă, de asemenea, cea mai scurtă axiomă a unei perechi de ecuații, care este echivalentă cu algebrei booleene.