Абстрактни булеви функции

Булева функция(илилогическа функция, илифункция на логическа алгебра) наnпроменливи — в дискретната математика, преобразуванеBn→B, къдетоB= —булев набор. Булевите елементи на набора 1 и 0 обикновено се интерпретират като булеви стойности "true" и "false", въпреки че като цяло те се считат за формални символи, които не носят конкретно значение. Неотрицателно цяло числоnсе нарича арност или локалност на функцията, в случай наn= 0, булевата функция ставабулева константа. Елементите на декартовото произведениеBnсе наричат ​​Булеви вектори. Наборът от всички булеви функции на произволен брой променливи често се означава сP2, а наnпроменливи сP2(n). Булевите функции са кръстени на математика Джордж Бул.

1. Основна информация

Всяка функция на булева арностnе напълно дефинирана чрез задаване на нейните стойности в нейната област на дефиниране, тоест на всички булеви вектори с дължинаn. Броят на тези вектори е 2n. Тъй като една булева функция може да приеме 0 или 1 за всеки вектор, броят на всичкиn-арни булеви функции е 2 2n. Следователно в този раздел се разглеждат само най-простите и най-важни булеви функции. Фактът, че всяка булева функция е дадена от краен масив от данни, прави възможно представянето им под формата на таблици. Такива таблици се наричат ​​таблици на истината и в общия случай имат формата:

Почти всички булеви функции на малки арити (0, 1, 2 и 3) са се развили исторически и имат специфични имена. Ако стойността на функцията не зависи от една от променливите (т.е., строго погледнато, за всеки два булеви вектора, които се различават само по стойността на тозипроменлива, стойността на функцията върху тях е една и съща), тогава тази променлива се наричадуми.

1.1. Нуларни функции

Когатоn= 0, броят на булевите функции се свежда до две 2 2 0 = 2 1 = 2, като първата от тях е идентично равна на 0, а втората е 1. Те ​​се наричат ​​булеви константи - еднаква нула и еднаква единица.

1.2. Унарни функции

Заn= 1, броят на булевите функции е 2 2 1 = 2 2 = 4. Дефиницията на тези функции е дадена в следващата таблица.

Таблица със стойности на булеви функции от една променлива:

Имена на булеви функции от една променлива:

1.3. Двоични функции

Приn= 2, броят на булевите функции е 2 2² = 2 4 = 16.

Таблица със стойности на булеви функции от две променливи:

Имена на булеви функции от две променливи:

1.4. Троични функции

Приn= 3, броят на булевите функции е 2 2³ = 2 8 = 256. Някои от тях са дефинирани в следната таблица:

Имена на булеви функции на три променливи:

2. ПЪЛНИ СИСТЕМИ ОТ БУЛЕВИ ФУНКЦИИ

2.1. Суперпозиция и затворени класове функции

Резултатът от изчисляването на булева функция може да се използва като един от аргументите на друга функция. Резултатът от такава операция на суперпозиция може да се разглежда като нова булева функция със собствена таблица на истината. Например функция (суперпозиция на конюнкция, дизюнкция и две отрицания) ще съответства на следната таблица:

Казва се, че набор от функции е затворен при операцията на суперпозиция, ако всяка суперпозиция на функции от даден набор също е включена в същия набор. Затворените набори от функции се наричат ​​още затворени класове.

Най-простите примери за затворени класове на булеви функции са множествотоx> , състоящ се от една идентична функция или набор, всички функции от които са идентично равни на нула, независимо от техните аргументи. Множеството от функции и множеството от всички унарни функции също са затворени. Но обединението на затворените класове може вече да не е такова. Например, чрез комбиниране на класовете и можем да използваме суперпозиция, за да получим константата 1, която отсъстваше в оригиналните класове.

Разбира се, множествотоP2 от всички възможни булеви функции също е затворено.

2.2. Идентичност и двойственост

Две булеви функции са идентични една на друга, ако приемат еднакви стойности за всякакви идентични набори от аргументи. Идентичността на функциите f и g може да бъде записана например по следния начин:

Разглеждайки таблиците на истината на булевите функции, е лесно да получите следните идентичности:

И проверката на създадените таблици за някои суперпозиции ще даде следните резултати:

(дистрибутивност на конюнкция и дизюнкция)

Една функция се нарича двойна функция, ако . Лесно е да се покаже, че в това равенство f и g могат да бъдат разменени, т.е. функциите f и g са двойствени една на друга. От най-простите функции константите 0 и 1 са двойствени една спрямо друга, а двойствеността на конюнкция и дизюнкция следва от законите на Де Морган. Идентичната функция, подобно на функцията за отрицание, е двойствена на себе си.

Ако в булева идентичност заменим всяка функция с нейната двойна, отново получаваме правилната идентичност. В горните формули е лесно да се намерят двойни двойки една на друга.

2.3. Завършеност на системата, критерий на Пост

Система от булеви функции се наричапълна, ако е възможно да се конструира тяхната суперпозиция, която е идентична с всяка друга предварително дефинирана функция. Те също така казват, че затварянето на тази система съвпада снаборP2.

Американският математик Емил Пост въвежда следните затворени класове булеви функции:

  • Функции, които запазват константатаT0 иT1 ;
  • Самодуални функцииS;
  • Монотонни функцииM;
  • Линейни функцииL.

Той доказа, че всеки затворен клас от булеви функции, който не съвпада сP2, се съдържа изцяло в един от тези пет така нареченипредварителни класа, но нито един от петте не се съдържа изцяло в обединението на останалите четири. Така критерият на Пост за пълнотата на една система се свежда до установяване дали цялата система се съдържа изцяло в един от предварително завършените класове. Ако за всеки клас в системата има функция, която не е включена в нея, тогава такава система ще бъде пълна и с помощта на функциите, включени в нея, ще бъде възможно да се получи всяка друга булева функция.

Имайте предвид, че има функции, които не са включени в нито един от класовете на Post. Всяка такава функция сама по себе си образува цялостна система. Примерите включват удар на Шефър или стрела на Пиърс.

3. Представяне на булеви функции

Теоремата на Пост отваря пътя за представяне на булеви функции по синтактичен начин, който в някои случаи е много по-удобен от таблиците на истината. Отправната точка тук е да се намери някаква пълна система от функции. Тогава всяка булева функция може да бъде представена чрез някакъв термин в сигнатурата Σ , която в този случай също се нарича формула. По отношение на избраната система от функции е полезно да знаете отговорите на следните въпроси:

  • Как да изградим формула, представяща тази функция?
  • Как да проверим дали две различни формули са еквивалентни, тоест задават едно и същофункция?
  • По-специално: има ли начин да се редуцира произволна формула до нейната еквивалентнаканоничнаформа, така че две формули да са еквивалентни тогава и само ако техните канонични форми са еднакви?
  • Как може дадена функция да се използва за конструиране на формула, която я представя с определени зададени свойства (например най-малък размер) и възможно ли е това?

    • Положителните отговори на тези и други въпроси значително повишават приложната стойност на избраната система от функции.

    3.1. Дизюнктивна нормална форма (DNF)

    Проста връзкаиликонюнкцияе връзка на някакъв краен набор от променливи или техните отрицания, като всяка променлива се среща най-много веднъж.Дизюнктивната нормална формаилиDNFе дизюнкцията на простите връзки. Елементарна връзка

    • правилно, ако всяка променлива се появява най-много веднъж в нея (включително отрицание);
    • complete, ако всяка променлива (или нейното отрицание) влиза в нея точно 1 път;
    • монотонен, ако не съдържа отрицания на променливи.

    Например - е DNF.

    Перфектната дизюнктивна нормална формаилиSDNFпо отношение на даден краен набор от променливи е DNF, чиято всяка конюнкция включва всички променливи от това множество и в същия ред. Например: .

    Лесно е да се види, че всяка булева функция съответства на някаква DNF и на функция, различна от идентичната нула, дори на SDNF. За да направите това, достатъчно е да намерите в таблицата на истината на тази функция всички булеви вектори, на които нейната стойност е равна на 1, и за всеки такъв вектор да конструирате връзка , където . Дизюнкцияот тези връзки е SDNF на оригиналната функция, тъй като на всички булеви вектори нейните стойности съвпадат със стойностите на оригиналната функция. Например за импликация резултатът е , което може да се опрости до .

    3.2. Конюнктивна нормална форма (CNF)

    Конюнктивната нормална форма1(CNF) се дефинира двойно спрямо DNF.Проста дизюнкцияилидизюнкцияе дизюнкция на една или повече променливи или техните отрицания, където всяка променлива се среща най-много веднъж. CNF е конюнкция на прости дизюнкции.

    Перфектната конюнктивна нормална форма(PCNF), по отношение на даден краен набор от променливи, е такава CNF, в която всяка дизюнкция включва всички променливи от този набор и в същия ред. Тъй като (C)CNF и (C)DNF са взаимно дуални, свойствата на (C)CNF повтарят всички свойства на (C)DNF, грубо казано, "точно обратното".

    CNF може да се преобразува в неговия еквивалент DNF чрез отваряне на скоби съгласно правилото:

    който изразява дистрибутивността на конюнкцията спрямо дизюнкцията. След това е необходимо да се премахнат повтарящите се променливи или техните отрицания във всяка връзка, както и да се изхвърлят от дизюнкцията всички връзки, в които променливата се среща заедно с нейното отрицание. В този случай резултатът няма да бъде непременно SDNF, дори ако оригиналният CNF е SKNF. По подобен начин човек винаги може да премине от DNF към CNF. За да направите това, използвайте правилото

    изразяващи дистрибутивността на дизюнкцията по отношение на конюнкцията. Резултатът трябва да се трансформира по описания по-горе начин, като се замени думата "конюнкция" с "дизюнкция" и обратно.

    3.3. Полиноми на Жегалкин

    Полиномът на Жегалкин е форма на представяне на логическа функция с помощта на функциятаЖегалкин (Изключителен ОР). За да получите полинома на Жегалкин, направете следното:

    1. Вземете DNF функции
    2. Заменете всички ИЛИ с Изключително ИЛИ
    3. Във всички условия заменете елементите с отрицание с конструкцията: ("елемент" "изключително ИЛИ" 1)
    4. Отворете скобите според правилата на алгебрата на Жегалкин и дайте еднакви термини по двойки

    Литература

    • Гаврилов Г.П., Сапоженко А.А.Сборник задачи по дискретна математика. - М .: Наука, 1969.
    • Кузнецов О.П., Аделсон-Велски Г.М.Дискретна математика за инженер. - М .: "Енергия", 1980. - 344 с.
    • Марченков С.С.Затворени класове на булеви функции. - М .: Физматлит, 2000.
    • Яблонски С.В.Въведение в дискретната математика. - М .: Наука, 1986.
    • Алексеев В. Б. Дискретна математика (курс лекции, II семестър). Comp. А. Д. Поспелов
    изтегли Това есе е базирано на статия от българската Уикипедия.Синхронизирането е извършено 13.07.11 21:42:07Свързани резюмета: Булеви операции, R-функции, Функционално изследване, Борелови функции, Хесиански функции, Непрекъснати функции, Атомни функции, Изпълнителни функции, Логически функции.