Осы жерден салдар ретінде функциялардан Жегалкин полиномы арќылы тек ќана бір түрде жазылуы келіп шығады.

Ќаралѓан мысалдардан кµптеген толыќ системалар барлыѓын көруі мүмкін. Олардыњ єр бірі элементар функциялар жиыны ретінде ќаралуы жєне сонымен буль функцияларыныњ берілуін түрлі формулалар тілінде пайдалану мүмкін.ал ќандай тіл ењ оњай екендігі ќаралатын мєселеніњ сипатына байланысты болады.

Толыќтыќ түсіндірілуі тұйыќталу жєне тұйыќ кластар түсініктерінен µте байланысты.

9-аныќтама. ₁ - Р₂ ден алынѓан функциялардыњ ішкі жиыны болсын.  ніњ тұйыќталуы деп  жиыныныњ функциялары арќылы формулалар ретінде жазылуы мүмкін болѓан барлыќ буль функцияларыныњ жиынына айтылады.  жиыныныњ тұйыќталуы  арќылы белгіленеді.

Мысал:

1)  ₂ .  ₂ .

1.    1, х₁ х₂. б±л жиынныњ т±йыќталуы L кластаѓы барлыќ сызыќты функциялар жиыны болады.

f(х₁ ,х₂ ,..., х_n) =C₀ C₁ х₁ C₂ х₂ ... C_n х_n ( mod 2 )

б±л жерде C_i =0,1 ( i=0,1,2,..., n ).

7-дәрістің тақырыбы: Буль функцияларын байланыс сұлбалармен іске асыру.

Жаспары:

1. Функциянальдық элементтерден сұлбаларды құру мысалдары.

2. Екілік қоқыш.

3. Функциональдық элементтерден минималды сұлбаларды құру есебі және оны шешу жолдары.

Буль функциялары. Буль функцияларының тұжырымдар формулаларымен өрнектелуі. Суперпозиция

Анықтама: Аргументтері де, өзі де 0 және 1 мәндерін қабылдайтын функциясы Буль функциясы деп аталады. функциясының аргументтері сәйкес мәндерін қабылдасын . мәндер құрамасы деу атау келісілген. құрамасының ұзындығы деп аталады. Әр құрама 2-лік жүйе цифрларынан тұрады және оларға(құрамаларға) нөмір беру келісілген. Құрамаларды нөмірлерінің табиғи өсу ретімен орналастырады. Мысал:

000; 001; 010; 011; 100; 101; 110; 111; - 8 құрама

0000; 0001; 0010; 0101; 0100; 0101; 0110; 0111;

1000; 1001; 1010; 1011; 1100; 1101; 1110; 1111;- 16 құрама

Құрамалардың осылайша табиғи нөмірлерінің өсуімен орналасуын стандартты орналасу дейміз. Ұзындығы ге тең элементтен жасалған орналасулардың саны екендігі белгілі. Бұдан ұзындығы ге тең 0 мен 1 жасалған барлық функциялардың саны тең екендігін көреміз. аргументтен тұратын барлық функциялардың саны тең. 0,1-константаларын 0-орынды Буль функциясы деу керек. Әрбір логикалық функцияны сол жағында барлық -құрамалар (айнымалының мәндері ұзындығының ге тең екілік вектор), ал оң жағында осы құрамадағы функцияның мәні орналасқан кесте арқылы беруге болады.

Мысалы, 3 айнымалыдан тәуелді функцияларын мына таблицамен беруге болады. Кестенің әр жолында айнымалылардың мәндерінен тұратын құрамалар және осы құрамаға сәйкес функцияның мәні орналасқан. Логикалық функцияның мәнін 1-ге тең (f = 1 ) ететін

айнымалылардың жиынтығы f – функцияның бірлік жиынтығы деп аталады. Бірлік жиын тықтар f – функцияның бірлік жиыны деп аталады Осыған ұқсас f = 0 болатын мәндер жиынтығы f – функцияның нольдік жиыны деп аталады. f (x1x2,…,xn) функци

суреттегідей ақиқаттық кестемен анықталады.Егер f буль функциясы мен формуласының ақиқаттық кестелері бірдей болса, формуласы f функциясын өрнектейді деп айтамыз.

Егер болса формуласындағы аргумент маңызсыз (фиктивный) деп аталады. Бұл жағдайда Шын мәнінде - айнымалыдан тәуелді, ал тен маңызсыз айнымалыны шығарып тастағаннан алынды дейді. Нөлден немесе бірден тұратын құрамалардағы 0 немесе 1 мәнін қабылдайтын f(x₁,…,x_n) функциясы түрақты деп аталады. f(x₁,x₂,…,x_n) 0; f(x₁,x₂,…,x_n) 1.

Логикалық алгебраның элементар функциялары.

Логикалық алгебрада бір немесе 2 айнымалысы бар унарлы, бинарлы операциялар көп қолданылады.Бір айнымалысы бар барлық логикалық функциялар жиынтығы кестеде

берілген. - 0,1 тұрақтылары.Олардың мәндері -тен тәуелсіз. Демек -ң мәні оларға маңызсыз (фиктивная). - -мәніне тәуелсіз

- -ті қайталайды; , -ң терістеуі деп аталады

айнымалысы бар логикалық функциялардың жиынтығы төменгі кестеде берілген. 16 функция бар

Мысалы, ₁ (x₁,x₂) =x₁ & x₂ =x₁ x₂– коньюнкция деп аталады.

₇ (x₁,x₂) = x₁ v x₂ (логикалық қосу, «немесе» операциясы)

1. ₀, ₁₅ - константалар

2 . конъюнкция : ₁ (x₁,x₂) =

3. импликацияға кері функция:

4.

5.

6.

7. 2-ң модулі бойынша қосу. :

8. Дизьюнкция:

9. Пирс бағыты:

10. Эквиваленция:

11.

12.

13.

14. импликация :

15. Шеффер штрихы:

16. константа:

Бұл 16 функцияның ішінен ₀, ₁₅ – 0 және 1 константалары, яғни екі маңызсыз айнымалы функция. Қалғандардың ішінен жиі қолданылатындары:

Конюнкция: 1 = x1 x2	Пирс стрелкасы немесе Вев функция : 8 = x1  x2
Дизюнкция: 7 = x1  x2	Шеффер функциясы : 14 = x1 x2 ;
Эквивалентция: 9 = x1 ~ x2	2-модулі бойынша қосу: 6 = x1 x2
импликация : 13 = x1  x2	терістеу

элементар функциялар болып есептеледі.  , ,  ,  ,  ,  ,  , 

Үш және одан көп айнымалысы бар функиялар ақиқаттық кесте арқылы және айнымалылардың символдары және оларға қолданылған унарлы, бинарлы опера циялардың символдарынан тұрады. Мысалы; f(x₁,x₂,x₃) = ( )  ( x₁  x₃ ) функция x₁,x₂,x₃ символдарынан және (), (),(),() операцияларынан тұрады.Сонымен формулалар ақиқаттық кестеге қоса функцияны (берілу) өрнектеу және есептеу үшін қолданылады. Жалпы жағдайда формулалар логикалық функцияны басқа элементар функциялардың суперпозициясы түрінде сипаттайды.

Суперпозициялар

Анықтама.Функция аргументтерінің орнына элементар немесе басқа да функцияларды (f₁,f₂,…,f_k) қою арқылы алынған жаңа функция (F) функциясы f₁,f₂,…f_k функцияларының суперпозициясы деп аталады.Мысалы, терістеу, коньюнкция, дизьюнкция, импликация, эквиваленция функциялары арқылы олардың суперпозициясы болып табылатын логикалық алгебраның жаңа функцияларын жазуға болады: х₂  x₁ ; x₁  ; (x₁  x₂)  ( ) ; ((x₂ ~ x₃)  х₁) ( x₂  ) т.б

Егер формулада операция таңбасы аргументтердің арасында тұрса,ондай жазуды инфиксті жазу деп атайды. f₁ = x₃  x₁; f₂ = x₁  x₂ ; f₃ = x₁ ( f₂); f₄ = (x₃  x₁)  (x₁ ( x₁  x₂ )) ;

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

f(x₁,x₂,x₃) = {[( ~ x₃)  ( x₁  x₂)]  ( x₁  x₂)} x₃

функциясын ақиқаттық кесте арқылы өрнектеу керек болсын; Жақшаларды қою ретіне логика алгебрасында арнаулы келісімдер қабыл данған: Сыртқы жақшалар жазылмайды. Мысалы, ( (xу z)) өрнегінің орнына xу z жазуға болады. Операциялардың орындалу приоритеттері :(  , ,  ,  ,, ,  ,  , );

Мысалдар:

1. xyz өрнегі ( (x  y )  z ) болып жазылады.

2. x yzu өрнегі ( (x  y )  ( zu ) болып жазылады.

3. x  y   u  v  w  x y өрнегі ( ( x  y)  (  (u  ( ( ( v  w )  x ) y ) болып жазылады

4. x ( z) өрнегінде жақшаны қалдыруға болмайды Жақшасыз жазылса (x  )z болып кетеді. Логикалық алгебра функциясын бульдік функция, екілік функция (двоичная) немесе ауыстырып қосқыш (переключательная) функция деп атайды.Буль функциялары арқылы қандай да бір құрылғыға берілген сигналдардың қортынды сигналға түрленуін белгілеуге болады. Мысалы, суретте көрсетілгендей қүрылғының n нүктеден тоқ қабылдау мүмкіндігі бар. Құрылғыларға берілген токқа байланысты x_i=1 айнымалының мәні тоқтың i- ші нүктеге берілуін көрсетеді, x_i=0 тоқ жоқты көрсетеді. f(б₁б₂,...,б_т) = 1 тоқтың шығу нүктесін берілуін, f = 0 болуы тоқтың берілмеуін көрсетеді.

	1-мысал. Мыс, коньюнкция X Y – екі тоқ беру нүктесі, бір шығу нүктесі бар құрылғыны көрсетеді. Шығу нүктесіне тоқ беріледі, егер x,y- ке тоқ берілсе.
2-мысал. Мысал. Үш адамнан тұратын комиссяның дауыс беруін белгілеп отыратын құрылғыны қарастырайық. Комиссия мүшелері резолюцияға (ұсынылған шешім) өз кнопкасын батырады.Егер комиссия мүшелерінің көпшілігі резолюцияны мақұлдаса, онда резолюция (шешім) қабылданады Бұл регистрация жасайтын құрылғымен белгіленіп отырылады.

Құрылғының жұмысының ақиқаттық кестесі суретте көрсетілгендей функциямен сипатталады; алынған функцияны f(0,0,0) = f(001) = f(010) = f(100) = 0 теңдіктер жүйесімен де беруге болады.

( 0 0 0 1 0 1 1 1 ) – жиынтығы f функциясының мәндер векторы деп аталады.