The IGNOU MCS-013 Solved Question Paper PDF Download page is designed to help students access high-quality exam resources in one place. Here, you can find ignou solved question paper IGNOU Previous Year Question paper solved PDF that covers all important questions with detailed answers. This page provides IGNOU all Previous year Question Papers in one PDF format, making it easier for students to prepare effectively.
- IGNOU MCS-013 Solved Question Paper in Hindi
- IGNOU MCS-013 Solved Question Paper in English
- IGNOU Previous Year Solved Question Papers (All Courses)
Whether you are looking for IGNOU Previous Year Question paper solved in English or ignou previous year question paper solved in hindi, this page offers both options to suit your learning needs. These solved papers help you understand exam patterns, improve answer writing skills, and boost confidence for upcoming exams.
IGNOU MCS-013 Solved Question Paper PDF
This section provides IGNOU MCS-013 Solved Question Paper PDF in both Hindi and English. These ignou solved question paper IGNOU Previous Year Question paper solved PDF include detailed answers to help you understand exam patterns and improve your preparation. You can also access IGNOU all Previous year Question Papers in one PDF for quick and effective revision before exams.
IGNOU MCS-013 Previous Year Solved Question Paper in Hindi
Q1. (a) सत्यता सारणी का उपयोग करके दिखाएं कि (p∧q)∨r और (p∨r)∧(q∨r) समतुल्य हैं या नहीं। (2) (b) गणितीय आगमन का उपयोग करके, सिद्ध करें कि: 1·2 + 2·3 + … + n(n+1) = n(n+1)(n+2)/3 (4) (c) सिद्ध करें कि: (AUB)’=A’∩B’ (3) (d) प्रत्येक फलन एक संबंध है। क्या प्रत्येक संबंध एक फलन है? क्यों? (3) (e) निम्नलिखित तर्क परिपथ के आउटपुट के लिए बूलियन व्यंजक ज्ञात कीजिए: (2) 
(f) यदि F: R → R एक फलन है जो f(x) = (2x-3)/4 द्वारा दिया गया है, तो ज्ञात करें कि f⁻¹ मौजूद है या नहीं। यदि f⁻¹ मौजूद है, तो इसे ज्ञात करें। (3) (g) मान लीजिए कि हम 15 खिलाड़ियों की एक टीम से दो खिलाड़ियों को कप्तान और उप-कप्तान के रूप में चुनना चाहते हैं। यह कितने तरीकों से किया जा सकता है? (3)
Ans. (a) यह जांचने के लिए कि क्या (p∧q)∨r और (p∨r)∧(q∨r) समतुल्य हैं, हम एक सत्यता सारणी का निर्माण करेंगे।
(नोट: प्रश्न पत्र में (p∧q)∧r के रूप में एक संभावित मुद्रण त्रुटि है। हम अधिक मानक समतुल्यता (p∧q)∨r का उपयोग कर रहे हैं, जो वितरण नियम के अनुसार (p∨r)∧(q∨r) के समतुल्य है।)
p q r p∧q (p∧q)∨r p∨r q∨r (p∨r)∧(q∨r) T T T T T T T T T T F T T T T T T F T F T T T T T F F F F T F F F T T F T T T T F T F F F F T F F F T F T T T T F F F F F F F F
चूंकि (p∧q)∨r और (p∨r)∧(q∨r) के लिए कॉलम में सत्य मानों का क्रम सभी संभावित मामलों के लिए समान है, इसलिए दोनों व्यंजक तार्किक रूप से समतुल्य हैं। (b) हम गणितीय आगमन द्वारा P(n): 1·2 + 2·3 + … + n(n+1) = n(n+1)(n+2)/3 सिद्ध करेंगे।
मूल चरण (Base Case): n = 1 के लिए L.H.S = 1(1+1) = 2 R.H.S = 1(1+1)(1+2)/3 = 1·2·3/3 = 2 चूंकि L.H.S = R.H.S, P(1) सत्य है।
आगमनात्मक परिकल्पना (Inductive Hypothesis): मान लें कि P(k) किसी पूर्णांक k ≥ 1 के लिए सत्य है। अर्थात्, 1·2 + 2·3 + … + k(k+1) = k(k+1)(k+2)/3
आगमनात्मक चरण (Inductive Step): हमें सिद्ध करना है कि P(k+1) सत्य है। P(k+1): 1·2 + 2·3 + … + k(k+1) + (k+1)(k+2) = (k+1)(k+2)(k+3)/3 L.H.S = [1·2 + 2·3 + … + k(k+1)] + (k+1)(k+2) आगमनात्मक परिकल्पना का उपयोग करने पर: L.H.S = [k(k+1)(k+2)/3] + (k+1)(k+2) = (k+1)(k+2) [k/3 + 1] = (k+1)(k+2) [(k+3)/3] = (k+1)(k+2)(k+3)/3 = R.H.S अतः, P(k+1) सत्य है जब भी P(k) सत्य है। गणितीय आगमन के सिद्धांत द्वारा, दिया गया सूत्र सभी प्राकृतिक संख्याओं n के लिए सत्य है। (c) डी मॉर्गन के नियम (De Morgan’s law) को सिद्ध करने के लिए: (A ∪ B)’ = A’ ∩ B’ , हम दिखाएंगे कि प्रत्येक समुच्चय दूसरे का उपसमुच्चय है। भाग 1: सिद्ध करें (A ∪ B)’ ⊆ A’ ∩ B’ मान लीजिए x, (A ∪ B)’ का एक स्वेच्छ अवयव है। x ∈ (A ∪ B)’ ⇒ x ∉ (A ∪ B) ⇒ x ∉ A और x ∉ B (संघ की परिभाषा से) ⇒ x ∈ A’ और x ∈ B’ (पूरक की परिभाषा से) ⇒ x ∈ A’ ∩ B’ (प्रतिच्छेदन की परिभाषा से) अतः, (A ∪ B)’ ⊆ A’ ∩ B’। भाग 2: सिद्ध करें A’ ∩ B’ ⊆ (A ∪ B)’ मान लीजिए y, A’ ∩ B’ का एक स्वेच्छ अवयव है। y ∈ A’ ∩ B’ ⇒ y ∈ A’ और y ∈ B’ ⇒ y ∉ A और y ∉ B ⇒ y ∉ (A ∪ B) ⇒ y ∈ (A ∪ B)’ अतः, A’ ∩ B’ ⊆ (A ∪ B)’। भाग 1 और 2 से, हम यह निष्कर्ष निकालते हैं कि (A ∪ B)’ = A’ ∩ B’ । (d) हाँ, प्रत्येक फलन एक संबंध है । एक संबंध समुच्चय A से समुच्चय B तक केवल क्रमित युग्मों (a, b) का एक समुच्चय है जहाँ a ∈ A और b ∈ B। एक फलन एक विशेष प्रकार का संबंध है जिसमें एक अतिरिक्त शर्त होती है: प्रांत (domain) के प्रत्येक तत्व के लिए, सह-प्रांत (codomain) में ठीक एक संगत तत्व होता है।
नहीं, प्रत्येक संबंध एक फलन नहीं है । एक संबंध को फलन होने में विफल होने के दो कारण हो सकते हैं:
- प्रांत के एक तत्व को सह-प्रांत के किसी भी तत्व पर मैप नहीं किया जा सकता है।
- प्रांत के एक तत्व को सह-प्रांत के एक से अधिक तत्वों पर मैप किया जा सकता है।
उदाहरण: मान लीजिए A = {1, 2} और B = {3, 4}। संबंध R = {(1, 3), (1, 4), (2, 3)} A से B तक एक संबंध है। यह एक फलन नहीं है क्योंकि तत्व ‘1’ दो अलग-अलग तत्वों, ‘3’ और ‘4’ से मैप किया गया है, जो फलन की ‘एक-से-एक’ या ‘अनेक-से-एक’ मैपिंग की परिभाषा का उल्लंघन करता है। (e) दिए गए लॉजिक सर्किट के लिए बूलियन व्यंजक निम्नानुसार प्राप्त किया जा सकता है:
- ऊपरी द्वार एक AND द्वार है। इसके इनपुट X₁ और X₂ हैं। इसका आउटपुट X₁ ∧ X₂ (या X₁·X₂) है।
- निचला द्वार एक OR द्वार है। इसके इनपुट AND द्वार का आउटपुट और X₃ हैं।
- इसलिए, OR द्वार के इनपुट (X₁ ∧ X₂) और X₃ हैं।
अंतिम आउटपुट इन इनपुटों का OR है, जो हमें व्यंजक देता है: आउटपुट = (X₁ ∧ X₂) ∨ X₃ या बूलियन बीजगणित संकेतन में, F = (X₁·X₂) + X₃ । (f) दिया गया फलन है f(x) = (2x – 3) / 4। फलन f: R → R एक-से-एक (one-to-one) और आच्छादक (onto) है, इसलिए इसका व्युत्क्रम मौजूद है। व्युत्क्रम ज्ञात करने के लिए: 1. y = f(x) लिखें: y = (2x – 3) / 4 2. x और y को बदलें: x = (2y – 3) / 4 3. y के लिए हल करें: 4x = 2y – 3 4x + 3 = 2y y = (4x + 3) / 2 4. y को f⁻¹(x) से बदलें। इसलिए, व्युत्क्रम फलन f⁻¹(x) = (4x + 3) / 2 है। (g) हमें 15 खिलाड़ियों में से एक कप्तान और एक उप-कप्तान चुनना है। यह एक क्रमचय (permutation) समस्या है क्योंकि चयन में क्रम मायने रखता है (अर्थात, खिलाड़ी A कप्तान और खिलाड़ी B उप-कप्तान होना, खिलाड़ी B कप्तान और खिलाड़ी A उप-कप्तान होने से अलग है)। हम n वस्तुओं में से k वस्तुओं को चुनने के लिए क्रमचय सूत्र का उपयोग करते हैं: P(n, k) = n! / (n – k)! यहाँ, n = 15 (कुल खिलाड़ी) और k = 2 (चयनित की जाने वाली भूमिकाएं)। तरीकों की संख्या = P(15, 2) = 15! / (15 – 2)! = 15! / 13! = (15 × 14 × 13!) / 13! = 15 × 14 = 210 अतः, कप्तान और उप-कप्तान को 210 विभिन्न तरीकों से चुना जा सकता है।
Q2. (a) “DEPARTMENT” शब्द के अक्षरों का उपयोग करके कितने शब्द बनाए जा सकते हैं, यदि प्रत्येक अक्षर का उपयोग अधिकतम एक बार किया जाना चाहिए? (4) (b) {1, 2, 3} x {2, 3} के लिए ज्यामितीय प्रतिनिधित्व दें। (2) (c) सत्यापित करें कि: p→q ≡ ¬p∨q (2) (d) 20 विभिन्न वस्तुओं को 10 विभिन्न बक्सों में वितरित करने के तरीकों की संख्या ज्ञात करें ताकि कम से कम 4 बक्से खाली रहें। (2)
Ans. (a) “DEPARTMENT” शब्द में 10 अक्षर हैं। यदि हम अक्षरों की आवृत्ति का विश्लेषण करें: D-1, E-2, P-1, A-1, R-1, T-2, M-1, N-1. प्रश्न में कहा गया है “यदि प्रत्येक अक्षर का उपयोग अधिकतम एक बार किया जाना चाहिए”। यह वाक्यांश आमतौर पर अक्षरों के क्रमचय को संदर्भित करता है। यदि हम इसे इस रूप में व्याख्या करते हैं कि हम 10 उपलब्ध अक्षर स्थितियों को कैसे व्यवस्थित कर सकते हैं, तो हमें दोहराए गए अक्षरों का हिसाब देना होगा। पुनरावृत्ति के साथ क्रमचय का सूत्र है: n! / (p₁! p₂! … pₖ!), जहाँ n अक्षरों की कुल संख्या है और p₁, p₂, … दोहराए गए अक्षरों की संख्या है। यहाँ, n = 10। अक्षर ‘E’ 2 बार और ‘T’ 2 बार आता है। तो, p₁ = 2 (E के लिए) और p₂ = 2 (T के लिए)। गठन किए जा सकने वाले शब्दों की संख्या = 10! / (2! × 2!) = 3,628,800 / (2 × 2) = 3,628,800 / 4 = 907,200 इसलिए, “DEPARTMENT” शब्द के अक्षरों का उपयोग करके 907,200 अलग-अलग शब्द बनाए जा सकते हैं।
(b) समुच्चय {1, 2, 3} × {2, 3} का कार्तीय गुणन (Cartesian product) क्रमित युग्मों का समुच्चय है: {1, 2, 3} × {2, 3} = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)} इसका ज्यामितीय प्रतिनिधित्व 2-आयामी कार्तीय तल पर 6 बिंदुओं का एक समुच्चय है। x-अक्ष मान {1, 2, 3} से और y-अक्ष मान {2, 3} से लिए गए हैं। बिंदुओं को एक ग्रिड के रूप में दर्शाया जाएगा:
- x=1 पर, हमारे पास बिंदु (1, 2) और (1, 3) हैं।
- x=2 पर, हमारे पास बिंदु (2, 2) और (2, 3) हैं।
- x=3 पर, हमारे पास बिंदु (3, 2) और (3, 3) हैं।
यह तल पर एक आयताकार ग्रिड में व्यवस्थित 6 असतत बिंदुओं का एक समूह बनाता है।
(एक ग्राफ की कल्पना करें जिसमें x-अक्ष पर 1, 2, 3 और y-अक्ष पर 2, 3 अंकित हैं। इन निर्देशांकों के प्रतिच्छेदन पर बिंदु खींचे जाते हैं।) (c) हम एक सत्यता सारणी का उपयोग करके p → q ≡ ¬p ∨ q को सत्यापित कर सकते हैं।
p q p → q ¬p ¬p ∨ q T T T F T T F F F F F T T T T F F T T T
चूंकि p → q और ¬p ∨ q के लिए कॉलम में सत्य मानों का क्रम समान है, इसलिए यह सत्यापित होता है कि वे तार्किक रूप से समतुल्य हैं। (d) यह एक जटिल संयोजन समस्या है जिसे समावेशन-बहिष्करण सिद्धांत (Principle of Inclusion-Exclusion) का उपयोग करके हल किया जाता है। एक सटीक गणना इस प्रश्न के अंकों के लिए बहुत जटिल है। हम उत्तर के पीछे के तर्क की रूपरेखा तैयार करेंगे। हमें उन तरीकों की संख्या ज्ञात करनी है जिनमें ठीक 4 बक्से खाली हैं, प्लस वे तरीके जिनमें ठीक 5 बक्से खाली हैं, …, ठीक 9 बक्से खाली हैं। ठीक k बक्सों को खाली रखने के तरीकों की संख्या है: C(10, k) × (शेष (10-k) बक्सों में 20 विभिन्न वस्तुओं को वितरित करने के तरीके ताकि कोई भी बक्सा खाली न रहे) दूसरे भाग की गणना स्टर्लिंग संख्या (Stirling numbers of the second kind) का उपयोग करके की जाती है, जिसे S(n, r) के रूप में दर्शाया जाता है। n विभिन्न वस्तुओं को r विभिन्न बक्सों में वितरित करने के तरीकों की संख्या ताकि कोई बक्सा खाली न रहे, r! × S(n, r) है। यहाँ, n=20 और r=10-k। तो, ठीक k बक्सों को खाली रखने के तरीकों की संख्या है: C(10, k) × (10-k)! × S(20, 10-k) । कुल तरीकों की संख्या इन मानों का k=4 से 9 तक का योग है: कुल तरीके = ∑ 9 k=4 [C(10, k) × (10-k)! × S(20, 10-k)] इस व्यंजक की गणना करना तुच्छ नहीं है और आमतौर पर इस पाठ्यक्रम के दायरे से परे है। यह प्रश्न शायद केवल अवधारणा की समझ का परीक्षण करने के लिए है।
Q3. (a) निम्नलिखित बूलियन व्यंजक को सरल रूप में घटाएं: (4) f(x₁, x₂, x₃) = [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] (b) दिखाएँ कि ¬(p → q) → p एक पुनरुक्ति (tautology) है। (2) (c) सिद्ध करें कि √2 अपरिमेय है। (4)
Ans. (a) दिए गए बूलियन व्यंजक को सरल बनाने के लिए: f(x₁, x₂, x₃) = [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] हम इसे सरलता के लिए अंकन में फिर से लिखेंगे: F = x₁x₂x₃ + x₁x₂’ + x₂x₃ पुनर्व्यवस्थित करने पर (क्रमविनिमेय नियम): F = x₁x₂x₃ + x₂x₃ + x₁x₂’ पहले दो पदों पर अवशोषण नियम (absorption law) (A + AB = A) लागू करें, जहाँ A = x₂x₃ और B = x₁ है। (x₁x₂x₃ + x₂x₃) = x₂x₃ तो, व्यंजक बन जाता है: F = x₂x₃ + x₁x₂’ यह व्यंजक आगे सरल नहीं किया जा सकता है। वैकल्पिक रूप से, कर्णघ मानचित्र (Karnaugh map) का उपयोग करके: व्यंजक [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] मिन्टरमों (minterms) 111, (100, 101), (011, 111) से मेल खाता है। तो मिन्टरम का समुच्चय {m₃, m₄, m₅, m₇} है, जो (011, 100, 101, 111) हैं। के-मैप (K-map):
x₁ \ x₂x₃
00
01
11
10
0
0
0
1
0
1
1
1
1
0
समूहीकरण:
- m₃(011) और m₇(111) को समूहित करने पर हमें x₂x₃ मिलता है।
- m₄(100) और m₅(101) को समूहित करने पर हमें x₁x₂’ मिलता है।
इन समूहों को मिलाकर, सरल व्यंजक है: F = x₁x₂’ + x₂x₃ या [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] । (b) यह दिखाने के लिए कि ¬(p → q) → p एक पुनरुक्ति (tautology) है, हम तार्किक समतुल्यताओं का उपयोग कर सकते हैं: ¬(p → q) → p ≡ ¬(¬p ∨ q) → p (सशर्त पहचान) ≡ (p ∧ ¬q) → p (डी मॉर्गन का नियम) ≡ ¬(p ∧ ¬q) ∨ p (सशर्त पहचान) ≡ (¬p ∨ ¬(¬q)) ∨ p (डी मॉर्गन का नियम) ≡ (¬p ∨ q) ∨ p (दोहरा निषेध) ≡ (p ∨ ¬p) ∨ q (साहचर्य और क्रमविनिमेय नियम) ≡ T ∨ q (निषेध नियम) ≡ T
(प्रभुत्व नियम) चूंकि व्यंजक हमेशा सत्य (T) होता है, यह एक पुनरुक्ति है। (c) हम विरोधाभास द्वारा सिद्धि (proof by contradiction) का उपयोग करके सिद्ध करेंगे कि √2 अपरिमेय है । मान्यता: मान लीजिए कि √2 परिमेय है। इसका मतलब है कि √2 को दो पूर्णांकों p और q के भिन्न के रूप में लिखा जा सकता है, जहाँ q ≠ 0 और p और q का कोई सामान्य भाजक नहीं है (अर्थात, भिन्न p/q अपने सरलतम रूप में है)। तो, √2 = p/q दोनों पक्षों का वर्ग करने पर: 2 = p²/q² p² = 2q² इस समीकरण का अर्थ है कि p² एक सम संख्या है (क्योंकि यह 2 का गुणज है)। यदि p² सम है, तो p भी सम होना चाहिए। (एक विषम संख्या का वर्ग हमेशा विषम होता है)। चूंकि p सम है, हम इसे p = 2k के रूप में लिख सकते हैं, जहाँ k एक पूर्णांक है। अब p = 2k को समीकरण p² = 2q² में प्रतिस्थापित करें: (2k)² = 2q² 4k² = 2q² q² = 2k² इसका अर्थ है कि q² भी एक सम संख्या है। इसलिए, q भी सम होना चाहिए। अब हमारे पास यह है कि p और q दोनों सम हैं। इसका मतलब है कि दोनों 2 से विभाज्य हैं, और उनका एक सामान्य भाजक 2 है। यह हमारी प्रारंभिक मान्यता का विरोधाभास करता है कि p और q का कोई सामान्य भाजक नहीं है। चूंकि हमारी प्रारंभिक मान्यता एक विरोधाभास की ओर ले जाती है, इसलिए मान्यता गलत होनी चाहिए। अतः, √2 अपरिमेय होना चाहिए।
Q4. (a) ¬(p ↔ q) ∨ (p → q) का CNF (Conjunctive Normal Form) ज्ञात कीजिए। (4) (b) कपोत-कोटर सिद्धांत (Pigeonhole principle) और सामान्यीकृत कपोत-कोटर सिद्धांत (Generalized Pigeonhole principle) लिखिए। (3) (c) निम्नलिखित बूलियन व्यंजक के लिए तर्क द्वारों (logic gates) का उपयोग करके परिपथ बनाएं: (3) Y = A’BC + A’BC’ + ABC’
Ans. (a) हमें व्यंजक E = ¬(p ↔ q) ∨ (p → q) का CNF ज्ञात करना है। आइए पहले व्यंजक को सरल बनाएं: E ≡ ¬(p ↔ q) ∨ (¬p ∨ q) (सशर्त पहचान) हम जानते हैं कि p ↔ q ≡ (p → q) ∧ (q → p) ≡ (¬p ∨ q) ∧ (p ∨ ¬q) और ¬(p ↔ q) ≡ p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q) E में ¬(p ↔ q) को प्रतिस्थापित करने पर: E ≡ (p ∧ ¬q) ∨ (¬p ∧ q) ∨ (¬p ∨ q) ध्यान दें कि (¬p ∧ q) ∨ (¬p ∨ q) = (¬p ∧ q) ∨ ¬p ∨ q. अवशोषण नियम (A ∨ (A ∧ B) = A) के अनुसार, ¬p ∨ (¬p ∧ q) = ¬p. तो, (¬p ∧ q) ∨ ¬p ∨ q = ¬p ∨ q. अब व्यंजक E बन जाता है: E ≡ (p ∧ ¬q) ∨ (¬p ∨ q) यह DNF (Disjunctive Normal Form) में है। इसे CNF में बदलने के लिए, हम वितरण नियम (distributive law) का उपयोग करते हैं: X ∨ (Y ∧ Z) = (X ∨ Y) ∧ (X ∨ Z). E ≡ (¬p ∨ q) ∨ (p ∧ ¬q) ≡ ((¬p ∨ q) ∨ p) ∧ ((¬p ∨ q) ∨ ¬q) ≡ (¬p ∨ p ∨ q) ∧ (¬p ∨ q ∨ ¬q) ≡ (T ∨ q) ∧ (¬p ∨ T) (निषेध नियम) ≡ T ∧ T ≡ T (सत्य) यह व्यंजक एक पुनरुक्ति (tautology) है। एक पुनरुक्ति का CNF केवल T होता है। यदि एक गैर-तुच्छ रूप की आवश्यकता है, तो इसे (p ∨ ¬p) के रूप में लिखा जा सकता है।
(b) कपोत-कोटर सिद्धांत (Pigeonhole Principle): यह सिद्धांत कहता है कि यदि n वस्तुओं को m कंटेनरों में रखा जाता है, और यदि n > m है, तो कम से कम एक कंटेनर में एक से अधिक वस्तु होनी चाहिए। अधिक औपचारिक रूप से: यदि k+1 या अधिक वस्तुओं को k बक्सों (कपोत-कोटरों) में रखा जाता है, तो कम से कम एक बक्से में एक से अधिक वस्तु होगी। यह एक फलन f: X → Y पर लागू होता है, जहाँ X वस्तुओं का समुच्चय है और Y कंटेनरों का समुच्चय है। यदि |X| > |Y|, तो f एक-से-एक (injective) नहीं हो सकता।
सामान्यीकृत कपोत-कोटर सिद्धांत (Generalized Pigeonhole Principle): यह सिद्धांत मूल सिद्धांत का विस्तार करता है। यह कहता है कि यदि N वस्तुओं को k बक्सों में रखा जाता है, तो कम से कम एक बक्से में ⌈N/k⌉ वस्तुएँ होंगी। यहाँ, ⌈x⌉ सीलिंग फलन (ceiling function) है, जो x से बड़ा या उसके बराबर सबसे छोटा पूर्णांक देता है। उदाहरण: यदि एक कक्षा में 100 छात्र हैं, तो कम से कम ⌈100/12⌉ = ⌈8.33⌉ = 9 छात्र एक ही महीने में पैदा हुए हैं। (N=100 वस्तुएं/छात्र, k=12 बक्से/महीने)। (c) दिया गया बूलियन व्यंजक है: Y = A’BC + A’BC’ + ABC’ परिपथ बनाने से पहले, हम व्यंजक को सरल बनाएंगे। Y = A’B(C + C’) + ABC’ (वितरण नियम) चूंकि C + C’ = 1: Y = A’B(1) + ABC’ Y = A’B + ABC’ अब हम फिर से वितरण नियम (X + YZ = (X+Y)(X+Z)) लागू कर सकते हैं। Y = (A’B + A)(A’B + BC’) यह और जटिल हो जाता है। आइए एक और तरीका आजमाएं: Y = A’B + ABC’ Y = B(A’ + AC’) सान्निध्य प्रमेय (Adjacency Theorem) X + X’Y = X + Y का उपयोग करके: A’ + AC’ = A’ + C’ तो, Y = B(A’ + C’) = A’B + BC’ यह सरलतम रूप है। अब हम Y = A’B + BC’ के लिए लॉजिक परिपथ बनाएंगे। हमें निम्नलिखित द्वारों की आवश्यकता होगी:
- 2 NOT द्वार (A से A’ और C से C’ बनाने के लिए)
- 2 AND द्वार (A’B और BC’ बनाने के लिए)
- 1 OR द्वार ((A’B) और (BC’) को जोड़ने के लिए)
परिपथ इस प्रकार होगा:
- इनपुट A एक NOT द्वार से गुजरता है जिससे A’ बनता है।
- A’ और इनपुट B एक AND द्वार में जाते हैं, जिसका आउटपुट A’B होता है।
- इनपुट C एक NOT द्वार से गुजरता है जिससे C’ बनता है।
- इनपुट B और C’ एक दूसरे AND द्वार में जाते हैं, जिसका आउटपुट BC’ होता है।
- दो AND द्वारों के आउटपुट (A’B और BC’) एक OR द्वार में जाते हैं।
- OR द्वार का अंतिम आउटपुट Y = A’B + BC’ है।
(इस विवरण के आधार पर एक आरेख बनाया जा सकता है।)
Q5. (a) बूलियन बीजगणित के तत्समक नियमों (Identity Laws) की व्याख्या करें। (2) (b) प्रायिकता के योग प्रमेय (Addition Theorem of Probability) का कथन और प्रमाण दें। (3) (c) सत्यापित करें कि p∧q∧¬p एक विरोधाभास (contradiction) है। (2) (d) मान लीजिए A और B परस्पर अपवर्जी (mutually exclusive) घटनाएँ हैं, जैसे कि P(A) = 0.3 और P(B) = 0.4। इसकी क्या प्रायिकता है कि: (3) (i) A घटित नहीं होती है? (ii) A या B घटित होती है? (iii) या तो A या B घटित नहीं होती है?
Ans. (a) बूलियन बीजगणित के तत्समक नियम (Identity Laws) बताते हैं कि एक चर का OR या AND ऑपरेशन एक विशेष मान (तत्समक तत्व) के साथ कैसे व्यवहार करता है। दो तत्समक नियम हैं:
- OR के लिए तत्समक नियम (Identity for OR): A + 0 = A इस नियम के अनुसार, किसी भी चर (A) का 0 के साथ OR करने पर परिणाम मूल चर (A) ही होता है। यहाँ, ‘0’ OR ऑपरेशन के लिए तत्समक तत्व है। यदि A सत्य (1) है, तो 1 + 0 = 1 (A)। यदि A असत्य (0) है, तो 0 + 0 = 0 (A)।
- AND के लिए तत्समक नियम (Identity for AND): A · 1 = A इस नियम के अनुसार, किसी भी चर (A) का 1 के साथ AND करने पर परिणाम मूल चर (A) ही होता है। यहाँ, ‘1’ AND ऑपरेशन के लिए तत्समक तत्व है। यदि A सत्य (1) है, तो 1 · 1 = 1 (A)। यदि A असत्य (0) है, तो 0 · 1 = 0 (A)।
ये नियम बूलियन व्यंजकों को सरल बनाने में मौलिक हैं। (b) प्रायिकता का योग प्रमेय (Addition Theorem of Probability)
कथन: यदि A और B किसी प्रतिदर्श समष्टि (sample space) S में कोई दो घटनाएँ हैं, तो A या B या दोनों के घटित होने की प्रायिकता इस प्रकार दी जाती है: P(A ∪ B) = P(A) + P(B) – P(A ∩ B) यदि घटनाएँ A और B परस्पर अपवर्जी (mutually exclusive) हैं (अर्थात, वे एक साथ घटित नहीं हो सकतीं, A ∩ B = ∅), तो P(A ∩ B) = 0, और प्रमेय सरल हो जाता है: P(A ∪ B) = P(A) + P(B) प्रमाण: प्रायिकता की अभिगृहीतीय परिभाषा से, एक घटना E की प्रायिकता P(E) = |E| / |S| है, जहाँ |E| घटना E में परिणामों की संख्या है और |S| प्रतिदर्श समष्टि में कुल परिणामों की संख्या है। समुच्चय सिद्धांत से, हम जानते हैं कि दो समुच्चयों के संघ के लिए, गणनांक (cardinality) का नियम है: |A ∪ B| = |A| + |B| – |A ∩ B| इस समीकरण के प्रत्येक पद को |S| से विभाजित करने पर: |A ∪ B| / |S| = |A| / |S| + |B| / |S| – |A ∩ B| / |S| प्रायिकता की परिभाषा का उपयोग करके, हम प्रत्येक पद को प्रायिकता के रूप में प्रतिस्थापित कर सकते हैं: P(A ∪ B) = P(A) + P(B) – P(A ∩ B) इस प्रकार प्रमेय सिद्ध होता है। (c) यह सत्यापित करने के लिए कि p ∧ q ∧ ¬p एक विरोधाभास है, हम बूलियन बीजगणित के नियमों का उपयोग कर सकते हैं। p ∧ q ∧ ¬p ≡ (p ∧ ¬p) ∧ q (साहचर्य और क्रमविनिमेय नियम) हम जानते हैं कि निषेध नियम (negation law) के अनुसार, p ∧ ¬p = F (असत्य) । ≡ F ∧ q और प्रभुत्व नियम (domination law) के अनुसार, F ∧ q = F । ≡ F (विरोधाभास) चूंकि व्यंजक हमेशा F (असत्य) होता है, यह एक विरोधाभास है। सत्यता सारणी द्वारा सत्यापन:
p q ¬p p ∧ q (p ∧ q) ∧ ¬p T T F T F T F F F F F T T F F F F T F F अंतिम कॉलम में सभी मान F हैं, जो पुष्टि करता है कि यह एक विरोधाभास है। (d) दिया गया है: P(A) = 0.3, P(B) = 0.4, और A और B परस्पर अपवर्जी हैं, जिसका अर्थ है P(A ∩ B) = 0 । (i) A घटित नहीं होती है? यह A के पूरक की प्रायिकता है, P(A’)। P(A’) = 1 – P(A) P(A’) = 1 – 0.3 = 0.7 (ii) A या B घटित होती है? यह A और B के संघ की प्रायिकता है, P(A ∪ B)। P(A ∪ B) = P(A) + P(B) – P(A ∩ B) चूंकि वे परस्पर अपवर्जी हैं, P(A ∩ B) = 0। P(A ∪ B) = P(A) + P(B) P(A ∪ B) = 0.3 + 0.4 = 0.7 (iii) या तो A या B घटित नहीं होती है? इसका अर्थ है P(A’ ∪ B’)। डी मॉर्गन के नियम का उपयोग करके, P(A’ ∪ B’) = P((A ∩ B)’)। P((A ∩ B)’) = 1 – P(A ∩ B) चूंकि P(A ∩ B) = 0: P(A’ ∪ B’) = 1 – 0 = 1 इसका मतलब है कि यह निश्चित है कि या तो A घटित नहीं होगा या B घटित नहीं होगा (या दोनों घटित नहीं होंगे)। यह समझ में आता है क्योंकि वे एक साथ घटित नहीं हो सकते।
IGNOU MCS-013 Previous Year Solved Question Paper in English
Q1. (a) Show using truth table whether (p∧q)∨r and (p∨r)∧(q∨r) are equivalent or not. (2) (b) Using mathematical induction, prove that: 1·2 + 2·3 + … + n(n+1) = n(n+1)(n+2)/3 (4) (c) Prove that: (AUB)’=A’∩B’ (3) (d) Every function is a relation. Is every relation a function? Why? (3) (e) Find Boolean expression for the output of the following logic circuits: (2) (f) If F: R → R be a function given by f(x) = (2x-3)/4, find whether f⁻¹ exists or not. If f⁻¹ exists, find it. (3) (g) Suppose we want to choose two players from a team of 15 players, as captain and vice captain. In how many ways can this be done? (3)
Ans. (a) To check if (p∧q)∨r and (p∨r)∧(q∨r) are equivalent, we will construct a truth table. (Note: The question paper has a potential typo as (p∧q)∧r. We are using the more standard equivalence (p∧q)∨r, which is equivalent to (p∨r)∧(q∨r) by the distributive law.)
p |
q |
r |
p∧q |
(p∧q)∨r |
p∨r |
q∨r |
(p∨r)∧(q∨r) |
| T | T | T | T | T |
T | T | T |
| T | T | F | T | T |
T | T | T |
| T | F | T | F | T |
T | T | T |
| T | F | F | F | F |
T | F | F |
| F | T | T | F | T |
T | T | T |
| F | T | F | F | F |
F | T | F |
| F | F | T | F | T |
T | T | T |
| F | F | F | F | F |
F | F | F |
Since the columns for
(p∧q)∨r
and
(p∨r)∧(q∨r)
have the identical sequence of truth values for all possible cases, the two expressions are
logically equivalent
.
(b) We will prove P(n): 1·2 + 2·3 + … + n(n+1) = n(n+1)(n+2)/3 by mathematical induction. Base Case: For n = 1 L.H.S = 1(1+1) = 2 R.H.S = 1(1+1)(1+2)/3 = 1·2·3/3 = 2 Since L.H.S = R.H.S, P(1) is true. Inductive Hypothesis: Assume P(k) is true for some integer k ≥ 1. i.e., 1·2 + 2·3 + … + k(k+1) = k(k+1)(k+2)/3 Inductive Step: We need to prove that P(k+1) is true. P(k+1): 1·2 + 2·3 + … + k(k+1) + (k+1)(k+2) = (k+1)(k+2)(k+3)/3 L.H.S = [1·2 + 2·3 + … + k(k+1)] + (k+1)(k+2) Using the inductive hypothesis: L.H.S = [k(k+1)(k+2)/3] + (k+1)(k+2) = (k+1)(k+2) [k/3 + 1] = (k+1)(k+2) [(k+3)/3] = (k+1)(k+2)(k+3)/3 = R.H.S Thus, P(k+1) is true whenever P(k) is true. By the principle of mathematical induction, the given formula is true for all natural numbers n.
(c) To prove De Morgan’s law: (A ∪ B)’ = A’ ∩ B’ , we will show that each set is a subset of the other. Part 1: Prove (A ∪ B)’ ⊆ A’ ∩ B’ Let x be an arbitrary element of (A ∪ B)’. x ∈ (A ∪ B)’ ⇒ x ∉ (A ∪ B) ⇒ x ∉ A and x ∉ B (by definition of union) ⇒ x ∈ A’ and x ∈ B’ (by definition of complement) ⇒ x ∈ A’ ∩ B’ (by definition of intersection) Thus, (A ∪ B)’ ⊆ A’ ∩ B’.
Part 2: Prove A’ ∩ B’ ⊆ (A ∪ B)’ Let y be an arbitrary element of A’ ∩ B’. y ∈ A’ ∩ B’ ⇒ y ∈ A’ and y ∈ B’ ⇒ y ∉ A and y ∉ B ⇒ y ∉ (A ∪ B) ⇒ y ∈ (A ∪ B)’ Thus, A’ ∩ B’ ⊆ (A ∪ B)’. From Parts 1 and 2, we conclude that (A ∪ B)’ = A’ ∩ B’ .
(d) Yes, every function is a relation . A relation from set A to set B is simply a set of ordered pairs (a, b) where a ∈ A and b ∈ B. A function is a special type of relation that has an additional condition: for every element in the domain, there is exactly one corresponding element in the codomain. No, not every relation is a function . A relation can fail to be a function for two reasons:
- An element of the domain might not be mapped to any element in the codomain.
- An element of the domain might be mapped to more than one element in the codomain.
Example:
Let A = {1, 2} and B = {3, 4}. The relation R = {(1, 3), (1, 4), (2, 3)} is a relation from A to B. It is not a function because the element ‘1’ is mapped to two different elements, ‘3’ and ‘4’, which violates the definition of a function which requires a ‘one-to-one’ or ‘many-to-one’ mapping.
(e) The Boolean expression for the given logic circuit can be derived as follows:
- The top gate is an AND gate. Its inputs are X₁ and X₂. Its output is X₁ ∧ X₂ (or X₁·X₂).
- The bottom gate is an OR gate. Its inputs are the output of the AND gate and X₃.
- Therefore, the inputs to the OR gate are (X₁ ∧ X₂) and X₃.
The final output is the OR of these inputs, which gives the expression:
Output = (X₁ ∧ X₂) ∨ X₃
or in Boolean algebra notation,
F = (X₁·X₂) + X₃
.
(f) The given function is f(x) = (2x – 3) / 4. The function f: R → R is both one-to-one and onto, so its inverse exists. To find the inverse: 1. Write y = f(x): y = (2x – 3) / 4 2. Swap x and y: x = (2y – 3) / 4 3. Solve for y: 4x = 2y – 3 4x + 3 = 2y y = (4x + 3) / 2 4. Replace y with f⁻¹(x). Therefore, the inverse function is f⁻¹(x) = (4x + 3) / 2 .
(g) We need to choose a captain and a vice-captain from 15 players. This is a permutation problem because the order of selection matters (i.e., Player A as Captain and Player B as Vice-Captain is different from Player B as Captain and Player A as Vice-Captain). We use the permutation formula for choosing k items from n items: P(n, k) = n! / (n – k)! Here, n = 15 (total players) and k = 2 (roles to be filled). Number of ways = P(15, 2) = 15! / (15 – 2)! = 15! / 13! = (15 × 14 × 13!) / 13! = 15 × 14 = 210 Thus, the captain and vice-captain can be chosen in 210 different ways.
Q2. (a) How many words can be formed using letters of the word “DEPARTMENT”, if each letter must be used at most once? (4) (b) Give geometric representation for {1, 2, 3} x {2, 3}. (2) (c) Verify that: p→q ≡ ¬p∨q (2) (d) Find the number of ways to distribute 20 distinct objects into 10 distinct boxes with at least 4 boxes remaining empty. (2)
Ans. (a) The word “DEPARTMENT” has 10 letters. If we analyze the frequency of the letters: D-1, E-2, P-1, A-1, R-1, T-2, M-1, N-1. The question states “if each letter must be used at most once”. This phrase typically refers to the permutation of the letters. Interpreting this as how we can arrange the 10 available letter positions, we must account for the repeated letters. The formula for permutations with repetition is: n! / (p₁! p₂! … pₖ!), where n is the total number of letters and p₁, p₂, … are the counts of the repeated letters. Here, n = 10. The letter ‘E’ appears 2 times and ‘T’ appears 2 times. So, p₁ = 2 (for E) and p₂ = 2 (for T). The number of words that can be formed = 10! / (2! × 2!) = 3,628,800 / (2 × 2) = 3,628,800 / 4 = 907,200 Therefore, 907,200 different words can be formed using the letters of the word “DEPARTMENT”.
(b) The Cartesian product of the sets {1, 2, 3} × {2, 3} is the set of ordered pairs: {1, 2, 3} × {2, 3} = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)} The geometric representation is a set of 6 points on the 2-dimensional Cartesian plane. The x-axis values are taken from {1, 2, 3} and the y-axis values are from {2, 3}. The points would be represented as a grid:
- At x=1, we have the points (1, 2) and (1, 3).
- At x=2, we have the points (2, 2) and (2, 3).
- At x=3, we have the points (3, 2) and (3, 3).
This forms a set of 6 discrete points arranged in a rectangular grid on the plane.
(Imagine a graph with 1, 2, 3 marked on the x-axis and 2, 3 on the y-axis. Points are drawn at the intersections of these coordinates.)
(c) We can verify p → q ≡ ¬p ∨ q using a truth table.
p |
q |
p → q |
¬p |
¬p ∨ q |
| T | T | T |
F | T |
| T | F | F |
F | F |
| F | T | T |
T | T |
| F | F | T |
T | T |
Since the columns for
p → q
and
¬p ∨ q
have the same truth values, it is verified that they are logically equivalent.
(d) This is a complex combinatorial problem solved using the Principle of Inclusion-Exclusion. An exact calculation is too complex for the marks on this question. We will outline the logic behind the answer. We need to find the number of ways for exactly 4 boxes to be empty, plus the ways for exactly 5 to be empty, …, up to exactly 9 boxes being empty. The number of ways to have exactly k boxes empty is: C(10, k) × (Number of ways to distribute 20 distinct objects into the remaining (10-k) boxes such that none are empty) The second part is calculated using Stirling numbers of the second kind, denoted S(n, r). The number of ways to distribute n distinct objects into r distinct boxes so that no box is empty is r! × S(n, r). Here, n=20 and r=10-k. So, the number of ways to have exactly k empty boxes is: C(10, k) × (10-k)! × S(20, 10-k) . The total number of ways is the sum of these values from k=4 to 9: Total Ways = ∑ 9 k=4 [C(10, k) × (10-k)! × S(20, 10-k)] Calculating this expression is non-trivial and generally beyond the scope of this course. The question likely tests the understanding of the concept.
Q3. (a) Reduce the following Boolean expression to simpler form: (4) f(x₁, x₂, x₃) = [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] (b) Show that ¬(p → q) → p is a tautology. (2) (c) Prove that √2 is irrational. (4)
Ans. (a) To simplify the given Boolean expression: f(x₁, x₂, x₃) = [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] We rewrite it in dot notation for simplicity: F = x₁x₂x₃ + x₁x₂’ + x₂x₃ Rearranging (Commutative Law): F = x₁x₂x₃ + x₂x₃ + x₁x₂’ Apply the absorption law (A + AB = A) to the first two terms, where A = x₂x₃ and B = x₁. (x₁x₂x₃ + x₂x₃) = x₂x₃ So, the expression becomes: F = x₂x₃ + x₁x₂’ This expression cannot be simplified further. Alternatively, using a Karnaugh map: The expression [x₁ ∧ x₂ ∧ x₃] ∨ [x₁ ∧ x₂’] ∨ [x₂ ∧ x₃] corresponds to minterms 111, (100, 101), and (011, 111). The set of minterms is {m₃, m₄, m₅, m₇}, which are (011, 100, 101, 111). The K-map:
x₁ \ x₂x₃ |
00 |
01 |
11 |
10 |
0 |
0 | 0 | 1 | 0 |
1 |
1 | 1 | 1 | 0 |
Grouping the 1s:
- Grouping m₃(011) and m₇(111) gives us x₂x₃ .
- Grouping m₄(100) and m₅(101) gives us x₁x₂’ .
Combining these groups, the simplified expression is:
F = x₁x₂’ + x₂x₃
or
[x₁ ∧ x₂’] ∨ [x₂ ∧ x₃]
.
(b) To show that ¬(p → q) → p is a tautology, we can use logical equivalences: ¬(p → q) → p ≡ ¬(¬p ∨ q) → p (Conditional Identity) ≡ (p ∧ ¬q) → p (De Morgan’s Law) ≡ ¬(p ∧ ¬q) ∨ p (Conditional Identity) ≡ (¬p ∨ ¬(¬q)) ∨ p (De Morgan’s Law) ≡ (¬p ∨ q) ∨ p (Double Negation) ≡ (p ∨ ¬p) ∨ q (Associative & Commutative Laws) ≡ T ∨ q (Negation Law) ≡ T (Domination Law) Since the expression always evaluates to True (T), it is a tautology .
(c) We will prove that √2 is irrational using proof by contradiction. Assumption: Let’s assume that √2 is rational. This means √2 can be written as a fraction of two integers p and q, where q ≠ 0, and p and q have no common factors (i.e., the fraction p/q is in its simplest form). So, √2 = p/q Squaring both sides: 2 = p²/q² p² = 2q² This equation implies that p² is an even number (as it is a multiple of 2). If p² is even, then p must also be even. (The square of an odd number is always odd). Since p is even, we can write it as p = 2k, where k is an integer. Now substitute p = 2k into the equation p² = 2q²: (2k)² = 2q² 4k² = 2q² q² = 2k² This implies that q² is also an even number. Therefore, q must also be even. We have now established that both p and q are even. This means they both have a common factor of 2. This is a contradiction of our initial assumption that p and q have no common factors. Since our initial assumption leads to a contradiction, the assumption must be false. Therefore, √2 must be irrational .
Q4. (a) Find CNF of ¬(p ↔ q) ∨ (p → q). (4) (b) Write Pigeonhole principle and Generalized Pigeonhole principle. (3) (c) Draw the circuit for the following Boolean expression using logic gates: (3) Y = A’BC + A’BC’ + ABC’
Ans. (a) We need to find the Conjunctive Normal Form (CNF) of the expression E = ¬(p ↔ q) ∨ (p → q). Let’s first simplify the expression: E ≡ ¬(p ↔ q) ∨ (¬p ∨ q) (Conditional Identity) We know that p ↔ q ≡ (p → q) ∧ (q → p) ≡ (¬p ∨ q) ∧ (p ∨ ¬q) And ¬(p ↔ q) ≡ p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q) Substituting ¬(p ↔ q) into E: E ≡ (p ∧ ¬q) ∨ (¬p ∧ q) ∨ (¬p ∨ q) Note that (¬p ∧ q) ∨ (¬p ∨ q) = (¬p ∧ q) ∨ ¬p ∨ q. By the absorption law (A ∨ (A ∧ B) = A), ¬p ∨ (¬p ∧ q) = ¬p. So, (¬p ∧ q) ∨ ¬p ∨ q = ¬p ∨ q. The expression E now becomes: E ≡ (p ∧ ¬q) ∨ (¬p ∨ q) This is in DNF (Disjunctive Normal Form). To convert to CNF, we use the distributive law: X ∨ (Y ∧ Z) = (X ∨ Y) ∧ (X ∨ Z). E ≡ (¬p ∨ q) ∨ (p ∧ ¬q) ≡ ((¬p ∨ q) ∨ p) ∧ ((¬p ∨ q) ∨ ¬q) ≡ (¬p ∨ p ∨ q) ∧ (¬p ∨ q ∨ ¬q) ≡ (T ∨ q) ∧ (¬p ∨ T) (Negation Law) ≡ T ∧ T ≡ T (True) The expression is a tautology . The CNF of a tautology is simply T . If a non-trivial form is required, it can be written as (p ∨ ¬p).
(b) Pigeonhole Principle: This principle states that if n items are put into m containers, and if n > m , then at least one container must contain more than one item. More formally: If k+1 or more objects (pigeons) are placed into k boxes (pigeonholes), then at least one box will contain more than one object. This applies to a function f: X → Y, where X is the set of objects and Y is the set of containers. If |X| > |Y|, then f cannot be injective (one-to-one). Generalized Pigeonhole Principle: This principle extends the basic one. It states that if N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects. Here, ⌈x⌉ is the ceiling function, which gives the smallest integer greater than or equal to x. Example: If there are 100 students in a class, then at least ⌈100/12⌉ = ⌈8.33⌉ = 9 students must be born in the same month. (N=100 objects/students, k=12 boxes/months).
(c) The given Boolean expression is: Y = A’BC + A’BC’ + ABC’ Before drawing the circuit, we will simplify the expression. Y = A’B(C + C’) + ABC’ (Distributive Law) Since C + C’ = 1: Y = A’B(1) + ABC’ Y = A’B + ABC’ Now we can apply another rule, the Adjacency Theorem X + X’Y = X + Y. Let’s rearrange: Y = B A’ + B(AC’) This is not a direct application. Let’s try another approach on Y = A’B + ABC’. Y = B(A’ + AC’) Using the theorem X + X’Y = X + Y, we get: A’ + AC’ = A’ + C’ So, Y = B(A’ + C’) = A’B + BC’ This is the simplest form. Now we will draw the logic circuit for Y = A’B + BC’ . We will need the following gates:
- 2 NOT gates (to create A’ from A and C’ from C)
- 2 AND gates (to create A’B and BC’)
- 1 OR gate (to combine (A’B) and (BC’))
The circuit would be as follows:
- Input A passes through a NOT gate to produce A’.
- A’ and input B go into an AND gate, outputting A’B.
- Input C passes through a NOT gate to produce C’.
- Input B and C’ go into a second AND gate, outputting BC’.
- The outputs from the two AND gates (A’B and BC’) go into an OR gate.
- The final output of the OR gate is Y = A’B + BC’.
(A diagram can be drawn based on this description.)
Q5. (a) Explain the Identity Laws of Boolean Algebra. (2) (b) State and prove the Addition Theorem of Probability. (3) (c) Verify that p∧q∧¬p is a contradiction. (2) (d) Suppose A and B are mutually exclusive events, such that P(A) = 0.3 and P(B) = 0.4. What is the probability that: (3) (i) A does not occur? (ii) A or B occurs? (iii) Either A or B does not occur?
Ans. (a) The Identity Laws of Boolean Algebra describe how a variable behaves when subjected to an OR or AND operation with a specific value (the identity element). There are two identity laws:
- Identity for OR: A + 0 = A This law states that ORing any variable (A) with 0 results in the original variable (A). Here, ‘0’ is the identity element for the OR operation. If A is True (1), then 1 + 0 = 1 (A). If A is False (0), then 0 + 0 = 0 (A).
- Identity for AND: A · 1 = A This law states that ANDing any variable (A) with 1 results in the original variable (A). Here, ‘1’ is the identity element for the AND operation. If A is True (1), then 1 · 1 = 1 (A). If A is False (0), then 0 · 1 = 0 (A).
These laws are fundamental in simplifying Boolean expressions.
(b) Addition Theorem of Probability Statement: If A and B are any two events in a sample space S, then the probability of A or B or both occurring is given by: P(A ∪ B) = P(A) + P(B) – P(A ∩ B) If the events A and B are mutually exclusive (i.e., they cannot happen together, A ∩ B = ∅), then P(A ∩ B) = 0, and the theorem simplifies to: P(A ∪ B) = P(A) + P(B)
Proof: From the axiomatic definition of probability, the probability of an event E is P(E) = |E| / |S|, where |E| is the number of outcomes in event E and |S| is the total number of outcomes in the sample space. From set theory, we know that for the union of two sets, the rule of cardinality is: |A ∪ B| = |A| + |B| – |A ∩ B| Dividing each term of this equation by |S|: |A ∪ B| / |S| = |A| / |S| + |B| / |S| – |A ∩ B| / |S| Using the definition of probability, we can substitute each term with its probability: P(A ∪ B) = P(A) + P(B) – P(A ∩ B) Thus, the theorem is proved.
(c) To verify that p ∧ q ∧ ¬p is a contradiction, we can use the laws of Boolean algebra. p ∧ q ∧ ¬p ≡ (p ∧ ¬p) ∧ q (Associative and Commutative Laws) We know from the negation law that p ∧ ¬p = F (False) . ≡ F ∧ q And from the domination law, F ∧ q = F . ≡ F (Contradiction) Since the expression always evaluates to F (False), it is a contradiction .
Verification by Truth Table:
p |
q |
¬p |
p ∧ q |
(p ∧ q) ∧ ¬p |
| T | T | F | T | F |
| T | F | F | F | F |
| F | T | T | F | F |
| F | F | T | F | F |
The final column has all values as F, confirming it is a contradiction.
(d) Given: P(A) = 0.3, P(B) = 0.4, and A and B are mutually exclusive , which means P(A ∩ B) = 0 . (i) A does not occur? This is the probability of the complement of A, P(A’). P(A’) = 1 – P(A) P(A’) = 1 – 0.3 = 0.7
(ii) A or B occurs? This is the probability of the union of A and B, P(A ∪ B). P(A ∪ B) = P(A) + P(B) – P(A ∩ B) Since they are mutually exclusive, P(A ∩ B) = 0. P(A ∪ B) = P(A) + P(B) P(A ∪ B) = 0.3 + 0.4 = 0.7
(iii) Either A or B does not occur? This means P(A’ ∪ B’). Using De Morgan’s Law, P(A’ ∪ B’) = P((A ∩ B)’). P((A ∩ B)’) = 1 – P(A ∩ B) Since P(A ∩ B) = 0: P(A’ ∪ B’) = 1 – 0 = 1 This means it is certain that either A will not occur, or B will not occur (or both will not occur). This makes sense because they cannot happen together.
Download IGNOU previous Year Question paper download PDFs for MCS-013 to improve your preparation. These ignou solved question paper IGNOU Previous Year Question paper solved PDF in Hindi and English help you understand the exam pattern and score better.
Thanks!
Leave a Reply