Mathematics > Mathematical Logic > Propositional Logic

Propositional Logic, also known as Propositional Calculus or Sentential Logic, is a subfield of Mathematical Logic that focuses on the analysis and manipulation of propositions and their logical relationships. This foundational area of logic deals with expressions built from simple, indivisible statements (known as propositions) and logical connectives.

A proposition is a declarative sentence that is either true or false but not both. In propositional logic, propositions are typically represented by variables such as \( P \), \( Q \), or \( R \). Logical connectives are used to form compound propositions from simpler ones. The primary logical connectives are:

1. Negation (¬): Given a proposition \( P \), its negation \( \neg P \) is true if and only if \( P \) is false.
2. Conjunction ( ∧ ): The conjunction \( P \wedge Q \) is true if and only if both \( P \) and \( Q \) are true.
3. Disjunction ( ∨ ): The disjunction \( P \vee Q \) is true if at least one of \( P \) or \( Q \) is true.
4. Implication ( → ): The implication \( P \rightarrow Q \) is true if and only if either \( P \) is false or \( Q \) is true (or both).
5. Biconditional ( ↔︎ ): The biconditional \( P \leftrightarrow Q \) is true if and only if \( P \) and \( Q \) are either both true or both false.

The truth value of a compound proposition is determined by the truth values of its constituent propositions and the logical connectives. This is often visualized using truth tables. For example, the truth table for the conjunction \( P \wedge Q \) is as follows:

\[
\begin{array}{|c|c|c|}
\hline
P & Q & P \wedge Q \\
\hline
\text{True} & \text{True} & \text{True} \\
\text{True} & \text{False} & \text{False} \\
\text{False} & \text{True} & \text{False} \\
\text{False} & \text{False} & \text{False} \\
\hline
\end{array}
\]

Propositional Logic serves as the basis for more complex forms of logic, such as Predicate Logic. It is vital in various applications, including computer science (particularly in the fields of database theory, algorithms, and artificial intelligence), philosophy, and linguistics. One of the primary uses in computer science is in the design and analysis of digital circuits and programming languages, where logical expressions are used to represent and simplify complex conditions and operations.

Propositional Logic also involves understanding logical equivalences, which are propositions that express the same truth value across all possible scenarios. Some common logical equivalences include:

• Identity Laws: \( P \wedge \text{True} \equiv P \) and \( P \vee \text{False} \equiv P \)
• Domination Laws: \( P \vee \text{True} \equiv \text{True} \) and \( P \wedge \text{False} \equiv \text{False} \)
• Double Negation Law: \( \neg(\neg P) \equiv P \)
• Idempotent Laws: \( P \wedge P \equiv P \) and \( P \vee P \equiv P \)
• De Morgan’s Laws: \( \neg(P \wedge Q) \equiv \neg P \vee \neg Q \) and \( \neg(P \vee Q) \equiv \neg P \wedge \neg Q \)

These equivalences are proven using truth tables or logical deductions and are essential tools for simplifying complex propositions in both theoretical and applied contexts.