Propositional Logic Fundamentals

Unit 5: Introduction to Logic in AI — Section 5.2

You probably already know that computers ultimately work in 1s and 0s — on and off, true and false. Propositional logic is the mathematical language that describes how those true/false values combine into decisions. Every if statement in a program, every filter in a database query, and every rule in an expert system is an expression of propositional logic.

Learn the foundations of propositional logic and logical operators.

Propositional Logic Basics

What Is a Proposition?

Recall from Section 5.1 that a proposition is a declarative statement with a definite truth value — either true (T) or false (F), and nothing in between.

In propositional logic, we represent atomic propositions with propositional variables, usually capital letters like P, Q, R, or descriptive abbreviations like Rain, Wet, Cold. A propositional variable stands in for a simple fact about the world.

Propositions and their variables:

P = "It is raining" (true or false depending on the weather)
Q = "The door is locked" (true or false depending on the door’s state)
R = "The patient has a fever" (true or false depending on the patient’s temperature)

None of these is more or less a proposition than the others — they all have definite truth values once we specify a situation.

Atomic propositions on their own are only marginally useful. The power of propositional logic comes from combining atoms into compound formulas using logical connectives.

The Five Logical Connectives

Propositional logic defines five fundamental connectives. Each takes one or two propositions and produces a new proposition.

Negation (¬)

Negation flips a truth value. If P is true, then ¬P is false. If P is false, then ¬P is true.

Negation (¬): The connective that inverts the truth value of a proposition. Written ¬P (also written ~P or NOT P). True when P is false; false when P is true. Read as "not P" or "it is not the case that P."

P	¬P
T	F
F	T

¬P

Conjunction (∧)

Conjunction represents "and." A conjunction is true only when both component propositions are true.

Conjunction (∧): The "and" connective. Written P ∧ Q. True only when both P and Q are true; false in all other cases. Read as "P and Q" or "P conjunction Q."

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

P ∧ Q

Disjunction (∨)

Disjunction represents "or." In logic, "or" is inclusive: a disjunction is true when at least one side is true — including the case where both are true.

Disjunction (∨): The "or" connective. Written P ∨ Q. True when at least one of P or Q is true (inclusive-or). False only when both P and Q are false. Read as "P or Q."

P	Q	P ∨ Q
T	T	T
T	F	T
F	T	T
F	F	F

P ∨ Q

English "or" is often exclusive in everyday speech. "Do you want coffee or tea?" typically implies you can pick only one. But in propositional logic, ∨ is always inclusive unless you explicitly add a "not both" clause: (P ∨ Q) ∧ ¬(P ∧ Q).

Conditional (→)

The conditional expresses an "if…then" relationship. P → Q says "if P is true, then Q must also be true."

Conditional (→): The "if…then" connective, also called material implication. Written P → Q, read as "P implies Q," "if P then Q," or "P only if Q." P is the antecedent (premise); Q is the consequent (conclusion). The conditional is false only when P is true and Q is false — that is, only when the premise holds but the conclusion fails.

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

P → Q

Many students find the last two rows surprising. Why is "If it rains, the ground is wet" considered true on a dry, sunny day? Because the statement makes a conditional promise: when it rains, the ground will be wet. A dry day puts no constraint on the formula — the promise was never put to the test. A conditional is falsified only by a counterexample: rain without wet ground.

The rainy-day test for implication:

Rule: "If it rains (P), then the ground is wet (Q)." — P → Q

| Situation | P | Q | P → Q | Why | |---|---|---|---|---| | It rains, ground is wet | T | T | T | Promise kept | | It rains, ground is dry | T | F | F | Promise broken | | No rain, ground is wet | F | T | T | Sprinkler ran; rule not violated | | No rain, ground is dry | F | F | T | Dry day; rule not violated |

The only way to falsify a conditional is to have the premise true and the conclusion false (row 2).

Biconditional (↔)

The biconditional expresses "if and only if." It is true when both sides have the same truth value — both true, or both false.

Biconditional (↔): The "if and only if" connective. Written P ↔ Q, read as "P if and only if Q" or "P iff Q." True when P and Q have the same truth value; false when they differ. Equivalent to (P → Q) ∧ (Q → P).

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	T

P ↔ Q

Syntax vs. Semantics

Propositional logic has both a syntax (the rules for forming legal formulas) and semantics (the rules for evaluating truth values). These are separate concerns.

Syntax: The formal grammar that specifies which strings of symbols are well-formed formulas (WFFs). Syntax is purely structural — it does not assign meaning. The string P ∧ ∧ Q is syntactically invalid; P ∧ Q is valid.
Semantics: The rules that assign a truth value to a formula given a truth assignment for its atomic variables. Semantics gives meaning to the syntax. Given P = T and Q = F, the semantics says P ∧ Q is F.

A truth assignment (or valuation) specifies a truth value for each propositional variable. The semantics of each connective tells us how to compute the truth value of a compound formula from the truth values of its parts.

Building Complex Formulas

Real logical statements combine multiple connectives. When reading a compound formula, we evaluate it like an arithmetic expression — inner parts first, then outer parts.

Evaluating a compound formula:

Formula: ¬P ∨ (Q ∧ R)

Given: P = T, Q = T, R = F

Step 1: Evaluate Q ∧ R: T ∧ F = F

Step 2: Evaluate ¬P: ¬T = F

Step 3: Evaluate F ∨ F = F

Result: The formula is false under this assignment.

Operator Precedence

When parentheses are omitted, operators are evaluated in this order (highest precedence first):

Operator	Precedence
¬	Highest — applied to the immediately following atom or parenthesized expression
∧	Second
∨	Third
→	Fourth
↔	Lowest

Operator

Precedence

Highest — applied to the immediately following atom or parenthesized expression

∧

Second

∨

Third

→

Fourth

↔

Lowest

So ¬P ∨ Q ∧ R means (¬P) ∨ (Q ∧ R), not ¬(P ∨ Q) ∧ R. In practice, use parentheses freely — they make intent explicit and prevent mistakes.

Truth Tables

A truth table systematically lists every possible truth assignment for a formula’s variables and the formula’s truth value under each assignment. With n distinct variables, a truth table has 2ⁿ rows.

Truth Table: A table that lists every possible combination of truth values for the propositional variables in a formula, along with the formula’s truth value for each combination. A formula with 2 variables has 4 rows (2²); with 3 variables, 8 rows (2³). Truth tables are used to verify logical equivalences, identify tautologies and contradictions, and evaluate formulas exhaustively.

Truth table for (P ∧ Q) → R:

P	Q	R	P ∧ Q	(P ∧ Q) → R
T	T	T	T	T
T	T	F	T	F
T	F	T	F	T
T	F	F	F	T
F	T	T	F	T
F	T	F	F	T
F	F	T	F	T
F	F	F	F	T

P ∧ Q

(P ∧ Q) → R

Reading the table: The formula is false only in row 2 — when P and Q are both true but R is false. In all other cases, either the premise (P ∧ Q) is false (so the conditional is vacuously true), or R is true (so the conditional holds).

Translating English Statements

Translating an English sentence to propositional logic:

English: "If you study hard and attend all classes, then you will pass."

Name the atoms:
- S = "You study hard"
- A = "You attend all classes"
- P = "You will pass"
Identify the structure:
- "If [condition], then [result]" → use →
- "study hard AND attend all classes" → use ∧ for the antecedent
Build the formula:
- (S ∧ A) → P
Verify: The formula says passing is guaranteed when both conditions are met. It says nothing about what happens if you study without attending, or attend without studying. That matches the original intent.

Practice identifying propositions and applying the five connectives.

Next: 5.3 Logical Equivalences and Validity →

Adapted from forall x: Calgary by P.D. Magnus et al., licensed under CC BY 4.0.

This work is licensed under CC BY-SA 4.0.