1 тарау. ТҰжырымдар алгебрасы 5

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

жүктеу 1,18 Mb.

бет	14/34
Дата	16.01.2022
өлшемі	1,18 Mb.
	#32886

1 ... 10 11 12 13 14 15 16 17 ... 34

Дип.-ТҰЖЫРЫМДАР-АЛГЕБРАСЫ

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

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

х	у	z	А(x,y,z)
1	1	1	1
1	1	0	0
1	0	1	0
0	1	1	1
1	0	0	1
0	1	0	0
0	0	1	0
0	0	0	0

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

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

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

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

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

хyz  xyz  xyz.

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

А(x,y,z)= хyz  xyz  xyz.

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

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

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

А(x,y,z)= (хyz) (xyz)(xyz) (xyz) (xyz).

жүктеу 1,18 Mb.

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

1 ... 10 11 12 13 14 15 16 17 ... 34

1 тарау. ТҰжырымдар алгебрасы 5

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

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

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