Propositional Logic (Entailment, Equivalence, and Normal Forms)
Logical Entailment (β¨): A formula π entails a formula π (π β¨ π) if, in every case where π is true, π is also true. It indicates a logical implication from π to π. For example, if π is p β§ q, and π is p, then π entails π because if both p and q are true, then p is certainly true.
Entailment: Concerns the logical relationship between formulas, focusing on whether the truth of one guarantees the truth of another.
Satisfaction: A formula is satisfied if there is some assignment of truth values to its variables that makes the formula true. Satisfaction relates to specific interpretations rather than the logical structure between propositions.
Logical Equivalence: Two formulas π and π are logically equivalent if, in every possible interpretation, they have the same truth value. This is denoted as π β‘ π. For instance, p β¨ q is logically equivalent to Β¬p β q.
Substitution Theorem: If a formula π is logically equivalent to a formula π, then substituting π for π in any larger formula does not change the truth value of the larger formula. For example, if π β‘ π, then any occurrence of π in a formula π can be replaced with π without changing the truth value of π.
Special Equivalences: Certain equivalences are recognized for their utility in simplifying formulas, such as p β¨ Β¬p is a tautology and p β§ Β¬p is a contradiction.
Logical Biconditional (β): Represents equivalence in propositional logic. p β q is true if p and q have the same truth values.
Simplification: The process of using logical equivalences to rewrite formulas in a simpler or more canonical form. For example, using De Morgan's Laws to simplify Β¬(p β¨ q) to Β¬p β§ Β¬q.
Normal Form: A way of writing formulas in a standardized or canonical form.
Conjunctive Normal Form (CNF): A conjunction of disjunctions of literals (e.g., (p β¨ q) β§ (Β¬r)).
Disjunctive Normal Form (DNF): A disjunction of conjunctions of literals (e.g., (p β§ q) β¨ (Β¬r)).
Canonical Normal Forms: Specific types of normal forms where every possible variable or its negation appears in each clause. They are useful for algorithmic treatment of logical formulas, especially in automated theorem proving.
Functional Completeness: A set of logical operators is functionally complete if any logical expression can be expressed using just those operators. For example, the set {Β¬, β§} is functionally complete because any logical operation can be constructed from these two operations.
Boolean Algebra: A branch of algebra that deals with boolean values (true and false). It includes laws such as the law of identity (p β§ True β‘ p), the law of domination (p β¨ False β‘ p), and the law of double negation (Β¬(Β¬p) β‘ p).
Important Identities: Include laws like the idempotent law (p β¨ p β‘ p), the negation law (p β¨ Β¬p β‘ True), and the domination law (p β§ True β‘ p).