Бульдік функциялар және олардың берілуі

Оңтүстік Қазақстан мемлекеттік педагогикалық университеті

[pic 1]

Реферат

Тақырыбы: Бульдік функциялар және олардың берілуі.

                                                                  Орындаған: Басхан Досхан

Тобы:1508-12ж

Қабылдаған: Байжуманов А.А.                                                

Шымкент 2022ж

ЖОСПАР

Кіріспе

Негізгі бөлім

1. Буль функциялары
2. Бульдік функциялардың тұйықты кластары 
3. Толықтық және тұйықтық

Қорытынды

Пайдаланған әдебиеттер

КІРІСПЕ

Логикалық функциялар теориясындағы жабық класс-бұл P логика алгебрасының функциялары, оның суперпозиция операциясына қатысты жабылуы өзіне сәйкес келеді: [P]=P} [P] = P. басқаша айтқанда, формула арқылы өрнектеуге болатын кез-келген функция жиынының функцияларын қолдана отырып P}p, қайтадан сол жиынтыққа енеді.

1941 жылы Эмиль Пост жабық кластар жүйесінің толық сипаттамасын ұсынды, оны пост торы деп те атайды.

Жабу қасиеттері:

1. Кез келген жиын оның жабылуының ішкі жиыны болып табылады: [pic 2]
2. Ішкі жиынның жабылуы-бұл ішкі жиын: [pic 3]
3. Айта кету керек, жиындардың қатаң тіркемесінен олардың жабылуының қатаң тіркемесі ғана пайда болады: [pic 4]
4. Жабу операциясын бірнеше рет қолдану бір реттік қолдануға тең: [pic 5]

Жабық сыныптардың мысалдары

• Тек бір мәнді (тұрақты) алатын көптеген функциялар жабық. Егер біз функцияның дәлелдері ретінде жалған айнымалыларды қарастырмасақ, тұрақты класстағы суперпозиция әдетте мүмкін болмайды.
• Көптеген унарлы функциялар жабық.
• Көптеген  [pic 6] барлық мүмкін логикалық функциялар жабық.

Логикалық функциялар теориясы үшін Эмиль пост белгілеген келесі жабық сыныптар ерекше маңызды:

1. Сынып T0 тұрақты мәнін сақтайтын функциялар:

[pic 7]

1. Сынып T1 тұрақтысын сақтайтын функциялар:

[pic 8]

1. Сынып S өзіндік ерекшеліктері:

[pic 9]

1. Класс  m монотонды функциялар:

[pic 10]

1. Сызықтық функциялар класы L :

[pic 11]

Тердің бірде-бір класы толығымен қалған төртеуінің бірігуінде жоқ;  P- ден басқа логикалық функциялардың кез-келген жабық класы толығымен посттың бес класының бірінде болады.

Буль функциялары

Анықтама. Функция f(x1,…, xn) Буль функциясы деп аталады, егер оның аргументтері және өзі екі 0 немесе 1 мәндерін ғана қабылдаса.

f(x1,…, xn) функциясының аргументтері x1,…, xn белігілі мәндер қабылдасын: [pic 12]; [pic 13]; ...; [pic 14]  осы мәндердің белгілі тәртіппен реттелуін аргументтер мәндерінің құрамасы деп атаймыз. Мәндердің санын құраманың ұзындығы деп атаймыз. Ұзындығы n–ге тең құраманы былайша белігілейміз;  [pic 15].

        Ноль және бірден тұратын құраманы [pic 16] натурал санның [pic 17] екілік системадағы жазылуы деп қарастыруға болады. Бұл жағдайда [pic 18] санын [pic 19] құраманың номері деп атаймыз. Номер [pic 20] мынандай формуламен анықталады:

[pic 21].

. [pic 22]формуласын Жегалкин полиномы деп атайды.

        х1,...,хn аргументтерінен құралған кез-келген Жегалкин полиномын былай жазуға болады:

[pic 23].

Бұл жерде [pic 24] . Яғни полиномға кірсе 1, басқа жағдайда 0 болады.

Теорема. Кез-келген f(x1,…,xn)  функциясы үшін оны реализациялайтын Жегалкин полиномы бар болады және мұндай полином біреу ғана.

Мысалы.  [pic 25]

Функциялар жүйесінің толықтылығы мен тұйықтылығы.

Р2 символымен барлық Буль функциялар жиыны белгіленсін.

Анықтама. Р2 жиынының ішкі жиыны болатын система P={f1,…,fs} толық деп аталады, егер әрбір Буль функциясы Р системасы үстіндегі формуламен реализацияланатын болса.