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

Бұл бөлімде 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. Барлық алынған дизъюнкцияларды ∧ арқылы көбейтіңіз — бұл ЖНКФ болады.