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

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

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

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

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

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

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

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

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

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

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

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

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

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

_{1.14 Логикалық байланыстардың толық жүйелері}

₁, ₂, …, _n логикалық амалдардың символдары болсын. Егер тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ₁, ₂, …, _n амалдарының көмегімен құрылған формула бар болса, онда <₁, ₂, …, _n> жүйе толық деп аталады.

Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және КНФ болғандықтан, <, ,  > – толық жүйе екендігі түсінікті.

Лемма 9.1 Логикалық байланыстардың келесі жиындары:

<, , ,  >, <,  >, <,  >, <, >

толық жүйе құрайды.

Лемма 9.2 <, ,  >, < > жиындары логикалық амалдардың толық жүйесін құрмайды.

Тақырып бойынша тесттер

1. Келесі импликациялардың қайсысы жалған?

1) егер 22=4, онда 2>3;

2) егер 22=4, онда 2<3;

3) егер 22=5, онда 2<3;

4) егер 22=5, онда 2>3;

2. Келесі сөйлемдердің қайсысы тұжырым болмайды?

1) «Информатика» кафедрасының студенті.

2) Париж – Испания астанасы.

3) 3 саны А жиынына тиісті.

3. Айнымалылардың қайсылары бір бірінің терістеулері болады:

1) 2>3, 23;

2) 6<9, 6>9;

3) f функциясы жұп, f функциясы тақ;

4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі.
4. AB тұжырымы ақиқат болсын. (AB )  ( AB ) тұжырымы қандай логикалық мәнге ие болады?

1) ақиқат

2) жалған
5.  (PQ )  ((PQ ) P) формуланы ықшамдаңыз:

1) 1

2) 0

3) Р

4) Q
<sub>6. Келесі өрнектердің қайсысы формула болады?:

1) ((P( QR ))  ((P~ R ) Q ))

2) ((PQ) R) S
7. КНФ-ті табыңыз: (xz )(xy)

1) x(yz)

2) (xy)(yz)

3) yz
8. 0 мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті бірмүшені құрыңыз</sub>:

1) xy

2) xy

3) xy

4) x y
_{9. формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз:}

1)  (xyz )

2)  xy
10. ДНФті табыңыз: (x~y)  ( zT )

1) (xyzT)  (xyzT);

2) x yz

жүктеу 8,05 Mb.

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