Тесты по теме 31 VI тарау. Алгоритмдер теориясының ЭлементтерІ 34

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

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

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

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

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

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

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

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

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

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

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

жүктеу 8,05 Mb.

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