मुझे मनमानी बुलियन अभिव्यक्ति को संयोजन या विचित्र सामान्य रूप में बदलने के लिए एक विधि कहां मिल सकती है?

Question

मैंने a little app लिखा है जो अमूर्त वाक्यविन्यास पेड़ों में अभिव्यक्तियों को पार्स करता है। अभी, मैं यह निर्णय लेने के लिए अभिव्यक्ति के खिलाफ हेरिस्टिक्स का एक गुच्छा का उपयोग करता हूं कि क्वेरी का सर्वोत्तम मूल्यांकन कैसे किया जाए। दुर्भाग्यवश, ऐसे उदाहरण हैं जो क्वेरी योजना को बहुत खराब बनाते हैं।

मैं एक तरह से provably कैसे प्रश्नों मूल्यांकन किया जाना चाहिए करने के लिए के रूप में बेहतर अनुमान बनाने के लिए मिल गया है, लेकिन मैं आदेश provably सही जवाब पाने के लिए पहले CNF या DNF में मेरी अभिव्यक्ति डाल करने के लिए की जरूरत है। मुझे पता है कि इसका संभावित रूप से घातीय समय और स्थान हो सकता है, लेकिन सामान्य प्रश्नों के लिए मेरे उपयोगकर्ता इसे चलाते हैं, यह कोई समस्या नहीं है।

अब, सीएनएफ या डीएनएफ में कनवर्ट करना जटिल अभिव्यक्ति को सरल बनाने के लिए हर समय हाथ से कुछ करता है। (ठीक है, शायद हर समय नहीं है, लेकिन मुझे पता है कि यह कैसे किया गया है जैसे कि डेमोरगन के कानून, वितरण कानून इत्यादि) हालांकि, मुझे यकीन नहीं है कि एक एल्गोरिदम के रूप में लागू करने योग्य विधि में इसका अनुवाद कैसे शुरू किया जाए । मैंने क्वेरी ऑप्टिमाइज़ेशन पर कागजात देखे हैं, और कई लोग "अच्छी तरह से पहले हम चीजों को सीएनएफ में डालते हैं" या "पहले हमने चीजों को डीएनएफ में डाल दिया" के साथ शुरू किया, और वे इसे पूरा करने के लिए अपनी विधि को कभी नहीं समझते।

मुझे कहां से शुरू करना चाहिए?

Answer 1

अनुभवहीन वेनिला एल्गोरिथ्म, परिमाणक मुक्त सूत्रों के लिए, यह है:

• CNF के लिए, negation normal form में बदलने के साथ डी मॉर्गन कानूनों तो वितरित या अधिक और
DNF के लिए
• , negation normal form में बदलने डी मॉर्गन के साथ कानून तब वितरित करते हैं और

यदि आपके सूत्रों को प्रमाणित किया गया है तो यह मेरे लिए अस्पष्ट नहीं है। लेकिन अगर वे नहीं हैं, तो यह conjunctive normal form पर विकिपीडिया लेखों का अंत लगता है, और इसकी - स्वचालित रूप से स्वचालित तूफान समर्थक दुनिया में समतुल्य समतुल्य है - clausal normal form अहंकार रूपरेखा एक प्रयोग योग्य एल्गोरिदम को बदलें (और संदर्भों को इंगित करें यदि आप यह परिवर्तन करना चाहते हैं थोड़ा और चालाक)। यदि आपको उससे अधिक की आवश्यकता है, तो कृपया हमें बताएं कि आपको कठिनाई का सामना करना पड़ता है।

Answer 2

https://github.com/bastikr/boolean.py उदाहरण देखें:

def test(self): 
    expr = parse("a*(b+~c*d)") 
    print(expr) 

    dnf_expr = normalize(boolean.OR, expr) 
    print(list(map(str, dnf_expr))) 

    cnf_expr = normalize(boolean.AND, expr) 
    print(list(map(str, cnf_expr))) 

आउटपुट है:

a*(b+(~c*d)) 
['a*b', 'a*~c*d'] 
['a', 'b+~c', 'b+d'] 

अद्यतन:

>>> from sympy.logic.boolalg import to_dnf 
>>> from sympy.abc import A, B, C 
>>> to_dnf(B & (A | C)) 
Or(And(A, B), And(B, C)) 
>>> to_dnf((A & B) | (A & ~B) | (B & C) | (~B & C), True) 
Or(A, C) 

Answer 3

मैं इस पार आया है: अब मैं इस sympy logic package पसंद करते हैं पृष्ठ: How to Convert a Formula to CNF। यह छद्म कोड में एक बूलियन अभिव्यक्ति को सीएनएफ में परिवर्तित करने के लिए एल्गोरिदम दिखाता है। इस विषय में शुरू करने में मेरी मदद की।