Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 68 · Logic

Propositional Logic

Learn propositions, truth values, the connectives AND, OR and NOT, how to build compound statements, operator precedence and how to evaluate them in Python.

Logic is the grammar of precise thinking, and every if statement you write is a small piece of it. Propositional logic is the simplest layer: it studies statements that are either true or false, and the ways of combining them with words like "and", "or" and "not". It is the foundation for proofs, for digital circuits, for database queries and for the SAT solvers that check huge software configurations.

In this lesson you will learn what counts as a proposition, how the basic connectives behave, how to read a compound statement, and how to evaluate one in Python. The next lessons add implication, truth tables and equivalences.

What is a proposition?

A proposition is a declarative statement that is definitely true or definitely false. It does not matter whether you know which one.

  • "7 is a prime number." is a proposition (true).
  • "10 is less than 4." is a proposition (false).
  • "Every even number greater than 2 is the sum of two primes." is a proposition, even though nobody has proved or refuted it. It is one or the other.

These are not propositions:

  • "What time is it?" (a question)
  • "Close the door." (a command)
  • "x + 1 = 5" (true for x = 4 and false otherwise, so it has no single truth value until x is given; it is a predicate, covered in Predicates and Quantifiers)
  • "This sentence is false." (it cannot consistently be either)

By convention we name propositions with letters such as p, q and r. In Python, a proposition is simply a variable holding True or False.

The three basic connectives

Negation (NOT). The negation of p, written ¬p, is true exactly when p is false.

Conjunction (AND). The statement p ∧ q is true only when both p and q are true.

Disjunction (OR). The statement p ∨ q is true when at least one of p and q is true. This is the inclusive or: if both are true, the whole thing is still true. English "or" is often exclusive ("soup or salad"), so watch out when translating a sentence.

p q ¬p p ∧ q p ∨ q
T T F T T
T F F F T
F T T F T
F F T F F

Python's not, and and or implement exactly these rules.

Python The three connectives

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A subtle point: Python's and and or are short-circuiting. In p and q, if p is false, Python never looks at q. This is harmless for pure true/false values but matters when q has side effects or can raise an error, as in x != 0 and 10 / x > 1. In pure logic there are no side effects, so the order of operands never changes the answer.

Exclusive or

A fourth connective shows up often enough to deserve a name. The exclusive or (XOR), written p ⊕ q, is true when exactly one of p and q is true. It differs from inclusive or only in the row where both are true. Python has no xor keyword for booleans, but != between two booleans works, and so does the ^ operator.

Python Inclusive versus exclusive or

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The only difference is the first row: with both inputs true, or gives True and xor gives False.

Compound statements and precedence

Combining connectives gives a compound proposition, such as (p ∧ q) ∨ ¬r. To evaluate one, you substitute truth values for the letters and work from the inside outward.

Without parentheses, the usual convention is the same as in Python:

  1. not (¬) binds tightest,
  2. then and (∧),
  3. then or (∨).

So not p or q and r means (not p) or (q and r). When in doubt, add parentheses; they cost nothing and spare the reader a guess.

Evaluate step by step

Substitute Replace each letter by True or False.
Innermost first Handle parentheses, then NOT.
Then AND AND binds tighter than OR.
Finally OR Combine what is left.

When unsure, add parentheses.

1 / 2

Let us translate an English sentence. "You may enter if you have a ticket and are over 12, or if you are staff." With t for "has a ticket", o for "over 12" and s for "is staff", the rule is (t ∧ o) ∨ s. Notice that here the parentheses are not optional in the English reading, though the precedence rules happen to agree.

Python A rule as a compound proposition

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last three lines print True, True and False. The first two expressions agree because that is how precedence groups the first one. The third, with parentheses placed differently, is a different formula and gives a different answer.

Translating English carefully

Natural language hides ambiguity. A few translation rules help:

  • "p but q" means p ∧ q. The word "but" adds contrast, not logic.
  • "neither p nor q" means ¬p ∧ ¬q, which equals ¬(p ∨ q).
  • "p unless q" is usually read as ¬q → p; implication is the subject of the next lesson.
  • "at least one of" means OR; "exactly one of" means XOR (for two statements); "both" means AND.

Bit-level operators in Python (&, |, ~) look similar, but they act on integers bit by bit. On booleans, & and | work, but ~True is -2, not False. Use not for logic and keep ~ for bit manipulation, as described in the Python lesson on bitwise operators.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which of these is a proposition?

    '12 is divisible by 5' is a declarative statement that is false, so it is a proposition. Questions and commands have no truth value, and a statement with a free variable x is a predicate.
  2. 2. If p is true and q is false, what is (not p) or q?

    not p is false and q is false, so false or false is false.
  3. 3. How does Python parse 'not a or b and c'?

    not binds tighter than and, and and binds tighter than or, giving (not a) or (b and c).
  4. 4. For which inputs do inclusive or and exclusive or differ?

    XOR is false when both inputs are true, while inclusive OR is true there. In every other row they agree.

Summary

  • A proposition is a statement that is definitely true or false; questions, commands and statements with free variables are not propositions.
  • NOT, AND and OR are defined by small truth tables; Python's not, and, or implement them.
  • OR in logic is inclusive; XOR is true when exactly one input is true.
  • Precedence is NOT, then AND, then OR; parentheses make intent clear.
  • Translate English carefully: "but" is AND, "neither/nor" is NOT-OR, and "unless" involves implication.

Next: Implication and Biconditional, the connectives behind "if ... then".