მაგალითი.იპოვეთ CNF ფორმულები

~ ~

SDNF-ის სრულყოფილი განცალკევებული ნორმალური ფორმა შეიძლება აშენდეს შემდეგი ალგორითმის გამოყენებით:

1. = 1. DNF ალგორითმი

2. = 2. DNF ალგორითმი

3. = 3. DNF ალგორითმი

4. = 4. DNF ალგორითმი

5. გამოტოვეთ იდენტური ცრუ ტერმინები, ანუ ფორმის ტერმინები

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

7. გაიმეორეთ პუნქტი 4.

მაგალითი.იპოვეთ SDNF ფორმულები.

~

SCNF-ის ასაგებად, შეგიძლიათ გამოიყენოთ შემდეგი სქემა:

მაგალითი.იპოვეთ SDNF ფორმულები.

~

ცნობილია (თეორემები 2.11, 2.12), რომ SDNF და SCNF ცალსახად არის განსაზღვრული ფორმულით და, შესაბამისად, მათი აგება შესაძლებელია ფორმულის ჭეშმარიტების ცხრილის გამოყენებით.

SDNF-ისა და SCNF-ის აგების სქემა სიმართლის ცხრილის მიხედვით მოცემულია ქვემოთ, ფორმულისთვის ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. ვარჯიში.

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

2.2.2. განმარტეთ f 1-ისა და f 2-ის ეკვივალენტობის საკითხი მათი SDNF-მდე შემცირებით (ცხრილი 1).

2.2.3. იპოვეთ f 3-ის ორმაგი ფუნქცია განზოგადებული და ლოგიკური პრინციპის გამოყენებით (ცხრილი 1). შეადარეთ შედეგები.

№	ვ 1	ვ 2	ვ 3

2.3. საკონტროლო კითხვები.

2.3.1. განსაზღვრეთ განცხადება.

2.3.2. ჩამოთვალეთ განცხადების ძირითადი ოპერაციები.

2.3.3. რა არის სიმართლის ცხრილი?

2.3.4. შექმენით სიმართლის ცხრილები შემდეგი ფორმულებისთვის:

~ ~ ~ ;

2.3.5. ოპერაციების თანმიმდევრობის შესახებ კონვენციების გათვალისწინებით, გამოტოვეთ "დამატებითი" ფრჩხილები და "" ნიშანი ფორმულებში:

;

2.3.6. ეკვივალენტური გარდაქმნების გამოყენებით დაამტკიცეთ ფორმულების იდენტური ჭეშმარიტება:

2.3.7. იპოვნეთ ორმაგი ფორმულები:

)

2.3.8. შეამცირეთ შემდეგი ფორმულები სრულყოფილ DNF (SDNF) ფორმამდე:

~

2.3.9. შეამცირეთ შემდეგი ფორმულები სრულყოფილ CNF (SCNF) ფორმამდე:

~

ლაბორატორიული სამუშაო No3

თემა:ლოგიკური ფუნქციების მინიმიზაცია. Ლოგიკა"

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

3.1. თეორიული ინფორმაცია.

მინიმალური ფორმები

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

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

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

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

მოდით, მაგალითად, ფუნქცია იყოს მოცემული სრულყოფილად ნორმალური დისიუნგციური ფორმით:

ვადების დაჯგუფება და წებოვნების ოპერაციის გამოყენება გვაქვს .

სხვა დაჯგუფების მეთოდით ვიღებთ:

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

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

მრავალგანზომილებიანი კუბი

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

ნახ. 3.1 SDNF-ში წარმოდგენილი ფუნქციის ჩვენება სამგანზომილებიან კუბზე

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

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

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

ნახ.3.2 ფუნქციის დაფარვა

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

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

ბრინჯი. 3.3 ფუნქციების დაფარვა.

დატოვა – ; მარჯვნივ –

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

ბრინჯი. 3.4 ფუნქციის ჩვენება ოთხგანზომილებიან კუბზე

კარნოს რუკები

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

ბრინჯი. 3.5 კარნოს რუქები ორი, სამი და ოთხი ცვლადი

როგორც ჩვეულებრივი სიმართლის ცხრილებში, სიმრავლეების უჯრედები, რომლებშიც ფუნქცია იღებს 1 მნიშვნელობას, ივსება ერთეულებით (ნოლები ჩვეულებრივ არ ჯდება, ისინი შეესაბამება ცარიელ უჯრედებს). მაგალითად, ნახ. 3.6, ააჩვენებს კარნოს რუკას ფუნქციისთვის, რომლის ჩვენება ოთხგანზომილებიან კუბზე მოცემულია ნახ. 3.4. ნივთების გასამარტივებლად, ცვლადისთვის 1-ის მნიშვნელობების შესაბამისი რიგები და სვეტები მონიშნულია ხვეული ფრჩხილით, რომელიც მიუთითებს ამ ცვლადზე.

ბრინჯი. 3.6 კარნოს რუკაზე ოთხი ცვლადის ფუნქციის ჩვენება

(ა) და მისი მინიმალური დაფარვა (ბ)

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

კარნოს რუქიდან მინიტერმების წაკითხვა მარტივი წესის მიხედვით ხდება. უჯრედების ფორმირება ს-კუბი, მიეცი მინიტერი (n–s)- რანგი, რომელიც მოიცავს მათ (n–s)ცვლადები, რომლებიც ინარჩუნებენ იგივე მნიშვნელობებს ს-cube, სადაც მნიშვნელობა 1 შეესაბამება თავად ცვლადებს, ხოლო მნიშვნელობა 0 შეესაბამება მათ უარყოფას. ცვლადები, რომლებიც არ ინარჩუნებენ თავიანთ მნიშვნელობებს ს-კუბი, მინიმტერში არ არის. წაკითხვის სხვადასხვა ხერხი იწვევს ფუნქციის განსხვავებულ წარმოდგენას განსხვავებულ ნორმალურ ფორმაში (მარჯვნივ მარცხნივ მინიმალურია) (სურათი 3.7).

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

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

კუბურების კომპლექსი

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

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

ბრინჯი. 3.8 სამი ცვლადის ფუნქციის კუბების კომპლექსი ( ა) და მისი სიმბოლური წარმოდგენა ( ბ)

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

,

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

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

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

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

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

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

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

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

მოცემული განმარტებები ილუსტრირებულია ნახ. 3.9, სადაც შემცირებული დაფარვა (იხ. სურ. 3.9a, ) და მინიმალური დაფარვები (ნახ. 3.9ბ) და (იხ. ნახ. 3.9, ბ) გამოიხატება შემდეგნაირად.

განმარტება 1.კავშირებითი მონომი (ელემენტარული კავშირი)ცვლადების არის ამ ცვლადების შეერთება ან მათი უარყოფა.

Მაგალითად, ელემენტარული კავშირია.

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

Მაგალითად, ელემენტარული დისიუნქციაა.

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

Მაგალითად,- DNF.

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

Მაგალითად, – KNF.

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

ნორმალური ფორმების აგების ალგორითმი

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

მოიშორეთ ორმაგი ნეგატივები.

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

2.6. სრულყოფილი განმანაწილებელი და სრულყოფილი კავშირებითი ნორმალური ფორმები

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

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

სტრუქტურულად, SDNF თითოეული პროპოზიციური ალგებრის ფორმულისთვის, რომელიც შემცირებულია DNF-მდე, შეიძლება განისაზღვროს შემდეგნაირად:

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

განმარტება 3. სრულყოფილი შეერთების ნორმალური ფორმა(SCNF) არის CNF, რომელშიც თითოეული დისიუქციური მონომი შეიცავს თითოეულ ცვლადს სიმრავლიდან ზუსტად ერთხელ და ჩნდება ან თავად ან მისი უარყოფა.

სტრუქტურულად, SCNF თითოეული პროპოზიციური ალგებრის ფორმულისთვის CNF-მდე შემცირებული შეიძლება განისაზღვროს შემდეგნაირად.

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

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

SDNF-ის პოვნის მეთოდები

1 მეთოდი

მე-2 მეთოდი

აირჩიეთ ხაზები, სადაც ფორმულა იღებს მნიშვნელობას 1;

ჩვენ ვადგენთ კავშირების დისუნქციას იმ პირობით, რომ თუ ცვლადი შედის კავშირში 1-ის მნიშვნელობით, მაშინ ჩავწერთ ამ ცვლადს, თუ მნიშვნელობით 0, მაშინ მის უარყოფას; ჩვენ ვიღებთ SDNF.

თეორემა 2.ცვლადების ყოველი ლოგიკური ფუნქცია, რომელიც არ არის იდენტური ჭეშმარიტი, შეიძლება წარმოდგენილი იყოს SCNF-ში და უნიკალური გზით.

SCNF-ის პოვნის მეთოდები

1 მეთოდი- ექვივალენტური გარდაქმნების გამოყენებით:

მე-2 მეთოდი- სიმართლის ცხრილების გამოყენებით:

აირჩიეთ ხაზები, სადაც ფორმულა იღებს მნიშვნელობას 0;

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

მაგალითი 1. CNF ფუნქციების აგება.

გამოსავალი

მოდით აღმოვფხვრათ შემაერთებელი "" ცვლადების ტრანსფორმაციის კანონების გამოყენებით:

= /დე მორგანის კანონები და ორმაგი უარყოფა/ =

/დისტრიბუციული კანონები/ =

მაგალითი 2.მიეცით ფორმულა DNF-ს.

გამოსავალი

მოდით გამოვხატოთ ლოგიკური მოქმედებები და:

= /მოდით, უარყოფა დავყოთ ცვლადებად და შევამციროთ ორმაგი უარყოფითი/ =

= /განაწილების კანონი/ .

მაგალითი 3.ჩაწერეთ ფორმულა DNF-ში და SDNF-ში.

გამოსავალი

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

SDNF-ის ასაგებად, მოდით შევქმნათ სიმართლის ცხრილი ამ ფორმულისთვის:

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

ხაზი 1: ;

ხაზი 3: ;

ხაზი 5: .

ამ სამი ფორმულის განცალკევება მიიღებს მნიშვნელობას 1 მხოლოდ ცვლადების კომპლექტებზე 1, 3, 5 სტრიქონებში და, შესაბამისად, იქნება სასურველი სრულყოფილი დისიუნგციური ნორმალური ფორმა (PDNF):

მაგალითი 4.მიიტანეთ ფორმულა SKNF-ში ორი გზით:

ა) ეკვივალენტური გარდაქმნების გამოყენება;

ბ) სიმართლის ცხრილის გამოყენებით.

გამოსავალი:

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

ფორმულა ასე გამოიყურება:

ბ) შეადგინეთ ჭეშმარიტების ცხრილი ამ ფორმულისთვის:

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

ხაზი 2: ;

ხაზი 6:.

ამ ორი ფორმულის შეერთება მიიღებს მნიშვნელობას 0 მხოლოდ მე-2 და მე-6 სტრიქონებში ცვლადების სიმრავლეზე და, შესაბამისად, იქნება სასურველი სრულყოფილი შემაერთებელი ნორმალური ფორმა (PCNF):

კითხვები და ამოცანები დამოუკიდებელი გადაწყვეტისთვის

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

2. ექვივალენტური გარდაქმნების გამოყენებით, მიიტანეთ ფორმულები CNF-მდე:

3. მეორე დისტრიბუციული კანონის გამოყენებით გადააკეთეთ DNF CNF-ად:

ა) ;

4. გადაიყვანეთ მოცემული DNF-ები SDNF-ებად:

5. გადააქციეთ მოცემული CNF SCNF-ად:

6. მოცემული ლოგიკური ფორმულებისთვის შექმენით SDNF და SCNF ორი გზით: ეკვივალენტური გარდაქმნების გამოყენებით და ჭეშმარიტების ცხრილის გამოყენებით.

ბ) ;

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

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

• 1 / 5

  ფორმულები KNF-ში:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\ჩვენების სტილი (A\vee B)\wedge (\neg B\vee C\vee \neg D)\სოლი ( D\vee\neg E)) A∧B. (\displaystyle A\wedge B.)

  ფორმულები არა KNF-ში:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\ჩვენების სტილი (A\სოლი B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\სოლი E)).)

  მაგრამ ეს 3 ფორმულა, რომელიც არ არის CNF-ში, ექვივალენტურია შემდეგი ფორმულების CNF-ში:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\ჩვენების სტილი (A\vee C)\სოლი (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  CNF-ის მშენებლობა

  CNF-ის აგების ალგორითმი

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

  A → B = ¬ A ∨ B, (\displaystyle A\მარჯვენა ისარი B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\მარცხენა მარჯვენა ისარი B=(\neg A\vee B)\სოლი (A\vee \neg B).)

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

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) მოიშორეთ ორმაგი ნეგატივები.

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

  CNF კონსტრუქციის მაგალითი

  მოდით მივიყვანოთ ფორმულა CNF-ში

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\მარჯვნივ ისარი Y)\სოლი ((\neg Y\მარჯვნივ Z)\მარჯვენა arrow \neg X).)

  მოდით გარდავქმნათ ფორმულა F (\displaystyle F)ფორმულამდე, რომელიც არ შეიცავს → (\displaystyle \მარჯვენა ისარი):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\სოლი (\neg (\neg Y\მარჯვნივ Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X))

  მიღებულ ფორმულაში ჩვენ უარყოფას გადავცემთ ცვლადებს და ვამცირებთ ორმაგ ნეგატივებს:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  მაგალითად, შემდეგი ფორმულა დაწერილია 2-CNF-ში:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  ან

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

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

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

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

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

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

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

  ლოგიკური ფუნქციების ნორმალური ფორმები ლოგიკური ფუნქციის წარმოდგენას Ki 2.7 ერთეულის შემადგენელი ნაწილების კავშირების დისუნქციური სახით ამ ფუნქციის DNF-ის დისიუნგციური ნორმალური ფორმა ეწოდება. შეიცავს ზუსტად ერთ-ერთ ლოგიკურ ცვლადს, რომელიც აღებულია უარყოფით ან მის გარეშე, მაშინ ფუნქციის წარმოდგენის ამ ფორმას ეწოდება ამ ფუნქციის სრულყოფილად განცალკევებული ნორმალური ფორმა SDNF. როგორც ხედავთ, SDNF ფუნქციის შედგენისას, თქვენ უნდა შექმნათ ყველა მინტერმის დისიუქცია, რომლისთვისაც ფუნქცია იღებს 1 მნიშვნელობას.

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

  თუ ეს ნამუშევარი არ მოგწონთ, გვერდის ბოლოში არის მსგავსი ნამუშევრების სია. თქვენ ასევე შეგიძლიათ გამოიყენოთ ძებნის ღილაკი

  
  

  ლექცია 1.xx

  ლოგიკური ფუნქციების ნორმალური ფორმები

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

  , (2.7)

  დაურეკა დისუნქციური ნორმალური ფორმაამ ფუნქციის (DNF).

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

  ზემოაღნიშნულის გათვალისწინებით, თეორემა 2.1-დან გამომდინარეობს შემდეგი თეორემა.

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

  მაგალითი 3. მოდით მივიღოთ ცხრილის მოცემული ფუნქცია f (x 1 , x 2 , x 3 ) (ცხრილი 10).

  ცხრილი 10

  			f (x 1 , x 2 , x 3 )

  ფორმულის (2.6) საფუძველზე ვიღებთ:

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

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

  , (2.8)

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

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

  თეორემა 3. ნებისმიერი ლოგიკური ფუნქცია(არ არის 1-ის იდენტური) შეიძლება წარედგინოს SKNF-ს, და ასეთი წარმოდგენა ერთადერთია.

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

  შენონის ლემა . ნებისმიერი ლოგიკური ფუნქცია f (x 1, x 2, ..., x m) m-დან ცვლადები შეიძლება წარმოდგენილი იყოს ასე:

  . (2.9)

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

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

  მაგალითი 4. f ფუნქციისთვის (x 1 , x 2 , x 3 ), მოცემულია ცხრილით. 10, ჩაწერეთ SKNF-ში.

  SDNF-ისგან განსხვავებით, ლოგიკური ფუნქციის ჭეშმარიტების ცხრილში SCNF-ის შედგენისას, თქვენ უნდა დაათვალიეროთ ცვლადების კომბინაციები, რომლებშიც ფუნქცია იღებს მნიშვნელობას 0, და შექმნათ შესაბამისი მაქსტერმების კავშირი.მაგრამ ცვლადები უნდა იქნას მიღებული საპირისპირო ინვერსიით:

  უნდა აღინიშნოს, რომ შეუძლებელია ფუნქციის SDNF-დან პირდაპირ გადაადგილება მის SCNF-ზე ან პირიქით. ასეთი გარდაქმნების მცდელობისას, შედეგები არის ფუნქციები, რომლებიც საპირისპიროა სასურველის. SDNF და SCNF ფუნქციების გამონათქვამები შეიძლება პირდაპირ იქნას მიღებული მხოლოდ მისი სიმართლის ცხრილიდან.

  მაგალითი 5. f ფუნქციისთვის (x 1 , x 2 , x 3 ), მოცემულია ცხრილით. 10, შეეცადეთ გადახვიდეთ SDNF-დან SKNF-ზე.

  მაგალითი 2.3-ის შედეგის გამოყენებით მივიღებთ:

  როგორც ხედავთ, ზოგადი ინვერსიით მივიღეთ ლოგიკური ფუნქციის SCNF, რომელიც არის 2.4-ში მიღებული ფუნქციის ინვერსია:

  რადგან ის შეიცავს ყველა მაქსტერმინს, რომელიც არ არის მოცემული ფუნქციის SCNF-ის გამოხატულებაში.

  1. ოპერაციების თვისებების გამოყენებით (იხ. ცხრილი 9) იდენტობის (), ჯამის მოდულის 2 (), იმპლიკაციით (), გადავდივართ ოპერაციებზე AND, OR, NOT (ლოგიკური საფუძველზე).

  2. უარყოფის თვისებებისა და დე მორგანის კანონების გამოყენებით (იხ. ცხრილი 9), ჩვენ უზრუნველვყოფთ, რომ უარყოფის ოპერაციები ვრცელდება მხოლოდ ცალკეულ ცვლადებზე და არა მთელ გამონათქვამებზე.

  3. AND და OR ლოგიკური ოპერაციების თვისებების გამოყენებით (იხ. ცხრილი 9), ვიღებთ ნორმალურ ფორმას (DNF ან CNF).

  4. საჭიროების შემთხვევაში გადადით სრულყოფილ ფორმებზე (SDNF ან SKNF). მაგალითად, SCNF-ის მისაღებად ხშირად გჭირდებათ ქონების გამოყენება: .

  მაგალითი 6. გადაიყვანეთ ლოგიკური ფუნქცია SKNF-ში

  ზემოაღნიშნული ალგორითმის ნაბიჯების თანმიმდევრობით განხორციელებისას მივიღებთ:

  შთანთქმის თვისების გამოყენებით ვიღებთ:

  ამრიგად, ჩვენ მივიღეთ CNF ფუნქცია f (x 1, x 2, x 3 ). მისი SCNF-ის მისაღებად, თქვენ უნდა გაიმეოროთ თითოეული დისუნქცია, რომელშიც რომელიმე ცვლადი აკლია, ორჯერ ამ ცვლადთან და მის უარყოფით:

  2.2.6. ლოგიკური ფუნქციების მინიმიზაცია

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

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

  ქუაინის მეთოდი

  მინიმიზაციის ფუნქცია წარმოდგენილია SDNF-ში და მასზე გამოიყენება ყველა შესაძლო არასრული წებოვანი ოპერაცია.

  , (2.10)

  და შემდეგ შეწოვა

  , (2.11)

  და ეს წყვილი ნაბიჯები გამოიყენება არაერთხელ. ამრიგად, შესაძლებელია ტერმინების რანგის შემცირება. ეს პროცედურა მეორდება მანამ, სანამ არ დარჩება არც ერთი ტერმინი, რომელიც შეიძლება სხვა ტერმინთან იყოს დაკავშირებული.

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

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

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

  კარნოს რუკის მეთოდი

  კარნოს რუქების (ცხრილების) მეთოდი უფრო ვიზუალური, ნაკლებად შრომატევადი და საიმედო გზაა ლოგიკური ფუნქციების მინიმიზაციისთვის, მაგრამ მისი გამოყენება პრაქტიკულად შემოიფარგლება 3-4 ცვლადის ფუნქციებით, მაქსიმუმ 5-6 ცვლადით.

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

  სიმართლის ცხრილები და კარნოს რუქები ორი ზოლის AND და OR ფუნქციებისთვისე ცვლადები წარმოდგენილია ნახ. 8. რუკის თითოეულ უჯრედში იწერება მნიშვნელობაა ფუნქციის მნიშვნელობა არგუმენტების მნიშვნელობების სიმრავლეში, რომელიც შეესაბამება ამ უჯრედს N ამხანაგო

  ა) და ბ) ან

  ბრინჯი. 8. კარნაუს რუქების მაგალითი ორი ცვლადის ფუნქციებისთვის

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

  f = x y.

  კარნოს რუკაზე OR ფუნქციისთვის უკვე არის სამი 1 და შეგიძლიათ გააკეთოთ ორი წებოვანი წყვილი, სადაც 1 შეესაბამება ტერმინს. xy , გამოიყენება ორჯერ. მინიმალური ფუნქციის გამონათქვამში, თქვენ უნდა ჩაწეროთ წყვილების ტერმინები, რომლებიც ერთმანეთთან არის შეკრული, დატოვოთ მათში ყველა ცვლადი, რომელიც არ იცვლება ამ წყვილისთვის და ამოიღოთ ცვლადები, რომლებიც ცვლის მათ მნიშვნელობას. ჰორიზონტალური წებოსთვის ვიღებთ x და ვერტიკალურადწ , შედეგად ვიღებთ გამოხატვას

  f = x + y.

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

  მინიმალური DNF ფუნქციის განსაზღვრისას გამოიყენება შემდეგი წესები. 1-ის შემცველი ყველა უჯრედი გაერთიანებულია დახურულ მართკუთხა უბნებში, რომელსაც ე.წ k-კუბურები, სადაც k = log 2 K, K რაოდენობა 1 მართკუთხა არეში. ამ შემთხვევაში, თითოეული უბანი უნდა იყოს მართკუთხედი 2 უჯრედის რაოდენობით k, სადაც k = 0, 1, 2, 3, .... იყიდება k = 1 მართკუთხედი ეწოდებაერთი არის კუბი და შეიცავს 2 1 = 2 ერთეულს; ამისთვის k = 2 მართკუთხედი შეიცავს 2-ს 2 = 4 ერთეული და ე.წორი კუბიკი; k = 3 რეგიონისთვის 2 3 = 8 ერთეული ეწოდებასამკუბური ; და ა.შ. შეიძლება ეწოდოს ერთეულები, რომელთა გაერთიანება მართკუთხედებად შეუძლებელიანულოვანი კუბურები , რომელიც შეიცავს მხოლოდ ერთ ერთეულს (2 0 = 1). როგორც ჩანს, თუნდაცკ უბნებს შეიძლება ჰქონდეს კვადრატული ფორმა (მაგრამ არა აუცილებლად), და თუ კენტიკ მხოლოდ მართკუთხედები.

  						ბ გ

  ბრინჯი. 9. კარნაუს რუქების მაგალითი სამი ცვლადის ფუნქციებისთვის

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

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

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

  ფუნქციისთვის კარნაუს რუკის მიხედვით ნახ. 9,ბ ვიპოვით

  ვინაიდან ზედა დახურული რეგიონისთვის ცვლადები x 1 და x 2 აქვს მნიშვნელობები ინვერსიების გარეშე, ქვედასთვის x 1 ინვერსიასთან დაკავშირებული საკითხები და x 3 ინვერსიის გარეშე.

  განუსაზღვრელი მნიშვნელობები რუკაზე ნახ. 9,ვ შეიძლება შემდგომ განისაზღვროს მისი ნულით ან ერთით შეცვლით. ამ ფუნქციისთვის ცხადია, რომ უფრო მომგებიანია ორივე განუსაზღვრელი მნიშვნელობის 1-ით ჩანაცვლება. ამ შემთხვევაში იქმნება ორი უბანი, რომლებიც სხვადასხვა ტიპის 2-კუბს წარმოადგენს. შემდეგ მინიმალური DNF ფუნქციის გამოხატულება იქნება შემდეგი:

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

  კარნოს რუქების დახატვა შესაძლებელია სხვადასხვა გზით (სურ. 10).

  									x 2 x 3

  ბ

  ბრინჯი. 10. კარნოს რუქების გამოსახვის სხვადასხვა გზა
  3 ცვლადის ფუნქციისთვის

  მაგრამ კარნაუს რუქებისთვის ყველაზე მოსახერხებელი ვარიანტები 2-4 ცვლადის ფუნქციებისთვის არის ის, რაც ნაჩვენებია ნახ. 11 ცხრილი, რადგან ისინი აჩვენებენ თითოეულ უჯრედსა ჩვენ გვაქვს ყველა ცვლადი პირდაპირი ან ინვერსიული ფორმით.

  ბ

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

  5 და 6 ცვლადის ფუნქციებისთვის, მეთოდი ნაჩვენებია ნახ. 10,ვ .

  ბრინჯი. 12. კარნოს რუკის სურათი 5 ცვლადის ფუნქციისთვის

  ბრინჯი. 13. კარნოს რუკის სურათი 6 ცვლადის ფუნქციისთვის

  სხვა მსგავსი ნამუშევრები, რომლებიც შეიძლება დაგაინტერესოთ.vshm>
  9020.		ორმაგობის პრინციპი. ბულის ფუნქციების გაფართოება ცვლადებად. სრულყოფილად განმასხვავებელი და კავშირებითი ნორმალური ფორმები	96.34 კბ
  	ეს თეორემა კონსტრუქციული ხასიათისაა, ვინაიდან ის საშუალებას აძლევს თითოეულ ფუნქციას ააგოს ფორმულა, რომელიც ახორციელებს მას სრულყოფილი d.n-ის სახით. ვ. ამისათვის, სიმართლის ცხრილში თითოეული ფუნქციისთვის, ჩვენ აღვნიშნავთ ყველა მწკრივს, რომელშიც
  6490.		ლოგიკური ფუნქციების აღწერა და მინიმიზაცია	187.21 კბ
  	კავშირი ფუნქციის არგუმენტებსა და მის მნიშვნელობებს შორის გამოიხატება ვერბალური ფორმით. მაგალითი: სამი არგუმენტიანი ფუნქცია იღებს მნიშვნელობას, როდესაც ნებისმიერი ორი ან მეტი ფუნქციის არგუმენტი ტოლია. იგი შედგება ჭეშმარიტების ცხრილის აგებისგან, რომელიც შეიცავს ფუნქციის მნიშვნელობებს არგუმენტების მნიშვნელობების ყველა ნაკრებისთვის. ამ მაგალითში, სიმართლის ცხრილის გამოყენებით, ვიღებთ შემდეგ ჩანაწერს DNF-ის სახით...
  6707.		რელაციური მონაცემთა ბაზების დიზაინი. დიზაინის პრობლემები კლასიკურ მიდგომაში. ნორმალიზაციის პრინციპები, ნორმალური ფორმები	70.48 კბ
  	რა არის რელაციური მონაცემთა ბაზის პროექტი. ამიტომ, მონაცემთა ბაზის დიზაინი უნდა იყოს ძალიან ზუსტი და დამოწმებული. სინამდვილეში, მონაცემთა ბაზის პროექტი არის მომავალი პროგრამული პაკეტის საფუძველი, რომელიც გამოიყენებს საკმაოდ დიდი ხნის განმავლობაში და მრავალი მომხმარებლის მიერ.
  4849.		სახელმწიფო ფუნქციების განხორციელების ფორმები და მეთოდები	197.3 კბ
  	ტერმინი „ფუნქცია“ შორს არის ერთი და იგივე მნიშვნელობა შიდა და უცხოურ სამეცნიერო ლიტერატურაში. ფილოსოფიური და ზოგად სოციოლოგიური თვალსაზრისით განიხილება, როგორც „ობიექტის თვისებების გარეგანი გამოვლინება ურთიერთობათა მოცემულ სისტემაში“; როგორც ინდივიდების ან ორგანოების ჩვეულებრივი ან კონკრეტული ქმედებების ერთობლიობა
  17873.		მე-3 კლასის მოსწავლეებისთვის ლოგიკური UUD-ის ფორმირება	846.71 კბაიტი
  	დაწყებითი სკოლის მოსწავლეებში ლოგიკური უნივერსალური მოქმედებების ფორმირების პრობლემის ფსიქოლოგიური და პედაგოგიური ასპექტები ლოგიკური UUD-ების ფორმირების შეფასების მეთოდები. ზოგადსაგანმანათლებლო სისტემაში საყოველთაო საგანმანათლებლო საქმიანობის განვითარების კონცეფციის შემუშავება აკმაყოფილებს ახალ სოციალურ საჭიროებებს. თანამედროვე განათლების სისტემის ყველაზე მნიშვნელოვანი ამოცანაა UUD-ის საყოველთაო საგანმანათლებლო საქმიანობის ფორმირება. საყოველთაო საგანმანათლებლო აქტივობების ფორმირება სასკოლო სირთულეების პრევენციის გასაღებია.
  2638.		ლოგიკური კავშირების ტექნიკური განხორციელება ავტომატურ დაბლოკვის სისტემებში	1.04 მბ
  	ლოგიკური კავშირების ტექნიკური განხორციელება ავტომატურ დაბლოკვის სისტემებში სამნიშნა და ოთხნიშნა ბატარეების მართვის ალგორითმების ტექნიკური დანერგვა შესაძლებელია სარელეო კონტაქტის და უკონტაქტო დისკრეტული და ინტეგრალური ლოგიკური ელემენტების გამოყენებით...
  10203.		რისკზე ორიენტირებული მიდგომის კონცეფციის გამოყენება გადაუდებელი შემთხვევების წარმოშობისა და განვითარების სტრუქტურული და ლოგიკური მოდელების მშენებლობაში	70.8 კბ
  	რისკის ზოგადი ანალიზი საწარმოო გარემო გაჯერებულია მძლავრი ტექნოლოგიური სისტემებითა და ტექნოლოგიებით, რომლებიც ხდის ადამიანის შრომას პროდუქტიულს და ფიზიკურად ნაკლებად რთულს, მაგრამ უფრო საშიშს. რისკი ხასიათდება სახიფათო სიტუაციის მოულოდნელობითა და მოულოდნელობით. ყოველდღიურად ვხვდებით უამრავ რისკს, მაგრამ მათი უმეტესობა რჩება პოტენციური რისკის თეორია ითვალისწინებს რაოდენობრივ შეფასებას ადამიანზე ნეგატიური ზემოქმედების, ასევე მისი ჯანმრთელობისა და სიცოცხლისათვის მიყენებული ზიანის შესახებ.
  11576.		გარიგების ცნება, სახეები და ფორმები. გარიგების საჭირო ფორმის შეუსრულებლობის შედეგები	49.82 კბ
  	გარიგების ბათილად ცნობა; საკურსო სამუშაოს გამოყენებული ღირებულება მდგომარეობს ტრანზაქციის კონცეფციის გამარტივებაში, ანუ მისი საჯარო წარმოდგენის უფრო ხელმისაწვდომი ფორმით.
  6213.		ფუნქციის დაახლოება	3.08 MB
  	პირველი მოიცავს ანალიტიკურად ან ტაბულურად განსაზღვრული გარკვეული ფუნქციის შეცვლას სხვა ფუნქციით, რომელიც ახლოსაა ორიგინალთან, მაგრამ უფრო მარტივი და მოსახერხებელი გამოთვლებისთვის. მაგალითად, ფუნქციის მრავალწევრით ჩანაცვლება საშუალებას გაძლევთ მიიღოთ რიცხვითი ინტეგრაციისა და დიფერენციაციის მარტივი ფორმულები; ცხრილის მიახლოებითი ფუნქციით ჩანაცვლება საშუალებას გაძლევთ მიიღოთ მნიშვნელობები მის შუალედურ წერტილებში. ასევე ჩნდება მეორე პრობლემა: გარკვეულ სეგმენტზე ფუნქციის აღდგენა ამ სეგმენტზე მოცემული ფუნქციის მნიშვნელობებიდან წერტილების დისკრეტულ ნაკრებში. ამ კითხვაზე პასუხი...
  14058.		სახელმწიფო ფუნქციების ევოლუცია	29.99 კბ
  	რუსეთის სახელმწიფომ, როგორც იურიდიულმა ფენომენმა, უპირველეს ყოვლისა უნდა უზრუნველყოს სახელმწიფოს მიზნის განხორციელება, ისევე როგორც მისი ძირითადი კონსტიტუციური მახასიათებლები, როგორც დემოკრატიული ფედერალური იურიდიული სოციალური სეკულარული სახელმწიფო მმართველობის რესპუბლიკური ფორმით. სახელმწიფოს ძირითადი მიზანი განისაზღვრება მუხ.