Neural Sync Active

Propositional Logic

Registry Synced

Propositional Logic

1269 words

6 min read

Reading compass

Now · 🎯 Learning Objectives

Propositional Logic

🎯 Learning Objectives

Identify propositions and their truth values
Use logical connectives: $\land$ , $\lor$ , $\neg$ , $\to$ , $\leftrightarrow$
Construct and interpret truth tables
Determine tautologies, contradictions, and contingencies
Prove logical equivalence using truth tables and algebraic manipulation

1.1 Intuition: The Language of Mathematical Reasoning

Logic is the grammar of mathematics. Just as grammar rules tell us which sentences are well-formed, logic rules tell us which arguments are valid. Propositional logic is the simplest form — it deals with whole statements that are either true or false.

🔑 Key Insight: The truth of a compound statement depends ONLY on the truth values of its parts, not on their meaning.

1.2 Propositions

A proposition (or statement) is a declarative sentence that is either true or false — but not both.

Example	Proposition?	Truth Value
"The sky is blue."	Yes	True
"2 + 2 = 5."	Yes	False
"Please sit down."	No (imperative)	—
"This statement is false."	No (paradox)	—
" $x > 5$ "	No (open sentence)	Depends on $x$

Atomic vs. Compound Propositions

Type	Definition	Example
Atomic	Cannot be broken down further	"It is raining."
Compound	Built from atomic propositions using connectives	"It is raining AND it is cold."

1.3 Logical Connectives

Name	Symbol	Read As	Meaning
Negation	$\neg p$	"not $p$ "	Opposite truth value
Conjunction	$p \land q$	" $p$ and $q$ "	True iff both true
Disjunction	$p \lor q$	" $p$ or $q$ "	True iff at least one true (inclusive)
Conditional	$p \to q$	"if $p$ then $q$ "	False only when $p$ true and $q$ false
Biconditional	$p \leftrightarrow q$	" $p$ iff $q$ "	True when $p$ and $q$ have same truth value

Truth Tables

\begin{array}{c|c||c|c|c|c|c} p & q & \neg p & p \land q & p \lor q & p \to q & p \leftrightarrow q \\ \hline T & T & F & T & T & T & T \\ T & F & F & F & T & F & F \\ F & T & T & F & T & T & F \\ F & F & T & F & F & T & T \end{array}

Tricky Case: Implication ( $p \to q$ )

The implication "if

p

then

q

" is vacuously true when

p

is false. This often confuses beginners. Example: "If it rains (

p

), then I'll take an umbrella (

q

)."

It rains and I take umbrella: $T \to T = T$ (kept promise)
It rains and I don't take umbrella: $T \to F = F$ (broke promise)
No rain and I take umbrella: $F \to T = T$ (still true — didn't break anything)
No rain and I don't take umbrella: $F \to F = T$ (also true)

1.4 Tautologies, Contradictions, Contingencies

Type	Definition	Example
Tautology	Always true	$p \lor \neg p$ (law of excluded middle)
Contradiction	Always false	$p \land \neg p$
Contingency	Neither	$p \land q$

Proving a Tautology

To show

p \lor \neg p

is a tautology:

\begin{array}{c|c|c} p & \neg p & p \lor \neg p \\ \hline T & F & T \\ F & T & T \end{array}

All entries in the result column are

T

→ it's a tautology.

1.5 Logical Equivalence

Two statements are logically equivalent (

\equiv

) if they have the same truth value for all assignments.

De Morgan's Laws

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

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

Proof by truth table:

\begin{array}{c|c|c|c|c|c|c} p & q & \neg(p \land q) & \neg p \lor \neg q & \neg(p \lor q) & \neg p \land \neg q \\ \hline T & T & F & F & F & F \\ T & F & T & T & F & F \\ F & T & T & T & F & F \\ F & F & T & T & T & T \end{array}

Columns 3=4 and 5=6, proving both equivalences.

Other Key Equivalences

Name	Law
Commutativity	$p \land q \equiv q \land p$ ; $p \lor q \equiv q \lor p$
Associativity	$(p \land q) \land r \equiv p \land (q \land r)$
Distributivity	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
Identity	$p \land T \equiv p$ ; $p \lor F \equiv p$
Domination	$p \lor T \equiv T$ ; $p \land F \equiv F$
Double negation	$\neg(\neg p) \equiv p$
Implication	$p \to q \equiv \neg p \lor q$
Contrapositive	$p \to q \equiv \neg q \to \neg p$
Biconditional	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

For

p \to q

Name	Form	Example
Original	$p \to q$	If it rains, I'll take umbrella
Converse	$q \to p$	If I take umbrella, it rains
Inverse	$\neg p \to \neg q$	If no rain, I won't take umbrella
Contrapositive	$\neg q \to \neg p$	If no umbrella, no rain

Important: Original and contrapositive are logically equivalent. Converse and inverse are not equivalent to the original.

📊 Formula Summary

Equivalence	Rule
Implication	$p \to q \equiv \neg p \lor q$
Contrapositive	$p \to q \equiv \neg q \to \neg p$
De Morgan (AND)	$\neg(p \land q) \equiv \neg p \lor \neg q$
De Morgan (OR)	$\neg(p \lor q) \equiv \neg p \land \neg q$
Distributive	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

✅ Practice Questions

Q1: Is

(p \to q) \land (q \to r) \to (p \to r)

a tautology?

Solution

This is hypothetical syllogism, a famous tautology. Proof: construct truth table. The only way to make it false would require $p \to q$ true, $q \to r$ true, and $p \to r$ false. $p \to r$ false requires $p=T, r=F$ . Then $p \to q$ true with $p=T$ requires $q=T$ . Then $q \to r$ with $q=T, r=F$ gives $F$ . Contradiction. So it's always true. Q2: Prove $\neg(p \to q) \equiv p \land \neg q$ . Solution

$p \to q \equiv \neg p \lor q$ , so $\neg(p \to q) \equiv \neg(\neg p \lor q) \equiv p \land \neg q$ (by De Morgan and double negation). Q3: Write the contrapositive of: "If a number is divisible by 6, then it is divisible by 2 and 3." Solution

Contrapositive: "If a number is NOT divisible by 2 OR NOT divisible by 3, then it is NOT divisible by 6." Q4: Use truth tables to prove $p \to (q \to r) \equiv (p \land q) \to r$ . Solution

> \begin{array}{c|c|c|c|c|c} p & q & r & q \to r & p \to (q \to r) & p \land q & (p \land q) \to r \\ \hline T & T & T & T & T & T & T \\ T & T & F & F & F & T & F \\ T & F & T & T & T & F & T \\ T & F & F & T & T & F & T \\ F & T & T & T & T & F & T \\ F & T & F & F & T & F & T \\ F & F & T & T & T & F & T \\ F & F & F & T & T & F & T \end{array} >

Columns 5 and 7 match exactly. Q5: Simplify $\neg(p \lor \neg q)$ . Solution

$\neg(p \lor \neg q) \equiv \neg p \land \neg(\neg q) \equiv \neg p \land q$ Join Discord NextPredicate Logic