Концепцията за булева функция

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

Булевата функция (от n променливи) е произволно преобразуване на формата

тези. булева функция е дефинирана върху множеството от всички n-елементни (за n ≥ 0) последователности (или n-компонентни кортежи) от нули и единици и приема две възможни стойности: 0 и 1.

Тясно свързани с концепцията за булева функция са понятията за булева константа и булева променлива*.

* В литературата по теория на булевите функции традиционно се използва терминът "булева променлива" (в женски род). Но тъй като в този комплекс от учебници терминът "променлива" (среден род) е приет, ние навсякъде пишем "булева променлива".

Булева константа е индивидуална константа с диапазон от . По този начин има две булеви константи: 0 и 1. По дефиниция се приема, че всяка булева константа също е булева функция на 0 променливи (което е доста подобно на определението за нулева операция).

Boolean е индивидуална променлива с диапазон от , т.е. това е променлива, която може да приема само две стойности: 0 и 1 (подобно на това как реалната променлива приема произволна реална стойност, а комплексната променлива приема произволна комплексна стойност). След това, използвайки концепцията за булева променлива, можем да дефинираме булевата функция (6.1), като напишем y = f(x1, . , xn), в която всяка булева променлива xi, i = 1,n, и функцията f приемат две възможни стойности: 0 и 1. Променливите x1, . ,xn се наричат променливи на булевата функция uu f. Фиксирайки стойност αi ∈ на всяка променлива xi, получаваме кортежα ˜ = (α1, . , αn) от множеството n , нареченомножество от стойности на променливи x1, . ,xn, и съответната стойност на функцията f(α1, . , αn), която ще бъде стойността на променливата y, свързана с дадените стойности на променливите x1, . ,xn.

Подчертаваме, че освен ако не е посочено друго, в израза y = f(x1, . , xn) се приема, че всички променливи са различни по двойки, т.е. преминаване през всеки набор независимо от другите.

Концепцията за булева функция може да получи различно значение чрез разбиране на елементите на набор като стойности на истината, а именно чрез разбиране на единица като „истина“ и нула като „фалшива“. Такива стойности на истината могат, както знаем, да бъдат свързани с всяко предложение. Тогава булевата функция е някакво правило, което позволява всеки фиксиран набор от истинностни стойности, т.е. набор от стойности на булеви променливи, за да сравните една или друга истинска стойност. По този начин например може да се изчисли стойността на истината на сложно твърдение, съставено от прости твърдения по определени правила. Сложни твърдения от този вид се съставят с помощта на логически операции: "или", "и", "ако. тогава" и т.н. Горната логическа интерпретация на булевата функция дава възможност да се разбере защо булева променлива често се нарича булева променлива*, а булева функция се нарича логическа функция (или функция от алгебрата на логиката).

* Традиционен термин: "булева променлива".

В допълнение, според дефиницията, булева функция от n променливи е преобразуване на n-тата декартова степен на множеството в множеството, т.е. не е нищо друго освен n-арна множествена операция. По този начин логическата интерпретация на булева функция е в съответствие с нейната алгебрична интерпретация: булевата функция е операция (в алгебричния смисъл на думата) върху набор от стойности на истинатастойности. Тогава понятието за логическа операция, което беше въведено по-рано (виж 1.1), се оказва частен случай на общото понятие за операция (виж 2.1).

Нека означим сP множеството от всички булеви функции (за всички възможни стойности n от броя на променливите), а сP 2,n множеството от всички булеви функции на n променливи (за фиксирани n).

От дефиницията следва, че

И така, домейнът на всяка булева функция от n променливи е множеството n, т.е. булев куб* с размерност n. Елементите на булев куб n се наричат n-мерни булеви вектори (или множества). Броят на всички елементи на булевия куб n е 2 n . Елементите на булевия куб също ще се наричат негови върхове.

* Използват се и термините: единичен куб с размерност n, n-мерен единичен куб; вместо думата "куб" казват и "хиперкуб".

Булевият куб n е носител на булевата алгебраB n (често ще използваме същата нотация за съответния булев куб). Но във всяка булева алгебраA = (A, ∨, ∧,0,1 ), както е известно, отношението на естествен ред ≤ е дефинирано така, че за произволни a, b ∈ A отношението a ≤ b е валидно тогава и само ако a ∨ b = b (или, еквивалентно, a ∧ b = a). Спомнете си (вижте 3.4), че булевата алгебраB n не е нищо друго освен n-та декартова степен на двуелементната булева алгебраB = (, ∨, ∧, 0, 1). Съгласно общия принцип за разширяване на връзката на реда към декартовото произведение на множества (вижте 4.5), за произволни две множества α ˜ = (α1, . , αn) и β ˜ = (β1, . , βn) отB n, имаме α ˜ ≤ β ˜ . ако и само ако αi ≤ βi за всяко i = 1,n, т.е. αi ∨ βi = βi.

С други думи, α ˜ ≤ β ˜ тогава и само ако αi = βi или αi = 0 и βi = 1 завсяко i = 1,n. Ако има поне едно i, за което αi = 0 и βi = 1, тогава строгото неравенство α ˜ ˜ е в сила. По-специално, ако има точно едно такова i, тогава множеството β ˜ доминира множеството α ˜ , тъй като е ясно, че в този случай е невъзможно да се намери множество γ ˜ такова, че α ˜ ˜ ˜ .

Пример 6.1. В булев куб B 4

(0, 0, 1, 1) n ще се наричабулев ред.

Булев куб като подреден набор може да бъде представен като диаграма на Хасе. На фиг. 6.1 показва диаграми на Хасе за булеви кубове с размери от 0 до 4.

Друг начин за визуализиране на булев куб се основава на факта, че диаграмата на Хасе на всяко крайно подредено множество A може да бъде дадена като насочена мрежа, така че дъгата от върха, свързан с елемента x ∈ A,

води до върха, свързан с елемент y ∈ A, ако и само ако y доминира над x и всяко ниво на мрежата се състои от върхове, свързани по двойки с несравними елементи от множеството A (т.е. елементи от някаква антиверига в A). Входовете на мрежата са свързани с минималните, а изходите - с максималните елементи на А.

Всяко ниво на мрежата, представляваща булевия кубB n, се състои от всички върхове, съответстващи на набори, които имат точно k (0 ≤ k ≤ n) ненулеви компоненти (множеството от всички такива набори за фиксирано k се нарича k-слой на булевия кубB n).

Мрежа, представляваща булев куб с размерност n, ще се нарича булева n-мрежа или просто булева мрежа, ако измерението е пропуснато. Тъй като булевият куб има най-малкия елемент, нулевия набор, и най-големия елемент, идентификационния набор, всяка булева мрежа има един вход (маркиран с нулевия набор) и уникален изход (маркиран с идентификационния набор).

На фиг.6.2 показва изображението на булевия кубB 4 като мрежа.

В допълнение към булевия ред, също така е полезно да се въведе друга връзка на реда на булевия куб, която ще наричаме лексикографски ред, използвайки нотацията ⪯. Нека α ˜ , β ˜ ∈B n (за произволно фиксирано n). По дефиниция, α ˜ ⪯ β ˜ if

Всяка от сумите в неравенството (6.2) не е нищо друго освен представяне на някакво естествено число (включително нула) в двоичната бройна система (с брой цифри, равен на фиксирана размерност n). Всеки булев вектор може да се разглежда като такова представяне (двоичен код) на естествено число и лексикографският ред на булевия кубB n не е нищо друго освен естествения числов ред на подмножество от множеството ℕ ∪ (при условие, че числата са дадени в двоичната бройна система)*.

* По-стриктно: подреденото множество (B n, ⪯) е изоморфно на подмножеството ⊂ ℕ ∪ с естествен числов ред.

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

Пример 6.2. Множеството (1, 0, 1) като двоичен код на числото 5 = = 1 2 2 +0 2 1 + 1 2 0 е лексикографски по-голямо от множеството (0, 1, 1), което служи като двоичен код на числото 3, но тези набори не са сравними по отношение на булевия ред. #

Лексикографският ред обаче играе спомагателна роля при изучаването на булеви кубове. По-специално, когато се изобразяват булеви кубове (под формата на диаграми на Хасе или под формата на мрежа), е обичайно да се подреждат върховете на всеки k-слой в лексикографски ред (във възходящ ред - отляво надясно или отгоре надолу). Навсякъде по-долу, когато обсъждаме булевия куб като подреден набор, имаме предвид булевия ред.

Лице на булев куб с размери n-k, където n е размерността на булевия куб, се нарича набор от набори, които имат поне k идентични компоненти.

Ребро с размерност n - k вB n ще бъде определено, ако фиксираме k числа 1 ≤ i1 ≤ . ≤ ik ≤ n и k константи σ1. σk от множеството. След това лицето, обозначено катоB n,i1. ik σ1. σk е множеството от всички α ∈B n, така че αi1 = σ1. σik = σk. В този случай наборът от числа (i1, . ik) се нарича посока на лицетоB n,i1. ik σ1. σk. Ако числото n -k, което определя размерността на лицето, е равно на 1 (т.е. k = n -1), тогава такова лице се нарича ръб на булевия кубB n. По този начин ръбът е набор, състоящ се от два набора, единият от които доминира над другия (в смисъла на булев ред). С други думи, тези два набора се различават един от друг по стойността на един компонент. За ръба на булевия куб ще използваме нотацията [a, ,8], като приемем, че второто множество доминира над първото. Всеки връх на булев куб се счита за лице с размерност 0.

Може да се покаже, че броят на всички лица с размерност n - k е 2 k · C k n .

Пример 6.3. В четиримерен булев кубВ 4, посоката на триизмерно лице се задава чрез фиксиране на едно от числата от 1 до 4 и фиксиране на стойността на съответния компонент на множествата, принадлежащи на това лице. На фиг. 6.1 ръбовете на лицетоB 4.1 0 са подчертани. Това лице се състои от осем комплекта:

(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),

(0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1).

На фиг. 6.1 са избрани всички ръбове на булевия кубB 3, имащи посока (1, 2). #

Лицата на булев куб, които имат една и съща посока, се наричат паралелни. Две успоредни лицаB n,i1. ik σ1. σk иВ n,i1. ik γ1. γk се наричасъседи, ако едно от множествата (σ1, . σk) и (γ1, . γk) доминира другото. На фиг. 6.1 лицаB 4,1 0 иB 4,1 1 са съседни, както и лица (ръбове)B 3,1,2 0,0 иB 3,1,2 0,1 . Но ребраB 3,1,2 1,0 иB 3,1,2 0,1 не са съседни.

Лесно е да се досетите, че всяко лице с размерност n - k на булевия кубB n сам по себе си е булев куб с размерност n - k и следователно съдържа 2 n-k върха. По-точно, това лице, заедно с отношението на реда, индуцирано от булевия ред наB n, ще бъде подредено множество и изоморфно на булевия кубB n-k (с булев ред върху него). Следователно, често лицата на булев куб се наричат подкубове.

В същото време булевият кубB n е изоморфно вграден (по няколко начина) в булев куб с по-високо измерение, а именно, булевият кубB n е вграден (като лице) в булевия кубB n+k, k ≥ 1, по толкова начини, колкото има различни n-измерни лица в a куб с размерност n + k, т.е. 2 k · C k n+k начина. Така едномерният кубB е вграден в двумернияB 2 по четири начина - като една от четирите му едномерни стени (т.е. като един от четирите му ръба, виж Фиг. 6.1).

Нека се съгласим оттук нататък да изписваме конкретни набори (елементи от булевия куб със съответната размерност) без скоби и запетаи, т.е. ще пишем не (0, 1, 0, 1), а 0101 (освен ако, разбира се, това не води до недоразумения).

Накрая намираме кардиналността на множеството от всички булеви функции на n променливи за фиксирано n. Тъй като всяка булева функция преобразува набор от 2 n елемента в набор от два елемента и е известно, че кардиналността на набора от всички преобразувания от набор от n елемента към набор от m елемента е m n , тогава кардиналността на набораP 2,n е 2 2 n . INПо-специално, за n = 0 получаваме две булеви константи: 0 и 1.

Забележка 6.1. Тъй като булева функция от n променливи е в същото време n-арна операция върху множеството, тогава за n = 0 получаваме нулева операция. Ясно е, че има две нулеви операции върху множеството: 0 и 1, които не са нищо друго освен нулата и идентичността на двуелементната булева алгебра.