Առաջին կարգի տրամաբանությունը CNF-ի փոխարկելու համար՝
- Փոխակերպել ժխտման նորմալ ձևի: Վերացնել հետևանքները և համարժեքները. բազմիցս փոխարինել; փոխարինել. …
- Փոփոխականների ստանդարտացում: …
- Սկոլեմիզացրեք հայտարարությունը: …
- Հեռացրեք բոլոր համընդհանուր չափիչները:
- Բաշխեք OR-ները դեպի ներս AND-ների վրա. մի քանի անգամ փոխարինեք.-ով
Ի՞նչ է CNF բանաձևը:
Համատեղ նորմալ ձևը (CNF) մոտեցում է բուլյան տրամաբանությանը, որն արտահայտում է բանաձևերը որպես նախադասությունների շաղկապումներ AND կամ OR-ի հետ: Յուրաքանչյուր նախադասություն, որը կապված է շաղկապով կամ AND-ով, պետք է լինի կամ բառացի կամ պարունակի անջատում կամ OR օպերատոր: CNF-ն օգտակար է թեորեմի ավտոմատացված ապացուցման համար։
Կարո՞ղ եք փոխարկել DNF-ը CNF-ի:
Եթե ցանկանում եք ներմուծել լրացուցիչ փոփոխականներ, կարող եք DNF-ից CNF ձևի վերածել բազմանդամ ժամանակում՝ օգտագործելով Tseitin փոխակերպումը: Ստացված CNF բանաձևը համարժեք կլինի սկզբնական DNF բանաձևի հետ.
Ինչպե՞ս կարող եմ ստանալ CNF:
Պարզապես գրեք ճշմարտության աղյուսակը, որը գտնելը բավականին պարզ է, և եզրակացրեք ձեր CNF-ն և DNF-ը: Եթե ցանկանում եք գտնել DNF, դուք պետք է նայեք բոլոր տողերին, որոնք ավարտվում են T-ով: Երբ գտնեք այդ տողերը, վերցրեք x, y և z արժեքները յուրաքանչյուր համապատասխան սյունակից: Այսպիսով, դուք ստանում եք (x∧y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧¬z)∨(¬x∧¬y∧z).
Ինչպե՞ս եք փոխակերպում դիզյունկտիվընորմալ ձև?
Բարդ դրույթը կոչվում է դիսյունկտիվ նորմալ ձևով կամ DNF, եթե այն պարզ տերմինների շաղկապներիդիսյունկցիա է, և եթե, ավելին, յուրաքանչյուր պրոպոզիցիոնալ փոփոխականը հանդիպում է առավելագույնը մեկ անգամ յուրաքանչյուր շաղկապում, և յուրաքանչյուր կապ հանդիպում է առավելագույնը մեկ անգամ դիսյունկցիոնում:
