
## Proposition

Generally speaking, a proposition is typically composed of a declarative sentence expressing a judgment. Propositions are classified into true and false propositions. Propositions can often be assigned to a symbol for expression, such as $p, q, r$, where these symbols are called propositional variables. A simple proposition is the most basic form of a proposition that cannot be divided into sub-propositions.

For convenience in operations, the truth or falsity of a proposition is represented using binary values $p=0$ and $p=1$, where they respectively indicate false and true propositions.

### Connectives

These connectives are basic tools in formal logic, used to construct and analyze complex logical expressions that describe the combination of propositions.

- Negation (Not), denoted as $\neg$
- Conjunction (And), denoted as $\land$
- Disjunction (Or), denoted as $\lor$
- Conditional (Implies, ImpliedBy), denoted as $\implies$ and $\impliedby$
- Biconditional (If and only if), denoted as $\iff$

Multiple simple propositions are combined into compound propositions using these connectives. The precedence of these connectives decreases from top to bottom.

Their truth table is as follows:

$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
p & q & \neg p & p \land q & p \lor q & p \implies q & p \iff q \\
\hline
0 & 0 & 1 & 0 & 0 & 1 & 1 \\
\hline
0 & 1 & 1 & 0 & 1 & 1 & 0 \\
\hline
1 & 0 & 0 & 0 & 1 & 0 & 0 \\
\hline
1 & 1 & 0 & 1 & 1 & 1 & 1 \\
\hline
\end{array}
$$

### Well-formed Formulas (WFF)

1. A single propositional variable is a well-formed formula (WFF), also called an atomic proposition.
2. If $A$ is a WFF, then $(\neg A)$ is a WFF.
3. If $A$ and $B$ are WFFs, then $(A \land B)$, $(A \lor B)$, $(A \implies B)$, and $(A \iff B)$ are WFFs.
4. A string of symbols formed by applying (1)~(3) a finite number of times is a WFF.

WFFs are also called propositional formulas, or simply formulas. They are often represented as $f(p_{1}, p_{2}, ..., p_{n})$.

### Formula Levels

1. If the formula $A = f(p)$ is a single propositional variable, then $A$ is called a level-0 formula.
2. A formula $A$ is called a level-$(n+1)$ formula (for $n \geq 0$) if one of the following holds:

   - (a) $A = \neg B$, where $B$ is a level-$n$ formula;
   - (b) $A = B \land C$, where $B$ and $C$ are formulas of levels $i$ and $j$, and $n = \max(i,j)$;
   - (c) $A = B \lor C$, where the levels of $B$ and $C$ and $n$ are as in (b);
   - (d) $A = B \implies C$, where the levels of $B$ and $C$ and $n$ are as in (b);
   - (e) $A = B \iff C$, where the levels of $B$ and $C$ are as in (b).

3. If the level of formula $A$ is $k$, then $A$ is called a level-$k$ formula.
4. The formula $f(p_{1}, p_{2}, ..., p_{n})$ is used to express a formula of level $n$.

### Tautologies and Contradictions

If $\forall p_{i} \in \{0,1\}$, $A = f(p_{1}, p_{2}, ..., p_{n}) \equiv 1$, then $A$ is called a tautology, or a logically valid formula. Conversely, if $\forall p_{i} \in \{0,1\}$, $A = f(p_{1}, p_{2}, ..., p_{n}) \equiv 0$, then $A$ is called a contradiction.

If a formula is not a contradiction, it is also called a satisfiable formula.

### Dummy Variables

A dummy variable (also known as a neutral element) refers to a special element that, under a certain operation, does not change the value of other elements.

If the value of formula $A = f(p_{1}, p_{2}, ..., p_{n})$ depends only on certain variables $p_{i1}, p_{i2}, ..., p_{in}$, then the remaining variables $\{i \in Z^{*}, i \in [1,n] \setminus \{p_{i_1}, p_{i_2}, \dots, p_{in}\}\}$ are called dummy variables. Changing the dummy variables does not affect the value of the formula.

For example, in $p \land q \equiv 1$, where $q = 1$, the formula is always true regardless of the value of $p$, making $p$ a dummy variable.

### Formula Equivalence

If two formulas have the same number of variables and the same truth table (or logical behavior), then these two formulas are equivalent. In other words, if $\forall i \in \{0,1,2,...,n\}$, $p_{i} = q_{i}$, and $f(p_{1}, p_{2}, ..., p_{n}) = g(q_{1}, q_{2}, ..., q_{n})$, then $f \equiv g$, and we can say that $f$ and $g$ are logically equivalent.

## Logical Equivalence Calculus

Let formulas $A$ and $B$ share the same propositional variables, and $A$ or $B$ may contain dummy variables. If $A$ and $B$ have the same truth table, then $A \iff B$ is a tautology. This indicates that $A$ and $B$ are logically equivalent, denoted as $A \iff B$.

Below are some common identities, which can be used to perform more complex logical operations.

### Equivalence Identities

#### 1.1 Double Negation

$$
A \iff \neg \neg A
$$

#### 1.2 Idempotent Laws

$$
A \lor A \iff A, \quad A \land A \iff A
$$

#### 1.3 Commutative Laws

$$
A \lor B \iff B \lor A, \quad A \land B \iff B \land A
$$

#### 1.4 Associative Laws

$$
(A \lor B) \lor C \iff A \lor (B \lor C),\\ (A \land B) \land C \iff A \land (B \land C)
$$

#### 1.5 Distributive Laws

$$
A \lor (B \land C) \iff (A \lor B) \land (A \lor C)
$$

(Distributivity of $\lor$ over $\land$)

$$
A \land (B \lor C) \iff (A \land B) \lor (A \land C)
$$

(Distributivity of $\land$ over $\lor$)

#### 1.6 De Morgan's Laws

$$
\neg (A \lor B) \iff \neg A \land \neg B, \\ \neg (A \land B) \iff \neg A \lor \neg B
$$

#### 1.7 Absorption Laws

$$
A \lor (A \land B) \iff A, \\ A \land (A \lor B) \iff A
$$

#### 1.8 Zero Laws

$$
A \lor 1 \iff 1, \\ A \land 0 \iff 0
$$

#### 1.9 Identity Laws

$$
A \lor 0 \iff A, \\ A \land 1 \iff A
$$

#### 1.10 Law of the Excluded Middle

$$
A \lor \neg A \iff 1
$$

#### 1.11 Law of Non-Contradiction

$$
A \land \neg A \iff 0
$$

#### 1.12 Implication Identity

$$
A \rightarrow B \iff \neg A \lor B
$$

#### 1.13 Biconditional Identity

$$
A \leftrightarrow B \iff (A \rightarrow B) \land (B \rightarrow A)
$$

#### 1.14 Contrapositive

$$
A \rightarrow B \iff \neg B \rightarrow \neg A
$$

#### 1.15 Biconditional Negation

$$
A \leftrightarrow B \iff \neg A \leftrightarrow \neg B
$$

#### 1.16 Reductio ad Absurdum

$$
(A \rightarrow B) \land (A \rightarrow \neg B) \iff \neg A
$$

The 16 equivalence identities presented above contain 24 important equivalences. The variables $A$, $B$, and $C$ in the equivalence patterns can be replaced by any propositional formulas, resulting in infinitely many specific equivalences of the same type.

These are typical examples of equivalences derived from truth tables and form the foundational formulas of logical operations.


Here are some basic mathematical logic definitions, theorems, and other notes.

NOTE & BLOG

Posts of DISCRETE-MATHEMATICS

The Basic Formal Logic (1)