<p><span style="font-size: 18px"><strong>Proposition</strong> is declarative sentence that can be either <strong>unversally true </strong>or <strong>unversally false</strong>, both can't be possible.</span><br></p><h2><span style="font-size: 18px"><strong>Example of Proposition:</strong></span></h2><h3><span style="font-size: 18px"><strong>True Proposition</strong>:</span></h3><ul><li style="font-size: 18px">"2 + 2 = 4" (This is always true.)</li><li style="font-size: 18px">"The Earth revolves around the Sun."</li></ul><h3><span style="font-size: 18px"><strong>False Proposition</strong>:</span></h3><ul><li style="font-size: 18px">"5 is an even number." (This is always false.).</li><li style="font-size: 18px">"All prime numbers are even." (False because 2 is the only even prime.).</li></ul><p><span style="font-size: 18px">Generally we denote proposition with small letters like p, q etc. So for example we may denote below poposition like:</span></p><div></div><p></p><p></p><p><span style="font-size: 15px">‘<strong>Ice is always cold</strong>.’ by p, or</span></p><p><span style="font-size: 15px"></span><span style="font-size: 15px"><span class="__se__katex katex" data-exp="sin^2\theta+cos^2\theta=1" data-font-size="1em" style="font-size: 16px"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>s</mi><mi>i</mi><msup><mi>n</mi><mn>2</mn></msup><mi>θ</mi><mo>+</mo><mi>c</mi><mi>o</mi><msup><mi>s</mi><mn>2</mn></msup><mi>θ</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">sin^2\theta+cos^2\theta=1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9474em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">s</span><span class="mord mathnormal">i</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mord mathnormal" style="margin-right:0.02778em;">θ</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8641em;"></span><span class="mord mathnormal">co</span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mord mathnormal" style="margin-right:0.02778em;">θ</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> for θ ∈ [ 0, 2π]’ by q.</span></p><p>p: <strong>Ice is always cold, or</strong></p><p>q:&nbsp;<span class="__se__katex katex" data-exp="sin^2\theta+cos^2\theta=1" data-font-size="1.5em" style="font-size: 24px"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>s</mi><mi>i</mi><msup><mi>n</mi><mn>2</mn></msup><mi>θ</mi><mo>+</mo><mi>c</mi><mi>o</mi><msup><mi>s</mi><mn>2</mn></msup><mi>θ</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">sin^2\theta+cos^2\theta=1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9474em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">s</span><span class="mord mathnormal">i</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mord mathnormal" style="margin-right:0.02778em;">θ</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8641em;"></span><span class="mord mathnormal">co</span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mord mathnormal" style="margin-right:0.02778em;">θ</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span>&nbsp;<span style="font-size: 15px">​ for θ ∈ [ 0, 2π].</span></p><p><span style="font-size: 15px"></span>​​</p><div><ul><li><p><span style="font-size: 15px">Now, given a proposition, we know that it is either true or false, but not both. If it is true, we will allot it the truth value <strong>T.</strong> If it is false, its truth value will be <strong>F</strong>. So, for example, the truth value of</span></p><p><span style="font-size: 15px">‘Ice melts at 30</span><span style="font-size: 9px">o </span><span style="font-size: 15px">C.’ is F, while that of ‘x<sup>2</sup>≥ 0 for x ∈ R’ is T.</span></p></li></ul><h2>Non-Propositions (Not Statements)<br></h2></div><div></div><p><span style="font-size: 18px">Some statements are not propositions because they are not definitively <strong>true</strong> or <strong>false</strong>:​​</span></p><ul><li style="font-size: 16px"><strong>Questions</strong>: "What time is it?" (Not a proposition)</li><li style="font-size: 16px"><strong>Commands</strong>: "Close the door!" (Not a proposition)</li><li style="font-size: 16px"><strong>Opinions</strong>: "Chocolate is the best ice cream flavor." (Subjective)</li></ul><h3><span style="font-size: 18px"><strong>​Types of Propositions</strong></span></h3><p></p><div></div><div></div><ol><li><p><span style="font-size: 16px"><strong>Atomic Proposition</strong>: A simple statement that does not contain logical connectors.</span></p></li><li><p><span style="font-size: 16px"><strong>Compound Proposition</strong>: A statement formed by combining multiple atomic propositions using logical operators (<strong>AND, OR, NOT, IF-THEN</strong>).</span></p><ul><li style="font-size: 16px">Example: "It is raining <strong>and</strong> it is cold."<br>(Using <strong>AND</strong>, meaning both must be true for the statement to be true.)</li></ul><ul><li style="font-size: 16px">Example: "It is raining."</li></ul></li></ol><div>​<div></div>​</div><div></div><div></div><div></div><div><p>​</p></div><div></div><p>​​<br></p><div></div><p><span style="font-size: 18px">​<br></span></p>

Propositions

<p><span style="font-size: 16px">​<strong>Discrete Mathematics</strong> is a branch of mathematics that deals with structures that are fundamentally discrete rather than continuous. Unlike calculus or real analysis—which focus on continuous functions and processes—discrete mathematics focuses on objects that can assume only distinct, separated values. This area of mathematics underpins many concepts in computer science, cryptography, combinatorics, logic, and more.​</span></p><p><span style="font-family:Arial"><span style="font-size: 16px">Mathematics is divided in to two basic structure&nbsp;</span></span></p><ol><li><span style="font-family:Arial"><span style="font-size: 16px">Discrete</span></span></li><li><span style="font-family:Arial"><span style="font-size: 16px">Continious</span></span></li></ol><div class="se-component se-image-container __se__float-none" style="width: 100%"><figure style="width: 100%;"><img src="https://www.api.ignoustudyadda.com/upload/editor-image/dicrete-vs-contin_1739275937735.png" alt="Discrete vs Continious Structure" data-rotate="" data-proportion="true" data-size="100%," data-align="none" data-percentage="100," data-file-name="dicrete-vs-contin.png" data-file-size="80779" data-origin="," style="width: 100%;"></figure></div><h2><span style="font-size: 16px"><strong><span style="font-family: Arial;font-size: 22px">Key Topics in Discrete Mathematics</span></strong></span><br></h2><p><span style="font-family: Arial;font-size: 16px">​</span></p><h3>1. <strong>Logic and Propositional Calculus</strong></h3><ul><li><strong>Propositions and Logical Connectives:</strong><br>Statements that are either true or false; connectives include AND, OR, NOT, IF-THEN, etc.</li><li><strong>Truth Tables:</strong><br>Tools to determine the truth value of compound statements.</li><li><strong>Predicate Logic:</strong><br>Extends propositional logic by dealing with predicates and quantifiers (e.g., ∀, ∃).</li><li><strong>Proof Techniques:</strong><br>Methods like direct proof, proof by contradiction, and mathematical induction are fundamental in proving theorems in discrete mathematics.</li></ul><h3>2. <strong>Set Theory</strong></h3><ul><li><strong>Basic Sets and Operations:</strong><br>Definitions of sets, subsets, unions, intersections, differences, and complements.</li><li><strong>Venn Diagrams:</strong><br>Graphical tools to illustrate relationships between sets.</li><li><strong>Cartesian Products and Power Sets:</strong><br>Concepts that form the basis for relations and functions.</li><li><strong>Applications:</strong><br>Set theory forms the foundation of modern mathematics and is used extensively in defining functions, relations, and more.</li></ul><h3>3. <strong>Combinatorics</strong></h3><ul><li><strong>Counting Principles:</strong><br>The rule of product (multiplication principle) and the rule of sum (addition principle).</li><li><strong>Permutations and Combinations:</strong><br>Methods for counting arrangements and selections of objects.</li><li><strong>Pigeonhole Principle:</strong><br>A principle used to prove the existence of certain configurations in large sets.</li><li><strong>Recurrence Relations:</strong><br>Equations that recursively define sequences, often solved by techniques such as iteration, substitution, or generating functions.</li><li><strong>Graph Theory:</strong><br>Study of graphs (networks of nodes connected by edges) that is crucial for modeling relationships and networks.</li></ul><h3>4. <strong>Graph Theory</strong></h3><ul><li><strong>Basic Concepts:</strong><br>Graphs, nodes (vertices), edges, directed vs. undirected graphs.</li><li><strong>Important Graphs:</strong><br>Trees, bipartite graphs, planar graphs.</li><li><strong>Algorithms:</strong><br>Algorithms for searching (BFS, DFS), shortest paths (Dijkstra’s algorithm), and network flows.</li><li><strong>Applications:</strong><br>Widely used in computer networks, social network analysis, transportation, and scheduling problems.</li></ul><h3>5. <strong>Number Theory</strong></h3><ul><li><strong>Divisibility, Primes, and Congruences:</strong><br>Fundamental properties of integers.</li><li><strong>Modular Arithmetic:</strong><br>Arithmetic with remainders, which is important in cryptography.</li><li><strong>Diophantine Equations:</strong><br>Equations that require integer solutions.</li></ul><h3>6. <strong>Discrete Probability</strong></h3><ul><li><strong>Counting Methods:</strong><br>Techniques like permutations and combinations are used to calculate probabilities.</li><li><strong>Random Variables and Distributions:</strong><br>Study of discrete distributions such as binomial, geometric, and Poisson distributions.</li><li><strong>Expectation and Variance:</strong><br>Basic statistical measures in a discrete setting.</li></ul><h3>7. <strong>Algorithms and Complexity</strong></h3><ul><li><strong>Algorithm Analysis:</strong><br>Evaluating the efficiency (time and space complexity) of algorithms, often using recurrence relations and Big-O notation.</li><li><strong>Discrete Structures in Computer Science:</strong><br>Data structures like trees, graphs, and hash tables rely on discrete mathematics.</li></ul><p><br></p><p><br></p>

Home

Logical Connectives

Methods of proof

Principle of Induction

<h2>Boolean Algebra Definition:</h2><p>​<span style="font-size: 18px">​Boolean algebra is a branch of algebra that deals with variables having only two distinct values, typically denoted as 0 (false) and 1 (true). It forms the foundation for digital logic, computer science, and electrical engineering. Below is an in-depth exploration of its concepts, principles, and applications.</span>​<br></p><p><span style="font-size: 18px">A Boolean algebra <strong>B</strong> is an algebraic structure which consists of a set X(≠ Ø) having two binary operations (denoted by ∨ and ∧), one unary operation(denoted by ' ) and two specially defined elements O and I (say), which satisfy thefollowing five laws for all x, y, z ∈ X.</span></p><p><span style="font-size: 15px"><strong>B1. Associative Laws:&nbsp;</strong></span></p><p><span style="font-size: 18px">x ∨ (y ∨ z) = (x ∨ y) ∨ z,</span></p><p><span style="font-size: 18px">x ∧ (y ∧ z) = (x ∧ y) ∧ z</span></p><p></p><p><span style="font-size: 15px"><strong>B2. Commutative Laws:</strong></span></p><p><span style="font-size: 18px">x ∨ y = y ∨ x,</span></p><p><span style="font-size: 18px">x∧y=y∧x</span></p><p><span style="font-size: 15px"><strong>​</strong></span><strong>B3. Distributive Laws:</strong></p><p><span style="font-size: 18px">x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z),</span></p><p><span style="font-size: 18px">x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)</span></p><p><span style="font-size: 15px"><strong>B4. Identity Laws:</strong></span></p><p><span style="font-size: 15px"></span>X V O = X</p><p>X ^ I = X<br><span style="font-size: 15px"><strong>B5. Complementation Laws:</strong></span></p><p></p><p><span style="font-size: 15px">x </span><span style="font-size: 15px">∧ </span><span style="font-size: 15px">x' = </span><span style="font-size: 15px">O</span><span style="font-size: 15px">,</span></p><p><span style="font-size: 15px">x ∨ x'= I.</span></p><p><br></p><p><span style="font-size: 18px"><strong>Origins:</strong></span><br></p><p><span style="font-size: 18px">​Boolean algebra was developed in the mid-19th century by George Boole. His work laid the groundwork for the algebraic treatment of logic, which was later adapted to electronic circuit design and computer programming.<br></span></p><p><span style="font-size: 18px"><strong>Evolution:</strong><br>Over time, Boolean algebra has become instrumental in designing circuits and algorithms, influencing everything from early computing machines to modern digital systems.<br></span></p><h2><span style="font-size: 18px">Boolean Variables and Values<br></span></h2><p><span style="font-size: 18px">Boolean variables are binary in the nature.<br></span></p><ul><li><span style="font-size: 18px">o (false)<br></span></li><li><span style="font-size: 18px">1 (true)</span></li></ul><p><span style="font-size: 18px">These values can represent logical truth values, electrical voltages (low/high), or even membership in a set.</span><br></p><h2><span style="font-size: 18px">Basic Operation Of Boolean Algebra<br></span></h2><p><span style="font-size: 18px">​The primary operations in Boolean algebra are analogous to logical operations:<br></span></p><p><span style="font-size: 18px"><strong>Conjunction (AND):</strong><br>Denoted by <span class="katex"><span class="katex-mathml">⋅\cdot</span><span class="katex-html"><span class="base"><span class="strut"></span><span class="mord">⋅, ^</span></span></span></span> or sometimes simply by juxtaposition (e.g., <span class="katex"><span class="katex-mathml">abab</span><span class="katex-html"><span class="base"><span class="strut"></span><span class="mord mathnormal">ab</span></span></span></span>).<br></span></p><p><span style="font-size: 18px"><strong>Truth Table:</strong></span><br></p><table class="se-table-layout-fixed"><thead><tr><th><div>a</div></th><th><div>b</div></th><th><div>a.b</div></th></tr></thead><tbody><tr><td><div>0</div></td><td><div>0</div></td><td><div>0</div></td></tr><tr><td><div>0</div></td><td><div>1</div></td><td><div>0</div></td></tr><tr><td><div>1</div></td><td><div>0</div></td><td><div>0</div></td></tr><tr><td><div>1</div></td><td><div>1</div></td><td><div>1</div></td></tr></tbody></table><p><span style="font-size: 18px"><strong>Disjunction (OR):</strong><br>Denoted by <span class="katex"><span class="katex-mathml">++</span><span class="katex-html">+, V</span></span>.<br><strong><em>Truth Table:</em></strong></span></p><table class="se-table-layout-fixed"><thead><tr><th><div>a</div></th><th><div>b</div></th><th><div>a+b</div></th></tr></thead><tbody><tr><td><div>0</div></td><td><div>0</div></td><td><div>0</div></td></tr><tr><td><div>0</div></td><td><div>1</div></td><td><div>1</div></td></tr><tr><td><div>1</div></td><td><div>0</div></td><td><div>1</div></td></tr><tr><td><div>1</div></td><td><div>1</div></td><td><div>1</div></td></tr></tbody></table><p><br></p><p><span style="font-size: 18px"><strong>Negation (NOT):</strong></span></p><p><span style="font-size: 18px">Denoted by ' or&nbsp;<span class="__se__katex katex" data-exp="\={a}" data-font-size="1.5em" style="font-size: 24px"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>a</mi><mo>ˉ</mo></mover></mrow><annotation encoding="application/x-tex">\={a}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5678em;"></span><span class="mord accent"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.5678em;"><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathnormal">a</span></span></span><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="accent-body" style="left:-0.25em;"><span class="mord">ˉ</span></span></span></span></span></span></span></span></span></span>​<br><strong><em>Truth Table:</em></strong></span></p><table class="se-table-layout-fixed"><thead><tr><th><div>a</div></th><th><div>a'</div></th></tr></thead><tbody><tr><td><div>0</div></td><td><div>1</div></td></tr><tr><td><div>1</div></td><td><div>0</div></td></tr></tbody></table><p style="line-height: 2em"><br></p><p><span style="font-size: 18px"><strong><em>​<br></em></strong></span></p>

Comments

MCS 212