Undergraduate
  1. Algebra  1.1. Linear Algebra  1.1.1. Matrices  1.1.2. Determinants  1.1.3. Systems of Linear Equations  1.1.4. Vector Spaces  1.1.5. Linear Transformations  1.1.6. Eigenvalues and Eigenvectors  1.1.7. Diagonalization  1.1.8. Inner Product Spaces  1.1.9. Orthogonality and Orthonormal Bases  1.1.10. Singular Value Decomposition  1.2. Abstract Algebra  1.2.1. Groups  1.2.2. Subgroups  1.2.3. Cyclic Groups  1.2.4. Permutation Groups  1.2.5. Homomorphisms  1.2.6. Normal Subgroups  1.2.7. Rings  1.2.8. Fields  1.2.9. Ideals and Quotient Rings  1.2.10. Polynomial Rings  1.2.11. Vector Spaces over Fields  1.2.12. Modules  1.2.13. Galois Theory
  2. Calculus  2.1. Differential Calculus  2.1.1. Limits  2.1.2. Continuity  2.1.3. Derivatives  2.1.4. Chain Rule  2.1.5. Implicit Differentiation  2.1.6. Applications of Derivatives  2.1.7. Optimization Problems  2.1.8. Mean Value Theorem  2.2. Integral Calculus  2.2.1. Definite Integrals  2.2.2. Indefinite Integrals  2.2.3. Techniques of Integration  2.2.4. Improper Integrals  2.2.5. Applications of Integration  2.2.6. Arc Length and Surface Area  2.3. Multivariable Calculus  2.3.1. Partial Derivatives  2.3.2. Gradient  2.3.3. Divergence and Curl  2.3.4. Multiple Integrals  2.3.5. Line Integrals  2.3.6. Surface Integrals  2.3.7. Green's Theorem  2.3.8. Stokes' Theorem  2.3.9. Divergence Theorem  2.3.10. Jacobians
  3. Differential Equations  3.1. Ordinary Differential Equations  3.1.1. First Order Differential Equations  3.1.2. Higher Order Differential Equations  3.1.3. Systems of Differential Equations  3.1.4. Series Solutions  3.1.5. Numerical Methods for ODEs  3.2. Partial Differential Equations  3.2.1. Heat Equation  3.2.2. Wave Equation  3.2.3. Laplace Equation  3.2.4. Separation of Variables  3.2.5. Fourier Transform Methods
  4. Real Analysis  4.1. Sequences and Series  4.1.1. Convergence of Sequences  4.1.2. Series Tests  4.1.3. Power Series  4.1.4. Uniform Convergence  4.2. Functions of Real Variables  4.2.1. Limits and Continuity  4.2.2. Uniform Continuity  4.2.3. Differentiation in Functions of Real Variables  4.2.4. Riemann Integration  4.2.5. Lebesgue Integration
  5. Complex Analysis  5.1. Complex Numbers  5.1.1. Polar Form  5.1.2. Exponential Form  5.2. Functions of a Complex Variable  5.2.1. Analytic Functions  5.2.2. Cauchy-Riemann Equations  5.2.3. Contour Integrals  5.2.4. Cauchy's Integral Theorem  5.2.5. Residue Theorem  5.2.6. Conformal Mapping
  6. Probability and Statistics  6.1. Probability Theory  6.1.1. Basic Probability Concepts  6.1.2. Random Variables  6.1.3. Probability Distributions  6.1.4. Expectation and Variance  6.1.5. Conditional Probability and Bayes' Theorem  6.2. Statistics  6.2.1. Descriptive Statistics  6.2.2. Inferential Statistics  6.2.3. Hypothesis Testing  6.2.4. Regression Analysis  6.2.5. ANOVA
  7. Numerical Methods  7.1. Root-Finding Algorithms  7.2. Numerical Integration  7.3. Numerical Differentiation  7.4. Numerical Solutions to Differential Equations  7.5. Matrix Computations  7.6. Interpolation and Extrapolation
  8. Discrete Mathematics  8.1. Logic and Proof  8.2. Combinatorics  8.3. Graph Theory  8.4. Boolean Algebra  8.5. Recurrence Relations
  9. Linear Programming and Optimization  9.1. Simplex Method  9.2. Duality  9.3. Integer Programming  9.4. Nonlinear Optimization
  10. Topology  10.1. Metric Spaces  10.2. Topological Spaces  10.3. Continuity and Homeomorphisms  10.4. Compactness  10.5. Connectedness
  11. Geometry  11.1. Euclidean Geometry  11.2. Differential Geometry  11.3. Non-Euclidean Geometry  11.4. Projective Geometry
  12. Mathematical Physics  12.1. Fourier Series  12.2. Laplace Transforms  12.3. Applications of Differential Equations  12.4. Special Functions
  13. Set Theory and Logic  13.1. Sets and Subsets  13.2. Relations and Functions  13.3. Cardinality  13.4. Formal Logic  13.5. Zermelo-Fraenkel Set Theory
  14. Functional Analysis  14.1. Normed Spaces  14.2. Banach Spaces  14.3. Hilbert Spaces  14.4. Linear Operators

Undergraduate → Discrete Mathematics ↓


Logic and Proof


Discrete mathematics plays an important role in mathematics curriculum globally, especially in the field of computer science. It deals with countable, distinct elements and includes topics such as logic, proof, set theory, graph theory, and combinatorics. In this comprehensive guide, we focus on the fundamental aspects of discrete mathematics: logic and proof.

Understanding the argument

The term 'logic' refers to a systematic method of arriving at a conclusion. In mathematics, logic is a tool used to infer truth and reasoning is the backbone of mathematical proof. It involves reasoning through premises to arrive at a conclusion.

Proposal

In logic, a proposition is a statement that can be either true or false, but not both. Here are some examples:

  • The sky is blue. (This statement is true on a clear day)
  • 2 + 2 equals 5. (a false proposition)
  • All human beings are immortal. (False proposition)

Non-examples would include the following:

  • What time is it now? (This is not a proposal, but a question)
  • Please close the door. (This is not an offer, but a request)

Logical operations

Logical operations are used to form complex propositions and understand their truth values. The main logical operations are given below:

Denial

The negation of a proposition changes its truth value. It is represented by the '¬' symbol. For example, if P is "the apple is red", then P is "the apple is not red". If P is true, then P is false, and vice versa.

Coordinator

The conjunction ('and') of propositions is true only if both the propositions are true. It is represented using the '∧' sign. For example, P ∧ Q means "the sky is blue and the grass is green". It is true only if both P and Q are true.

    +---------------+------+------+
| P     | Q    | P ∧ Q |
+---------------+------+------+
| True  | True | True   |
| True  | False| False  |
| False | True | False  |
| False | False| False  |
+---------------+------+------+

Isolation

The disjunction ('or') of propositions is true if at least one of the propositions is true. It is represented using the '∨' symbol. For example, P ∨ Q means "the sky is blue or the grass is green".

    +---------------+------+------+
| P     | Q    | P ∨ Q |
+---------------+------+------+
| True  | True | True   |
| True  | False| True   |
| False | True | True   |
| False | False| False  |
+---------------+------+------+

Implications

Implication states that one proposition leads to another proposition and is represented by '→'. For example, P → Q means "if P , then Q ". The implication is false only if the first proposition is true and the second is false.

    +---------------+------+------+
| P     | Q    | P → Q |
+---------------+------+------+
| True  | True | True   |
| True  | False| False  |
| False | True | True   |
| False | False| True   |
+---------------+------+------+

Binary

A biconditional statement states " P if and only if Q ", which is represented by '↔'. It is true if the truth value of both the propositions is the same.

    +---------------+------+------+
| P     | Q    | P ↔ Q |
+---------------+------+------+
| True  | True | True   |
| True  | False| False  |
| False | True | False  |
| False | False| True   |
+---------------+------+------+

Visual examples of logical statements

Logical concepts can be understood better with visual aids.

Example of combination:
p ∧ q

Example of disjunction:
p ∨ q

Mathematical proof

A proof is a logical argument that verifies the truth of a proposition. Mathematicians use proofs to rigorously test and establish new theorems. The basic goal is to show how initial assumptions logically lead to a conclusion. Let's explore different methods of proof.

Direct evidence

Direct evidence is a direct method in which you assume given premises (assumptions) to be true, and through a series of logical steps show that the conclusion must be true.

Example: Prove that if n is an even integer, then n^2 is even.

Proof: Assume that n is even. By definition, n = 2k for some integer k . Then, n^2 = (2k)^2 = 4k^2 = 2(2k^2) , which is even. Therefore, if n is even, n^2 is even.

Proof by contradiction

In proof by contradiction, you assume the opposite of what you want to prove, and show that this leads to an illogical or contradictory situation. Therefore, the original statement must be true.

Example: Prove that the square root of 2 is irrational.

Proof: Assume that the square root of 2 is rational. This implies that it can be expressed as a fraction a/b , where a and b are integers with no common factors, and b ≠ 0 . Thus, (a/b)^2 = 2 becomes a^2 = 2b^2 . This implies that a^2 is even, so a must be even. Let a = 2c , then (2c)^2 = 2b^2 simplifies to 4c^2 = 2b^2 , or 2c^2 = b^2 . Therefore, b^2 is even, which makes b even. However, this implies that a and b both have a factor of 2, which contradicts our assumption. Therefore, the square root of 2 is irrational.

Proof by induction

Proof by induction is a technique used to prove propositions about an infinitely large set of objects. It involves a base case and an inductive step.

Example: Prove that for all n ≥ 1 , 1 + 2 + 3 + ... + n = n(n + 1)/2

Evidence:

  1. Base case: Let n = 1 The left side is 1 and the right side is 1(1 + 1)/2 = 1 Thus, it is true for n = 1 .
  2. Inductive step: Assume that it is true for n = k (induction hypothesis), that is, 1 + 2 + ... + k = k(k + 1)/2 . We have to show that it is true for n = k + 1 .
  3. Consider the sum up to k + 1 : 1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) .
  4. Simplify: k(k + 1)/2 + 2(k + 1)/2 = (k + 1)(k + 2)/2 .
  5. Therefore, the formula is true for k + 1 By induction, it is true for all n ≥ 1 .

Common mistakes in reasoning and proof

It's important to be aware of logical fallacies and common mistakes in argument construction. Some examples include:

  • Affirming the consequence: Assuming that since the conclusion is true, the premise must also be true. This is a fallacy. For example, If it rains, the ground gets wet . The ground is wet, therefore it rained, which could be false if sprinklers were being used.
  • Denying the antecedent: Assuming that since the premise is false, the conclusion must also be false, which may not be true.
  • Circular reasoning: When the conclusion of an argument is assumed based on one of the premises. Basically, the argument moves in a circular direction without any initial evidence.

Conclusion

Understanding logic and proof is the basis of mathematics and all scientific reasoning. It helps hone problem-solving skills and structured thinking. When you practice making and proving arguments, you not only gain mathematical insight but also improve your cognitive skills.


Undergraduate → 8.1


U
username
0%
completed in Undergraduate

← Prev (8)
Discrete Mathematics
Next (8.2) →
Combinatorics

Comments 



Logic and Proof

https://www.buddymath.com/ug/8.1?bmal=en