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

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,18 Mb.

Достарыңызбен бөлісу: