Жетілдірілген дизъюнктивті қалыпты форма (ЖДҚФ) және Жетілдірілген конъюнктивті қалыпты форма (ЖКҚФ)

Білім және Ғылым Министрлігі

Алматы Технологиялық Университеті

[pic 1]

№ 10 Зертхалық жұмыс

Тақырыбы: Жетілдірілген дизъюнктивті қалыпты форма (ЖДҚФ) және Жетілдірілген конъюнктивті қалыпты форма (ЖКҚФ)

Орындаған: Қуанышбай Асель ИС 21-13

Тексерген: Шайкулова Ақтоты

Алматы 2022

Конъюнкция.

«АВСD параллелограмының диагональдары қиылысады және қиылысу нүктесінде қақ бөлінеді» тұжырымының логикалық құрылымын анықтайық. Мысалдағы күрделі тұжырым «және» жалғауы арқылы байланысқан екі қарапайым тұжырымдардан құралып тұр. «АВСD параллелограмының диагональдары қиылысады» тұжырымын А деп, « қиылысу нүктесінде қақ бөлінеді» тұжырымын В деп белгілесек,онда берілген тұжырым «А және В» деп жазылады.

Анықтама. А және В тұжырымдарының конъюнкциясы(біріктірушісі) деп, егер екі тұжырымда ақиқат болғанда ақиқат және егер кем дегенде біреуі жалған болғанда жалған болатын жаңа тұжырымды айтамыз. А және В Тұжырымдарының конъюнкциясы мына символмен белгіленеді А∧В (АּВ, А В, А&В) және былай оқылады «А және В». А, В тұжырымдары конъюнкция мүшелері деп аталады.

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

Дизъюнкция.

Математикада «21 ≥10», «16 ≤ 7 » деген пікірлер жиі кездеседі. Енді осы пікірлердің ақиқат не жалғандығын анықтап көрейік. «21 ≥ 10» теңсіздігін «21 саны 10-нан артық немесе тең» деп оқимыз. Сонда бұл тұжырым «21>10» деген ақиқат және «21= 10» деген жалған тұжырымдардан құралып тұр.

Осы тұжырымдарды «немесе» жалғаулығымен байланыстыра алынған күрделі тұжырым ақиқат. «16 ≤ 7» жалған тұжырым, өйткені ол «16< 7» және «16= 7» деген екі жалған тұжырымдардан құралып тұр. «126 саны жұп немесе 3-ке бөлінеді» тұжырымы ақиқат,өйткені ондағы екі тұжырымда ақиқат. Бұл тұжырымдардың бәрі күрделі, олардың логикалық құрылымы «А немесе В» болады.

Анықтама. А және В тұжырымдарының дизъюнкциясы (ажыратушысы) деп, егер екі тұжырымның бірі ақиқат болса, ақиқат және егер екеуі де жалған болса, жалған болатын жаңа тұжырымды айтамыз. А және В тұжырымдардың дизъюнкциясы мына символмен белгіленеді: А∨В және былай оқылады «А немесе В». А, В Тұжырымдары дизъюнкция мүшелері деп аталады.

Буль функцияларының канондық формалары.

 Түрлі функцияларды белгілі бір ереже бойынша жазуды функциялардың канондық формасы деп атайды. Буль функциясын канондық түрде жазудың екі формасы бар: қалыпты форма және жетілдірілген қалыпты форма. А(а1, а2, …, аn) n тұжырымның формуласын қарастырайық.

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

Мысал 1. xyz, ¬xy – қарапайым конъюнкция; ¬x∨y∨z, y∨z, x∨¬z –қарапайым дизъюнкция.

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

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