Back to Logic Hub
[ MODULE 01 ]

PROPOSITIONAL LOGIC

Before we can build complex mathematics or computer programs, we have to define the absolute ground floor of reality. We must define what it means for a statement to be True or False.

The Atomic Proposition

A proposition is simply a declarative statement that is exactly one of two things: True or False. It cannot be both, and it cannot be neither.

Valid Propositions
  • ▶ "Paris is the capital of France." (T)
  • ▶ "The earth is flat." (F)
  • ▶ "2 + 2 = 5." (F)
Not Propositions
  • ▶ "What time is it?" (Question)
  • ▶ "Read this book." (Command)
  • ▶ "This sentence is false." (Paradox)

By assigning these statements variable names like P and Q, we can stop worrying about what the sentences actually mean, and start calculating their structural truth.

[ INTERACTIVE LAB ]
The Universal Truth Table
Select a row to isolate
PQP∧QP \land Q ANDP∨QP \lor Q ORP  ⟹  QP \implies Q IMPLIESP  ⟺  QP \iff Q XNOR (IFF)
T
T
T
T
T
T
T
F
F
T
F
F
F
T
F
T
T
F
F
F
F
F
T
T

State 1 (T, T): The only universe where AND evaluates to True. Because P and Q match, the Biconditional (IFF) is also True.

Logical Equivalence

Just like in algebra where x + y is equivalent to y + x, logical statements can be manipulated and simplified without changing their ultimate truth value. When two statements output the exact same Truth Table, they are logically equivalent (≡).

De Morgan's Laws

Augustus De Morgan formalized two rules that are arguably the most important transformation tools in all of computer science. They describe how to distribute a NOT (¬) operator inside a parenthesis.

Law 1: Negating an AND

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

"If it is NOT true that (I have an Apple AND a Banana), then I must NOT have an Apple, OR I must NOT have a Banana."

Law 2: Negating an OR

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

"If it is NOT true that (I am walking OR I am running), then I am NOT walking, AND I am NOT running."

Notice the beautiful symmetry: When you distribute a negation, the ∧ flips to an ∨, and vice versa.

[ MODULE VERIFICATION ]
Knowledge Check: Propositional Logic1 / 4

Which of the following statements is a valid proposition?

Return to Logic HubNext: First-Order Logic