Propositional Logic: Notation and Vocabulary

Note: much of this was created with AI and hasn't been fully fact-checked yet. Find a substantial error and earn 1 ZEC!

Propositions

A proposition is a declarative sentence that can be either true or false, but not both. Propositions are typically represented by lowercase letters such as:

• $p,q,r,s,\dots$

Logical Connectives

Propositional logic involves combining propositions using logical connectives. Below are the common connectives:

Symbol	Name	Meaning	Example
$\neg$	Negation	"Not"	$\neg p$
$\wedge$	Conjunction	"And"	$p\wedge q$
$\vee$	Disjunction	"Or" (inclusive)	$p\vee q$
$\to$	Implication	"If...then..."	$p\to q$
$\leftrightarrow$	Biconditional	"If and only if"	$p\leftrightarrow q$

Truth Values

A truth value is the attribute assigned to a proposition:

• $T$ (True)
• $F$ (False)

Negation ($\neg$)

Negation reverses the truth value of a proposition. If $p$ is true, then $\neg p$ is false, and vice versa.

$p$	$\neg p$
$T$	$F$
$F$	$T$

Conjunction ($\wedge$)

Conjunction is true if both propositions are true. Otherwise, it is false.

$p$	$q$	$p\wedge q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Disjunction ($\vee$)

Disjunction is true if at least one proposition is true. It is only false if both are false.

$p$	$q$	$p\vee q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Implication ($\to$)

Implication is true unless the first proposition (the antecedent) is true and the second proposition (the consequent) is false.

$p$	$q$	$p\to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Vacuous Truth

The last 2 rows in the implication table can seem counter-intuitive. If $p$ is False, then it seems like we don't really know anything about the truth of $p\to q$?

• When $p$ is true and $q$ is true, $p\to q$ is true (this makes sense since both the antecedent and the consequent are true).
• When $p$ is true and $q$ is false, $p\to q$ is false (this captures the idea that $q$ must follow from $p$ if $p$ is true, and it doesn’t here).
• When $p$ is false, the implication $p\to q$ is always true, regardless of the truth value of $q$.

This last point is where it can feel counterintuitive.

Why is $p\to q$ true when $p$ is false?

In classical propositional logic, an implication $p\to q$ is defined to be true when the antecedent $p$ is false, regardless of the truth value of $q$. This is often called vacuous truth. The reasoning is as follows:

• If $p$ is false, the statement "If $p$, then $q$" doesn’t make any claim about $q$ because the condition $p$ wasn’t met.
• Therefore, the implication is considered true because it’s impossible to find a counterexample to the claim. Since the premise never holds, we don't care what happens with $q$.

This is a formal convention in classical logic, and it helps ensure that logical systems work as expected in various proofs and formal arguments.

Example:

Consider the statement "If the moon is made of cheese ($p$), then 2 + 2 = 5 ($q$)."

• The moon is not made of cheese ($p$ is false).
• It doesn't matter whether 2 + 2 equals 5 ($q$ can be true or false); the implication holds as true because the antecedent (the moon being made of cheese) is false.

Although it feels unintuitive that a false $p$ can make $p\to q$ true regardless of $q$, this is a standard convention in classical logic. The truth table provided is correct according to formal logic rules, even though it may clash with everyday reasoning.

Biconditional ($\leftrightarrow$)

A biconditional is a logical connective that represents the statement "if and only if." It expresses that both propositions must have the same truth value for the biconditional to be true. This means that:

• If $p$ is true, then $q$ must be true.
• If $p$ is false, then $q$ must be false.

In symbols, $p\leftrightarrow q$ is equivalent to saying:

• "$p$ if and only if $q$," or
• "$p$ is true if $q$ is true, and $p$ is false if $q$ is false."

The biconditional can be broken down into two implications:
$$
(p \leftrightarrow q) \equiv (p \rightarrow q) \land (q \rightarrow p)
$$
This reads as: "If $p$ implies $q$, and $q$ implies $p$, then $p$ and $q$ are logically equivalent."

Truth Table

$p$	$q$	$p\leftrightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

Intuition Behind Biconditional

A biconditional is true only when both propositions have the same truth value. This means that either both $p$ and $q$ are true, or both are false. If their truth values differ, the biconditional is false.

The phrase "if and only if" is key to understanding this connective. It ensures a two-way dependency:

• $p$ is true if $q$ is true.
• $p$ is false if $q$ is false.

Example for Clarity:

Consider the statement:

"You can go to the party if and only if you finish your homework."

This means:

• If you finish your homework (let $p$ represent this), then you can go to the party (let $q$ represent this).
• But also, if you go to the party, it implies you must have finished your homework.

Thus, $p\leftrightarrow q$ enforces a bi-directional implication.

Equivalence and Transformations

Biconditionals can be transformed using logical equivalences. Here’s a useful transformation:
$$
p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q
$$
This states that negating both sides of a biconditional preserves the equivalence. In other words, if $p$ is equivalent to $q$, then the negation of $p$ is also equivalent to the negation of $q$. This helps clarify that the relationship between the two propositions is symmetrical: if one is true, the other is true, and if one is false, the other is false.

Example of Negation Equivalence:

Suppose:

• $p$: "The sky is blue."
• $q$: "It is daytime."

We could say:

• $p\leftrightarrow q$: "The sky is blue if and only if it is daytime."

Now, apply the negation:

• $\neg p$: "The sky is not blue."
• $\neg q$: "It is not daytime."

Using the equivalence $p\leftrightarrow q\equiv \neg p\leftrightarrow \neg q$, we get:

• "The sky is not blue if and only if it is not daytime."

This reinforces the logical connection: if the sky isn’t blue, it must not be daytime, and vice versa.

Visual Representation (Intuition Aid)

One way to think about the biconditional is to visualize it as a mirror:

• Whatever happens on one side of the mirror must be reflected on the other side.
• If $p$ is true, $q$ must reflect that and be true as well. If $p$ is false, $q$ must reflect that falsity.

Important Biconditional Properties:

1. Symmetry:
   • $p\leftrightarrow q$ is the same as $q\leftrightarrow p$.
2. Self-biconditional:
   • Any proposition $p\leftrightarrow p$ is always true (because a proposition is always equivalent to itself).
3. Equivalence with Implications:
   • $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$ shows that a biconditional is essentially two implications bundled together.

Truth Tables

Truth tables systematically show the truth values of propositions and their logical combinations. For example, the truth table for $p\to q$:

$p$	$q$	$p\to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Tautology

A tautology is a proposition that is always true, regardless of the truth values of the individual propositions.

• Example: $p\vee \neg p$ (A proposition is either true or its negation is true).

Contradiction

A contradiction is a proposition that is always false.

• Example: $p\wedge \neg p$ (A proposition cannot be both true and false simultaneously).

Logical Equivalence

Two propositions are logically equivalent if they always have the same truth value. This is denoted as:
$$
p \equiv q
$$
Example: $p\to q\equiv \neg p\vee q$ (Implication is equivalent to "not p or q").

Common Logical Laws

These laws describe common transformations in propositional logic.

• Commutative Laws:

  • $p\wedge q\equiv q\wedge p$
  • $p\vee q\equiv q\vee p$

• Associative Laws:

  • $$ (p \land (q \land r)) \equiv ((p \land q) \land r) $$
  • $$ (p \lor (q \lor r)) \equiv ((p \lor q) \lor r) $$

• Distributive Laws:

  • $$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$
  • $$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$

• De Morgan’s Laws:

  • $$ \neg (p \land q) \equiv \neg p \lor \neg q $$
  • $$ \neg (p \lor q) \equiv \neg p \land \neg q $$

• Double Negation Law:

  • $$ \neg (\neg p) \equiv p $$

• Implication Law:

  • $$ p \rightarrow q \equiv \neg p \lor q $$

Inference Rules

Inference rules are used to derive conclusions from premises.

• Modus Ponens (Direct inference):
  • If $p\to q$ and $p$, then $q$.

• Modus Tollens:
  • If $p\to q$ and $\neg q$, then $\neg p$.

• Disjunction Introduction:
  • If $p$, then $p\vee q$.

• Conjunction Introduction:
  • If $p$ and $q$, then $p\wedge q$.

Conclusion

Propositional logic is a formal system used to analyze logical relationships between propositions. It forms the basis for more advanced logics and is widely applied in fields like mathematics, computer science, and philosophy. The above notation and vocabulary capture its essential elements.