Логикалық кеңейту теоремасы - Booles expansion theorem - Wikipedia

Бульдің кеңею теоремасы, жиі деп аталады Шеннонды кеңейту немесе ыдырау, болып табылады жеке басын куәландыратын: , қайда кез келген Логикалық функция, айнымалы, толықтауыш болып табылады , және және болып табылады аргументпен тең және дейін сәйкесінше.

Шарттары және кейде оң және теріс деп те аталады Шеннонның кофакторларысәйкесінше құрметпен . Бұл есептелген функциялар шектеу оператор, және (қараңыз бағалау (логика) және ішінара қолдану ).

Ол «буль алгебрасының негізгі теоремасы» деп аталды.[1] Теориялық маңыздылығымен қатар, оған жол ашылды екілік шешім схемалары, қанағаттанушылықты шешетіндер, және басқа да көптеген техникалар компьютерлік инженерия және ресми тексеру цифрлық тізбектер

Теореманың тұжырымы

Теореманы анықтаудың айқын тәсілі:

Өзгерістер мен салдарлар

XOR-нысаны
Мәлімдеме сонымен қатар орындалады дизъюнкция «+» таңбасы ауыстырылады XOR оператор:
Қос нысаны
Шеннон кеңеюінің қос нысаны бар (онымен байланысты XOR формасы жоқ):

Әр аргумент үшін қайталанған өтініш Өнімдердің жиынтығы Логикалық функцияның канондық түрі (SoP) . Мысалы үшін бұл болар еді

Сол сияқты, қос форманы қолдану келесіге әкеледі Сомалардың өнімі (PoS) канондық формасы ( тарату заңы туралы аяқталды ):

Кофакторлардың қасиеттері

Кофакторлардың сызықтық қасиеттері:
Логикалық функция үшін F ол екі логикалық функциялардан тұрады G және H мыналар дұрыс:
Егер содан кейін
Егер содан кейін
Егер содан кейін
Егер содан кейін
Унат емес функциялардың сипаттамалары:
Егер F Бұл unate функциясы және...
Егер F ол кезде оң
Егер F ол кезде жағымсыз

Кофакторлармен жұмыс

Логикалық айырмашылық:
Логикалық айырмашылық немесе буль туындысы x әріпіне қатысты F функциясының мәні келесідей анықталады:
Әмбебап сандық бағалау:
F-нің әмбебап сандық өлшемі келесідей анықталады:
Бар сандық бағалау:
F-тің экзистенциалдық сандық өлшемі келесідей анықталады

Тарих

Джордж Бул бұл кеңейтуді өзінің «Кез-келген логикалық символдармен байланысты функцияны кеңейту немесе дамыту» ұсынысы ретінде ұсынды Ойлау заңдары (1854),[2] және оны «Буль және ХІХ ғасырдың басқа логикалары кеңінен қолданды».[3]

Клод Шеннон бұл кеңейту туралы, басқа логикалық сәйкестіктермен бірге, 1948 жылғы мақалада,[4] және жеке тұлғаның коммутациялық желілік интерпретацияларын көрсетті. Компьютер дизайны мен коммутация теориясының әдебиеттерінде сәйкестілік көбінесе Шеннонға қате жатқызылған.[3]

Коммутациялық тізбектерге қолдану

  1. Екілік шешім схемалары осы теореманы жүйелі түрде қолданудан шығыңыз
  2. Логикалық кез-келген функцияны a коммутациялық тізбек базалық иерархияны қолдану мультиплексор осы теореманы бірнеше рет қолдану арқылы.

Ескертулер

  1. ^ Пол С. Розенблум, Математикалық логика элементтері, 1950, б. 5
  2. ^ Джордж Бул, Ойлау заңдылықтарын зерттеу: логикалық және ықтималдықтың математикалық теориялары негізделеді, 1854, б. 72 Google Books-тағы толық мәтін
  3. ^ а б Фрэнк Мархэм Браун, Логикалық пайымдау: логикалық теңдеулердің логикасы, 2-басылым, 2003, б. 42
  4. ^ Клод Шеннон, «Екі терминалды коммутациялардың синтезі», Bell System техникалық журналы 28:59–98, толық мәтін, б. 62

Сондай-ақ қараңыз

Сыртқы сілтемелер