ТЕЗИСЫ+1-7. 1 жиын жне оан олданатын амалдар. Асиеттері

• Название: 1 жиын жне оан олданатын амалдар. Асиеттері
• Дата: 25.12.2021
• Размер: 480.5 Kb.
• Имя файла: ТЕЗИСЫ+1-7.doc
• Тип: Документы; #317658

1 ЖИЫН ЖӘНЕ ОҒАН ҚОЛДАНАТЫН АМАЛДАР. ҚАСИЕТТЕРІ.

1.1 Негізгі анықтамалар. Жиын ұғымы фундаментальді анықталмаған ұғым. Интуициялық түрде ішкі жиын деп бір бүтін кез – келген жиынтық

Интуитивно под множеством понимают любую совокупность вполне определенных различаемых объектов, рассматриваемых как единое целое.

Жиын деп белгілі бір объектінің белгілі қасиеттеріне байланысты топтастырылуы.

Ол объектілердің де өз айырмашылықтары болуы мүмкін. Жиындарға мысалдар ретінде бөлмедегі орындықтар жиынын, бір үйде тұратын адамдар, топтағы студенттер, натурал сандар жиыны, алфавиттегі әріптер жиыны, т.б. мысалдар келтіруге болады.

Жиынның құрамындағы жеке объектілер оның элементтері деп аталады. Нақты жиындарды белгілеу үшін латынның үлкен әріптері қабылданған: A,S,X,..... Жиынның элементтерін белгілеу үшін кіші әріптерді a,s,x,... қолдану қабылданған. x объектісі X жиынына тиісті екенін көрсету үшін, яғни, x элементі X жиынының элементі екенін көрсету үшін, x X белгісі қолданылады. Ал xX белгісі (жазбасы) x элементі X жиынына тиісті емес екенін көрсетеді. А жиыны В жиынының ішкі жиыны деп аталады, егер, А жиынының кез – келген элементі В жиында жатса. Бұл факт _{ } арқылы белгіленеді. (кейде, бұл жиындар әртүрлі екені нақты белгілі болса, онда: АВ деп белгіленеді).

Бір де бір элементі жоқ жиын құр (бос) жиын деп аталады. Оны  деп белгілейміз.

1.2 Жиындарғы қолданылатын амалдар және қасиеттері. Жиындарға элементар алгебрадағы қосу, көбейту сияқты амалдарды қолдануға болады. Жиындарға қолданылатын амалдарды графикалық бейнеде кескіндеу үшін Эйлера-Венн деп аталатын диаграмманы қолданамыз.

X және Y жиындарының бірігуі (кейде қосындысы) деп, X, Y жиындарыныңтым болмаса біреуінде жататын элементтер жиыны.

X және Y жиындарының айырмасы деп, X жиынына тиісті ал, Y жиынына тиісті емес элементтердің жиынын айтамыз

X және Y жиындары қиылыспайтын деп аталады, егер оларда ортақ элемент болмаса, яғни, егер XY = .

X және Y жиындарының симметриялы айырмасы деп, жиындардың біреуіне тиісті ал екіншісіне тиісті емес элементтердің жиынын айтамыз.

A,B,C, X, Y, Z  кез – келген жиындар болсын.

1. Қиылысудың, бірігудің, симметриялық айырманың коммутативтілігі:

а) A∩B = B∩A; б) AB = B A; в) A÷B = B÷A.

2. Қиылысудың, бірігудің, симметриялық айырманың ассоциативтілігі:

а) A∩(B∩C) = (A∩B)∩C; б) A (B C) = (A B) C; в) A÷(B÷C) = (A÷B)÷C.

3. Қиылысудың, бірігудің, симметриялық айырманың дистрибутивтігі:

а) A (B C) = (AB) (A C), б) A (B÷C) = (A÷B) (A÷C).

2. БИНАРЛЫҚ ҚАТЫНАСТАР. қасиеттері

n элементтер тізбегінен тұратын жиын n – ші реттелген жиын немесе кортеждер деп аталады. n- де әрбір элементтің өз орыны болады. Мысалы, a  b реттелген (a,b) және (b,a) екіліктері әртүрлі (кейде реттелген жұптар a,b деп белгіленеді). Онда {a,b} = {b,a}.

X және Y жиындарының элементтерінен құралған, реттелген (x,y) жұптарының жиыны X және Y жиындарының декарттық немесе тура көбейтінді деп аталады. Сайып келгенде, декарттық көбейтінді элементтері ұзы ндығы екі болатын (x,y) түріндегі барлық кортеждер. Геометриялық бейнеде 1 суретпен көрсетуге болады. Мұнда X және Y жиындары нақты осьтер, ал X  Y  декарттық көбейтіндісі боялған бөлігі.

X₁, X₂, ... X_n жиындарының декарттық көбейтіндісі деп, X₁X₂...X_n деп белгіленетін, ұзындығы n болатын барлық мүмкін болатын кортеждерді айтамыз. Бірінші компонент X₁ – ге тиісті элемент, екінші компонент болып  X₂ -нің элементі, т.с.с. болады.

Қатынасқа мысалдар болып теоретикалық – сандық немесе теоретика – жиындық немесе предикаттың геометриялық қасиеті: «…- дан кіші», «…- ға бөлінеді», «конгруэнтті ...». Сәйкестік ұғымын нақтылау үшін жиынның реттелген жұбын, үштігін, n-ші кортежін қолданамыз.

Бинарлық қатынас деп XY жиынының еркін ішкі жиындарының бірін айтамыз. Бұл жағдайда X және Y жиындарының арасында бинарлық қатынас (сәйкестік) анықталған дейміз. Бұл факт (x,y) R деп белгіленеді. Немесе басқаша түрде бұл жазба xRy, мұндағы xX, yY, R  XY нақты ішкі жиынын көрсететін қатынас белгісі.

Тернарлы қатынас (сәйкестілік) деп XYZ декарттық көбейтіндінің элементтерінен құралған реттелген үштіктер жиынының ішкі жиыны.

n-ды қатынас (сәйкестілік) деп X₁X₂...X_n декарттық көбейтіндінің элементтерінен құралған реттелген n-ды жиынының ішкі жиыны.

Бинарлық қатынастардың қасиеттері

1. Егер X және Y жиындары бинарлық сәйкестілікте беттессе, онда Х жиынындағы элементтердің қатынасты туралы айтылады. Қатынастардың негізгі қасиеттерін қарастырамыз.

1. R қатынасы X жиынында рефлексивті деп аталады, егер кез – келген xX элементі үшін xRx орындалса. (немесе, басқаша (x,x)R).

2 R қатынасы X жиынында антирефлексивті деп аталады, егер кез – келген xX элементі үшін xRx орындалмаса. (немесе, басқаша (x,x) R).

3. БИНАРЛЫҚ ҚАТЫНАСТАРДЫҢ МАҢЫЗДЫ ТҮРЛЕРІ. Ерекше бинарлы қатынастар түріндегі функциялар.

Әрбір R қатынасына R^-1 кері қатынас наықтауға болады. Бұның қысқаша анықтамасы келесі түрде болады:

R^-1 = {(x,y)| xRy} = {(x,y)| (y,x)R}.

Мысалы, «x y-тің бөлгіші» қатынасына кері қатынас «y x-ке еселі», «x y-тен үлкен» қатынасына кері қатынас «y x-тен кіші».

Нөлдік қатынас деп, элементтердің ешқай жұбына орындалмайтын қатынас. Әмбебап (бірлік) қатынас деп кез – келген элементтер жұбына орындалатын қатынасты айтамыз.

R қатынасына толықтауыш қатынас деп (x₁,x₂)  (x₁, x₂) R қатынасын айтамыз.

Енді қатынастардың негізгі түрлерін қарастырамыз.

1. R XX қатынасы Х жиынының элементтері арасындағы рефлексивті, симметриялы және транзитивті қатынас эквивалентті қатынас деп аталады және x₁  x₂, немесе x₁  x₂, немесе кейде x₁  x₂, x₁  x₂, ≂,≃ т.б. деп белгіленеді. Эквиваленттік қатынасқа мысал болып Евклид кеңістігіндегі векторлар теңдігі, Евклид геометриясындағы фигуралар теңдігі жатады.

X жиынының бөлшектенуі деп оның ішкі жиындарының төмендегі шарттарды қанағаттандыратын {X₁, X₂, ... X_n} жиынын айтамыз:

1) X_i  , i = 1, ... , n; 2) X_i  X_j = , мұнда i  j; 3)

Лемма (эквиваленттілік кластарға бөлу туралы). Жиында берілген эквиваленттіктің кез – келген қатынасы осы жиынды қиылыспайтын ішкі жиындарға бөледі. Кері тұжырым да дұрыс: жиынның әрбір қиылыспайтын ішкі жиындарға бөлшектенуі эквиваленттіліктің қандайда бір қатынасын анықтайды.

Бір факультеттің курстары осы факультеттегі студенттер жиынының бөлшектенуі, ал бір курстың топтары курс студенттері жиынының бөлшектенуі.  эквиваленттілік қатынасы қоятын бөлшектену келесідей анықталады: x және y элементтері бөлшектенудің бір ішкі жиынына түседі, егер олар эквивалентті болса, яғни, x,yX_i  xy. Бұл ішкі жиындар эквиваленттік кластар деп аталады.

Қатынас жартылай ретті деп аталады, егер ол рефлексивті немесе антирефлексивті, антисимметриялы және транзитивті болса. Егер қатынас антирефлексивті болса, онда реті қатаң; ал ол рефлексивті болса, онда  қатаң емес ретті деп атайды. Мысалы, нақты сандар жиынында «x₁  x₂» қатынасы және P(A) дәреже – жиында «X  Y» қатынасы қатаң емес ретті жартылай қатынас деп аталады. Ал «x₁ > x₂» және «X  Y» қатынастары  қатаң жартылай ретті қатынастарға мысалдар. Белгіленуі: >,<,⊏,⊐ - қатаң ретті жағдайда және ⊑,⊒,,≤ қатаң емес жағдайларда.
4. БУЛЬДІК АЛГЕБРА. ПІКІРЛЕР ЛОГИКАСЫНДАҒЫ ДӘЛЕЛДЕУ ӘДІСТЕРІ. КҮРДЕЛІ ПІКІРЛЕР БУЛЬДІК ФУНКЦИЯ РЕТІНДЕ. ПІКІРЛЕРДІ ЕСЕПТЕУ ТОЛЫҚТЫҒЫ ТУРАЛЫ ТЕОРМА.

2.1 Бульдік алгебра

A,B,C  X көпмүшесінің туынды көпмүшесі делік, яғни A,B,C P(X). Бұдан келесі теңдеулер шығады:

1. Қиылысу, бірігу коммутативтілігі: а) A∩B = B∩A; б) AB = B A.

2. Қиылысу, бірігу ассоциативтілігі: а) A∩(B∩C) = (A∩B)∩C; б) A (B C) = (A B) C.

3. Жуық бірігудің қиылысуының және жуық қиылысудың бірігуінің делдалдығы:

а) A (BC) = (AB) (AC), б) A (BC) = (A  B)  (A  C).

5. Бірігу мен қиылысудың идемпотенттілігі: а) AA = A;б) AA = A.

7. Бос көпмүшенің құрылымы: а) A = A;б) A = .

8. Толықтауыш құрылымы: а) AA = ; б) BB = X; в) ; г) =  ; д) =  , бұнда толықтауыш X көпмүшесіне байланысты алынады.

Сонымен көпмүше – булевалық алгебра (көпмүшелер) деп аталатын жүйені құрайтын қиылысу, бірігу және толықтыру операциялары бар дәреже.
2.2 Пікірлер алгебрасы
Математикалық логиканы оқуды біз басқа логикалық есептеулер (ықтималдық логикасы т.б.) негізделетін пікірлер алгебрасын оқудан бастаймыз. Пікірлер алгебрасы кейбір дискретті құрылғылар сипаттайтын құрастыру модельдері үшін негіз ретіндегі өзіндік қызығушылық болып табылады.

Пікірлер деп ненің анық ақиқат, ненің жалған екенін, екеуін бір бірінсіз дербес мағынасын білдіретін жай сөйлемді ұғамыз.

Мысалы 1. Волга Каспий теңізіне құяды. 2. Екі үштен көп. 3. Мен жалған айттым.

Бұл мысал пікір болып табылады (1 – ақиқат, 2 – жалған). 3 – пікір емес (егер ол шындық деп ұйғарсақ, онда ол ой бір уақытта жалған және керісінше осы сөйлемнен ақиқат ойы жеткізіліп тұр). Бұл суайт парадоксы деп аталады.

Алгебрада пікірлер пікірлердің ішкі құрылымын қарастырмайды, тек олардың ақиқат және жалған екендігін анықтаумен шектеледі. Сондықтан да пікірге екі «ақиқат» немесе «шындық» мәндерінің біреуін білдіретін көлем ретінде қарауға болады.

5. Пікірлерді есептеу. дәлелдеу тәсілдері.

Біз пікірлер алгебрасын қарастырдық. Бұл қарастыру мазмұнды болды. Енді онды формальді тұрғысынан алғанда формальді теорияға түсінік бере отырып сипаттауға тырысып көрейік.

2.3.1 Формальді теориялардың арасында ең маңыздысы болып аксиомалық (немесе дедуктивті) деп аталатын формальді теориялар тобы саналады. Біз соларды қарастырумен шектелеміз.

Аксиомалық теорияларға келесі «ақиқат» формулаларын белгілеу тәртібі тән:

I. Формальді теорияны құруды оның әліппесін құрайтын белгілердің көпмүшелерін белгілеуден бастайды;

II. Содан кейін теория формулалары (есептеулердің дұрыс құрылымы) құралатын ережелер көрсетіледі;

III формулалардың кейбір көпмүшелері бар, олар теория аксиомалары деп аталады;

IV формулалар арасындағы қатынастың соңғы көпмүшесі көрсетіледі; бұл қатынастар қорытынды ережелері деп аталады;

V қорытынды ережелері жаңа формулаларды осы формулалардың шекті қатарына сәйкес қояды; осы ережелердің көмегімен аксиомалардан жаңа «ақиқат» формулалары – теоремалар алынады.

Формальді теория – бұл «ақиқат» теоремалары деп аталатын көпмүше формулалары белгіленген формальді тілдегі барлық формулалардың көпмүшесі. Барлық формулалары ақиқат болып табылмайтын теория қарама қайшылықсыз деп аталады.

Теорема 2.1. Пікірлерді есептеудің кез келген теоремасы пікірлер алгебрасының тавтологиясы болып табылады.

Теорема 2.2. Пікірлерді есептеу қарама қайшылықсыз.

Дәлелдеу. Пікірлерді есептеудің кез келген теоремасы тавтология болып табылады. Пікірлер алгебрасындағы теоремаларды жоққа шығару өтірікке тең және пікірлерді есептеу теоремасы болып табылады.

Теорема 2.3. Пікірлер алгебрасының кез келген тавтологиясы пікірлерді есептеу теоремасы болып табылады.

Салдар 2.1. (пікірлерді есептеудің дұрыстығы (толықтығы) туралы теорема). Пікірлер формуласын (теоремасын) есептеуде дәлелденетін көпмүше тавтология көпмүшесімен сәйкес келеді.

Теорема 2.4. (Пікірлерді есептеу Посты бойынша толықтық туралы теорема)φ(X₁,...,X_n)  теорема болып табылмайтын формула болсын.φ(X₁,...,X_n) алынған барлық формулалар аксиомалары ретінде қосылған пікірлерді есептеуден алынған теория ауыспалы пікірлерді дербес формулаларға ауыстырғанда қарама қайшы болады.

6. ПРЕДИКАТТАР МЕН КВАНТОРЛАР. ПРЕДИКАТТАР ЛОГИКАСЫНДА ДӘЛЕЛДЕУЛЕР ҚҰРУ. КВАНТОРЛАРМЕН ІС ӘРЕКЕТТІҢ КЕЙБІР ЕРЕЖЕЛЕРІ. КҮРДЕЛІ ҰЙҒАРЫМДАР ЖАЗБАСЫ ҮШІН ФОРМУЛАЛАР ТІЛІН ҚОЛДАНУ

3.1 Предикаттар мен кванторлар

Пікірлер алгебрасының дамуы предикаттар логикасы болып табылады. Бұл да логикалық жүйе немесе ғылымды сипаттайтын белгілі бір тіл. Предикаттар логикасында пікірлермен бірге предикаттар деп аталатын күрделірек ұйғарым қарастырылады.

xP(x) теңдеуі (кез келген х үшін, Р(х) дұрыс») пікірді білдіреді, яғни Р(х) предикаты М көпмүшесінің барлық элементтері үшін нақты болған жағдайда ғана ақиқат болып табылады. Мұндағы  белгісі  жалпылық кванторы.

xP(x) теңдеуі («Р(х) дұрыс болатындай х бар») пікірді білдіреді, яғни Р(х) предикаты М кем дегенде бір элементі үшін анық болған жағдайда ғана ақиқат болып табылады;  белгісі  тіршілік кванторы.

Кванторларды қолдану мысалдарын қарастырайық. Натуралды сандар өрісінің үстінен предикаттар берілді делік:

1) x² = xx, онда x(x² = xx)  нақты пікір;

2) x+2 = 7, онда x(x+2 = 7)  жалған, ал x(x+2 = 7)  шындық пікірі;

3) x+2 = x, онда x(x+2 = x)  жалған пікір.

3.2 Предикаттар логикасының теңбе тең формулалары

М жүйесіндегі предикаттар логикасының қарастырғанда берілген жүйеде (өрісте) тепе тең әсерлі формулалар туралы айтуға болады, яғни барлық бос заттық ауыспалы заттарына және барлық предикаттар белгілеріне ортақ бір мән – нақты предикаттар қабылдайтын формулалар туралы.

Мысал. Жүйелер (өрістер) үстіндегі xW(x) және xW(x) формулаларын қарастырайық 1) М₁, {a} көпмүшесінен және A(x) пен B(x) предикаттарынан, A(a) шындық, B(a) жалған; 2) М₂, {a,b} көпмүшесінен және A(x ) предикатынан: A(a) шындық, A(b) жалған. Сонда xW(x) және xW(x) формулалары M₁, өрісінде (жүйесінде) тең әсерлі, бірақ М₂ өрісінде олай емес.

Предикаттар логикасының формулалары тепе тең әсерлі деп аталады, егер кез келген өрісте тепе тең әсерлі болса.

Теорема 3.2 Келесы формулалар жалпымәнді:

1. xW(x)xW(x). 2. xyV(x,y)yxV(x,y).
7. күрделі бекітулерді жазу үшін формула тілінің қолдануы. БУЛЬДІК ФУНКЦИЯЛАРДЫҢ НЕГІЗГІ ҚАСИЕТТЕРІ. ЖАСАЛҒАН ДҚФ МЕН КҚФ. БУЛЬДІК ФУНКЦИЯ ҮШІН ЖЕГАЛКИН КӨПМҮШЕЛІГІ.

4.1 Функцияның негізгі және қарапайым булевалары

Тек екі мәнді ғана қабылдай алатын айнымалыларды кейде сондай–ақ логикалық айнымалылар немесе пропозиционалдық айнымалылар деп атайды. Дәлірек айтқанда, х логикалық айнымалысы белгілі бір пікірді білдіріуі мүмкін. Мұнда х айнымалысының мәні 0 тең деп есептелінеді, егер оның мәнін білдіретін пікір жалған болса, және 1 тең болса, егер бұл пікір шындық болса.

Функция тәуелді аргументтер саны (міндетті түрде булева емес) кеңістік немесе арность деп аталады.

Кесте 4.2.
x	F(x)
0	0	1
1	1	0

4.2 Қарапайым бульдік функциялардың негізгі қасиеттері мен олардың арасындағы айырмасы
Бұл теңдеулерді логикалық заңдар ретінде де қарастыруға болады, егер айнымалылар кез-келген ұйғарым болса, ал теңдеулерді ұйғарымдардың тең әсерлілігі ретінде қабылдасақ.
4.3 Нақты және жалған айнымалылар, тапсырманың векторлық тәсілі
4.3.1 x_i айнымалысы f(x₁,…,x_i,… .x_n) функциясы үшін нақты болып табылады, егер басқа айнымалалар ,…,_i–1, ,…, (_j{0,1}) мәні f( ,…, , , ,…, ) f( ,…, ,1, ,…, )болса. Нақты емес айнымалылар жалған айнымалылар деп аталады.

Табл. 4.4
x	y	z	f
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

Осы бөлімнің басында айнымалылар мәндері жазбасының лексикографиялық тәртібі талқыланды. Ары қарай барлық жерде осы жазба тәсілін қолданамыз. Бірақ онда барлық кестені сызудың мәні болмайды – оның соңғы бағанасын ғана көрсеткен жеткілікті. Бір қатарға жазылған бұл бағанада жоғарыдан төменге қарай реті солдан оңға қарай ретіне сәйкес келсе функцияның мәндік векторы деп аталады. Мысалы , f функциясы үшін 4.1 мысалы бойынша бұл вектор f = (1,0,1,0,0,0,0,0), ал 4 по табл. 4.4 кестесі бойынша f = (1,0,0,0) деп жазылады.
8. формуланың эквиваленттілігі, бульдік функцияның негізгі қасиеттері. Ерекшеленген днф және кнф. Бульдік функция үшін жегалкиннің полиномы. Екі жақты функция.
= f(x₁,…,x_n) функциясы f функциясы үшін екі жақты функция деп аталады және f* білдіреді.

Мысал 4.2: (x & y)* = .

Пікір 1. f екі жақты функциясына екі жақты функция f функциясының өзіне тең.

Дәлелдеу. [f^*(x₁,...,x_n)]*= [ ]*= =f(x₁,...,x_n).

Теорема 4.1 (Екі жақтылық қағидасы). Функцияның суперпозициясына екі жақты функция [f₀(f₁,...,f_m)]^* = f₀^*(f₁^*,...,f_m^*) екі жақты функциясының суперпозициясына тең.

Дәлелдеу. [f₀(f₁(x₁,...,x_n),...,f_m(x₁,...,x_n))]^* = ¬f₀(f₁(¬x₁,...,¬x_n),...,f_m(¬x₁,..., ¬x_n)) =¬f₀(¬¬f₁(¬x₁,...,¬x_n),...,¬¬f_m(¬x₁,...,¬x_n)) =¬f₀(¬f₁^*(x₁,...,x_n),...,¬f_m^*(x₁,...,x_n)) = f₀^*(f₁^*(x₁,...,x_n),...,f_m^*(x₁,...,x_n)).

Салдары 4.1 (Екі жақтылық қағидасының басқаша құрылуы). Формулада берілген функцияның екі жақтылығын табу үшін осы формуладағы барлық функцияларды екі жақты функцияға ауыстыру қажет.
4.5 Дизъюнктивті және конъюнктивті қалыпты формалар
f булевалық функциясы үшін (ары қарай жай ғана функция) дизъюнктивті қалыпты формасы (дқф) f функциясына тең ретіндегі қарапайым конъюнкциялардың дизъюнкцисы деп аталады, ал қарапайым конъюнкция деп айнымалы немесе олардың жоққа шығарылуының конъюнкциясы аталады.

Мысал. Бірнеше булевалық функцияларды қарастырайық: A=x , B=  y z, C=x , D= (y z)= (yz)=  (y z), E= (xz). А, В, С функциялары д.қ.ф. орналасқан, находятся в д.н.ф., А екі қарапайым x и z; В конъюнкциялардың дизъюнкциясы болғандықтан – әрбіреуі бір әріптен тұратын үш қарапайым конъюнкциялардың дизъюнкциясы. С – бір қарапайым конъюнкцияның дизъюнкциясы.
Теорема 4.2 1) 0 тең әрбір булева функция д.қ.ф. түрінде жазылуы мүмкін; 2) 1 тең әрбір булева функция к.қ.ф. түрінде жазылуы мүмкін.

Салдар 4.2 Әрбір булева функция д.қ.ф. түрінде де, к.қ.ф. түрінде де жазылуы мүмкін.
9. ЕКІЛІК ЖӘНЕ ӨЗАРА ЕКІЛІК БУЛЬДІК ФУНКЦИЯЛАР МОНОТОНДЫҚ ФУНКЦИЯЛАР. ЖЕГАЛКИН КӨПМҮШЕСІ
Түрі кәдімгі көпмүше бірнеше айнымалылардың, қайсыда көбейту ролінде конъюнкция, қосу ролінде орындайды – қосу модульмен екі, ал коэффициенттермен нольдер немесе бірліктерді келеді.

n айнымалыларымен Жегалкин көпмүшесінің max дәрежесі қандай? Жауап : n . дәреже n жоғарырақ теңдіктердің түрында алынбайды : x 2= x ( x = x ( x = x , x 3= x және т . б .

Теорема 4.3 кез келген жалғыз тәсілмен Жегалкин көпмүшесі түрінде булева функцияны жазып қоюға болады .
Дәлелдеу ( ал бір жағынан құру тәсілі ). Бұл тәсіл негізделген. Егер функция ДҚФ түрінде берілсе, онда ең алдымен де Морганның ережелерін қолдана отырып дизъюнкцияны жоямыз, ал барлық жоққа шығаруларды бірлікті қосумен ауыстырамыз.
4.7 Функция суперпозициясы. Функция жиынының тұйықталуы. Функцияның тұйық топтары. Толық жиындар.

Теорема 4.4 Егер D = {f₁,…,f_k} – жиыны толық, ал F = {g₁,…,g_l} жүйесі әрбір D алынған f_j функциясы F жүйесі функциясының суперпозициясы ретінде жазылатын болса, онда F жиыны да – толық болады.

Дәлелдеу. h – өздігімен таңдалған булева функция болсын. D жүйесі толық болса, онда h – D жүйесінің функциялары ғана кіретін формула түрінде жазылуы мүмкін. f_j функциясының әрбір жағдайы бойынша бұл формулада F функциясын суперпозициямен ауыстыруға болады, нәтижесінде жазбасында g_i функциясы ғана қатысатын формула пайда болады.

Лемма 4.1 «Жаппай үлкен емес» қатынасы – бөлшектік қатар, яғни ол рефлексивті, антисимметриялы және транзитивті.

Теорема 4.5 Т₀, Т₁, L, M, S функциясының топтары тұйық.

Бұл ұйғарым осы топтың өз анықтамасынан, сондай ақ тұйықтық анықтамасынан шығады.

Булевалық функциялар теориясында толықтық туралы келесі теорема өте маңызды болып табылады.

Теорема 4.6 (толықтық туралы). K функциясының кейбір жиыны толық болуы үшін осы жиынның T₀, T₁, L, M, S тобының ешбіреуінде толығымен болмауы қажет және жеткілікті.