ლოგიკური ფუნქციის კავშირებითი ნორმალური ფორმა ეწოდება. შემაერთებელი ნორმალური ფორმა. მედიანისთვის scnf-ის აგების მაგალითი

მოდით გავაცნოთ ელემენტარული დისიუნქციის ცნება.

ელემენტარული დისიუნქცია არის ფორმის გამოხატულება

ლოგიკური ფუნქციის შემაერთებელი ნორმალური ფორმა (CNF) არის ნებისმიერი სასრული სიმრავლის შეერთება წყვილ-წყვილად განსხვავებული ელემენტარული დისიუნქციებისა. მაგალითად, ლოგიკური ფუნქციები

ელემენტარული დისიუნქციების კავშირებია. ამიტომ ისინი იწერება კავშირებითი ნორმალური ფორმით.

ანალიტიკური გამოხატვის მიერ მოცემული თვითნებური ლოგიკური ფუნქცია შეიძლება შემცირდეს CNF-მდე შემდეგი ოპერაციების შესრულებით:

ინვერსიის წესის გამოყენება, თუ უარყოფის ოპერაცია გამოიყენება ლოგიკურ გამოხატულებაზე;

განაწილების აქსიომის გამოყენება გამრავლების მიმართ:

შთანთქმის ოპერაციის გამოყენებით:

გამონაკლისები განმეორებადი ცვლადების ან მათი უარყოფების დისუნქციებში;

ყველა იდენტური ელემენტარული დისიუნქციის ამოღება, გარდა ერთისა;

ყველა დისიუნქციის წაშლა, რომელიც ერთდროულად მოიცავს ცვლადს და მის უარყოფას.

ჩამოთვლილი მოქმედებების მართებულობა გამომდინარეობს ლოგიკის ალგებრის ძირითადი აქსიომებიდან და იდენტურობის მიმართებებიდან.

კავშირებით ნორმალურ ფორმას სრულყოფილს უწოდებენ, თუ მასში შემავალი ყოველი ელემენტარული დისიუნქცია შეიცავს ყველა ცვლადს, რომელზედაც დამოკიდებულია ფუნქცია პირდაპირი ან შებრუნებული სახით.

CNF-ის სრულყოფილ CNF-ად გარდაქმნა ხორციელდება შემდეგი ოპერაციების შესრულებით:

ცვლადების კავშირების თითოეულ ელემენტარულ დისიუნქციაზე დამატებები და მათი უარყოფა, თუ ისინი არ შედის ამ ელემენტარულ დისიუნქციაში;

განაწილების აქსიომის გამოყენება;

ყველა იდენტური ელემენტარული დისუნქციის ამოღება, გარდა ერთისა.

ნებისმიერი ლოგიკური ფუნქცია შეიძლება წარმოდგენილი იყოს სრულყოფილ CNF-ში გარდა

იდენტურად უდრის ერთს (). სრულყოფილი CNF-ის გამორჩეული თვისება ის არის, რომ მასში ლოგიკური ფუნქციის წარმოდგენა უნიკალურია.

სრულყოფილ CNF ფუნქციაში შემავალ ელემენტარულ დისუნქციებს ნულოვანი კომპონენტები ეწოდება. ყოველი ნულოვანი კომპონენტი სრულყოფილ CNF-ში ქრება ცვლადი მნიშვნელობების ერთადერთ ნაკრებზე, რომელიც არის ფუნქციის ნულოვანი ნაკრები. შესაბამისად, ლოგიკური ფუნქციის ნულოვანი კომპლექტების რაოდენობა ემთხვევა მის სრულყოფილ CNF-ში შეტანილი ნულოვანი კომპონენტების რაოდენობას.

ლოგიკური ფუნქცია ნულოვანი მუდმივი სრულყოფილ CNF-ში წარმოდგენილია ნულის 2n შემადგენელი შეერთებით. ჩამოვაყალიბოთ ლოგიკური ფუნქციის SKNF-ის შედგენის წესი კორესპონდენციის ცხრილის მიხედვით.

კორესპონდენციის ცხრილის თითოეული სტრიქონისთვის, რომელშიც ფუნქცია ნულის ტოლია, შედგენილია ყველა ცვლადის ელემენტარული დისუნქცია. დისიუქცია მოიცავს თავად ცვლადს, თუ მისი მნიშვნელობა ნულის ტოლია, ან უარყოფას, თუ მისი მნიშვნელობა ერთის ტოლია. მიღებული ელემენტარული დისიუნქციები გაერთიანებულია შემაერთებელი ნიშნით.


მაგალითი 3.4.საძიებო ცხრილით 2.2 მოცემული z(x) ლოგიკური ფუნქციისთვის, ჩვენ განვსაზღვრავთ სრულყოფილ კავშირურ ფორმას.

ცხრილის პირველი რიგისთვის, რომელიც შეესაბამება ნულოვანი ფუნქციის კომპლექტს 000, ვპოულობთ null კომპონენტს. მსგავსი ოპერაციების შესრულება მეორე, მესამე და მეხუთე რიგებისთვის, ჩვენ განვსაზღვრავთ სასურველ სრულყოფილ CNF ფუნქციას:

უნდა აღინიშნოს, რომ ფუნქციებისთვის, რომელთა ერთეულების რაოდენობა აღემატება ნულოვანი კომპლექტების რაოდენობას, უფრო კომპაქტურია მათი ჩაწერა SKNF-ის სახით და პირიქით.

სტანდარტული საფუძველი. ელემენტარული ფორმულები ლიტერალებია. ელემენტარული შეერთება (დისიუნქცია). დისჯუნქტური (შეერთება) ნორმალური ფორმა და სრულყოფილი ფორმა. თეორემა: ნებისმიერი ლოგიკური ფუნქცია 0-ის გარდა (1-დან) შეიძლება წარმოდგენილი იყოს როგორც SDNF (SKNF). სტანდარტული ბაზის სისრულე. სრული ბაზების მაგალითები: ჟეგალკინის საფუძველი, შეფერის ინსულტი, პირსის ისარი.

სტანდარტული საფუძველი არის სამი საწყისი ლოგიკური ალგებრის მოქმედების ნაკრები: შეკრება (კავშირი), გამრავლება (გადაკვეთა) და უარყოფა.

აქ ჩვენ დავუძახებთ სიტყვასიტყვით ცვლადი x ან მისი უარყოფა x და აღნიშნავენ xˆ. სხვადასხვა ცვლადით განსაზღვრული მრავალი ლიტერალის ლოგიკური კვეთა, ე.ი. ფორმის გამოხატულება X = xˆ 1 xˆ 2 . . . xˆ l, ე.წ ელემენტარული შეერთება . მოთხოვნა, რომ ყველა ცვლადი იყოს განსხვავებული, განპირობებულია შემდეგით. თუ კავშირი მოიცავს რამდენიმე იდენტურ ლიტერალს, მაშინ კავშირის ურთიერთობის, ასოციაციურობისა და იმპოტენციის გამო, ეკვივალენტურ ფორმულაზე გადასვლის გამო, შეგვიძლია დავტოვოთ მხოლოდ ერთი ლიტერალი (მაგალითად, x 1 x 1 = x 1). თუ კავშირი შეიცავს ცვლადს და მის უარყოფას, მაშინ ფორმულა უდრის მუდმივ 0-ს, ვინაიდან x x = 0 და ნებისმიერი Y ფორმულისთვის გვაქვს Y x x = 0.

რამდენიმე ელემენტარული კავშირის დისუნქცია ეწოდება დისუნქციური ნორმალური ფორმა , ან DNF . Მაგალითად,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

თუ მოცემული DNF-ის თითოეულ ელემენტარულ შეერთებაში ცვლადების შემადგენლობა იგივეა, მაშინ DNF ე.წ. სრულყოფილი . მოყვანილი მაგალითი არის DNF, რომელიც არ არის სრულყოფილი. პირიქით, ფორმულა

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

იდეალური ფორმაა.

ვინაიდან ბულის ალგებრაში შეკრება და გამრავლება არის სიმეტრიული ოპერაციები და ყოველთვის შეიძლება შეკრების ინტერპრეტაცია გამრავლებად და გამრავლება, როგორც შეკრება, ასევე არსებობს ორმაგი კონცეფცია - შემაერთებელი ნორმალური ფორმა (KNF ), რომელიც ელემენტარული დისიუნქციების შეერთებაა და სრულყოფილი კავშირების ფორმა (SKNF ). სიმეტრიული ნახევრადრების ორმაგობის პრინციპიდან გამომდინარეობს, რომ ნებისმიერი დებულება DNF-ის შესახებ შეესაბამება ორმაგ განცხადებას CNF-ის შესახებ, რომელიც მიიღება შემატების (განშორების) შეცვლით გამრავლებით, გამრავლებით (შეერთებით) შეკრებით, მუდმივი 0-ით 1-ით, მუდმივით 1-ით. მუდმივი 0-ით, წესრიგის მიმართებები ორმაგი (შებრუნებული) თანმიმდევრობით. ამიტომ, შემდგომში ჩვენ ყურადღებას გავამახვილებთ მხოლოდ DNF-ის შესწავლაზე.

თეორემა 1.4.ნებისმიერი ლოგიკური ფუნქცია, გარდა მუდმივი 0-ისა, შეიძლება წარმოდგენილი იყოს როგორც SDNF.

◀მოდით, შევთანხმდეთ x σ-ით, რომ ვიგულისხმოთ x ფორმულა, თუ σ = 1, და x ფორმულა, თუ σ = 0. მოდით, ფუნქციამ f(y 1 , . . . , y n) მიიღოს მნიშვნელობა 1 ვექტორზე (t 1). , . . . , t n ) (ასეთ ვექტორს ე.წ შემადგენელი ერთეული ). შემდეგ ელემენტარული შეერთება ასევე იღებს მნიშვნელობას 1 ამ კომპლექტში, მაგრამ ქრება ყველა სხვა n-განზომილებიან ლოგიკურ ვექტორებზე. განვიხილოთ ფორმულა

რომელშიც ჯამი (კავშირი) ვრცელდება არგუმენტების მნიშვნელობების ყველა იმ სიმრავლეზე (t 1 , . . . . . . . . . , t n), რომლებზეც მოცემული ფუნქცია იღებს მნიშვნელობას 1. გაითვალისწინეთ, რომ ასეთი სიმრავლეების სიმრავლე არ არის ცარიელი, ასე რომ ჯამი შეიცავს მინიმუმ ერთ ტერმინს.

ადვილი მისახვედრია, რომ ფორმულა Φ იქცევა 1-ად მათთვის და მხოლოდ იმ ცვლადების მნიშვნელობებისთვის, რომლებისთვისაც განხილული ფუნქცია იქცევა 1-ად. აქედან გამომდინარე, ფორმულა Ψ წარმოადგენს f ფუნქციას.

დასკვნა 1.1.სტანდარტული საფუძველი დასრულებულია.

◀ მართლაც, თუ ფუნქცია არ არის მუდმივი 0, მაშინ ის შეიძლება იყოს წარმოდგენილი როგორც SDNF, რომელიც არის ფორმულა სტანდარტულ საფუძველზე. მუდმივი 0 შეიძლება წარმოდგენილი იყოს, მაგალითად, ფორმულით f(x 1 , x 2 , . . . , x n) = x 1 x 1 .

მაგალითი 1.2.განვიხილოთ სამი ცვლადის ფუნქცია m(x 1 , x 2 , x 3) (ცხრილი 1.4), ე.წ. უმრავლესობის ფუნქცია ̆. ეს ფუნქცია ფასდება 1-მდე, თუ მისი არგუმენტების ნახევარზე მეტს აქვს მნიშვნელობა 1. ამიტომ მას ხშირად ხმის მიცემის ფუნქციას უწოდებენ. მოდით ავაშენოთ SDNF ამისთვის.

სტანდარტული ბაზის სისრულე საშუალებას გაძლევთ აირჩიოთ ფუნქციების სხვა სრული სისტემები. F ნაკრების სისრულე შეიძლება დადგინდეს შემდეგი მოსაზრებებიდან. დავუშვათ, სამი სტანდარტული ბუზის ფუნქციიდან თითოეული წარმოდგენილია F ფორმულით. მაშინ, თეორემა 1.3-ის ძალით, F-ის სხვაობა სრული იქნება.

მაგალითი 1.3.ოპერაციების სიმრავლე მოდულო 2 მიმატება, გამრავლება და მუდმივი 1 ეწოდება ჟეგალკინის საფუძველი . მოდული 2 შეკრება და გამრავლება არის Z2 რგოლის ძირითადი მოქმედებები, მათი დახმარებით შედგენილი გამონათქვამები არის პოლინომები Z2 რგოლზე. მუდმივი 1 ამ შემთხვევაში საჭიროა თავისუფალი წევრის ჩასაწერად. ვინაიდან xx \u003d x, მაშინ მრავალწევრში ყველა ფაქტორს აქვს ხარისხი 1. ამიტომ, მრავალწევრის დაწერისას, შეგიძლიათ გააკეთოთ ხარისხის კონცეფციის გარეშე. ფორმულების მაგალითები ჟეგალკინის საფუძველზე:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

ნებისმიერ ასეთ ფორმულას ეწოდება ჟეგალკინის პოლინომი. სინამდვილეში, ჟეგალკინის პოლინომი არის პოლინომი Z2 რგოლზე.

ადვილია ფორმულების აგება ჟეგალკინის საფუძველზე, რომელიც წარმოადგენს სტანდარტული საფუძვლის დამატებისა და უარყოფის ოპერაციებს (ორი ფუძის გამრავლება ხშირია):

x+y=x⊕y⊕xy, x=x⊕1.

ამიტომ, ჟეგალკინის საფუძველი არის სრული ნაკრები.
შეიძლება აჩვენოს, რომ ნებისმიერი ლოგიკური ფუნქციისთვის ჟეგალკინის პოლინომი ცალსახად არის განსაზღვრული

(უფრო ზუსტად, ვადების თანმიმდევრობამდე). ჟეგალკინის მრავალწევრის კოეფიციენტები მცირე რაოდენობის ცვლადებით შეიძლება მოიძებნოს განუსაზღვრელი კოეფიციენტების მეთოდით.

მაგალითი 1.4.განვიხილოთ ერთი ფუნქციის კომპლექტი - შაფერის ინსულტი*. ეს ნაკრები დასრულებულია, რომელიც გამომდინარეობს შემდეგი ადვილად დამოწმებული იდენტობებიდან:

x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).

მაგალითი 1.5.ერთი ფუნქციისგან, პირსის ისარისაგან შემდგარი საფუძველიც დასრულებულია. ამის დადასტურება შეფერის ინსულტის შემთხვევის მსგავსია. თუმცა, ეს დასკვნა ასევე შეიძლება გამოვიტანოთ სიმეტრიული ნახევრად დგომების ორმაგობის პრინციპის საფუძველზე.

* შაფერის ინსულტი ორობითი ოპერაციაა, მაგრამ არა ასოციაციური. ამიტომ, ინფიქსის ფორმის გამოყენებისას ფრთხილად უნდა იყოთ: შედეგი დამოკიდებულია ოპერაციების შესრულების თანმიმდევრობაზე. ამ შემთხვევაში რეკომენდებულია ცალსახად მიუთითოთ მოქმედებების თანმიმდევრობა ფრჩხილების გამოყენებით, მაგალითად ჩაწერეთ (x | y) | z, არა x | y | z, თუმცა ორივე ფორმა ექვივალენტურია.

მარტივი შეერთება დაურეკა შეერთება ერთი ან რამდენიმე ცვლადები, ზე ეს თითოეული ცვლადი ხვდება არა მეტი ერთი ჯერ (ან თავად, ან მისი უარყოფა).

მაგალითად, არის მარტივი კავშირი,

განმანაწილებელი ნორმალური ფორმა(DNF) დაურეკა დისიუნქცია მარტივი კავშირები.

მაგალითად, გამოხატულება არის DNF.

სრულყოფილი განმანაწილებელი ნორმალური ფორმა(SDNF) დაურეკა ასეთი განმანაწილებელი ნორმალური ფორმა, ზე რომელიც in ყოველი შეერთება შედის ყველა ცვლადები მოცემული სია (ან საკუთარ თავს, ან მათ უარყოფა), და in ერთი და მოცულობა იგივეკარგი.

მაგალითად, გამოთქმა არის DNF, მაგრამ არა SDNF. გამოხატულება არის SDNF.

მსგავსი განმარტებები (კავშირის ჩანაცვლებით დისიუნქციით და პირიქით) მართალია CNF-სა და SKNF-სთვის. წარმოგიდგენთ ზუსტ ფორმულირებებს.

მარტივი დისიუნქცია დაურეკა დისიუნქცია ერთი ან რამდენიმე ცვლადები, ზე ეს თითოეული ცვლადი შედის არა მეტი ერთი ჯერ (ან თავად, ან მისი უარყოფამაგალითად, გამოთქმა არის მარტივი დისიუნქცია,

კონიუნქტივალური ნორმალური ფორმა(KNF) დაურეკა შეერთება მარტივი დისუნქციები(მაგალითად, გამოთქმა - CNF).

სრულყოფილი კავშირებითი ნორმალური ფორმა (CKNF) არის CNF, რომელშიც ყოველი მარტივი დისიუნქცია მოიცავს მოცემული სიის ყველა ცვლადს (თვითონ ან მათ უარყოფით) და იმავე თანმიმდევრობით.

მაგალითად, გამოხატულება არის SKNF.

წარმოგიდგენთ ალგორითმებს ერთი ფორმიდან მეორეზე გადასვლისთვის. ბუნებრივია, კონკრეტულ შემთხვევებში (გარკვეული შემოქმედებითი მიდგომით), ალგორითმების გამოყენება შეიძლება იყოს უფრო შრომატევადი, ვიდრე მარტივი გარდაქმნები, რომლებიც იყენებენ მოცემული ფორმის სპეციფიკურ ფორმას:

ა) DNF-დან CNF-ზე გადასვლა

ამ გადასვლის ალგორითმი ასეთია: ჩვენ ვათავსებთ ორ უარყოფას DNF-ზე და დე მორგანის წესების გამოყენებით (ზედა უარყოფის შეხების გარეშე), ვაბრუნებთ DNF-ის უარყოფას DNF-ზე. ამ შემთხვევაში, თქვენ უნდა გახსნათ ფრჩხილები შთანთქმის წესით (ან ბლეიკის წესით). მიღებული DNF-ის (ზედა) უარყოფა (ისევ დე მორგანის წესით) დაუყოვნებლივ გვაძლევს CNF-ს:

გაითვალისწინეთ, რომ CNF ასევე შეიძლება მივიღოთ ორიგინალური გამონათქვამიდან, თუ ამოვიღებთ ზებრეკეტებისთვის;

ბ) CNF-დან DNF-ზე გადასვლა

ეს გადასვლა ხორციელდება ფრჩხილების უბრალოდ გახსნით (ამ შემთხვევაში კვლავ გამოიყენება შთანთქმის წესი)

ამრიგად, ჩვენ მივიღეთ DNF.

საპირისპირო გადასვლა (SDNF-დან DNF-ზე) დაკავშირებულია DNF-ის მინიმიზაციის პრობლემასთან. ეს უფრო დეტალურად იქნება განხილული განყოფილებაში. 5, აქ ჩვენ ვაჩვენებთ როგორ გავამარტივოთ DNF (ან SDNF) ბლეიკის წესის მიხედვით. ასეთ DNF ეწოდება შემოკლებული DNF;

გ) აბრევიატურა DNF (ან SDNF) მიერ წესი ბლეიკი

ამ წესის გამოყენება ორი ნაწილისგან შედგება:

თუ DNF-ში განსხვავებულ ტერმინებს შორის არის ტერმინები , შემდეგ ვამატებთ ტერმინს მთელ დისიუნქციას რომ 1 რომ 2. ამ ოპერაციას ვაკეთებთ რამდენჯერმე (შეიძლება თანმიმდევრულად, შესაძლებელია ერთდროულად) ყველა შესაძლო წყვილი ტერმინისთვის და შემდეგ ვიყენებთ ჩვეულებრივ შთანთქმას;

თუ დამატებული ტერმინი უკვე შეიცავს DNF-ში, მაშინ ის შეიძლება საერთოდ გაუქმდეს, მაგალითად,

ან

რა თქმა უნდა, შემოკლებული DNF არ არის ცალსახად განსაზღვრული, მაგრამ ისინი ყველა შეიცავს ასოების ერთსა და იმავე რაოდენობას (მაგალითად, არსებობს DNF , მასზე ბლეიკის წესის გამოყენების შემდეგ, შეიძლება მივიღოთ მოცემულის ეკვივალენტური DNF):

გ) DNF-დან SDNF-ზე გადასვლა

თუ ცვლადი აკლია რაიმე მარტივ კავშირში, მაგალითად, ზ, ჩადეთ მასში გამოთქმა, რის შემდეგაც ვხსნით ფრჩხილებს (განმეორებით განცალკევებულ ტერმინებს არ ვწერთ). Მაგალითად:

დ) CNF-დან SKNF-ზე გადასვლა

ეს გადასვლა ხორციელდება წინას მსგავსი წესით: თუ რაიმე ცვლადი აკლია მარტივ დისიუნქციაში (მაგალითად, ზ, შემდეგ მას ვამატებთ გამონათქვამს (ეს არ ცვლის თავად დისუნქციას), რის შემდეგაც ვხსნით ფრჩხილებს განაწილების კანონის გამოყენებით):

ამრიგად, SKNF მიიღება CNF-დან.

გაითვალისწინეთ, რომ მინიმალური ან შემოკლებული CNF ჩვეულებრივ მიღებულია შესაბამისი DNF-დან.

მარტივი დისუნქცია(ინგლ. inclusive disjunction) ან დისიუნქტომური(ინგლისურად disjunct) ეწოდება ერთი ან რამდენიმე ცვლადის დისიუნსქციას ან მათ უარყოფას და თითოეული ცვლადი ხდება არა უმეტეს ერთხელ.

მარტივი დისუნქცია

  • სრული, თუ თითოეული ცვლადი (ან მისი უარყოფა) შედის მასში ზუსტად ერთხელ;
  • ერთფეროვანი, თუ ის არ შეიცავს ცვლადების უარყოფას.

შემაერთებელი ნორმალური ფორმა, CNF(ინგლისური კავშირებითი ნორმალური ფორმა, CNF) არის ნორმალური ფორმა, რომელშიც ლოგიკური ფუნქცია აქვს რამდენიმე მარტივი პუნქტის შეერთების ფორმას.

CNF მაგალითი:$f(x,y) = (x \lor y) \land (y \lor \neg (z))$

SKNF

იდეალური შემაერთებელი ნორმალური ფორმა, SKNF(ინგლისური სრულყოფილი შეერთების ნორმალური ფორმა, PCNF) არის CNF, რომელიც აკმაყოფილებს პირობებს:

  • მას არ აქვს იდენტური მარტივი დისიუნქციები
  • ყოველი მარტივი გათიშვა დასრულებულია

SKNF მაგალითი:$f(x,y,z) = (x \lor \neg (y) \lor z) \land (x\lor y \lor \neg (z))$

თეორემა:ნებისმიერი ლოგიკური ფუნქციისთვის $f(\vec ( x))$, რომელიც არ უდრის იდენტურ ერთეულს, არის SKNF, რომელიც განსაზღვრავს მას.

მტკიცებულება:ვინაიდან $\neg ( f ) (\vec x)$ ფუნქციის ინვერსია უდრის ერთს იმ ტოპებზე, რომლებზეც $f(\vec x)$ ნულის ტოლია, მაშინ SDNF $\neg ( f ) (\vec x)$ შეიძლება დაწეროთ ასე:

$\neg (f) (\vec x) = \bigvee\limits_ (f(x^ ( \sigma_ (1)) , x^ ( \sigma_ (2)) , ... ,x^ ( \sigma_ (n ) )) = 0 ) (x_ ( 1 ) ^ ( \ სიგმა_ ( 1 ) ) \ სოლი x_ ( 2 ) ^ ( \ სიგმა_ ( 2 ) ) \ სოლი ... \ სოლი x_ ( n ) ^ ( \ სიგმა_ ( n ) )) $, სადაც $ \sigma_ (i) $ აღნიშნავს უარყოფის არსებობას ან არარსებობას $ x_ (i) $-ზე

იპოვეთ გამოხატვის მარცხენა და მარჯვენა მხარის ინვერსია:

$ f(\vec x) = \neg (( \bigvee\limits_ (f(x^ ( \sigma_ (1)) , x^ ( \sigma_ (2)) , ... ,x^ ( \sigma_ (n ) )) = 0 ) (x_ ( 1 ) ^ ( \ სიგმა_ ( 1 ) ) \ სოლი x_ ( 2 ) ^ ( \ სიგმა_ ( 2 ) ) \ სოლი ... \ სოლი x_ ( n ) ^ ( \ სიგმა_ ( n ))))))) $

მარჯვენა მხარეს მიღებულ გამონათქვამზე დე მორგანის წესის ორჯერ გამოყენებისას მივიღებთ: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots , x^ ( \ sigma_n )) = 0 ) $ $ (\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) )) $

ბოლო გამოთქმა არის SKNF. ვინაიდან SKNF მიიღება SDNF-დან, რომელიც შეიძლება აშენდეს ნებისმიერი ფუნქციისთვის, რომელიც არ არის იდენტური ნული, თეორემა დამტკიცდა.

SKNF-ის აგების ალგორითმი სიმართლის ცხრილის მიხედვით

  • ჭეშმარიტების ცხრილში ჩვენ აღვნიშნავთ ცვლადების იმ კომპლექტს, რომლებზეც ფუნქციის ღირებულება $0$-ის ტოლია.
  • თითოეული მონიშნული სიმრავლისთვის ჩვენ ვწერთ ყველა ცვლადის დისუნქციას შემდეგი წესის მიხედვით: თუ რომელიმე ცვლადის მნიშვნელობა არის $0$, მაშინ ცვლადს ჩავრთავთ დისუნქციაში, წინააღმდეგ შემთხვევაში მის უარყოფას.
  • ყველა მიღებულ დისუნქციას ვაკავშირებთ შეერთების ოპერაციებით.

მედიანისთვის SKNF-ის აგების მაგალითი

ერთი). ჭეშმარიტების ცხრილში ჩვენ აღვნიშნავთ ცვლადების იმ კომპლექტს, რომლებზეც ფუნქციის ღირებულება $0$-ის ტოლია.

x წ ზ $ \langle x,y,z \rangle $
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

2). თითოეული მონიშნული სიმრავლისთვის ვწერთ ყველა ცვლადის შეერთებას შემდეგი წესის მიხედვით: თუ რომელიმე ცვლადის ღირებულებაა $0$, მაშინ ცვლადს ჩავრთავთ დისუნქციაში, წინააღმდეგ შემთხვევაში მის უარყოფას.

x წ ზ $ \langle x,y,z \rangle $
0 0 0 0 $(x \lor y \lor z)$
0 0 1 0 $(x \lor y \lor \neg (z))$
0 1 0 0 $(x \lor \neg (y) \lor z)$
0 1 1 1
1 0 0 0 $(\neg ( x) \lor y \lor z)$
1 0 1 1
1 1 0 1
1 1 1 1

3). ყველა მიღებულ დისუნქციას ვაკავშირებთ შეერთების ოპერაციებით.

$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg (x) \lor y \lor z) \land (x \lor \neg (y) \lor z) \land (x \lor y \lor \neg (z))$

SKNF მაგალითები ზოგიერთი ფუნქციისთვის

Pierce arrow: $ x \ქვემოთ y = (\neg (x) \lor (y)) \land (( x) \lor \neg (y)) \land (\neg (x) \lor \neg (y) )$

ექსკლუზიური ან: $ x \oplus y \oplus z = (\neg (x) \lor \neg (y) \lor z) \land (\neg (x) \lor y \lor \neg (z)) \land (x \lor \neg (y) \lor \neg (z)) \land (x \lor y \lor z)$

შემაერთებელი ნორმალური ფორმა მოსახერხებელია თეორემების ავტომატური მტკიცებულებისთვის. ნებისმიერი ლოგიკური ფორმულა შეიძლება შემცირდეს CNF-მდე. ამისათვის შეგიძლიათ გამოიყენოთ: ორმაგი უარყოფის კანონი, დე მორგანის კანონი, განაწილება.

ენციკლოპედიური YouTube