Алгебралық тұжырымдау туралы түсінік

 

 

 

 

 

 

 

Мысалы, “егер 12  6-ға бөлінсе, онда ол 3-ке бөлінеді” тұжырымы ақиқат. Мұнда ақиқат сілтеме және ақиқат қорытынды.

Импликация математикалық  дәлелдеуде үлкен роль атқарады. Теоремалардың  белгілі бөлігі қажетті және жеткілікті формада құрылады. Егер бұл жағдайда a ақиқат болып және a® b импликацияның ақиқаттығы дәлелденген болса, онда b салдардың ақиқат екенін қорытындылаймыз. 

Логикалық амалдармен алғаш  танысқанда импликациядан басқаның барлығы мейлінше табиғи түрде енгізілген секілді. Ал импликация анықтамасын  енгізуді қабылдауға біздің санамыз  қарсылық көрсетіп жатқандай болып  көрінеді. Бірақ импликацияның мұндай анықтамасы біздің түйсікті ішкі логикамызға және математикада өте жиі қолданылатын «егер …, онда ххх»  конструкциясына сәйкес келетіндігін көрсететін мысал келтіруге болады. Арифметикадан бір теореманы еске түсірейік - Q(x)= «Егер х натурал саны 4-ке бөлінсе онда, ол 2-ге бөлінеді». Бұл теореманың әділдігіне біз күмән келтіреміз, яғни Q(x ) - қа қандай х натурал санын қойсақ та біз ақиқат айтылым аламыз. Белгілеу енгіземіз: А(х)= «х натурал саны 4-ке бөлінеді», В(х)= «х натурал саны 2-ге бөлінеді».

       Сонда  шығатыны:

               Q(x )= А(x )® В(x )                                       (1)

 

(1) формулаға х=8, 2, 3 мәндерін  қоя отырып келесілерді аламыз: 1® 1, 0®1, 0® 0. (1) формулаға 1® 0 шарты орындалатындай х-тің мәнін қою мүмкін емес (себебі келтірілген теорема әділ).

Қарапайым тілде «Егер  А, онда В» түрдегі сөйлемде А мен  В мазмұны жағынан байланысты екенін көреміз. Біздің импликация анықтамасында  бұл мүлде міндетті емес. Яғни біз  мынадай импликацияны қарастыру  құқымыз бар: «Егер бүгін бейсенбі болса, онда 2*2=5», бұл бейсенбіден басқа барлық күні ақиқат, ал бейсенбіде жалған.

      

_{1.7 Тұжырымдар алгебрасының формулалары}

 

 

 Тұжырымдарға қолданылатын логикалық амалдары көмегімен берілген тұжырымдардан күрделі тұжырымдарды құруға болады. Операциялардың орындалу реті жақшамен көрсетіледі. Мысалы, x, y, z үш тұжырымдарынан мынадай тұжырымды құруға болады:

  және   .

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

Тұжырымдар алгебрасының формулаларын латын алфавиттің бас  әріптерімен белгілейміз: A, B, C,…,X, Y, Z,…

Жазуды жинақтау үшін формулалардағы амалдарды ретімен орындау келісілген. Басқа барлық операциялардан бұрын конъюнкция орындалады, ал дизъюнкция импликация мен эквиваленттік бұрын орындалады. Бұл амалдардың орындалу ретін анықтайтын жақшалар қойылмауы мүмкін. Егер кейбір формуладан немесе ішформуладан терістеу алынса, ол жағдайда да жақша қойылмайды.

Демек, жоғарыда келтірілген  және   формулаларды былай жазуға болады:

 және

немесе                                     және .

Логика алгебрасында формуланың логикалық мәні оған кіретін қарапайым тұжырымдардың логикалық мәндерімен толығымен анықталады. Мысалы, x=1, y=1, z=0 болғанда Ø(xÙy)ÚØz  формуланың логикалық мәні ақиқат болады, яғни Ø(xÙy)ÚØz =1.

Логикалық амалдар сияқты, формуланың барлық мүмкін болған мәндері  оның ақиқаттық кестесі көмегімен  берілу мүмкін.

Мысалы, ØxÚy®хÙØу  формуласы үшін ақиқаттық кестесінің көрінісі төмендегідей:

 

х	у	Øx	Øу	ØxÚy	хÙØу	ØxÚy®хÙØу
1 1 0 0	1 0 1 0	0 0 1 1	0 1 0 1	1 0 1 1	0 1 0 0	0 1 0 0

 

Егер формуланың құрамына n қарапайым тұжырым енетін болса, онда ол нөл және бірден тұратын 2ⁿ  мән қабылдайды немесе формуланың ақиқаттық кестесі  2ⁿ қатардан тұрады деп айтуға болады.

_1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған формулалары

 

Егер логика алгебрасының А және В формулалары олардың  құрамына енетін қарапайым тұжырымдарының кез келген мәндерінде бірдей мән  қабылдаса, онда бұл формулалар пара-пар деп аталады. Формулалардың пара-парлығын º белгісімен белгілейміз, яғни

А ºВ Û А және В формулалары пара-пар.

Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 1 мәнді қабылдайтын болса, онда бұл формула тепе-тең ақиқат (немесе тавтология) деп аталады.

Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 0 мәнді қабылдайтын болса, онда бұл формула тепе-тең жалған (немесе қарама-қайшылық) деп аталады.

Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар: егер А және В формулалар пара-пар болса, онда А«В формуласы – тавтология, және керісінше, егер А«В формуласы тавтология болса, онда А және В формулалары пара-пар болады.

_{1.9 Негізгі тепе-теңдіктер}

 

Теорема 1 Келесе  тепе-теңдіктер  орындалады:

а® bºØaÚb;

a~b º (а® b)( b® a) º (ØaÚb)( aÚØb) º (ab) Ú (ØaØb)

Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен  дәлелдеуге болады.

Келтірілген тепе-тең  көрінетіндей, ® және ~ амалдары Ù, Ú арқылы ¬ өрнектеледі. Кейінірек Ú, Ù және Ø арқылы айтылымдар алгебрасының кез-келген амалын өрнектеуге болатыны көрсетіледі. Сол себепті біз басты назарды осы амалдардың қасиеттерін зерттеуге аударамыз. Оларды айтылымдар алгебрасының буль амалдары деп атайды.

Теорема 2 Айтылымдар алгебрасының булдік амалдары үшін келесі 19 тепе-теңдік орындалады:

0. – екі еселі терістеу заңы

         – коммутативтік заңдары

        – ассоциативтік  заңдары

        _{– дистрибутивтік заңдары}  

        _{–идемпотенттік  заңдары}

        _{– де Морган заңдары}

        _– 0 мен 1 заңдары

        _– жұту заңдары

         _– үшіншісі өшірілген заңы

   _– қайшылық заңы

 Бұлардың кез-келгенін ақиқаттық  кесте көмегімен дәлелдеуге болады.

1.10 Формулаларды тепе-тең түрлендіру

 

Тепе-теңдіктерді пайдаланып, формуланы немесе оның бөлігін оған пара-пар формулаға ауыстыруға болады. Мұндай түрлендірулер тепе-тең түрлендірлер деп аталады.

Тепе-тең түрлендірулер тепе-теңдіктерді дәлелдеу, формуланы берілген түрге келтіру, формуланы ықшамдау үшін қолданылады.

Егер А формуланың құрамына оған пара-пар В формулаға қарағанда аз әріптер мен логикалық амалдар кіретін болса, онда А формуласы В дан ықшам деп саналады. Әдетде эквиваленция және импликация амалдары дизъюнкция және конъюнкция амалдарына ауыстырылады, ал терістеу қарапайым тұжырымдардан алынады.

1.11  Логика алгебрасының функциялары

 

Жоғарыда айтылғандай, логика алгебрасы формуласының мәні бұл формулаға кіретін тұжырымдардың  мәндеріне тәуелді. Сондықтан логика алгебрасының формуласы оған кіретін қарапайым тұжырымдардың функциясы болады.

Мысалы, формуласы үш айнымалының f(x,y,z) функциясы болады. Бұл функция және оның аргументтері тек нөл немесе бір екі мәннің біреуін қабылдайды.

Анықтама Функцией алгебры логики n переменных (или функций Буля) называется функция n переменных, где каждая переменная принимает два значения: 0 и 1, и при этом функция может принимать только одно из двух значений: 0 или 1.

Ясно, что тождественно истинные и тождественно ложные формулы  алгебры логики представляют собой постоянные функции, а две равносильные функции выражают одну и ту же функцию.

 n айнымалы функциялардың санын анықтаймыз. Логика алгебрасының әрбір функциясын (логика алгебрасының формуласы сияқты) 2ⁿ қатардан тұратын ақиқаттық кестесі көмегімен беруге болады, яғни логика алгебрасының әрбір n айнымалы функциясы 2ⁿ әртүрлі мән қабылдайды. Сондықтан, n айнымалы функциясы ұзындығы 2ⁿ болған нөл және бір мәндерінен тұратын кейбір тобымен толығымен анықталады, ал ұзындығы 2ⁿ болған нөл және бірден тұратын топтарының жалпы саны тең. Демек, логика алгебрасының барлық n айнымалы функциялардың саны санына тең.

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

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

 

x	f1(x)	f2(x)	f3(x)	f4(x)
1	1	1	0	0
0	1	0	1	0

 

Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар болады: f₁(x)=1, f₄(x)=0, ал .

Барлық мүмкін болған екі айнымалы функциялардың ақиқаттық  кестесі келесі түрде болады: .

 

x	Y	f1	f2	f3	f4	f5	f6	f7	f8	F9	f10	f11	f12	f13	f14	f15	f16
1	1	1	1	1	1	0	1	1	0	0	0	1	0	0	0	1	0
1	0	1	1	1	0	1	1	0	0	1	1	0	0	0	1	0	0
0	1	1	1	0	1	1	0	0	1	1	0	1	0	1	0	0	0
0	0	1	0	1	1	1	0	1	1	0	1	0	1	0	0	0	0

 

Түсінікті, бұл функциялардың  аналитикалық өрнектері келесі түрде  жазылуы мүмкін:

,   ,   ,   ,

,           ,   ,                      ,

,          ,   ,                              ,

,  ,   ,                      .

 функциясы Пирс функциясы деп аталады және былай белгіленеді: (Пирс бағыты), ал функциясы Шеффер функциясы деп аталады, арқылы белгіленеді (Шеффер сызығы). Осы екі функциялардың әрбірі барлық бульдік функциялардың жиынын туындатады.

1.12  Нормал және жетілдірілген формалар

 

А(а₁, а₂, …, а_n) n тұжырымның формуласын қарастырайық.

Анықтама 1. n тұжырымның қарапайым конъюнкциясы (қарапайым дизъюнкциясы) деп тұжырымдардың немесе олардың терістеулерінің конъюнкциясын (дизъюнкциясын) айтады.

Мысал 1. xyz, Øxy – қарапайым конъюнкция;

ØxÚyÚz, yÚz, xÚØz –қарапайым дизъюнкция.

Анықтама 2. Егер А формуладағы қарапайым дизъюнкциялар бір-бірімен конъюнкцияның көмегімен байланысқан болса, онда формуланы конъюнктивті нормал форма (КНФ) деп атаймыз.

Анықтама 3. Егер А формуладағы қарапайым конъюнкциялар бір-бірімен дизъюнкцияның көмегімен байланысқан болса, онда формуланы дизъюнктивті нормал форма (ДНФ) деп атаймыз.

Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер  көмегімен оның ДНФ немесе КНФ  алуға болады, бұл формалар жалғыз болмайды.

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

Анықтама 5 Егер конъюнктивті нормал формадағы қарапайым дизъюнкцияның құрамына әрбір қарапайым тұжырымның өзі немесе кері шамасы міндетті түрде енетін болса, формуланы  жетілдірілген конъюнктивті нормал форма (ЖКНФ) деп атаймыз.

Мысал 2. А(x,y,z)= xyzÚØxy – дизъюнктивті нормал форма;

B(x,y,z)= (ØxÚyÚz)( yÚz)( xÚØz) – конъюнктивті нормал форма;

C(x,y,z)= xyzÚØxyz – жетілдірілген дизъюнктивті нормал форма;

D(x,y,z)= (ØxÚyÚz)( xÚyÚz)( xÚyÚØz) – жетілдірілген конъюнктивті нормал форма.

Теорем 1 Тұжырымдар алгебрасының кез келген формуласының оған пара-пар ДНФ және КНФ бар.

Теорема 2 Тұжырымдар алгебрасының кез келген тепе-тең жалған емес формуласының  бірмәнді ЖДНФ түрінде өрнектелуі бар.

Теорема 3 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат емес формуласының  бірмәнді ЖКНФ түрінде өрнектелуі бар.