Propositional logic examines statements that are either true or false, focusing on how these are combined using operators. It forms a foundational sub-field of mathematical logic alongside first-order logic, higher-order logic, and others. This formal system represents and analyzes statements with definite truth values. Syntax defines the formal structure with propositions and logical connectives. Semantics determines truth values using truth tables, identifying tautologies and contradictions. Equivalences include laws like De Morgan's and distributive laws for simplification. Inference Rules such as modus ponens enable step-by-step proofs. Normal Forms provide standard representation methods like CNF and DNF. Proof Techniques include contradiction and direct proof methods to validate arguments. This logical system finds applications across mathematics, computer science (circuit design, program verification), artificial intelligence (knowledge representation), philosophy, and many other fields.
Basic laws of Propositional Logic
Understanding Propositional Logic Laws
Propositional logic provides a powerful framework for formal reasoning, and at its core are several fundamental laws that help us manipulate logical expressions. On this page we aggregated a summary of these laws and rules. They may be grouped into families based on their logical functions: Basic Operators: Identity, Domination, and Idempotent laws establish how basic operations behave with constants and themselves Structural Laws: Commutative, Associative, and Distributive laws govern how expressions can be rearranged Transformation Rules: Double Negation, De Morgan's Laws, and Absorption laws help convert between different logical forms Semantic Principles: Negation laws represent fundamental truths about contradictions and the law of excluded middle Implications: Contrapositive and Conditional laws help reason through logical implications Special Operators: Exclusive OR laws define the behavior of XOR operations Advanced Principles: Resolution, Monotonicity, and Peirce's Law provide powerful tools for formal proofs Each law is presented with its formal notation, a plain-language explanation, and its relevant topic area (such as Equivalences, Semantics, Normal Forms, or Proof Techniques). This organization makes it easier to find specific laws when constructing proofs or simplifying expressions. Whether you're working on simplifying complex logical statements, converting expressions to normal forms, or building formal proofs, these laws provide the essential toolkit for manipulating propositional logic expressions with confidence and precision.
Propositions in classical logic have several important properties. Here are a few key ones:
1.Logical Equivalence:
Two propositions P and Q are logically equivalent (denoted Pβ‘Q) if they have the same truth value in every possible interpretation. Example: Pβ¨Qβ‘Qβ¨P (Commutativity of disjunction) Read more about equivalence.
2.Consistency & Inconsistency:
A set of propositions is consistent if it is possible for all of them to be true at the same time. A set of propositions is inconsistent if they cannot all be true simultaneously (i.e., they lead to a contradiction). Example: The set {"It is raining", "It is not raining"} is inconsistent. The set {"It is raining", "The ground is wet"} is consistent.
3.Implication (Entailment / Logical Consequence):
A proposition Q is a logical consequence of P (denoted Pβ¨Q) if whenever P is true, Q must also be true. Example: P= "It is raining." Q= "The ground is wet." If P is true, then Q logically follows (assuming no weird circumstances).
4. Independence:
A proposition is independent of another if neither one logically determines the truth value of the other. Example: "It is raining" and "The stock market is up" are independent because knowing one does not tell us anything about the other.
5.Validity & Invalidity:
A proposition is valid if it is true in all possible interpretations (i.e., a tautology). A proposition is invalid if it is not true in all interpretations (i.e., it is either a contingency or a contradiction).
Validity is an important concept in logic because valid statements are universally true, meaning they hold regardless of the truth values of their components.
6.Satisfiability & Unsatisfiability:
A proposition is satisfiable if there is at least one interpretation where it is true (i.e., a tautology or a contingency). A proposition is unsatisfiable if it is false in all possible interpretations (i.e., a contradiction).
Logical Equivalences
Logical equivalences are statements in propositional logic that always have the same truth value regardless of the truth values of their individual components. If two propositions A and B are logically equivalent, we write:Aβ‘B. This means that for every possible truth assignment,A and B yield the same truth value. Logical equivalences form the foundation of propositional logic laws. Each law in Boolean algebra is a logical equivalence that helps us simplify, manipulate, or prove logical expressions. However, not all logical equivalences are laws. Some are specific derivations that are still true but are not considered "fundamental" enough to be named as laws. Logical equivalences are essential in mathematical logic, shaping both syntax and semantics. Syntactically, they allow transformations between logically identical formulas, crucial for normal forms like CNF and DNF. Semantically, they ensure truth preservation across interpretations, making them fundamental in truth tables and model theory. In proof techniques, equivalences justify valid transformations within formal systems, aiding in inferences and proof simplifications. By bridging truth conditions with formal derivations, logical equivalences unify reasoning in propositional logic, predicate logic, and beyond.
A proposition that is always true, no matter what. Example: pβ¨Β¬p ("Either it will rain or it wonβt"βthis is always true.) Validity and Tautologies A proposition is valid if it is true in all possible interpretationsβin other words, if it is a tautology. If a proposition is valid, it means there is no possible scenario where it is false.
pβ¨Β¬p (Law of the Excluded Middle) is valid because itβs always true.
2. Contradiction
A proposition that is always false, no matter what. Example: pβ§Β¬p ("It is raining and it is not raining"βthis is never true.) Unsatisfiability and Contradictions A proposition is unsatisfiable if it is false in every possible interpretationβwhich means it is a contradiction.
pβ§Β¬p is unsatisfiable because there is no way to make it true.
3. Contingency
A proposition that is sometimes true and sometimes false, depending on the values of its variables. Example: pβ¨q (If p is "It will rain" and q is "It will snow," this can be true or false depending on the weather.) Satisfiability and Contingencies A proposition is satisfiable if there is at least one interpretation where it is true.Otherwise it would be contradiction. A contingent proposition (one that is sometimes true and sometimes false) is always satisfiable because it has at least one true case.
pβ¨q is satisfiable because itβs true in cases where either p or q is true.
These three categories exhaust all possibilities for a proposition in classical logic. Every proposition must be one of these.