Ақиқат кестесін құру
Өткен сабақта ЖӘНЕ, НЕМЕСЕ, ЕМЕС операцияларының жеке-жеке кестелерін көрдік. Ал енді сұрақ туады: егер бір өрнекте осы амалдардың БІРНЕШЕУІ бірге кездессе ше? Мысалы, `A ∧ (B ∨ ¬A)` деген секілді ұзын өрнектің әр жағдайда қандай мән қабылдайтынын қалай білеміз? Дәл осындай күрделі өрнектерді реттеп, қадам-қадаммен есептеуге көмектесетін құрал — ақиқат кестесі.
Ақиқат кестесі — логикалық өрнектегі қарапайым пікірлердің БАРЛЫҚ мүмкін комбинациялары үшін, күрделі пікірдің қандай мән (0 немесе 1) қабылдайтынын көрсететін кесте.
Кестедегі жолдар саны айнымалылар санына тәуелді — әр қосымша айнымалы комбинация санын ЕКІ ЕСЕ көбейтеді:
| Айнымалылар саны | Комбинация саны |
|---|---|
| 2 (мыс. A, B) | 2² = 4: (0,0), (0,1), (1,0), (1,1) |
| 3 (мыс. A, B, C) | 2³ = 8 |
Мұны есте сақтаудың оңай жолы бар — бір қосымша айнымалы, бір қосымша «еселенген» жол дегенді білдіреді, дәл компьютер жадындағы биттер сияқты.
Кестені құру — реттелген процесс, оны әрдайым бір ретпен орындасаң қателеспейсің:
1. Айнымалылар санын (n) анықта.
2. Жол саны m = 2ⁿ формуласымен есепте.
3. Өрнектегі операциялар санын анықта.
4. Жақша мен басымдылықты ескеріп, операциялардың орындалу ретін белгіле.
5. Баған саны = айнымалылар саны + операциялар саны.
6. Кіріс айнымалыларының барлық мүмкін жиынтығын жаз.
7. Кестені басымдылық ретімен, баған-баған толтыр.
6-қадамдағы «барлық мүмкін жиынтықты» қалай жүйелі түрде жазамыз? Мұнда әдіс бар: біріншісі айнымалы бағанын ЕКІГЕ бөліп (жоғарғы жарты — 0, төменгі жарты — 1), екінші айнымалыны ТӨРТКЕ бөліп (0-1-0-1 ауыспалы топпен), үшіншісін СЕГІЗГЕ бөліп, осылай бөлу санын әрдайым ЕКІ ЕСЕ арттыра отырып, топ бір таңбаға жеткенше жалғастырамыз.
Алгоритмді нақты өрнекпен қолданып көрейік.
Берілді: A ∧ (B ∨ ¬B ∧ ¬A) формуласы.
Табу керек: осы формуланың ақиқат кестесі.
Неге дәл осылай шешеміз? Айнымалылар саны n=2 (A, B), сондықтан жол саны m=2²=4. Операциялар саны — 5 (¬B, ¬A, ∧, ∨, ∧), сондықтан баған саны 2+5=7. Әр аралық операцияны БӨЛЕК бағанға жазып, соңғы нәтижеге дейін қадам-қадаммен жүреміз.
| A | B | ¬B | ¬A | (¬B)∧(¬A) | B∨(...) | A∧(...) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Жауабы: формула ТЕК A=1, B=1 болғанда ғана ақиқат (1) мәнін қабылдайды, қалған барлық жағдайда — жалған (0).
Ал ақиқат кестесін толтырмас бұрын, жеке-жеке пікірлерді есептеу керек кездер де болады:
Берілді: A = «22 — жұп сан» (ақиқат), B = «3 — жұп сан» (жалған).
Табу керек: A∧B, A∨B, ¬A, ¬B мәндерін есептеу.
Шешуі: A = 1, B = 0 деп белгілейміз.
A∧B = 1∧0 = 0(жалған) — ЖӘНЕ екеуі де ақиқат болғанда ғана ақиқатA∨B = 1∨0 = 1(ақиқат) — НЕМЕСЕ біреуі ақиқат болса жеткілікті¬A = 0(жалған) — «22 жұп сан емес» деген жалған пікір¬B = 1(ақиқат) — «3 жұп сан емес» деген ақиқат пікір
Жауабы: A∧B = жалған, A∨B = ақиқат, ¬A = жалған, ¬B = ақиқат.
- Ақиқат кестесі — өрнектегі айнымалылардың барлық мүмкін комбинациясы үшін нәтижені көрсететін кесте.
- Жол саны m = 2ⁿ (n — айнымалылар саны); баған саны = айнымалылар + операциялар саны.
- Кестені толтырғанда алдымен айнымалылар жиынтығын жүйелі жазып, содан кейін басымдылық ретімен аралық бағандарды толтырамыз.
- Күрделі өрнекте әр аралық операцияны бөлек бағанға жазу қатені болдырмайды.