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

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

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

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

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

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

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

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

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

 

   Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар болады: f₁(x)=1, f₄(x)=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 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат емес формуласының  бірмәнді ЖКНФ түрінде өрнектелуі бар.

_{1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру}

 

   Есеп. А(x,y,z) формуласының ақиқаттық кестесі берілсін. 

     
 
 
 
 
 
 
 
 
 
 

   Формуланың  ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген формула қарпайым тұжырымдардың 1, 4, 5 жолдардағы үлестірулерінде ақиқат мән қабылдайды. Конъюнкцияның ақиқаттық кестесңн пайдаланып, осы жолдардан қарапайым конъюнкция құрайық.

   Бірінші жолдағы мәндерде  xyz ақиқат,

   Төртінші  жолдағы мәндерде Øxyz ақиқат,

   Бесінші жолдағы мәндерде xØyØz ақиқат.

   Енді, осы қарапайым конъюнкциялардан жетілдірілген нормал дизъюнктивті форма құрайық:

   хyz Ú Øxyz Ú xØyØz.

   Бұл формуланың ақиқаттық кестесінің  А(x,y,z) формуласының ақиқаттық кестесімен сәйкес кедетіндігін тексеру қиын емес. Себебі, басқа жолдардаңы қарапайым тұжырымдардың мәндерінің үлестірулерінде жоғырыдағы қарапайым конъюнкциялардың әрқайсысы жалған мән қабылдайды.

   А(x,y,z)= хyz Ú Øxyz Ú xØyØz.

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

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

   Мәселен, жоғарыда қарастырылған формуланың ЖКНФ келесі түрде болады: