Բուլյան ֆունկցիա

Բուլյան ֆունկցիա (կամ տրամաբանական ֆունկցիա, կամ հանրահաշվական տրամաբանության ֆունկցիա)^[1], n արգումենտից պատկերումը Bⁿ → B (դիսկրետ մաթեմատիկայում), որտեղ B = {0,1}-ն հանդիսանում է բուլյան բազմություն։ Բուլյան բազմության {1, 0} տարրերը սովորաբար մեկնաբանվում են, որպես «ճիշտ» և «սխալ» տրամաբանական արժեքներով, չնայած ընդհանուր դեպքում նրանք դիտարկվում են որպես ֆորմալ սիմվոլներ, որոնք չեն կրում ինչ-որ առանձնակի իմաստ։ Ոչ բացասական ամբողջ n թիվը անվանում են ֆունկցիայի տարածք կամ առնոստ, n = 0 դեպքում բուլյան ֆունկցիան դառնում է բուլյան հաստատուն։ Դեկարտյան արտադրյալի տարրերը՝ Bn անվանում են բուլյան վեկտորներ։ Բոլոր բուլյան ֆունկցիաների բազմությունը կախված ցանկացած քանակի արգումենտներից հաճախ նշանակվում է P2-ով, իսկ կախված n արգումենտներից՝ P2(n): Փոփոխականները, որոնք ընդունում են արժեքներ բուլյան բազմությունից, անվանում են բուլյան փոփոխականներ։ Բուլյան ֆունկցիաները կոչվել են ի պատիվ մաթեմատիկոս Ջորջ Բուլի։

Բուլյան ֆունկցիաների հետ աշխատելիս տեղի է ունենում լրիվ վերացարկում բովանդակային իմաստից, որը հանդես է եկել հանրահաշվական ասույթներում^[2]։ Դրանից բացի բուլյան ֆունկցիաների և հանրահաշվական բանաձևերի ասույթներում կարելի է սահմանել փոխադարձ-միարժեք համապատասխանություն, եթե^[3].

սահմանենք փոխադարձ-միարժեք համապատասխանություն բուլյան փոփոխականների և ենթադիրքային փոփոխականների միջև,
սահմանենք կապ բուլյան ֆունկցիաների և տրամաբանական շղթաների միջև,
թողնենք փակագծերի դասավորությունը առանց փոփոխության։

Հիմնական տեսություն[խմբագրել | խմբագրել կոդը]

n առնոստի կամայական բուլյան ֆունկցիա ամբողջության որոշվում է իրեն տրված արժեքներով իր որոշման տիրույթի վրա, այսինքն n երկարություն ունեցող բոլոր բուլյան վեկտորների վրա։ Նման վեկտորների քանակը հավասար է 2n-ի։ Քանի որ ամեն վեկտորի վրա բուլյան ֆունկցիան կարող է ընդունել կամ 1 կամ 0, ապա բոլոր n-ային բուլյան ֆունկցիաների քանակը հավասար է 2(2n): Այդ իսկ պատճառով այս բաժնում դիտարկվում են միայն պարզագույն և կարևորագույն բուլյան ֆունկցիաները։

Գործնականորեն փոքրագույն առնոստների բուլյան ֆունկցիաները (0, 1, 2 և 3) դասավորվել են պատմականորեն և ունեն իրենց կոնկրետ անունները։ Եթե ֆունկցիայի արժեքը կախված չէ որևիցե փոփոխականից (այսինքն կոպիտ ասած կամայական երկու բուլյան վեկտորների համար, որոնք իրարից տարբերվում են միայն այդ փոփոխականով՝ ֆունկցիայի արժեքը նրանց վրա կրկնվում է), ապա այդ փոփոխականը անվանվում է ոչ էական կամ ֆիկտիվ։

Ճշմարտության աղյուսակներ[խմբագրել | խմբագրել կոդը]

Բուլյան ֆունկցիան տրվում է վերջավոր թվով արժեքների հավաքածուներով, ինչը թույլ է տալիս ներկայացնել այն ճշմարտության աղյուսակների տեսքով, օրինակ՝^[4]


x₁	x₂	…	x_n-1	x_n	f(x₁,x₂,…,x_n)
0	0	…	0	0	0
0	0	…	0	1	0
0	0	…	1	0	1
0	0	…	1	1	0
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
1	1	…	0	0	1
1	1	…	0	1	0
1	1	…	1	0	0
1	1	…	1	1	0

Նուլյար ֆունկցիաներ[խմբագրել | խմբագրել կոդը]

n = 0 դեպքում բուլյան բունկցիաների քանակը հավասարվում է 2^2⁰ = 2¹ = 2, նրանցից առաջինը նույնաբար հավասար է 0, իսկ երկրորդը՝ 1: Նրանց անվանում են բուլյան հաստատուններ՝ նույնաբար զրո և նույնաբար մեկ։

Արժեքների աղյուսակը և նուլյար բուլյան ֆունկցիաների անվանումները։

	Արժեք	Նշանակում	Անուն
	0	F0,0 = 0	Նույնաբար զրո
	1	F0,1 = 1	նույնաբար մեկ, կրկնաբանություն

Ունար ֆունկցիաներ[խմբագրել | խմբագրել կոդը]

n = 1 դեպքում բուլյան ֆունկցիաների քանակը հավասարվում է 2^2¹ = 2² = 4: Այդ ֆունկցիաների սահմանումը պարունակվում է հետևյալ աղյուսակում.

Արժեքների աղյուսակը և մեկ փոփոխական պարունակող բուլյան ֆունկիցաների անվանումները.

x₀=x	1	0	Նշանակում	Անուն
0	0	0	F1,0 = 0	նույնաբար զրո
1	0	1	F1,1 = x = ¬x = x' = NOT(x)	բացասում, տրամաբանակ «ոչ», «չ», ինվերտոր, SWAP (փոխանակում)
2	1	0	F1,2 = x	նույնական ֆունկցիա, տրամաբական "այո", կրկնող
3	1	1	F1,3 = 1	նույնաբար մեկ, կրկնաբանություն

Բինար ֆունկցիաներ[խմբագրել | խմբագրել կոդը]

n = 2 դեպքում բուլյան ֆունկցիաների քանակը հավասար է 2^2² = 2⁴ = 16:

Արժեքների աղյուսակը և երկու փոփոխականից կազմված բուլյան ֆունկցիաների անվանումները.

x₀=x	1	0	1	0
x₁=y	1	1	0	0	Ֆունկցիայի նշանակում	Ֆունկցիայի անվանում
0	0	0	0	0	F2,0 = 0	նույնաբար զրո
1	0	0	0	1	F2,1 = x ↓ y = x NOR y = NOR(x,y) = x չէ-կամ y = չէ-կամ(x,y) = NOT(MAX(X,Y))	Պիրսի սլաք - "↓" (Կուայնի դաշույն - "†"), Բաբբայի ֆունկցիա - "°"^[5], չէ-կամ, 2կամ-չէ, հակադիզյունկցիա, մաքսիմումի բացասում
2	0	0	1	0	F2,2 = x > y = x GT y = GT(x,y) = x → y = x ↛ y	համեմատության ֆունկցիան «առաջին օպերանդը մեծ է երկրորդ օպերանդից», ուղիղ իմպլիկացիայի բացասում
3	0	0	1	1	F2,3 = y = y' = ¬y = NOT2(x,y) = ոչ2(x,y)	երկրորդ օպերանդի բացասում (ժխտում, ինվերսիա)
4	0	1	0	0	F2,4 = x < y = x LT y = LT(x,y) = x ← y = x ↚ y	համեմատության ֆունկցիա «առաջին օպերանդը փոքր է երկրորդ օպերանդից», հակառակ իմպլիկացիայի բացասում
5	0	1	0	1	F2,5 = x = x' = ¬x = NOT1(x,y) = ոչ1(x,y)	առաջին օպերանդի բացասում (ժխտում, ինվերսիա)
6	0	1	1	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR(x,y)	համեմատության ֆունկցիան "օպերանդները հավասար չեն", գումարում ըստ մոդուլ 2-ի, բացառող «կամ», Ժեգալկինի գումար^[6]
7	0	1	1	1	F2,7 = x \| y = x NAND y = NAND(x,y) = x ոչ-և y = ոչ-և(x,y) = NOT(MIN(X,Y))	Շեֆֆերի շտրիխ, ոչ-և, 2և-ոչ, հակակոնյունկցիա, մինիմումի ինվերսիա
8	1	0	0	0	F2,8 = x ∧ y = x · y = xy = x & y = x AND y = AND(x,y) = x և y = և(x,y) = min(x,y)	կոնյունկցիա, 2և, մինիմում
9	1	0	0	1	F2,9 = (x ≡ y) = x ~ y = x ↔ y = x EQV y = EQV(x,y)	համեմատության ֆունկցիա «օպերանդները հավասար են», էկվիվալենտություն
10	1	0	1	0	F2,10 = YES1(x,y) = Այո1(x,y) = x	առաջին օպերանդ
11	1	0	1	1	F2,11 = x ≥ y = x >= y = x GE y = GE(x,y) = x ← y = x ⊂ y	համեմատության ֆունկցիա "առաջին օպերանդը փոքր չէ երկրորդ օպերանդից", հակառակ իմպլիկացիա (երկրորդ օպերանդից առաջինին)
12	1	1	0	0	F2,12 = YES2(x,y) = ԱՅՈ2(x,y) = y	երկրորդ օպերանդ
13	1	1	0	1	F2,13 = x ≤ y = x <= y = x LE y = LE(x,y) = x → y = x ⊃ y	համեմատության ֆունկցիա "առաջին օպերանդը ավելի չէ երկրորդ օպերանդից", ուղիղ (նյութական) իմպլիկացիա (առաջին օպերանդից երկրորդին)
14	1	1	1	0	F2,14 = x ∨ y = x + y = x OR y = OR(x,y) = x կամ y = կամ(x,y) = max(x,y)	դիզյունկցիա, 2կամ, մաքսիմում
15	1	1	1	1	F2,15 = 1	նույնաբար մեկ, կրկնաբանություն

Երկու փոփոխականի դեպքում ենթակայուն, միջակայուն և հետնակայուն արտահայտությունները շահավետությամբ համարյա նույնն են։

Թվային տեխնիկայի իմաստը կրող որոշ ֆունկցիաներ, օրինակ համեմատության ֆունկցիա՝ մինիմում և մաքսիմումը չունեն իմաստ տրամաբանության մեջ, քանի որ տրամաբանության մեջ ընդհանուր դեպքում TRUE և FALSE տրամաբանական արժեքները չունեն խիստ կապեր թվային արժեքների հետ (օրինակ՝ TurboBasic'е-ում որոշ հաշվարկներ պարզեցնելու համար TRUE = -1, իսկ FALSE = 0) և հնարավոր չէ որոշել TRUE-ն է ավելի մեծ թե՝ FALSE-ը։

Տերնար ֆունկցիաներ[խմբագրել | խմբագրել կոդը]

n = 3 դեպքում բուլյան ֆունկցիաների քանակը հավասար է 2^(2³) = 2⁸ = 256: Նրանցից որոշները ներկայացված են աղյուսակում։

Արժեքների աղյուսակ և երեք փոփոխականից կազմված որոշ բուլյան ֆունկցիաների անվանումներ.

x₀=x	1	0	1	0	1	0	1	0
x₁=y	1	1	0	0	1	1	0	0
x₂=z	1	1	1	1	0	0	0	0	Նշանակում	Անվանում
1	0	0	0	0	0	0	0	1	F3,1 = x↓y↓z = ↓(x,y,z) = Webb₂(x,y,z) = NOR(x,y,z)	3ԿԱՄ-ՉԷ, Վեբի ֆունկցիա, Պիրսի սլաք, Կուայնի դաշույն - "†"
23	0	0	0	1	0	1	1	1	F3,23 = $\neg (>=2(x,y,z))$ = ≥2(x,y,z)	Միացնող ինվերսիոն մեծամասնությանը, 3PPB-ՉԷ, մաժորիտային տարր ինվերսիայով
126	0	1	1	1	1	1	1	0	F3,126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	անհավասարություն
127	0	1	1	1	1	1	1	1	F3,127 = x\|y\|z = \|(x,y,z) = NAND(x,y,z)	3և-ՉԷ, Շեֆֆերի շտրիխ
128	1	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x և y և z) = և(x,y,z) = min(x,y,z)	3և, մինիմում
129	1	0	0	0	0	0	0	1	F3,129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	հավասարություն
150	1	0	0	1	0	1	1	0	F3,150 = x⊕y⊕z = x⊕₂y⊕₂z = ⊕₂(x,y,z)	Տերնար բաժանում ըստ մոդուլ 2-ի
216	1	1	0	1	1	0	0	0	F3,216 = f₁	Փոխառության լիցքահանում տերնար հանման ժամանակ
232	1	1	1	0	1	0	0	0	F3,232 = f₂ = [>=2(x,y,z)] = ≥2(x,y,z) = (x И y) ИЛИ (y И z) ИЛИ (z И x)	Փոխանցման լիցքահանում տերնար բաժանման ժամանակ, միացնող ըստ մեծամասնությամբ
254	1	1	1	1	1	1	1	0	F3,254 = (x+y+z) = +(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ԿԱՄ y ԿԱՄ z) = ԿԱՄ(x,y,z) = max(x,y,z)	ԿԱՄ, մաքսիմում

Երեք կամ ավելի արգումենտների ենթաֆիքսման ժամանակ գրառումը ավելի նպատակահարմար է քան ինֆիքսման դեպքում։ Ֆունկցիայի գրառման սովորական տեսքը ենթաֆիքսային է։ Ինֆիքսման ֆունկցիայի գրառման ֆունկցիան կոչվում է օպերատոր, իսկ արգումենտները՝ օպերանդներ։

Բուլյան ֆունկցիաների լրիվ դասեր[խմբագրել | խմբագրել կոդը]

Սուպերպոզիցիաներ և ֆունցիայի փակ դասեր[խմբագրել | խմբագրել կոդը]

Բուլյան ֆունցիայի հաշվման արդյունքը կարող է օգտագործվել, որպես որևիցե արգումենտ մեկ այլ բուլյան ֆունկցիայի համար։ Այդպիսի գործողությունների արդյունքը՝ սուպերպոզիցիաները կարելի է դիտարկել, որպես նոր բուլյան ֆունկցիա, որն ունի իր ճշմարտության աղյուսակը։ Օրինակ՝ $f(x,y,z)={\overline {x({\overline {y}}\lor z)}}$ ֆունկցիային (կոնյուկցիայի, դիզյունկցիայի և երկու բացասման սուպերպոզիցիան) կհամապատասխանի հետևյալ աղյուսակը.

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Ասում են, որ փակ ֆունկցիաների բազմությունը հարաբերում է սուպերպոզիցիաների գործողություններին, եթե տվյալ բազմությունից կամայական ֆունկցիայի սուպերպոզիցիա նույնպես մտնում է այդ բազմության մեջ։ Ֆունկցիաների փակ բազմությունը անվանում են նաև փակ դաս։

Որպես բուլյան ֆունկցիաների փակ դասերի պարզագույն օրինակ կարելի է անվանել $\{x\}$ բազմությունը, որը բաղկացած է մեկ նույնական ֆունկցիայից կամ $\{0\}$ բազմությունը, որում բոլոր ֆունկցիաները նույնաբար հավասար են զրոյի անկախ արգումենտներից։ Փակ են նաև $\{x,{\overline {x}}\}$ և բոլոր ունար ֆունկցիաների բազմությունները։ Իսկ ահա փակ դասերի միավորումը արդեն կարող է փակ չհամարվել։ Օրինակ՝ միավորելով $\{0\}$ և $\{x,{\overline {x}}\}$ փակ դասերը մենք ${\overline {0}}$ սուպերպոզիցիայի միջոցով կարող ենք ստանալ 1 հաստատունը, որը մեր ունեցած դասերում բացակայում էր։

Պարզվում է, որ $P_{2}$ բազմության բոլոր հնարավոր բուլյան ֆունկցիաները կրկին համարվում են փակ։

Նույնականություն և երկակիություն[խմբագրել | խմբագրել կոդը]

Երկու բուլյան ֆունկցիաներ համարժեք են միմիանց, եթե կամայական միանման արգումենտների հավաքածուներում նրանք ընդունում են հավասար արժեքներ։ f և g ֆունկցիաների համարժեքությունը կարելի գրառել, օրինակ այսպես.
$f(x_{1},x_{2},\dots ,x_{n})=g(x_{1},x_{2},\dots ,x_{n})$

Բուլյան ֆունկցիաների ճշմարտության աղյուսակներին նայելով՝ կարելի է ստանալ նաև այսպիսի համարժեքություններ.

${\overline {0}}=1$	${\overline {1}}=0$	${\overline {\overline {x}}}=x$	$xy=yx$	$x\lor y=y\lor x$
$0x=0$	$1x=x$	$0\lor x=x$	$1\lor x=1$	$xx=x\lor x=x$

Իսկ որոշ հավաքածուների վրա դիտարկված աղյուսակային տվյալները տալիս են այս արդյունքները.

x{\overline {x}}=0

x\lor {\overline {x}}=1

{\overline {x\cdot y}}={\overline {x}}\lor {\overline {y}}

{\overline {x}}\cdot {\overline {y}}={\overline {x\lor y}}

(դե Մորգանի կանոններ)

$x(y\lor z)=xy\lor xz$
$x\lor yz=(x\lor y)(x\lor z)$ (կոնյունկցիայի և դիզունկցիայի դիստրիբուտիվություն)

$g(x_{1},x_{2},\dots ,x_{n})$ ֆունկցիան կոչվում է $f(x_{1},x_{2},\dots ,x_{n})$ ֆունկցիայի երկակի, եթե $f({\overline {x_{1}}},{\overline {x_{2}}},\dots ,{\overline {x_{n}}})={\overline {g(x_{1},x_{2},\dots ,x_{n})}}$ : Հեշտ է ցույց տալ, որ այս հավասարության մեջ f-ի և g-ի տեղերը կարելի է փոխել, այսինքն f և g գունկցիաները երկակի են մեկը մյուսի հանդեպ։ Պարզագույն ֆունկցիաների փոխադարձաբար երկակի են 0 և 1 հաստատունները, իսկ դե Մորգանի կաննոներից հետևում է կոնյունկցիայի և դիզյունկցիայի փոխադարձաբար երկակիությունը։ Նույնական ֆունկցիան, ինչպես նաև բացասում ֆունկցիան երկակի են իրենք իրենց նկատմամբ։

Եթե բուլյան ֆունկցիայի մեջ ամեն ֆունկցիա փոխարինենք իր երկակիի հետ, ապա կրկին կստանանք ճիշտ համարժեքություն։ Վերոնշյալ բանաձևերում հեշտությամբ կարելի է գտնել փոխադարձաբար երկակի ֆունկցիաներ։

Համակարգի լրիվություն, Պոստի չափանիշներ[խմբագրել | խմբագրել կոդը]

Բուլյան ֆունկցիաների համակարգը կոչվում է լրիվ, եթե կարելի է կառուցել սուպերպոզիցիաներ, որոնք համարժեք են ավելի շուտ սահմանված ֆունկցիաներին։ Ասում են նաև, որ տվյալ համակարգի միավորումը համընկնում է $P_{2}$ դասի հետ։

Ամերիկացի մաթեմատիկոս Էմիլ Պոստը ներմուծել է հետևկալ բուլյան ֆունկցիաների փակ դասերի քննարկումը.

Հաստատունը պահպանող ֆունկցիաներ՝ $P_{0}$ և $P_{1}$ ,
Ինքնաերկակի ֆունկցիաներ՝ $S$ ,
Մոնոտոն ֆունկցիաներ՝ $M$ ,
Գծային ֆունկցիաներ՝ $L$ :

Այս ֆունկցիաների միջոցով ապացուցվել է, որ բուլյան ֆունկցիաների ցանկացած փակ դաս, որը չի համընկնում $P_{2}$ -ի հետ, ամբողջովին պարունակվում է այս հինգ դասերից որևիցե մեկին, սակայն միևնույն դեպքում հինգից ոչ մի դաս չի պարունակվում չորսի միավորման մեջ։ Այս ձևով Պոստի սահմանած չափանիշները համակարգի լրիվության համար հանգում է նրան թե արդյոք այս ամբողջ համակարգը չի պարունակվում ամբողջովին այս ենթալրիվ դասերից որևիցե մեկին։ Եթե համակարգի կամայական դասում գտնվում է ֆունկցիա, որը չի մտնում իր փակման մեջ, ապա այդպիսի համակարգը կլինի լրիվ և նրա մեջ մտնող ֆունկցիաների միջոցով հնարավոր կլինի ստանալ ցանկացած այլ բուլյան ֆունկցիա։ Պոստը ապացուցել է, որ բուլյան ֆունկցիաների փակ դասերի բազմությունը հաշվելի է։

Նկատենք, որ գոյություն ունեն ֆունկցիաներ, որոնք չեն մտնում Պոստի դասերից որևիցե մեկի կազմում։ Ցանկացած այդպիսի ֆունկցիա ինքն իրենով արդեն ձևավորում է լրիվ համակարգ։ Որպես օրինակի կարելի է ներկայացնել Շեֆֆերի շտրիխ և Պիրսի սլաք ֆունկցիաները։

Բուլյան ֆունկցիաների ներկայացում[խմբագրել | խմբագրել կոդը]

Պոստի թեորեմը ճանապարհ է բացում բուլյան ֆունկցիաների շարահյուսական տեսքով ներկայացման համար, որը դեպքերի շարքում պարզվում է ավելի հարմար, քան ճշմարտության աղյուսակները։ Որպես ելակետային պահ այստեղ հանդես է գալիս որևիցե $\Sigma =\{f_{1},\ldots ,f_{n}\}$ ֆունկցիաների լրիվ համակարգի որոնումը։ Այդժամ կամայական բուլյան ֆունկցիա կարելի է ներկայացնել, որպես որևեցի սիգնատուրային $\Sigma$ տերպ, որը տվյալ դեպքում նույնպես անվանում են բանաձև։ Հարաբերականորեն ֆունկցիաների տվյալ համակարգի դեպքում օգտակար է իմանալ հետևյալ հարցերի պատասախանները.

ինչպե՞ս կառուցել ըստ տվյալ ֆունկցիայի իր ներկայանալի բանաձևը,
ինչպե՞ս ճշտել, որ երկու տարբեր բանաձևեր համարժեք են, այսինքն հաղորդում են միևնույն ֆունկցիան,
Ինչպե՞ս ըստ տվյալ ֆունկցիայի կառուցել իր ներկայանալի բանաձևը տրվող կամ արդեն տրված հատկությունների միջոցով (օրինակ՝ փոքրագույն չափը ներկայացնող տվյալով), և արդյո՞ք հնարավոր է դա։

Այս հարցերին տրվող դրական պատասխանները և այլ հարցեր էականորեն մեծացնում են տվյալ ֆունկցիաների համակարգի կիրառական նշանակություն։

Դիզյունկտիվ նորմալ ձև (ԴՆՁ)[խմբագրել | խմբագրել կոդը]

Տարրական կոնյունկցիա կամ կոնյունկտ կոչվում է որոշակի վերջավոր քանակով փոփոխականների կամ նրանց բացասման կոնյունկցիան, ընդ որում յուրաքանչյուր փոփոխական հանդիպում է ոչ ավելին քան մեկ անգամ։ Դիզյունկտիվ նորմալ ձև կամ ԿՆՁ կոչվում է տարրական կոնյունկտների դիզյունկցիան։ Տարրական կոնյունկցիան՝

ճիշտ է, եթե կամայական փոփոխական մտնում է նրա կազմում ոչ ավելին քան մեկ անգամ (նրա բացասումը ներառյալ),
լրիվ է, եթե կամայական փոփոխական (կամ նրա բացասումը) մտնում է նրա կազմում ճիշտ մեկ անգամ,
մոնոտոն է, եթե այն չի պարունակում փոփոխականների բացասում։

Օրինակ՝ $a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}$ համարվում է ԴՆՁ։

Կատարյալ դիզյունկտիվ նորմալ ձև կամ ԿԴՆՁ է կոչվում հարաբերականորեն որոշակի տրված վերջավոր քանակով փոփոխականներով այն ԴՆՁ, որի կամայական կոնյունկցիայի կազմում մտնում է տվյալ հավաքածուի բոլոր փոփոխականները, ընդ որում միևնույն հերթականությամբ։ Օրինակ՝ $a{\overline {b}}c\lor abc\lor {\overline {a}}b{\overline {c}}$ :

Հեշտ է համոզվել, որ ցանկացած բուլյան ֆունկցիայի համապատասխանում է որոշակի ԴՆՁ, իսկ ահա նույնաբար զրոյից տարբեր ֆունկցիային անգամ համապատասխանում է իր ԿԴՆՁ-ն։ Դրա համար անհրաժեշտ է ճշմարտության աղյուսակներում գտնել բոլոր այն բուլյան վեկտորները, որոնց վրա նրանց արժեքը հավասարվում է 1-ի և յուրաքանչյուր այդպիսի $b=(b_{1},b_{2},\ldots ,b_{n})$ վեկտորի համար կառուցենք $x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots x_{n}^{b_{n}}$ կոնյունկցիան, որտեղ $x_{i}^{1}=x_{i}$ $x_{i}^{0}={\overline {x_{i}}}$ : Այս կոնյունկցիաների դիզունկցիան համարվում է տրված ֆունկցիայի ԿԴՆՁ-ն, քանի որ բոլոր բուլյան վեկտորների համար նրանց արժեքները համապատասխանում են սկզբանական ֆունկցիայի արժեքների հետ։ Օրինակ՝ $x\to y$ իմպլիկացիայի համար ԿԴՆՁ-ային տեսք է համարվում ${\overline {x}}y\lor {\overline {x}}\,{\overline {y}}\lor xy$ -ը, որը կարելի է պարզեցնել մինչև ${\overline {x}}\lor y$ տեսքը։

Կոնյունկտիվ նորմալ ձև (ԿՆՁ)[խմբագրել | խմբագրել կոդը]

Կոնյուկտիվ նորմալ ձևը որոշվում է կրկնակի դիզյունկտիվ նորմալ ձևով։ Տարրական դիզյունկցիա կամ դիզյունկտ է կոչվում մեկ կամ մի քանի փոփոխականների կամ նրանց բացասման դիզյունկցիան, ընդ որում յուրաքանչյուր փոփոխական մտնում է նրա կազմում ոչ ավելի քան մեկ անգամ։ ԿՆՁ-ն դա տարրական դիզյունկցիայի կոնյունկցիան է։

Կատարյալ կոնյունկտիվ նորմալ ձևը, մասնավորապես որոշակի վերջավոր թվով փոփոխականներից կազմված հավաքածուներ են անվնավում այնպիսի ԿՆՁ-ն, որի յուրաքանչյուր դիզյունկցիայի մեջ է մտնում տվյալ հավաքածուի բոլոր փոփոխականները, ընդ որում նույն հերթականությամբ։ Քանի որ (Կ)ԿՆՁ-ը և (Կ)ԴՆՁ-ը փոխադարձաբար երկակի են, ԿԿՆՁ-ի հատկությունները կրկնում են ԿԴՆՁ-ի հատկությունները, կոպիտ ասած՝ «ճշտությամբ մինչև հակառակ»։

ԿՆՁ-ը կարող է կառուցվել իրեն համարժեք ԴՆՁ-ից փակագծերի բացման կանոնի ճանապարհով.

a(b\lor c)\to ab\lor ac

ինչը արտահայտում է կոնյունկցիայի դիստիբուտիվությունը դիզյունկցիայի հարաբերությամբ։ Դրանից հետո անհրաժեշտ է յուրաքանչյուր կոնյունկցիայում ջնջել կրկնվող փոփոխականները և նրանց բացասումները, ինչպես նաև դիզյունկցիայից հեռացնել բոլոր կոնյունկցիաները, որոնցում հանդիպում են փոփոխականները իրենց բացասումների հետ միասին։ Որպես արդյունք անպայման չէ, որ ստացվի ԿԴՆՁ, եթե անգամ ի սկզբանե տրված ԿՆՁ-ն ԿԿՆՁ էր։ Այսպիսով կարելի է միշտ ԴՆՁ-ից անցում կատարել ԿՆՁ։ Դրա համար անհրաժեշտ է օգտագործել կանոնը

a\lor bc\to (a\lor b)(a\lor c)

արտահայտված դիզյունկցիայի բաշխականությունը հարաբերում է կոնյունկցիային։ Արդյունքը կարելի է փոփոխության ենթարկել վերոնշյալ մեթոդով՝ «կոնյունկցիա» բառը փոխարինելով «դիզյունկցիա» բառով և ընդհակառակը։

Հանրահաշվական նորմալ ձև (ՀՆՁ կամ Ժեգալկինի բազմանդամ)[խմբագրել | խմբագրել կոդը]

Հանրահաշվական նորմալ ձևը (արտասահմանյան գրականության մեջ ընդունված ձև) կամ Ժեգալկինի բազմանդամը (անվանում, որը օգտագործվում է մայրենի գրականության մեջ) դա տրամաբանական ֆունկցիայի ներկայացման ձև է 0 և 1 գործակիցներով բազմանդամի տեսքով, որում որպես արտադրյալ է օգտագործվում կոնյունկցիա (և, AND) գործողությունը, իսկ որպես գումարում՝ Գումարում ըստ մոդուլ 2-ի (բացառող ԿԱՄ, XOR) գործողությունը։ Ժեգալկինի բազմանդամն ստանալու համար անհրաժեշտ է կատարել հետևյալ գործողությունները.

Ստանալ ֆունկցիայի ԿԴՆՁ-ը,
Բոլոր ԿԱՄ-երը փոխարինել բացառող ԿԱՄ-երով,
Բոլոր բացասումներով տարրերին փոխարինել հետևյալ կառույցով՝ «տարր» «բացառող կամ» 1,
Բացել փակագծերը Ժեգալկինի հանրահաշվի օրենքներով և զույգերի բերել միանման տարրերը։

Բուլյան ֆունկցիաների դասակարգում[խմբագրել | խմբագրել կոդը]

Ըստ մուտքային n օպերանդների քանակի, որոնցից կախված է ֆունկցիայի արժեքը ելքում, տարբերակում են նուլար (n=0), ունար (n=1), բինար (n=2), տերնար (n=3) բուլյան ֆունկցիաներ և մեծ քանակի օպերանդներ ունեցող ֆունկցիաներ։
Ըստ ճշմարտության աղյուսակներում նշված մեկերի և զրոների քանակի տարբերակում են հաշվեկշռված բուլյան ֆունկցիաների դասը (ինչպես նաև այսպես կոչված հավասառակշռված կամ հավասարահարաբերական, քանի որ հավասարահարաբերական պատահական ելքային արժեքների դեպքում կամ ըստ ճշմարտության աղյուսակի բոլոր հավաքածուների գերազանցման դեպքում ելքում 1 արժեք ստանալու հավանականությունը հավասար է 1/2) ավելի լայն չհաշվեկշռված բուլյան ֆունկցիաներից (ինչպես նաև այսպես կոչելի չհավասարակշռված, քանի որ հավանականությունը ելքում 1 արժեք ստանալու համար մեծ է 1/2-ից)։ Հավասարակշռված բուլյան ֆունկցիաները օգտագործվում են կրիպտոգրաֆիայում։
Կախված ֆունկցիայի արժեքների ելքային բիթերի վերադասավորմանը տարբերակում են սիմետրիկ (որոնց արժեքները կախված է միայն ելքում հանդիպող մեկերի քանակից) և ոչ սիմետրիկ (որոնց արժեքները կախված են ելքային բիթերի վերադասավորումից) բուլյան ֆունկցիաներ։
Ըստ ֆունկցիայի մեկը մյուսին հակադիր հավաքածուներում արգումենտների արժեքների տարբերակում են ինքնաերկակի ֆունկցիաները (որոնց արժեքները փոխակերպվում են բոլոր ելքերի արժեքների փոխակերպումից) մնացյալ բուլյան ֆունկցիաներից, որոնք օժտված չեն նման հատկությամբ։ Ինքնաերկակի ֆունկցիաների ճշմարտության աղյուսակների ներքևի մասը հանդիսանում է վերևի փոխակերպված մասի հայելային պատկերը (եթե տեղադրենք ելքային հավաքածուները սովորական դասավորությամբ)։
Ոչ գծայնության հանրահաշվական աստիճանով տարբերակում են գծային բուլյան ֆունկցիաները (որոնց ՀՆՁ-ը հանգեցվում է գծային գումարի ըստ մոդուլ 2-ի ելքային արժեքներում) և ոչ գծային բուլյան ֆունկցիաներ (որոնց ՀՆՁ-ը պարունակում է գոնե մեկ ոչ գծային գործողության կոնյունկցիա ելքային արժեքներում)։ Գծային ֆունկցիայի օրինակներ են համարվում՝ գումարում ըստ մոդուլ 2-ի (բացառող ԿԱՄ, XOR), էկվիվալենցիա, ինչպես նաև բոլոր այն բուլյան ֆունկցիաները, որոնց ՀՆՁ-ն պարունակում է միայն գծային գործողություների գումարում ըստ մոդուլ 2-ի առանց կոնյունկցիայի։ Ոչ գծային ֆունկցիաների օրինակներ են՝ կոնյունկցիան (և, AND), Շեֆֆերի շտրիխը (չ-և, NAND), Պիրսի սլաքը (Չ-ԿԱՄ, NOR), ինչպես նաև բոլոր այն բուլյան ֆունկցիաները, որոնց ՀՆՁ-ն պարունակում է միայն մեկ ոչ գծային գործողության կոնյունկցիա։

Տես նաև[խմբագրել | խմբագրել կոդը]

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

↑ Игошин, 2008, Глава 2. Булевы функции
↑ Игошин, 2008, էջ 94
↑ Игошин, 2008, էջ 104-105
↑ Самофалов, 1987
↑ Элементарные булевы функции
↑ Игошин, 2008, էջ 96

Գրականություն[խմբագրել | խմբագրել կոդը]

Алексеев В. Б. (лектор), Поспелов А.Д. (составитель) Дискретная математика (курс лекций, II семестр). — М.: Изд. отд. фак. Вычислит. математики и кибернетики МГУ им. М. В. Ломоносова, 2002. — 44 с.
Быкова С. В., Буркатовская Ю. Б. Булевы функции: учебное пособие для студентов высших учебных заведений, обучающихся по специальности ВПО 010501 «Прикладная математика и информатика». — Томск: Томский гос. ун-т, 2010. — 190 с.
Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. — М.: ФИЗМАТЛИТ, 2009.
Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с.
Кузнецов О. П. Дискретная математика для инженера. — СПб.: Лань, 2007. — 394 с.
Учебные пособия кафедры математической кибернетики ВМиК МГУ (на сайте кафедры математической кибернетики МГУ ВМК).
Ложкин С.А. Лекции по основам кибернетики : учеб. пособие по курсам «Основы кибернетики» и «Структур. реализация дискрет. функций». — М.: Изд. отд. фак. Вычислит. математики и кибернетики МГУ им. М. В. Ломоносова, 2004. — 254 с.
Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2001. — 126 с.
Самофалов К. Г., Романкевич А. М., Валуйский В. Н., Каневский Ю. С., Пиневич М. М. Прикладная теория цифровых автоматов. — Киев: Вища Школа, 1987. — С. 183-189. — 375 с.
Яблонский С. В. Введение в дискретную математику. — М.: Высш. шк., 2006. — 384 с.

[Игошин—2008—Глава_2._Булевы_функции—-1] Игошин, 2008, Глава 2. Булевы функции

[Игошин—2008——94-2] Игошин, 2008, էջ 94

[Игошин—2008——104-105-3] Игошин, 2008, էջ 104-105

[Самофалов—1987——-4] Самофалов, 1987

[5] Элементарные булевы функции

[Игошин—2008——96-6] Игошин, 2008, էջ 96

[1]

[2]

[3]

[4]

[5]

[6]