Propositional Logic

Propositional logic, also known as sentential logic or statement logic, is the branch of logic that studies ways of combining or altering statements or propositions to form more complicated statements or propositions. It is the most basic level of formal logic and serves as the foundation for all mathematical reasoning.

Propositions

A proposition is a declarative sentence that is either true or false, but not both. In mathematics, we often represent propositions using lowercase letters like $p,q,r,s$.

Examples of propositions:

• “The square root of 2 is irrational.” (True)
• “7 is an even number.” (False)
• ”$\pi >3$.” (True)

Examples that are NOT propositions:

• “What time is it?” (Question)
• “Read this carefully.” (Command)
• ”$x+1=2$.” (This is an open sentence, as its truth depends on the value of $x$. In predicate logic, we will handle this using quantifiers.)

Logical Connectives

We use logical connectives to build complex statements from simpler ones. The primary connectives are:

1. Negation ($\neg$): The negation of $p$ is $\neg p$ (read as “not $p$”). If $p$ is True, $\neg p$ is False.
2. Conjunction ($\wedge$): The conjunction of $p$ and $q$ is $p\wedge q$ (read as ”$p$ and $q$”). It is true only if both are true.
3. Disjunction ($\vee$): The disjunction of $p$ and $q$ is $p\vee q$ (read as ”$p$ or $q$”). It is true if at least one is true. This is the “inclusive or.”
4. Exclusive Or ($\oplus$): $p\oplus q$ is true if exactly one of $p$ or $q$ is true.
5. Implication ($\to$): The conditional statement $p\to q$ (read as “if $p$, then $q$”). It is false only when $p$ is true and $q$ is false.
6. Biconditional ($\leftrightarrow$): $p\leftrightarrow q$ (read as ”$p$ if and only if $q$”) is true when $p$ and $q$ have the same truth value.

Truth Tables

Truth tables are a fundamental tool for defining connectives and analyzing the possible truth values of complex statements.

Logical Equivalences

Two statements are logically equivalent if they have the same truth values in all possible cases. We denote equivalence as $P\equiv Q$.

Some important equivalences:

• De Morgan’s Laws:
  • $\neg (p\wedge q)\equiv \neg p\vee \neg q$
  • $\neg (p\vee q)\equiv \neg p\wedge \neg q$
• Distributive Laws:
  • $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$
  • $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$
• Contrapositive:
  • $p\to q\equiv \neg q\to \neg p$

The contrapositive is particularly important in mathematical proofs. If you want to prove “If $n^2$ is even, then $n$ is even,” it is often easier to prove the contrapositive: “If $n$ is odd, then $n^2$ is odd.”

Tautologies and Contradictions

• A tautology is a statement that is always true (e.g., $p\vee \neg p$).
• A contradiction is a statement that is always false (e.g., $p\wedge \neg p$).
• A contingency is a statement that is neither a tautology nor a contradiction.

Applications and Formal Systems

Propositional logic forms the backbone of digital circuit design (Boolean algebra is its algebraic counterpart) and computer programming. In “pure” mathematics, it is the metalanguage we use to define the rules of inference.

A formal system of propositional logic consists of a set of symbols (atoms and connectives), rules for forming well-formed formulas (WFFs), and rules of inference (like Modus Ponens: from $p$ and $p\to q$, infer $q$).

Exercise

Understanding these foundations is critical before moving into Predicate Logic, where we introduce variables and quantifiers, allowing us to make statements about sets of objects.