सत्य फलन

तर्क में, सत्य फलन एक ऐसा फलन (गणित) है जो सत्य मानों को इनपुट के रूप में स्वीकार करता है और आउटपुट के रूप में अद्वितीय सत्य मान उत्पन्न करता है। दूसरे शब्दों में: सत्य फलन के इनपुट और आउटपुट सभी सत्य मान हैं; सत्य फलन हमेशा सत्य मान का उत्पादन करेगा; और समान सत्य मान (ओं) को इनपुट करने से हमेशा समान सत्य मान का उत्पादन होगा। विशिष्ट उदाहरण प्रस्ताविक कलन में है, जिसमें तार्किक संयोजकों द्वारा जुड़े अलग-अलग कथनों का उपयोग करके यौगिक कथन का निर्माण किया जाता है; यदि मिश्रित कथन का सत्य मान घटक कथन(नों) के सत्य मान द्वारा पूरी तरह से निर्धारित किया जाता है, तो मिश्रित कथन को सत्य फलन कहा जाता है, और उपयोग किए गए किसी भी तार्किक संयोजक को सत्य कार्यात्मक कहा जाता है।

शास्त्रीय तर्क सत्य-कार्यात्मक तर्क है, इसमें प्रत्येक कथन का सत्य मान होता है जो या तो सत्य या असत्य होता है, और प्रत्येक तार्किक संयोजक सत्य कार्यात्मक होता है ( संगत सत्य तालिका के साथ), इस प्रकार प्रत्येक यौगिक कथन सत्य फलन है। दूसरी ओर, मॉडल तर्क गैर-सत्य-कार्यात्मक है।

अवलोकन

एक तार्किक संयोजक सत्य-कार्यात्मक होता है यदि एक यौगिक वाक्य का सत्य-मूल्य उसके उप-वाक्यों के सत्य-मूल्य का एक कार्य है। संयोजकों का एक वर्ग सत्य-कार्यात्मक होता है यदि उसका प्रत्येक सदस्य है। उदाहरण के लिए संयोजी "और" सत्य-कार्यात्मक है क्योंकि "सेब फल हैं और गाजर सब्जियां हैं" जैसे वाक्य सत्य हैं, और केवल अगर इसके प्रत्येक उप-वाक्य "सेब फल हैं" और "गाजर सब्जियां हैं" सत्य हैं , और यह अन्यथा झूठा है। एक प्राकृतिक भाषा के कुछ संयोजक, जैसे अंग्रेजी, सत्य-कार्यात्मक नहीं हैं।

"x का मानना है कि ..." स्वरूप के संयोजक उन संयोजकों के विशिष्ट उदाहरण हैं जो सत्य-कार्यात्मक नहीं हैं। यदि उदा. मैरी गलती से मानती है कि अल गोर 20 अप्रैल 2000 को अमेरिका के राष्ट्रपति थे, लेकिन वह नहीं मानती कि चांद हरे पनीर से बना है, तो वाक्य

मैरी का मानना ​​है कि अल गोर 20 अप्रैल 2000 को अमेरिका के राष्ट्रपति थे

जबकि सत्य है

मैरी का मानना ​​है कि चांद हरी चीज से बना है

गलत है। दोनों ही मामलों में, प्रत्येक घटक वाक्य (अर्थात अल गोर 20 अप्रैल, 2000 को संयुक्त राज्य अमेरिका के राष्ट्रपति थे और चंद्रमा हरे पनीर से बना है) झूठा है, लेकिन वाक्यांश मैरी के उपसर्ग द्वारा गठित प्रत्येक यौगिक वाक्य का मानना ​​है कि सत्य-मान में भिन्न है . यही है, फॉर्म के वाक्य का सत्य-मान मैरी का मानना ​​है कि ... केवल इसके घटक वाक्य के सत्य-मान से निर्धारित नहीं होता है, और इसलिए (ात्मक) तार्किक संयोजक (या केवल संकारक क्योंकि यह एकात्मक है) गैर-सत्य-कार्यात्मक है।

सूत्रों के निर्माण में उपयोग किए जाने वाले क्लासिकल लॉजिक संयोजक (जैसे और (लॉजिक)|&, मटेरियल कंडीशनल|→) का वर्ग सत्य-कार्यात्मक है। तर्क के रूप में विभिन्न सत्य-मानों के लिए उनके मान आमतौर पर सत्य तालिकाओं द्वारा दिए जाते हैं। सत्य-कार्यात्मक प्रोपोज़िशनल कैलकुलस औपचारिक प्रणाली है जिसके सूत्रों की व्याख्या सत्य या असत्य के रूप में की जा सकती है।

द्विआधारी सत्य फलनों की तालिका

दो-मूल्यवान तर्क में, दो इनपुट P और Q के सोलह संभावित सत्य फलन हैं, जिन्हें बूलियन समारोह भी कहा जाता है। इनमें से कोई भी कार्य शास्त्रीय तर्क में निश्चित तार्किक संयोजक की सत्य तालिका से मेल खाता है, जिसमें कई अध: पतन (गणित) मामले शामिल हैं। जैसे फलन जो इसके या दोनों तर्कों पर निर्भर नहीं करता है। संक्षिप्तता के लिए निम्नलिखित सत्य तालिकाओं में सत्य और असत्य को क्रमशः 1 और 0 के रूप में दर्शाया गया है।

Contradiction/False Notation Equivalent formulas Truth table Venn diagram $\bot$ "bottom" P ∧ ¬P Opq   Q 0 1 P 0    0   0  1    0   0  File:Venn0000.svg	Tautology/True Notation Equivalent formulas Truth table Venn diagram $\top$ "top" P ∨ ¬P Vpq   Q 0 1 P 0    1   1  1    1   1  File:Venn1111.svg
Proposition P Notation Equivalent formulas Truth table Venn diagram P p Ipq   Q 0 1 P 0    0   0  1    1   1  File:Venn0101.svg	Negation of P Notation Equivalent formulas Truth table Venn diagram ¬P ~P Np Fpq   Q 0 1 P 0    1   1  1    0   0  File:Venn1010.svg
Proposition Q Notation Equivalent formulas Truth table Venn diagram Q q Hpq   Q 0 1 P 0    0   1  1    0   1  File:Venn0011.svg	Negation of Q Notation Equivalent formulas Truth table Venn diagram ¬Q ~Q Nq Gpq   Q 0 1 P 0    1   0  1    1   0  File:Venn1100.svg
Conjunction Notation Equivalent formulas Truth table Venn diagram P ∧ Q P & Q P · Q P AND Q P ↛¬Q ¬P ↚ Q ¬P ↓ ¬Q Kpq   Q 0 1 P 0    0   0  1    0   1  File:Venn0001.svg	Alternative denial Notation Equivalent formulas Truth table Venn diagram P ↑ Q P | Q P NAND Q P → ¬Q ¬P ← Q ¬P ∨ ¬Q Dpq   Q 0 1 P 0    1   1  1    1   0  File:Venn1110.svg
Disjunction Notation Equivalent formulas Truth table Venn diagram P ∨ Q P OR Q P ← ¬Q ¬P → Q ¬P ↑ ¬Q ¬(¬P ∧ ¬Q) Apq   Q 0 1 P 0    0   1  1    1   1  File:Venn0111.svg	Joint denial Notation Equivalent formulas Truth table Venn diagram P ↓ Q P NOR Q P ↚ ¬Q ¬P ↛ Q ¬P ∧ ¬Q Xpq   Q 0 1 P 0    1   0  1    0   0  File:Venn1000.svg
Material nonimplication Notation Equivalent formulas Truth table Venn diagram P ↛ Q P $\not \supset$ Q P $>$ Q P NIMPLY Q P ∧ ¬Q ¬P ↓ Q ¬P ↚ ¬Q Lpq   Q 0 1 P 0    0   0  1    1   0  File:Venn0100.svg	Material implication Notation Equivalent formulas Truth table Venn diagram P → Q P ⊃ Q P $\leq$ Q P IMPLY Q P ↑ ¬Q ¬P ∨ Q ¬P ← ¬Q Cpq   Q 0 1 P 0    1   1  1    0   1  File:Venn1011.svg
Converse nonimplication Notation Equivalent formulas Truth table Venn diagram P ↚ Q P $\not \subset$ Q P $<$ Q P ↓ ¬Q ¬P ∧ Q ¬P ↛ ¬Q Mpq   Q 0 1 P 0    0   1  1    0   0  File:Venn0010.svg	Converse implication Notation Equivalent formulas Truth table Venn diagram P ← Q P ⊂ Q P $\geq$ Q P ∨ ¬Q ¬P ↑ Q ¬P → ¬Q Bpq   Q 0 1 P 0    1   0  1    1   1
Exclusive disjunction Notation Equivalent formulas Truth table Venn diagram P ↮ Q P ≢ Q P ⨁ Q P XOR Q P $\leftrightarrow$ ¬Q ¬P $\leftrightarrow$ Q ¬P ↮ ¬Q Jpq   Q 0 1 P 0    0   1  1    1   0	Biconditional Notation Equivalent formulas Truth table Venn diagram P $\leftrightarrow$ Q P ≡ Q P XNOR Q P IFF Q P ↮ ¬Q ¬P ↮ Q ¬P $\leftrightarrow$ ¬Q Epq   Q 0 1 P 0    1   0  1    0   1  File:Venn1001.svg

कार्यात्मक पूर्णता

See also: Functional completeness

क्योंकि फलन को कार्यों की संरचना के रूप में व्यक्त किया जा सकता है, सत्य-कार्यात्मक तार्किक कलन को उपरोक्त सभी कार्यों के लिए कार्यात्मक पूर्णता होने के लिए समर्पित प्रतीकों की आवश्यकता नहीं है। यह कुछ यौगिक कथनों की तार्किक तुल्यता के रूप में प्रस्तावपरक कलन में व्यक्त किया गया है। उदाहरण के लिए, शास्त्रीय तर्क है ¬P ∨ Q के बराबर P → Q. सशर्त ऑपरेटर → शास्त्रीय-आधारित तार्किक प्रणाली के लिए आवश्यक नहीं है यदि ¬ (नहीं) और ∨ (या) पहले से ही उपयोग में हैं।

ऑपरेटरों का न्यूनतम तत्व सेट जो प्रत्येक बयान को व्यक्त कर सकता है जो प्रस्ताविक कलन में अभिव्यक्त होता है, न्यूनतम कार्यात्मक रूप से पूर्ण सेट कहलाता है। अकेले NAND {↑} और NOR अकेले {↓} द्वारा ऑपरेटरों का न्यूनतम पूर्ण सेट प्राप्त किया जाता है।

निम्नलिखित ऑपरेटरों के न्यूनतम कार्यात्मक रूप से पूर्ण सेट हैं जिनकी संख्या 2 से अधिक नहीं है:

तत्व

{↑}, {↓}।

दो तत्व: $\{\vee ,\neg \}$, $\{\wedge ,\neg \}$, $\{\to ,\neg \}$, $\{\gets ,\neg \}$, $\{\to ,\bot \}$, $\{\gets ,\bot \}$, $\{\to ,\nleftrightarrow \}$, $\{\gets ,\nleftrightarrow \}$, $\{\to ,\nrightarrow \}$, $\{\to ,\nleftarrow \}$, $\{\gets ,\nrightarrow \}$, $\{\gets ,\nleftarrow \}$, $\{\nrightarrow ,\neg \}$, $\{\nleftarrow ,\neg \}$, $\{\nrightarrow ,\top \}$, $\{\nleftarrow ,\top \}$, $\{\nrightarrow ,\leftrightarrow \}$, $\{\nleftarrow ,\leftrightarrow \}$. तीन तत्व: $\{\lor ,\leftrightarrow ,\bot \}$, $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$, $\{\lor ,\nleftrightarrow ,\top \}$, $\{\land ,\leftrightarrow ,\bot \}$, $\{\land ,\leftrightarrow ,\nleftrightarrow \}$, $\{\land ,\nleftrightarrow ,\top \}$.

बीजगणितीय गुण

कुछ सत्य फलनों में ऐसे गुण होते हैं जिन्हें संगत संयोजक वाले प्रमेयों में अभिव्यक्त किया जा सकता है। उन गुणों में से कुछ जो द्विआधारी सत्य फलन (या संबंधित तार्किक संयोजक) हो सकते हैं:

• साहचर्य: पंक्ति में ही साहचर्य संयोजकों के दो या दो से अधिक अभिव्यक्ति के भीतर, संचालन का क्रम तब तक मायने नहीं रखता जब तक कि संचालन का क्रम नहीं बदला जाता है।
• क्रमविनिमेयता : अभिव्यक्ति के सत्य-मान को प्रभावित किए बिना संयोजी के संचालन की अदला-बदली की जा सकती है।
• वितरण: संयोजी द्वारा निरूपित · वितरित अन्य संयोजक पर + द्वारा निरूपित किया जाता है, यदि a · (b + c) = (a · b) + (a · c) सभी ऑपरेंड a, b, c के लिए।
• idempotence: जब भी ऑपरेशन के ऑपरेंड समान होते हैं, तो संयोजी परिणाम के रूप में ऑपरेंड देता है। दूसरे शब्दों में, ऑपरेशन सत्य-संरक्षण और असत्य-संरक्षण दोनों है (नीचे देखें)।
• अवशोषण कानून: संयोजकों की जोड़ी $\land ,\lor$ अवशोषण कानून को संतुष्ट करता है अगर $a\land (a\lor b)=a\lor (a\land b)=a$ सभी ऑपरेंड ए, बी के लिए।

सत्य फलनों का सेट कार्यात्मक पूर्णता है अगर और केवल अगर निम्नलिखित पांच गुणों में से प्रत्येक के लिए इसमें कम से कम सदस्य की कमी है:

• 'मोनोटोनिक': यदि f(a₁, ..., ए_n) ≤ च (बी₁, ..., बी_n) सभी के लिए ए₁, ..., ए_n, बी₁, ..., बी_n ∈ {0,1} जैसे कि ए₁ ≤ बी₁, ए₂ ≤ बी₂, ..., ए_n ≤ बी_n. जैसे, $\vee ,\wedge ,\top ,\bot$.
• एफ़िन परिवर्तन: प्रत्येक चर के लिए, अन्य सभी चर के सभी निश्चित मानों के लिए, इसके मान को बदलने से या तो हमेशा या कभी भी संचालन का सत्य-मान नहीं बदलता है। जैसे, $\neg ,\leftrightarrow$, $\not \leftrightarrow ,\top ,\bot$.
• स्वयं द्वैत: इसकी सत्य तालिका पर ऊपर से नीचे तक संचालन के लिए सत्य-मान असाइनमेंट को पढ़ने के लिए इसे नीचे से ऊपर तक पढ़ने के पूरक के समान है; दूसरे शब्दों में, एफ(¬ए₁, ..., ¬a_n) = ¬च (ए₁, ..., ए_n). जैसे, $\neg$.
• सत्य-संरक्षण: व्याख्या जिसके तहत सभी चरों को 'सत्य' का सत्य मान दिया जाता है, इन परिचालनों के परिणामस्वरूप 'सत्य' का सत्य मान उत्पन्न करता है। जैसे, $\vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset$. (देखें वैधता (तर्क))
• झूठ-संरक्षण: व्याख्या जिसके तहत सभी चरों को 'गलत' का सत्य मान दिया जाता है, इन परिचालनों के परिणामस्वरूप 'गलत' का सत्य मान पैदा करता है। जैसे, $\vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset$. (देखें वैधता (तर्क))

आरती

See also: arity

ठोस कार्य को ऑपरेटर के रूप में भी संदर्भित किया जा सकता है। दो-मूल्यवान लॉजिक में 2 नलरी ऑपरेटर (स्थिरांक), 4 ात्मक ऑपरेशन , 16 बाइनरी ऑपरेशन, 256 टर्नरी ऑपरेशन और $2^{2^{n}}$ एन-आरी ऑपरेटरों। तीन-मूल्यवान लॉजिक में 3 नलरी ऑपरेटर (स्थिरांक), 27 यूनरी ऑपरेशन, 19683 बाइनरी ऑपरेशन, 7625597484987 टर्नरी ऑपरेशन और $3^{3^{n}}$ एन-आरी ऑपरेटरों। के-वैल्यू लॉजिक में, के न्यूलरी ऑपरेटर्स होते हैं, $k^{k}$ यूनरी ऑपरेटर्स, $k^{k^{2}}$ बाइनरी ऑपरेटर्स, $k^{k^{3}}$ त्रिगुट ऑपरेटरों, और $k^{k^{n}}$ एन-आरी ऑपरेटरों। के-मूल्यवान तर्क में एन-आरी ऑपरेटर कार्य है $\mathbb {Z} _{k}^{n}\to \mathbb {Z} _{k}$. इसलिए, ऐसे ऑपरेटरों की संख्या है $|\mathbb {Z} _{k}|^{|\mathbb {Z} _{k}^{n}|}=k^{k^{n}}$, जिससे उपरोक्त संख्याएँ प्राप्त हुईं।

हालांकि, विशेष एरिटी के कुछ ऑपरेटर वास्तव में पतित रूप हैं जो कुछ इनपुट पर लोअर-एरिटी ऑपरेशन करते हैं और बाकी इनपुट को अनदेखा करते हैं। ऊपर उद्धृत 256 टर्नरी बूलियन ऑपरेटरों में से, ${\binom {3}{2}}\cdot 16-{\binom {3}{1}}\cdot 4+{\binom {3}{0}}\cdot 2$ उनमें से बाइनरी या लोअर-एरिटी ऑपरेटरों के ऐसे पतित रूप हैं, जो समावेशन-बहिष्करण सिद्धांत का उपयोग करते हैं। टर्नरी ऑपरेटर $f(x,y,z)=\lnot x$ ऐसा ऑपरेटर है जो वास्तव में इनपुट पर लागू यूनरी ऑपरेटर है, और अन्य दो इनपुट को अनदेखा कर रहा है।

निषेध| नहीं ल संक्रिया है, इसमें शब्द (¬P) लगता है। बाकी बाइनरी ऑपरेशन हैं, मिश्रित बयान बनाने के लिए दो शब्द लेते हैं (पी ∧ क्यू, पी ∨ क्यू, पी → क्यू, पी ↔ क्यू)।

तार्किक ऑपरेटरों का सेट Ω किसी सेट का असंयुक्त उपसमुच्चय में निम्नानुसार विभाजन हो सकता है:

$\Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,.$

इस विभाजन में, $\Omega _{j}$ एरिटी के ऑपरेटर प्रतीकों का सेट है j.

अधिक परिचित प्रस्तावात्मक गणना में, $\Omega$ आमतौर पर निम्नानुसार विभाजित किया जाता है:

अशक्त संचालक: $\Omega _{0}=\{\bot ,\top \}$

यूनरी ऑपरेटर्स: $\Omega _{1}=\{\lnot \}$

बाइनरी ऑपरेटर्स: $\Omega _{2}\supset \{\land ,\lor ,\rightarrow ,\leftrightarrow \}$

रचना का सिद्धांत

सत्य तालिकाओं का उपयोग करने के बजाय, तार्किक संयोजी प्रतीकों की व्याख्या व्याख्या समारोह और सत्य-कार्यों के कार्यात्मक रूप से पूर्ण सेट (गैमट 1991) के माध्यम से की जा सकती है, जैसा कि अर्थ की संरचना के सिद्धांत द्वारा विस्तृत किया गया है। चलो मैं व्याख्या कार्य करता हूं, चलो Φ, Ψ कोई भी दो वाक्य हो और सत्य को कार्य करने दें f_nand के रूप में परिभाषित किया जाना चाहिए:

• एफ_nand(टी, टी) = एफ; एफ_nand(टी, एफ) = एफ_nand(एफ, टी) = एफ_nand(एफ, एफ) = टी

फिर, सुविधा के लिए, f_not, एफ_or f_and और इसी तरह च के माध्यम से परिभाषित किया गया है_nand:

• एफ_not(्स) = एफ_nand(्स, ्स)
• एफ_or(्स, वाई) = एफ_nand(एफ_not(्स), एफ_not(वाई))
• एफ_and(्स, वाई) = एफ_not(एफ_nand(्स, वाई))

या, वैकल्पिक रूप से एफ_not, एफ_or f_and और इसी तरह सीधे परिभाषित हैं:

• एफ_not(टी) = एफ; एफ_not(एफ) = टी;
• एफ_or(टी, टी) = एफ_or(टी, एफ) = एफ_or(एफ, टी) = टी; एफ_or(एफ, एफ) = एफ
• एफ_and(टी, टी) = टी; एफ_and(टी, एफ) = एफ_and(एफ, टी) = एफ_and(एफ, एफ) = एफ

तब

• I(~) = I($\neg$) = f_not
• I(&) = I($\wedge$) = f_and
• I(v) = I($\lor$) = f_or
• I(~Φ) = I($\neg$Φ) = I($\neg$)(I(Φ)) = f_not(I(Φ))
• I(Φ$\wedge$Ψ) = I($\wedge$)(I(Φ), I(Ψ)) = f_and(I(Φ), I(Ψ))

वगैरह।

इस प्रकार यदि S वाक्य है जो तार्किक प्रतीकों v से युक्त प्रतीकों की स्ट्रिंग है₁...में_n तार्किक संयोजकों और गैर-तार्किक प्रतीकों का प्रतिनिधित्व करना c₁...सी_n, तो अगर और केवल अगर I(v₁)...I(v_n) व्याख्या वी प्रदान किया गया है₁ पत्र बी_n एफ के माध्यम से_nand (या कार्यात्मक पूर्ण सत्य-कार्यों का कोई अन्य सेट) तो का सत्य-मूल्य $I(s)$ पूरी तरह से c के सत्य-मानों द्वारा निर्धारित होता है₁...सी_n, अर्थात् I(c₁)...I(c_n). दूसरे शब्दों में, अपेक्षित और आवश्यक के रूप में, S अपने सभी गैर-तार्किक प्रतीकों की व्याख्या के तहत ही सही या गलत है।

कंप्यूटर विज्ञान

तार्किक ऑपरेटर्स को डिजिटल सर्किट में तर्क द्वार ्स के रूप में लागू किया जाता है। व्यावहारिक रूप से सभी डिजिटल सर्किट (प्रमुख अपवाद DRAM है) तार्किक नंद , तार्किक न ही, नकार और लॉजिक गेट से निर्मित होते हैं। सामान्य 2 इनपुट के बजाय 3 या अधिक इनपुट वाले NAND और NOR गेट काफी सामान्य हैं, हालांकि वे तार्किक रूप से 2-इनपुट गेट के कैस्केड के बराबर हैं। अन्य सभी ऑपरेटरों को उपरोक्त लॉजिक गेट्स के 2 या अधिक के तार्किक समकक्ष संयोजन में तोड़कर कार्यान्वित किया जाता है।

NAND अकेले, NOR अकेले, और NOT और AND की तार्किक तुल्यता ट्यूरिंग तुल्यता (गणना का सिद्धांत) के समान है।

तथ्य यह है कि सभी सत्य फलनों को अकेले NOR के साथ व्यक्त किया जा सकता है, अपोलो मार्गदर्शन कंप्यूटर द्वारा प्रदर्शित किया गया है।

यह भी देखें

• बर्ट्रेंड रसेल और अल्फ्रेड नॉर्थ व्हाइटहेड,
  Principia Mathematica, दूसरा संस्करण
• लुडविग विट्गेन्स्टाइन,
  ट्रैक्टेटस लोगिको-फिलोसोफिकस, प्रस्ताव 5.101
• बिटवाइज़ ऑपरेशन
• बाइनरी फ़ंक्शन
• बूलियन डोमेन
• बूलियन फ़ंक्शन
• बूलियन तर्क
• बूलियन-मूल्यवान फ़ंक्शन
• बूलियन बीजगणित विषयों की सूची
• तार्किक संयोजक
• तार्किक स्थिरांक
• मोडल ऑपरेटर
• प्रस्तावक कलन
• प्रस्ताव समारोह
• सत्य-कार्यात्मक प्रस्तावपरक तर्क
• ट्रुथ टेबल
• सत्य मान

संदर्भ

• This article incorporates material from TruthFunction on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

अग्रिम पठन

• Józef Maria Bocheński (1959), A Précis of Mathematical Logic, translated from the French and German versions by Otto Bird, Dordrecht, South Holland: D. Reidel.
• Alonzo Church (1944), Introduction to Mathematical Logic, Princeton, NJ: Princeton University Press. See the Introduction for a history of the truth function concept.