एक बूलियन अभिव्यक्ति

Question

मैं एक अभिव्यक्ति हो रहा है, लगता है,

a = 1 && (b = 1 || b != 0) && (c >= 35 || d != 5) && (c >= 38 || d = 6) 

मैं उम्मीद यह करने के लिए कम किया जा करने के लिए,

a = 1 && b != 0 && (c >= 38 || d = 6) 

किसी को भी किसी भी सुझाव हैं कम करना? किसी भी एल्गोरिदम के लिए पॉइंटर्स?

नोटा बेने: कर्णघ मानचित्र या क्विन-मैकक्लूसकी यहां कोई विकल्प नहीं है, मुझे विश्वास है। चूंकि ये विधियां भूरे रंग के मामलों को संभालती नहीं हैं। मेरा मतलब है, अभिव्यक्ति केवल तब तक कम हो सकती है जब तक चीजें जैसे, ए या ए 'या कुछ भी नहीं, या काले या सफेद या अनुपस्थित रंग का कहना है। लेकिन यहां मुझे भूरे रंग के रंग हैं, क्योंकि आप लोग देख सकते हैं।

समाधान: मैंने क्लोजर में इसके लिए कार्यक्रम लिखा है। मैंने एक मानचित्र के मानचित्र का उपयोग एक समारोह के रूप में किया था। यह बहुत आसान था, कुछ संयोजनों के लिए कुछ नियम और आप अच्छे हैं। आपके सहायक उत्तरों के लिए धन्यवाद।

Answer 1

मुझे लगता है कि आप Constraint Handling Rules का उपयोग करके जो चाहते हैं उसे प्राप्त करने में सक्षम होना चाहिए। आपको उन नियमों को लिखना होगा जो OR- और AND-expressions को सरल बनाते हैं।

मुख्य कठिनाई बाधा प्रक्षेपण जांच होगी जो आपको बताती है कि आप कौन से हिस्सों को छोड़ सकते हैं। उदाहरण के लिए, (सी> = 35 || डी! = 5) & & (सी> = 38 || डी = 6) (सी> = 38 || डी = 6) को सरल बनाता है क्योंकि पूर्व को बाद वाले द्वारा लागू किया जाता है, यानी , उत्तरार्द्ध अधिक विशिष्ट है। OR-expressions के लिए, आपको अधिक सामान्य भाग चुनना होगा, हालांकि।

Google को paper on an extension of CHR with entailment check for user-defined constraints मिला। मैं आपको यह बताने में सक्षम होने के लिए पर्याप्त सीएचआर नहीं जानता कि आपको ऐसे एक्सटेंशन की आवश्यकता होगी या नहीं।

Answer 2

मुझे विश्वास है कि इस तरह की चीजें constraint logic programming में नियमित रूप से की जाती हैं। दुर्भाग्य से मुझे अधिक सटीक विवरण देने के लिए पर्याप्त अनुभव नहीं हुआ है, लेकिन यह एक अच्छा प्रारंभिक बिंदु होना चाहिए।

सामान्य सिद्धांत सरल है: एक अनबाउंड चर के पास कोई मूल्य हो सकता है; जैसा कि आप असमानताओं के खिलाफ परीक्षण करते हैं, यह संभव मूल्यों का सेट एक या अधिक अंतराल से प्रतिबंधित है। जब/अगर उन अंतराल एक बिंदु पर अभिसरण होते हैं, तो वह चर उस मान से बंधी होती है। यदि, ओटीओएच, इनमें से किसी भी असमानता को अंतराल में प्रत्येक मूल्य के लिए असफल समझा जाता है, तो [प्रोग्रामिंग] तर्क विफलता होती है।

this भी देखें, उदाहरण के लिए यह स्विई-प्रोलॉग का उपयोग करके अभ्यास में कैसे किया जाता है। उम्मीद है कि आपको अंतर्निहित एल्गोरिदम के लिंक या संदर्भ मिलेगा, ताकि आप उन्हें अपने पसंद के प्लेटफ़ॉर्म में पुन: उत्पन्न कर सकें (शायद तैयार किए गए पुस्तकालयों को भी ढूंढें)।

अद्यतन: मैंने स्विई-प्रोलॉग और सीएलपीएफडी का उपयोग करके अपने उदाहरण को पुन: पेश करने का प्रयास किया, लेकिन मुझे अपेक्षित नतीजे नहीं मिले, केवल नज़दीक ही। उलटे पांव लौटने पर

?- [library(clpfd)]. 
simplify(A,B,C,D) :- 
    A #= 1 , 
    (B #= 1 ; B #\= 0) , 
    (C#>= 35 ; D #\= 5) , 
    (C#>= 38 ; D #= 6). 

और मेरे परिणाम, (पंक्ति विराम पठनीयता के लिए डाला): यहाँ मेरी कोड है

10 ?- simplify(A,B,C,D). 

A = 1, 
B = 1, 
C in 38..sup ; 

A = 1, 
B = 1, 
D = 6, 
C in 35..sup ; 

A = 1, 
B = 1, 
C in 38..sup, 
D in inf..4\/6..sup ; 

A = 1, 
B = 1, 
D = 6 ; 

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup, 
C in 35..sup ; 

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup, 
D in inf..4\/6..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup. 

11 ?- 

तो, कार्यक्रम झुकेंगे 8 परिणाम उन लोगों के बीच, 2 तुम पर रुचि (5 वीं थे और 8 वीं):

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup. 

अन्य अनावश्यक थे, और शायद सरल, automatable तर्क नियमों का उपयोग कर समाप्त किया जा सकता:

1st or 5th ==> 5th   [B == 1 or B != 0 --> B != 0] 
2nd or 4th ==> 4th   [C >= 35 or True --> True ] 
3rd or 1st ==> 1st ==> 5th [D != 5 or True --> True ] 
4th or 8th ==> 8th   [B == 1 or B != 0 --> B != 0] 
6th or 8th ==> 8th   [C >= 35 or True --> True ] 
7th or 3rd ==> 3rd ==> 5th [B == 1 or B != 0 --> B != 0] 

मैं जानता हूँ कि यह एक सामान्य समाधान किया जा रहा है के पीछे एक लंबा रास्ता है, लेकिन जैसा कि मैंने कहा, उम्मीद है कि यह एक शुरुआत है ...

पी.एस. मैंने "नियमित" और OR (, और ;) का उपयोग किया क्योंकि clpfd के (#/\ और #\/) ने एक बहुत ही अजीब परिणाम दिया कि मैं खुद को समझ नहीं पाया ... शायद कोई और अनुभवी इस पर कुछ प्रकाश डाल सकता है ...