Қазақша рефераттар

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

Ақиқаттық кесте бойынша формуланы қалпына келтіру

Бұл бөлімде A(x, y, z) логикалық формуласының ақиқаттық кестесі берілгенде, сол кестеге дәл сәйкес келетін формуланы қалай құрастыруға болатынын көрсетеміз. Негізгі мақсат — формуланы жетілдірілген нормал дизъюнктивті формаға (ЖНДФ) және жетілдірілген нормал конъюнктивті формаға (ЖНКФ) келтіру.

Есеп шарты

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

x y z A(x,y,z)
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0

Бұл кестеде A=1 болатын жолдар — формуланы ЖНДФ арқылы құруға негіз болады, ал A=0 болатын жолдар — ЖНКФ үшін қолданылады.

ЖНДФ (жетілдірілген нормал дизъюнктивті форма)

Кесте бойынша A(x,y,z) формуласы 1-, 4-, 5-жолдарда ақиқат мән қабылдайды. Осы жолдардың әрқайсысынан қарапайым конъюнкция (минтерм) құрамыз:

  • 1-жол: x=1, y=1, z=1 болғандықтан, x ∧ y ∧ z.

  • 4-жол: x=1, y=0, z=0 болғандықтан, x ∧ ¬y ∧ ¬z.

  • 5-жол: x=0, y=1, z=1 болғандықтан, ¬x ∧ y ∧ z.

Енді осы конъюнкцияларды дизъюнкция арқылы біріктіріп, формуланың ЖНДФ-ын аламыз:

A(x,y,z) = (x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ y ∧ z)

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

ЖНДФ құру ережесі (қысқа алгоритм)

  1. Ақиқаттық кестеден A=1 болатын барлық жолдарды таңдаңыз.
  2. Әр жол үшін қарапайым конъюнкция құрыңыз: айнымалы 1 болса — өзін, ал 0 болса — терістеуін (¬) алыңыз.
  3. Барлық алынған конъюнкцияларды ∨ арқылы біріктіріңіз — бұл ЖНДФ болады.

ЖНКФ (жетілдірілген нормал конъюнктивті форма)

Тепе-тең ақиқат емес формуланы ЖНКФ-қа келтіру үшін ақиқаттық кестедегі A=0 болатын жолдарды негізге аламыз. Әрбір осындай жолдан қарапайым дизъюнкция (макстерм) құрамыз: егер айнымалы 1 болса — терістеуін, ал 0 болса — өзін аламыз.

Жоғарыдағы кесте үшін ЖНКФ мына түрде жазылады:

A(x,y,z) = (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ y ∨ z)

Мұндағы әр жақша — A=0 болатын нақты бір жолға сәйкес келетін макстерм.

ЖНКФ құру ережесі (қысқа алгоритм)

  1. Ақиқаттық кестеден A=0 болатын барлық жолдарды таңдаңыз.
  2. Әр жол үшін қарапайым дизъюнкция құрыңыз: айнымалы 1 болса — терістеуін, ал 0 болса — өзін алыңыз.
  3. Барлық алынған дизъюнкцияларды ∧ арқылы көбейтіңіз — бұл ЖНКФ болады.