Mathematical Logic for MCA

Logic is the foundation of computer science. In this section, we will cover the basic concepts of mathematical logic, including statements, logical connectives, and truth tables.

1. Statements

A statement (or proposition) is a declarative sentence that is either true or false, but not both.

Example:

• "The Earth is round" (True)
• "$$2 + 2 = 5$$" (False)

2. Logical Connectives

We use connectives to build compound statements.

A. Conjunction (AND)

The conjunction of $p$ and $q$ is denoted by $p \land q$. It is true only if both $p$ and $q$ are true.

B. Disjunction (OR)

The disjunction of $p$ and $q$ is denoted by $p \lor q$. It is false only if both $p$ and $q$ are false.

C. Negation (NOT)

The negation of $p$ is denoted by $\neg p$. It has the opposite truth value of $p$.

3. Conditional and Biconditional

• Conditional: $p \to q$ (If $p$, then $q$)
• Biconditional: $p \leftrightarrow q$ ($p$ if and only if $q$)

Contrapositive

The contrapositive of $p \to q$ is $\neg q \to \neg p$.
Theorem: A conditional statement is logically equivalent to its contrapositive.

4. Tautology and Contradiction

• Tautology: A compound statement that is always true (e.g., $p \lor \neg p$).
• Contradiction: A compound statement that is always false (e.g., $p \land \neg p$).

Summary

Understanding these basics is crucial for digital logic and programming.