Импликация мен эквиваленцияны конъюнкция, дизъюнкция, терістеу арқылы өрнектеу.
белгілері бар кез-келген формуланы белгілері жоқ басқа эквивалентті формуламен ауыстыруға болатының дәлелдейміз.
Айталық (1) (2) формулалары белгілі болсын. Бірінші формулада импликация дизъюнкция мен терістеу арқылы, ал екінші формуладағы импликация конъюнкция мен терістеу арқылы өрнектеліп тұр. Мына эквиваленцияны (3) конъюнкция, импликация арқылы өрнектеуге болатындығын көрсетейік. Тексеру:
|
|
|
|
()& ()
|
|
а
|
а
|
а
|
а
|
а
|
а
|
а
|
ж
|
ж
|
а
|
ж
|
ж
|
ж
|
а
|
а
|
ж
|
ж
|
ж
|
ж
|
ж
|
а
|
а
|
а
|
а
|
(3) пен (1) ден (4) ( конъюнкция, дизъюнк ция, терістеу) (3)-пен (2)-ден (5) (конъюнкция, терістеу)
Буль функциялары. Буль функцияларының тұжырымдар формулаларымен өрнектелуі. Суперпозиция
Анықтама: Аргументтері де, өзі де 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(x1,…,xn) функциясы түрақты деп аталады. f(x1,x2,…,xn)0; f(x1,x2,…,xn) 1.
Достарыңызбен бөлісу: |