1: Propositional logic

Section 1: Logic - 1: Propositional Logic

Propositional logic (also called sentential logic) forms the bedrock of formal reasoning. It focuses on the truth values (True or False) of declarative statements called propositions and how these values change when propositions are combined using logical connectives.

Propositions and Symbols

• A proposition is a statement that is definitively true (T) or false (F). Examples: "2 + 2 = 4" (T), "Paris is the capital of Mars" (F).
• Simple propositions are represented by propositional variables, typically lowercase letters like $p$, $q$, $r$.

Logical Connectives

These operators build complex propositions (compound propositions) from simpler ones:

1. Negation ($\neg$, ~): "Not $p$". Reverses the truth value. If $p$ is T, $\neg p$ is F; if $p$ is F, $\neg p$ is T.
2. Conjunction ($\land$): "$p$ and $q$". True only if both $p$ and $q$ are true.
3. Disjunction ($\lor$): "$p$ or $q$". True if at least one of $p$ or $q$ is true (This is the inclusive "or").
4. Implication ($\rightarrow$): "If $p$, then $q$". False only when $p$ is true and $q$ is false. (True otherwise, including when $p$ is false). $p$ is the antecedent, $q$ is the consequent.
5. Biconditional ($\leftrightarrow$): "$p$ if and only if $q$". True only when $p$ and $q$ have the same truth value.

Truth Tables

Truth tables systematically list all possible combinations of truth values for the propositional variables in a compound proposition and show the resulting truth value of the whole proposition. They are the primary tool for defining connectives and analyzing propositions.

• Example for Implication ($p \rightarrow q$):

  $p$	$q$	$p \rightarrow q$
  T	T	T
  T	F	F
  F	T	T
  F	F	T

Key Concepts Defined by Truth Tables

• Tautology: A compound proposition that is always true for all possible truth values of its variables (e.g., $p \lor \neg p$).
• Contradiction: A compound proposition that is always false for all possible truth values (e.g., $p \land \neg p$).
• Contingency: A proposition that is neither a tautology nor a contradiction; its truth value depends on its variables.

Logical Equivalence

Two compound propositions $P$ and $Q$ are logically equivalent ($P \equiv Q$) if they have identical truth tables – they produce the same truth value for every possible combination of truth values of their component variables. Crucial equivalences include:

• Double Negation: $\neg(\neg p) \equiv p$
• De Morgan's Laws:
  • $\neg(p \land q) \equiv \neg p \lor \neg q$
  • $\neg(p \lor q) \equiv \neg p \land \neg q$
• Implication Equivalence: $p \rightarrow q \equiv \neg p \lor q$
• Contrapositive: $p \rightarrow q \equiv \neg q \rightarrow \neg p$

Understanding propositional logic, its connectives, and how to use truth tables to analyze truth values and equivalences is fundamental for constructing and understanding logical arguments, proofs, and further topics in discrete mathematics.