Proving Logic Laws with 0s and 1s

A light switch has two positions#

A light switch is either off or on. Call off 0 and call on 1. Nothing else is possible.

A statement in logic is the same. It is either false or true. So write false as 0 and true as 1. Your professor does this in the truth tables already, instead of writing T and F.

Here is the payoff. Once truth values are numbers, you can do arithmetic with them. “Not”, “and”, “or” and “if…then” each turn into a short formula. Then a logic law becomes an algebra identity, and you can prove it by multiplying out, the same way you check (a + b)² = a² + 2ab + b².

A connective is just a word that joins statements: not, and, or, if…then. That is all the jargon you need for this page.

The translation table#

Each row says what a connective becomes. The last column is how to say the symbol out loud.

You do not need to memorize six formulas. You need the first three. The rest can be built from them, and the next section shows why each one is right.

Why each formula works#

Not. Negation swaps 0 and 1. The expression 1 − p does exactly that: 1 − 0 = 1 and 1 − 1 = 0.

And. p ∧ q is true only when both are true. A product of 0s and 1s is 1 only when every factor is 1. So pq is the conjunction. (A conjunction is an “and” statement.)

Or. Adding p + q counts how many are true. That count can be 0, 1 or 2, but a truth value must be 0 or 1. The only bad row is p = q = 1, where the sum is 2. Subtracting pq fixes exactly that row, because pq is 1 there and 0 everywhere else.

If…then. A conditional is false in one row only: p = 1 and q = 0. The expression p(1 − q) is 1 in that row and 0 in the others, so 1 − p(1 − q) is the conditional. Multiply it out and you get 1 − p + pq.

Exclusive or. Start from p + q again. In the both-true row it gives 2, but exclusive or wants 0 there. Subtract 2pq instead of pq, and that row drops all the way to 0.

The one extra rule: p² = p#

Ordinary algebra has one rule that 0/1 algebra does not need, and 0/1 algebra has one rule that ordinary algebra does not have:

p² = p. The only values p can take are 0 and 1, and squaring leaves both of them alone. So whenever a square shows up, replace it by the letter itself.

This rule is the algebra version of “p and p is just p”. It is also what makes contradictions vanish:

p ∧ ¬p becomes p(1 − p) = p − p² = p − p = 0. Always false. That is a contradiction.

p ∨ ¬p becomes p + (1 − p) − p(1 − p) = 1 − 0 = 1. Always true. That is a tautology, a statement that is true in every row.

Worked example: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)#

The symbol ≡ means “is equivalent to”: the two sides have the same truth value in every row. This is the example from the lecture.

Left side. First p ∨ q = p + q − pq. Now “or” that with r, using the same formula with (p + q − pq) in place of p:

(p + q − pq) + r − (p + q − pq)r = p + q + r − pq − pr − qr + pqr.

Right side. First q ∨ r = q + r − qr. Then p ∨ (that):

p + (q + r − qr) − p(q + r − qr) = p + q + r − pq − pr − qr + pqr.

The two expressions are identical, so the two statements are equivalent. No truth table was needed. Notice the pattern: every single letter with +, every pair with −, the triple with +. The expression treats p, q and r the same way, which is why the grouping does not matter.

The shortcut: write “or” as a product#

Multiplying out gets messy with four or five letters. There is a cleaner way, and it comes from De Morgan’s law: p ∨ q means the same as ¬(¬p ∧ ¬q). In words, “at least one is true” is the opposite of “both are false”.

Translate it: ¬p is 1 − p, the “and” is a product, and the outer “not” is one minus everything. So

p ∨ q = 1 − (1 − p)(1 − q).

Multiply it out and you get 1 − (1 − p − q + pq) = p + q − pq, the same formula as before. The product form scales with no effort:

p ∨ q ∨ r ∨ s = 1 − (1 − p)(1 − q)(1 − r)(1 − s).

One extra letter is just one extra factor. Grouping cannot matter, because multiplication does not care about grouping. That is a one-line proof of associativity for “or”, for any number of letters.

Worked example: the contrapositive, by algebra#

The contrapositive of p → q is ¬q → ¬p. The claim is that they always agree. Use the conditional formula 1 − a + ab with a = 1 − q (that is ¬q) and b = 1 − p (that is ¬p):

1 − (1 − q) + (1 − q)(1 − p)

= q + (1 − p − q + pq)

= 1 − p + pq.

That is exactly the formula for p → q. The algebra proves the equivalence in three lines.

Where this goes wrong#

• Writing p ∨ q as p + q. It gives 2 when both are true. The −pq is not optional.
• Forgetting p² = p. Without it, p(1 − p) looks like p − p² and seems not to simplify. With it, the answer is 0.
• Writing p → q as 1 − q + pq. That is the converse, q → p. The row that must be 0 is p = 1, q = 0, so test that row first.
• Stopping at “they look different”. Two formulas can look different and still be equal once you multiply out and use p² = p. Always simplify both sides fully before comparing.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.