პირველი რიგის ლოგიკის CNF-ად გადაქცევა:
- კონვერტირება უარყოფით ნორმალურ ფორმაში. შედეგების და ეკვივალენტების აღმოფხვრა: განმეორებით ჩანაცვლება; შეცვლა. …
- ცვლადების სტანდარტიზაცია. …
- შეასწორეთ განცხადება. …
- მოაგდეთ ყველა უნივერსალური კვანტიფიკატორი.
- გაანაწილეთ OR-ები შიგნით AND-ებზე: განმეორებით ჩაანაცვლეთ.-ით
რა არის CNF ფორმულა?
შეერთებული ნორმალური ფორმა (CNF) არის მიდგომა ლოგიკისადმი, რომელიც გამოხატავს ფორმულებს, როგორც პუნქტების კავშირებს AND ან OR-თან. ყოველი პუნქტი, რომელიც დაკავშირებულია კავშირით, ან AND, უნდა იყოს ან ლიტერალური ან შეიცავდეს დისიუნქციას, ან ოპერატორს. CNF სასარგებლოა ავტომატური თეორემის დასამტკიცებლად.
შეგიძლიათ გადაიყვანოთ DNF CNF-ად?
თუ გსურთ შემოიტანოთ დამატებითი ცვლადები, შეგიძლიათ გადაიყვანოთ DNF-დან CNF ფორმაში პოლინომიურ დროში წეიტინის ტრანსფორმაციისგამოყენებით. შედეგად მიღებული CNF ფორმულა თანაბარი იქნება ორიგინალური DNF ფორმულით: CNF ფორმულა დამაკმაყოფილებელი იქნება, თუ და მხოლოდ იმ შემთხვევაში, თუ ორიგინალური DNF ფორმულა იყო დამაკმაყოფილებელი.
როგორ მივიღო CNF?
უბრალოდ ჩაწერეთ სიმართლის ცხრილი, რომლის პოვნა საკმაოდ მარტივია და გამოიტანეთ თქვენი CNF და DNF. თუ გსურთ იპოვოთ DNF, უნდა დაათვალიეროთ ყველა სტრიქონი, რომელიც მთავრდება T-ით. როდესაც იპოვით ამ მწკრივებს, აიღეთ x, y და z მნიშვნელობები თითოეული შესაბამისი სვეტიდან. ამრიგად, თქვენ მიიღებთ (x∧y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧¬z)∨(¬x∧¬y∧z).
როგორ გადაიყვანთ განსხვავებულს?ნორმალური ფორმა?
შედგენილი წინადადება არის განსხვავებულ ნორმალურ ფორმაში, ან DNF, თუ ეს არის მარტივი ტერმინების კავშირების განშორება და თუ, უფრო მეტიც, თითოეული პროპოზიციური ცვლადი ჩნდება მაქსიმუმ ერთხელ თითოეულ კავშირში და ყოველი კავშირი ჩნდება მაქსიმუმ ერთხელ დისიუნქციაში.
