ბულის ალგებრის გამარტივება Quine–McCluskey მეთოდით
ბულის გამოსახულებების ხელით გამარტივება ხშირად დაკავშირებულია შეცდომებთან, განსაკუთრებით მაშინ, როდესაც ცვლადების რაოდენობა სამს ან ოთხს აჭარბებს. "ბულის ალგებრის გამამარტივებელი" არის ონლაინ ინსტრუმენტი, რომელიც ავტომატურად ამცირებს ნებისმიერ ლოგიკურ გამოსახულებას მის უმარტივეს მათემატიკურ ფორმებამდე. მომხმარებლის მიერ შეყვანილი გამოსახულების საფუძველზე, სისტემა მყისიერად ითვლის და გამოსახავს ორ ალტერნატიულ მინიმალურ ფორმას: მინიმალური ნამრავლთა ჯამი (SOP) და მინიმალური ჯამთა ნამრავლი (POS).
ეს გამამარტივებელი არ ეყრდნობა მიახლოებით ჰევრისტიკულ გამოთვლებს. იგი იყენებს Quine–McCluskey ალგორითმს (ზუსტი მინიმალური დაფარვის მეთოდს), რომელიც მათემატიკურად უზრუნველყოფს აბსოლუტურად მინიმალური ფორმის მიღებას. პროცესის გამჭვირვალობისთვის, ხელსაწყო აჩვენებს ნაბიჯ-ნაბიჯ დერივაციას, პოულობს ყველა მარტივ იმპლიკანტს და აგებს სრულ ჭეშმარიტების ცხრილს, სადაც ორიგინალი და გამარტივებული ვერსიები შედარებულია სტრიქონების მიხედვით.
მხარდაჭერილი ფორმატები და შეყვანის წესები
ინსტრუმენტი გამოირჩევა მოქნილობით და საშუალებას იძლევა სხვადასხვა სინტაქსური სისტემის თავისუფლად შერევა ერთ გამოსახულებაში. ცვლადები უნდა ჩაიწეროს ცალკეული ლათინური ასოებით. მაქსიმალური ლიმიტი შეადგენს 6 უნიკალურ ცვლადს, ხოლო თავად გამოსახულების სიგრძე არ უნდა აღემატებოდეს 2,000 სიმბოლოს.
ლოგიკური ოპერატორების ჩაწერა შესაძლებელია შემდეგი ფორმატებით:
- AND (კონიუნქცია): ნაგულისხმევი სახით (მაგალითად,
AB), წერტილითA·B, ვარსკვლავითA*B, ტექსტურადA AND B, პროგრამირების სტილშიA && B, ან შესაბამისი ლოგიკური სიმბოლოთი. რამდენიმე ასოს მიმდევრობა (მაგ.ABC) ავტომატურად აღიქმება როგორცA AND B AND C. - OR (დიზიუნქცია): პლუსის ნიშნით
A + B, ტექსტურადA OR B, პროგრამირების სტილშიA || B, ან ლოგიკური სიმბოლოთი. - NOT (უარყოფა): პრიმით
A', ძახილის ნიშნით!A, ტექსტურადNOT A, ან სიმბოლოთი¬A. - XOR (გამომრიცხავი OR): სიმბოლოთი
A ^ B, ტექსტურადA XOR B, ან სპეციალური ნიშნითA ⊕ B. - NAND: ტექსტურად
A NAND Bან სიმბოლოთი⊼. - NOR: ტექსტურად
A NOR Bან სიმბოლოთი⊽. - კონსტანტები: გამოსახულებაში ნებადართულია ციფრები
0და1.
ინტერფეისში მოცემულია დამხმარე ღილაკები ოპერატორების სწრაფი ჩასასმელად, ასევე ფუნქცია "გასუფთავება" ველის გასასუფთავებლად. მომხმარებელს შეუძლია გამოიყენოს მზა შაბლონებიც სექციიდან "სცადეთ გამოსახულება", სადაც ხელმისაწვდომია სამი კლასიკური მაგალითი: "წევრების შერწყმა" (კონსენსუსის თეორემა), "უარყოფილი ნამრავლი" (დე მორგანის კანონი) და "სამმაგი XOR".
გამარტივების ეტაპები და დიაგნოსტიკა
გამოსახულების შეყვანის შემდეგ, ხელსაწყო აჩვენებს ინტერპრეტირებულ ფორმას ველში "წაკითხული როგორც" და ააქტიურებს პანელს "ერთი შეხედვით", რომელიც მოიცავს შემდეგ პარამეტრებს:
- ცვლადები: აღმოჩენილი ცვლადების სია.
- სტრიქონები, რომლებიც უდრის 1-ს: მინტერმების რაოდენობა ან სია.
- მარტივი იმპლიკანტები: ნაპოვნი მარტივი იმპლიკანტების ჯამური რაოდენობა.
- არსებითი მარტივი იმპლიკანტები: იმ იმპლიკანტების რაოდენობა, რომლებიც აუცილებელია მინიმალური დაფარვისთვის.
- ლიტერალები, მანამდე → შემდეგ: ლიტერალების რაოდენობა გამარტივებამდე და მის შემდეგ.
- მეთოდი: გამოყენებული ალგორითმი, სადაც ყოველთვის მითითებულია "Quine–McCluskey, ზუსტი მინიმალური დაფარვა".
სექციაში "როგორ გამარტივდა" მოცემულია დეტალური მათემატიკური აღწერა. თუ გამოსახულება შეიცავს ცვლადებს, სისტემა მიუთითებს მათ რაოდენობას და შესაბამისი ჭეშმარიტების ცხრილის სტრიქონების რაოდენობას (მაგალითად, 6 ცვლადის შემთხვევაში მიიღება 2⁶ = 64 სტრიქონი). აღიწერება მინტერმებისა და მაქსტერმების განაწილება, მარტივი იმპლიკანტების შერწყმის ეტაპები, არსებითი იმპლიკანტების გამოყოფა და დარჩენილი დაუფარავი სტრიქონების ოპტიმალური დაფარვა.
შეცდომების დამუშავება და განსაკუთრებული შემთხვევები
სისტემა მკაცრად აკონტროლებს შეყვანილი მონაცემების სინტაქსურ სისწორეს და შეზღუდვებს. შეცდომის აღმოჩენისას ეკრანზე გამოდის შესაბამისი შეტყობინება:
- თუ ველი ცარიელია: "შეიყვანეთ ბულის გამოსახულება."
- თუ სიმბოლოების რაოდენობა აჭარბებს ლიმიტს: "გამოსახულება უნდა იყოს 2,000 სიმბოლოზე ნაკლები."
- თუ გამოყენებულია არასწორი სიმბოლო: ""
‹char›" (პოზიცია‹position›) არ არის ბულის ოპერატორი, ცვლადი ან კონსტანტა." - თუ ოპერატორს აკლია არგუმენტი: "ოპერატორს აკლია ოპერანდი
‹position›პოზიციასთან ახლოს — შეამოწმეთ ხომ არ არის დარჩენილი ზედმეტი + · ან ⊕." - თუ ფრჩხილების ბალანსი დარღვეულია: "ფრჩხილები არაბალანსირებულია — დაამატეთ ან წაშალეთ ფრჩხილი."
- თუ ცვლადების რაოდენობა 6-ზე მეტია: "ეს გამოსახულება იყენებს
‹count›სხვადასხვა ცვლადს; გამამარტივებელს აქვს მაქსიმუმ 6-ის მხარდაჭერა."
თუ შეყვანილი გამოსახულება უკვე ოპტიმალურია, სისტემა აჩვენებს შეტყობინებას: "თქვენი გამოსახულება უკვე წარმოადგენს მინიმალურ ნამრავლთა ჯამს.". მუდმივი მნიშვნელობების (ტაუტოლოგია ან წინააღმდეგობა) შემთხვევაში კი მიიღება შესაბამისი განმარტება: "ეს გამოსახულება ყოველთვის 1-ია: მნიშვნელობების ყოველი კომბინაცია ხდის მას ჭეშმარიტს." ან "ეს გამოსახულება ყოველთვის 0-ია: მნიშვნელობების არცერთი კომბინაცია არ ხდის მას ჭეშმარიტს.".
მონაცემთა დამუშავება და კონფიდენციალურობა
ბულის გამოსახულებების გამარტივება ხდება უშუალოდ მომხმარებლის ბრაუზერში: მონაცემები არ იგზავნება გარე სერვერებზე და არასოდეს ტოვებს თქვენს მოწყობილობას. მომხმარებელს შეუძლია მარტივად დააკოპიროს მიღებული შედეგები ბუფერში სპეციალური ღილაკის "შედეგის კოპირება" მეშვეობით.
ხშირად დასმული კითხვები
გამოსახულების ჩაწერის რომელი ფორმატებია მხარდაჭერილი?
ყველა გავრცელებული ფორმატი თავისუფლად შეიძლება შეერიოს ერთმანეთს: საინჟინრო სტილი (AB + A'C, ნაგულისხმევი AND-ით და პრიმით NOT-ისთვის), პროგრამირების სტილი (A &&!B || C, A ^ B), ლოგიკური სიმბოლოები (¬ ∧ ∨ ⊕ ⊼ ⊽) და ჩვეულებრივი სიტყვები (A AND B OR NOT C, NAND, NOR). მრავალასოიანი კომბინაციები, როგორიცაა ABC, ნიშნავს A AND B AND C, ხოლო სიტყვები AND, OR, NOT, XOR, NAND, NOR ყოველთვის იკითხება როგორც ოპერატორები.
რა განსხვავებაა SOP და POS შედეგებს შორის?
ორივე აღწერს ერთსა და იმავე ფუნქციას. ნამრავლთა ჯამი (SOP) აერთიანებს AND-წევრებს OR ოპერატორით, როგორიცაა AB' + BC, და პირდაპირ ასახავს AND–OR სქემებს; ჯამთა ნამრავლი (POS) აერთიანებს OR-წევრებს AND ოპერატორით, როგორიცაა (A + B)(B' + C), და ასახავს OR–AND სქემებს. ფუნქციიდან გამომდინარე, ერთ ფორმას შეიძლება დასჭირდეს ნაკლები ვენტილი, ვიდრე მეორეს, ამიტომ ინსტრუმენტი ყოველთვის აჩვენებს ორივეს.
როგორ ხდება მინიმალური ფორმის პოვნა?
ინსტრუმენტი აგებს ჭეშმარიტების სრულ ცხრილს, აერთიანებს მეზობელ 1-იანების სტრიქონებს მარტივ იმპლიკანტებად (Quine–McCluskey მეთოდი), ტოვებს არსებითებს და ხურავს ნებისმიერ დარჩენილ სტრიქონს ზუსტი მინიმალური დაფარვით. შედეგი გარანტირებულად მინიმალურია ნამრავლთა ჯამის ფორმისთვის — ეს არ არის ჰევრისტიკა — და იგივე პროცედურა 0-იანების სტრიქონებზე იძლევა ჯამთა ნამრაველს.
რატომ არის მხარდაჭერილი მაქსიმუმ 6 ცვლადი?
ექვსი ცვლადი უკვე წარმოქმნის 64-სტრიქონიან ჭეშმარიტების ცხრილს, რაც არის ზღვარი იმისა, რისი წაკითხვა და ხელით შემოწმებაც ჯერ კიდევ შესაძლებელია. ამის მიღმა, მინიმიზაცია თეორიულად აგრძელებს მუშაობას, მაგრამ გამოყვანის პროცესი და ცხრილი, რომელზეც ეს გვერდია აგებული, კარგავს თვალსაჩინოების ფუნქციას. უფრო ფართო ფუნქციებისთვის უკეთესია ფაილის ექსპორტის მქონე ლოგიკური პროექტირების პროგრამული უზრუნველყოფის გამოყენება.