Skip to content

Propositional Logic

Propositional logic is a branch of logic that deals with propositions (statements that are either true or false) and the relationships between them.

Basic Elements

  1. Proposition: A statement that is either true or false.

  2. Example: "It is raining."

  3. Variable: A symbol that represents a proposition.

  4. Example: P, Q, R

Logical Operators

  1. NOT (\(\lnot\)): Negation

  2. \(\lnot P\) is true if \(P\) is false.

  3. AND (\(\land\)): Conjunction

  4. \(P \land Q\) is true if both P and Q are true.

  5. OR (\(\lor\)): Disjunction

  6. \(P \lor Q\) is true if either \(P\) or \(Q\) is true.

  7. IMPLIES (\(\rightarrow\)): Implication

  8. \(P \rightarrow Q\) is true unless \(P\) is true and \(Q\) is false.

  9. IFF (\(\leftrightarrow\)): Bi-conditional

  10. \(P \leftrightarrow Q\) is true if \(P\) and \(Q\) have the same truth value.

Compound Propositions

  • Formed by combining simple propositions using logical operators.
  • Example: \((P \land Q) \lor \lnot R\)

Truth Tables

  • A table that lists all possible truth values of a compound proposition.

Logical Equivalence

  • Two propositions are logically equivalent if they have the same truth values in their truth tables.

Tautology and Contradiction

  • Tautology: A proposition that is always true.
  • Contradiction: A proposition that is always false.

Logical Inference

  • The process of deriving new propositions from existing ones.

Rules of Inference

  • Commonly used patterns of reasoning.
  • Example: Modus Ponens, Modus Tollens

Quantifiers (in Predicate Logic)

  • Universal Quantifier (\(\forall\)): "For all"
  • Existential Quantifier (\(\exists\)): "There exists"