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 𝜓.

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. It 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. Denoted as 𝜙 ≡ 𝜓.

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.

Special Equivalences

Recognized equivalences for simplifying formulas, like p ∨ ¬p as a tautology and p ∧ ¬p as 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.

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, useful for algorithmic treatment of logical formulas.

Functional Completeness

A set of logical operators is functionally complete if any logical expression can be expressed using just those operators.

Boolean Algebra

A branch of algebra dealing with boolean values (true and false) and including laws like the law of identity, law of domination, and law of double negation.

Important Identities

Include laws like the idempotent law, negation law, and domination law in Boolean Algebra.