Logic is basically the machinery underneath mathematical arguments. We use it constantly, even when nobody bothers to write the symbols down.
At the beginning, most of it looks pretty harmless. Statements are true or false. We have AND, OR, NOT, and IF. Then implication shows up and tells you that a false hypothesis makes the implication true, and people understandably start wondering who designed this thing.
But there is a reason for all of it.
Propositions
A proposition is a statement that is either true or false.
For example,
7 is prime.
That is a proposition, and it is true.
10 is prime.
Also a proposition. False this time.
Something like
Is 7 prime?
is not a proposition because it is a question. It does not itself have a truth value.
We usually use letters such as p, q, and r to stand for propositions. So we could let
p: 7 is prime
and
q: 10 is even.
The letters are just shorthand. The interesting part is what happens when we start doing things to the propositions.
Negation
The negation of p is written
¬p
and means “not p.”
If
p: 7 is prime,
then
¬p: 7 is not prime.
Negation just flips the truth value.
p | ¬p |
|---|---|
| T | F |
| F | T |
That one is about as painless as logic gets.
AND and OR
The statement
p ∧ q
means “p and q.”
It is true only when both p and q are true.
p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The statement
p ∨ q
means “p or q.”
This OR is inclusive. So if both statements are true, p ∨ q is still true.
p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
This is a little different from the way people sometimes use “or” in normal conversation. If somebody says you can have soup or salad, they may not be thrilled when you take both.
Mathematical logic is fine with it.
Implication
Here is where things usually get weird.
p → q
means
If p, then q.
The truth table is
p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The only time an implication is false is when p is true and q is false.
Suppose I say:
If a number is divisible by 4, then it is even.
If you find a number that is divisible by 4 but is not even, the statement is false. That would be an actual counterexample.
The part that bothers people at first is what happens when p is false. In that case, the implication is considered true.
Why? Because the statement only tells us what has to happen when p is true. If p never happens, then you have not violated the statement.
You may not like it the first time you see it. That is fine. Most people do not.
Truth Tables
Truth tables are just a way of checking every possible combination of truth values.
With two propositions, we have four possibilities:
TT
TF
FT
FF
With three propositions, there are eight. In general, with propositions there are possible combinations.
That means truth tables can get obnoxious pretty quickly, but for small expressions they are extremely useful.
If two logical expressions are supposed to mean the same thing, build the table and compare the final columns.
How to Flatten Reality Into Rows and Columns
Biconditional
The biconditional is written
p ↔ q
and means
p if and only if q.
It is true when p and q have the same truth value.
p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
The phrase “if and only if” matters. It gives us both directions.
p → q
and
q → p.
That is much stronger than proving only one implication.
There is also exclusive OR, usually written XOR. XOR is true when exactly one of the two propositions is true.
So biconditional and XOR behave in opposite ways. Biconditional wants the truth values to match. XOR wants them to be different.
The Last Honest Lie: If and Only If vs. Exclusive OR
Logical Equivalence
Two logical expressions are logically equivalent if they have the same truth value in every possible case.
We write
P ≡ Q.
For example,
p → q ≡ ¬p ∨ q.
That might not look obvious the first time you see it. The easiest way to check it is with a truth table. The final columns are identical.
That means the two expressions have the same logical meaning.
This becomes useful when an expression starts turning into a mess.
One of the most important examples comes from De Morgan’s laws:
¬(p ∧ q) ≡ ¬p ∨ ¬q
and
¬(p ∨ q) ≡ ¬p ∧ ¬q.
Notice what the negation does. It moves inside, but the connective changes.
AND becomes OR.
OR becomes AND.
That is worth remembering because forgetting it is a very efficient way to get the wrong answer.
The Art of Killing Chaos With Logic: Simplifying Ugly
Tautologies and Contradictions
Consider
p ∨ ¬p.
No matter what p is, that statement is true.
If p is true, the first part is true. If p is false, then ¬p is true.
So the entire expression is always true.
That is called a tautology.
Now look at
p ∧ ¬p.
There is no way for p and ¬p to both be true. So this expression is always false.
That is a contradiction.
If a compound proposition is true in some cases and false in others, it is a contingency.
These definitions are simple, but tautologies end up being important because a tautology is true because of its logical form. We are not checking whether 7 is prime or whether Minnesota is cold in January. The structure itself forces the result.
What Makes a Statement a Tautology?
Predicates
Things change a little once variables show up.
Take
.
Is that true or false?
We do not know. We need to know what x is.
If , it is true. If , it is false.
So is not yet a proposition. It is a predicate.
We could write
P(x):.
Once we choose a value for x, then P(x) becomes a proposition.
But choosing one value at a time is not how mathematics usually works. We want to say things about whole collections of values.
That is where quantifiers come in.
Quantifiers
The symbol
∀
means “for all.”
So
∀x P(x)
means that P(x) is true for every x in whatever domain we are talking about.
The symbol
∃
means “there exists.”
So
∃x P(x)
means there is at least one x for which P(x) is true.
If our domain is the integers, then
∀x,
is true.
Every integer has a nonnegative square.
But
∀x,
is false.
Negative integers exist. Zero is also sitting there being zero.
On the other hand,
∃x,
is true because we only need one example.
How to Negate the Universe: Universal and Existential Quantifiers
Negating Quantified Statements
This is one of the parts worth slowing down for.
Suppose we have
∀x P(x).
To negate it, we do not say
∀x ¬P(x).
That would mean every single x fails to satisfy P.
We do not need that much.
To show that “every x has property P” is false, we only need one x that does not.
So
¬∀x P(x) ≡ ∃x ¬P(x).
Similarly,
¬∃x P(x) ≡ ∀x ¬P(x).
If it is false that there exists even one x satisfying P, then every x fails.
The practical rule is that negation switches the quantifier and negates the predicate.
∀ becomes ∃.
∃ becomes ∀.
When Logic Eats Itself: Negating the Universal and the Existential
Where This Is Going
Most of this notation exists because eventually we want to prove things.
When a theorem says “if this, then that,” we are dealing with implication.
When a theorem says two conditions are equivalent, we usually need both directions.
When somebody claims something is true for every object in a set, one counterexample kills the claim.
And when we use proof by contradiction, all of this negation business suddenly stops looking like pointless symbol pushing.
That is really the reason to learn beginning logic. Not because truth tables are thrilling. They are not. It is because logic gives us a way to see the structure of an argument before we start trying to prove anything.
Once that structure is clear, the proof usually has somewhere to go.
Dogmathic Logic Videos
If you want to keep going, here are the Dogmathic videos that go with the ideas in this post.
How to Flatten Reality Into Rows and Columns
The Last Honest Lie: If and Only If vs. Exclusive OR
The Art of Killing Chaos With Logic: Simplifying Ugly
What Makes a Statement a Tautology?
How to Negate the Universe: Universal and Existential Quantifiers
When Logic Eats Itself: Negating the Universal and the Existential
More from Dogmathic
For more math news, explanations, proofs, examples, and commentary, check out Dogmathic Math Notes and the latest Dogmathic videos. You can also grab free PDFs and LaTeX resources or sign up for occasional email updates when something worth sharing gets published.
Leave a Reply