Recognize and transform between equivalent logical statements.
Negate logical statements and quantified logical statements correctly.
Apply the logical rules of deduction and follow if-then chains formally.
We start with definitions:
logical statement
A declaration that is either true or false but not both. For
example:
Today is Monday.
Languages contain many statements and declarations that are not logical
statements:
Symbolic logic is fun.
While that is a declaration, it is neither true nor false in general. An example
of a logical statement from set theory,
x A.
negation
A logical statement over the same topics that is false if the original
statement is true or true if the original is false. The statement
My dog has fleas.
has as its negation
My dog does not have fleas.
However, a statement about my cat(s) cannot be a negation of either of the
above regardless of which statements are true or false.
quantifier
When a statement applies to all, some, every of something,
the statement is quantified. The word denoting how many is the
quantifier. This is where negation becomes tricky. For example, the
statement
Expressing logical statements with symbols lets us focus on manipulating the logic
itself. We can talk about the dog having fleas without mentioning dogs or
fleas.
Variables like p
and q
can take the values true or false. Like many items, true and false are given different
symbols by different authors. Common symbols include
The first operator is negation. This is a unary operation; it applies to a
single operand. Two symbols are commonly used for the negation operator,
\mathop{¬} and
~, as is adding a bar
to a variable, \overline{p}. I will
stick with the symbol \mathop{¬}
for most cases.
With one operand, listing all possible inputs and outputs is
simple. The list is also called a truth table. The truth table for
\mathop{¬} is as
follows:
p
\mathop{¬}p
1
0
0
1
Programming languages may represent \mathop{¬}
with operators or functions like !, not(), .NOT., not.
When and joins pieces of a logical statement, we understand that the statement as a whole
it true only if both pieces are true. This is the conjunction operator. The conjunction
operator ∧
is the symbol we use to represent the same idea. The truth table for the
∧
operator has four lines and is as follows:
p
q
p ∧ q
1
1
1
1
0
0
0
1
0
0
0
0
The and operator sometimes is written as multiplication, or just
pq.
Most often, that is paired with using a bar for negation, so
p ∧\mathop{¬}q is written
p\overline{q}. This is
common notation in electrical engineering. Occasionally the negation will be written as
q'. Programming
languages may represent ∧
with operators or functions like &&, and(), .AND., and.
The English word or, however, has quite a few different meanings. Sometimes we
mean the logical exclusive-or, where one choice rules out the other, and sometimes
we mean logical or, where both choices are possible.
In symbolic logic, the disjunction operator,
∨,
is the latter type of or. The disjunction is true when either sub-clause is
true:
p
q
p ∨ q
1
1
1
1
0
1
0
1
1
0
0
0
In electrical engineering, or often is represented by
+, so
p ∨\mathop{¬}q would be written
p + \overline{q}. Programming
languages may represent ∨
with operators or functions like ||, or(), .OR., or.
The exclusive-or operator, which we will denote
⊕, is
true whenever exactly one operand is true:
p
q
p ⊕ q
1
1
0
1
0
1
0
1
1
0
0
0
Mathematically, the symbol for the exclusive-or operator is not particularly standardized. The symbol
⊻ sometimes appears, as
does the operator \mathop{xor}\nolimits . We will
expand on the notation ⊕
once we discuss addition of binary numbers.
Note that ⊕
often is not considered a core operator. We can write
p ⊕ q as
(p ∨ q)\mathop{¬}(p ∧ q).
Programming languages rarely provide ⊕
logical operators, although they often provide exclusive-or operators on the binary
representations of integers. More on those in the next chapter. But if you notice, this
is the negation of equality. So programming languages express the logical exclusive-or
by negating the equality of two logical expressions.
In symbolic logic, equality of two logical statements is equivalence.
When expressed as an operator, equivalence takes the symbols
≡,
⇔, or
↔. The
reason for the arrow forms will become clear soon.
p
q
p ≡ q
1
1
1
1
0
0
0
1
0
0
0
1
Again, ≡ is not a core
operator. p ≡ q is the
same statement as (p ∧ q) ∨ (\mathop{¬}p ∧\mathop{¬}q).
Programming languages represent equality with ==, =, equal?, and many other
forms.
A logical statement that always is true is a tautology. So
p ∨\mathop{¬}p is a
tautology:
The sky is periwinkle or the sky is not periwinkle.
Symbolically,
\mathrel{⊧}p ∨\mathop{¬}p.
A statement that always is false is a contradiction. Here
p ∧\mathop{¬}p is an
example:
The sky is blue and the sky is not blue.
A statement that is neither always true nor always false is logically contingent. So
pq is contingent on
the values of p
and q.
We use the symbol for tautology, \mathrel{⊧},
to make certain equivalence statements unambiguous. Because we defined
≡ as an
operator above, the plain statement
p ∨ q ≡ q ∨ p
appears contingent on its values. By adding
\mathrel{⊧}, we
make it clear that we are asserting that the statement is always true. To state that
p ∨ q is the
same as q ∨ p,
we say
Three properties from arithmetic also hold for the core logical operators
∧ and
∨:
commutative
In language, and and or are commutative, or p
and q
is the same as q
and p.
Symbolically, \mathrel{⊧}p ∧ q ≡ q ∧ p
and \mathrel{⊧}p ∨ q ≡ q ∨ p.
associative
Again, linguistically we don’t use parenthesis. Run-on statements
are just as true or false as well-structured ones, so we expect and and or to
be associative. We could build a large truth table to verify this, but for now
let us just state that \mathrel{⊧}(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
and \mathrel{⊧}(p ∨ q) ∨ r ≡ p ∨ (q ∨ r).
distributive
As with sets, both operations distribute over the other. So p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).
As a demonstration of using a truth table to show equivalence,
p
q
r
q ∨ r
p ∧ (q ∨ r)
p ∧ q
p ∧ r
(p ∧ q) ∨ (p ∧ r)
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
Which of these hold for ⊕
and ≡?
Over which operations may each be distributed?
Say we are provided with a truth table showing all possible values for an unknown logical
statement f(p,q).
From that truth table, we can construct a logical statement equivalent to
f(p,q).
Take:
p
q
f(p,q)
1
1
0
1
0
1
0
1
0
0
0
1
To construct f,
we can combine all the true outputs with
∨. The terms to be
combined are the ∧ of all
the variables. In each ∧
expression, each variable is negated to make its value true.
So in the above table, there are two true entries. One has
p ≡ 1 and
q ≡ 0, while the
other has p ≡ 0 and
q ≡ 0. The two corresponding
∧-statements
are p ∧\mathop{¬}q
and \mathop{¬}p ∧\mathop{¬}q.
So an equivalent statement is
There is another method for simplifying expressions which we will not cover. If you
are interested in a more visual method for simplifying expressions over a few
variables, look up Veitch charts or Karnaugh maps from electrical engineering. With
those forms, you draw a 2-d truth table and cover the true values with boxes of area
{2}^{k}. This
mechanism is particularly useful when you have don’t care values, places where the
output value does not matter.
One (compound) operator we have not mentioned so far is the conditional, the
symbolic form of an if-then rule. A statement like
If the sky is blue, then it is not raining.
is translated to
\text{the sky is blue} →\text{it is not raining},
or p → q using only
symbols. Here p is the
antecedent and q
is the consequent.
Many English statements are forms of conditionals. For example,
It is not raining when the sky is blue.
Rain does not fall from a blue sky.
A blue sky implies no rain.
A blue sky is sufficient for it not to be raining.
Not raining is necessary for a blue sky.
Many forms:
If p,
then q.
p
implies q.
p
only if q.
pis sufficient for q.
qis necessary for p.
q
if p.
The two in bold are very important in mathematics and science because they are
very, very common and often read incorrectly. Sufficient follows the arrow in
p → q, and
necessary works backward. We will see why when we examine the appropriate truth
table.
Colloquially, we can refer to p as
a premise or hypothesis and q
as a conclusion. However, we will stop using those terms when we discuss logical deduction. Identifying
p as a premise is useful
for reasoning about p → q,
but it introduces ambiguity when we consider
→ as an operator.
Just like with \mathrel{⊧}
and ≡,
additional symbols provide the appropriate context.
The truth table defining the conditional
→ is
slightly surprising:
p
q
p → q
1
1
1
1
0
0
0
1
1
0
0
1
The first and last lines are expected. When truth implies truth or falsity implies
falsity, the statement as a whole is true.
The second line also is expected. A true premise implying a false conclusion renders
the statement false.
Now comes the surprise. A false hypothesis implying a true conclusion renders the
statement as a whole true! This is only surprising because we are looking at one line
at a time. Consider the general case where the premise is false. If you start
reasoning from a false hypothesis, what is the result? Anything. So any time
p is
false, the statement as a whole is true.
We can break the conditional operator into core operators by listing the single
negated output and applying De Morgan’s laws:
Considering a few rules from arithmetic, we see that
→ is not commutative!
The form q → p is the
converse of p → q, but the
two statements are not equivalent. Similarly, we cannot simply negate terms to obtain the negation,
so \mathop{¬}(p → q) is not the same
as the inverse \mathop{¬}p →\mathop{¬}q.
There is one other form here that is equivalent. The contrapositive\mathop{¬}q →\mathop{¬}q is equivalent
to p → q.
One more form of the conditional is important because it is so frequently used, the
phrase if and only if .
p if and
only if q
is a double conditional or biconditional. It means
p → q ∧ q → p and is written
symbolically as p ↔ q.
In text, if and only if often is abbreviated as iff.
Looking at its truth table, we see that ↔
is the same as equivalence:
p
q
p → q
q → p
p ↔ q
1
1
1
1
1
1
0
0
1
0
0
1
1
0
0
0
0
1
1
1
Which symbol you use is a matter of preference and emphasis.
We are interested in two quantifiers for logical statements: for all and there exists.
These are universal and existential quantifiers, respectively. To demonstrate these,
I’m going to switch to predicate logic. Here properties have parameters,
and the quantifiers describe possible values for those parameters. There is a
third common quantifier, the uniqueness quantifier, but we will not explore
it.
Say Dexter has fleas (which he doesn’t). So far, we would simply associate this
statement with a single variable. But to examine quantifiers, we need a bit
more.
Let P(p) be the property
of having fleas. This P(\text{Dexter})
is a (false) statement that Dexter has fleas. We can generalize this to state that
\mathop{∃}p D : P(p) where
D is the set
of dogs. If p is
Dexter, then P(p)
would be stating that Dexter has fleas, so there does exist such a
p. The
colon ( :)
is read as “such that” or “satisfies” and sometimes is replaced by a vertical bar
| or the backwards
epsilon-ish symbol ∋.
But Dexter does not have fleas, so in reality
\mathop{∃}p D : \mathop{¬}P(p).
Because Dexter is a dog, we know not all dogs have fleas. So
\mathop{∃}p D : \mathop{¬}P(p) is the
same as \mathop{¬}\mathop{∀}p D : P(p).
Translating to and from English needs attention to detail. The word always does not always
translate into \mathop{∀}.
Some translations:
P(p) is always true.
\mathop{∀}p : P(p).
P(p) is almost always true.
\mathop{∃}p : \mathop{¬}P(p).
There always is some way for P(p) to be true.
\mathop{∃}p : P(p)
Sometimes P(p).
\mathop{∃}p : P(p).
And here are the reasons why we care about formalizing quantifiers in this
class: Negation is tricky, and composing or nesting quantifiers istricky.
One other item to note: Different quantifiers are not operators, hence you
cannot assume they commute! Quantifiers nest. As an example, consider two
statements:
All homework questions have been answered by at least one student. Some student has answered all homework problems.
Translating the first (true) statement into a symbolic form gives
The symbolic versions appear similar. The only difference is the order of the
quantifiers. But the statements obviously have very different meanings.
The text gives a nice visual interpretation in Section 3.5 using diagrams
akin to Venn diagrams from set theory. Here we consider a more syntactic
approach.
Given the English and logic statements:
All homework questions have been answered by at least one student. \mathop{∀}q \text{questions}\kern 1.66702pt \mathop{∃}s \text{students} : s\text{ answered }q.
You can read the latter as the former, or as
For all questions, there is some student who has answered that
question.
Which student is meant depends on which question is considered.
Now consider the other statement:
Some student has answered all homework problems. \mathop{∃}s \text{students}\kern 1.66702pt \mathop{∀}q \text{questions} : s\text{ answered }q.
Here the questions answered depends on which student is considered. And this
statement says that one student has answered all questions.
For a more formal example, you read \mathop{∀}p {J}^{+}\mathop{∃}q {J}^{+} : p < q
as
For all positive integers p
there exists a positive integer q
such that p > q.
The particular q depends
on the p. There is not be
a single q that works for
all positive integers p.
This statement is true over the integers.
Swapping the quantified statements produces a false statement. The translation of
\mathop{∃}q {J}^{+}\mathop{∀}p {J}^{+} : p < q
is
There exists a positive integer q
such that for all positive integers p,
p < q.
How do we negate the following true and equivalent English and logic statements?
All homework questions have been answered by at least one person. \mathop{∀}q \text{questions}\kern 1.66702pt \mathop{∃}s \text{students} : s\text{ answered }q.
Consider working symbolically with the rules we already established:
Now that we have if-then statements, we can speak more
about logical deduction. And the simplest level, we can chain
→
operators to show deduction. But then we end up with statements like
\left ((p → q) ∧ (q → r) ∧\mathop{¬}r\right ) →\left ((p → r) ∧\mathop{¬}r\right ) → p.
These become unreadable quickly.
Instead, we introduce new symbols. The above could be written as
p → q,q → r,\mathop{¬}r ⊢ p → r,\mathop{¬}r ⊢ p.
Taking up more room but being more clear, we can write the logical argument or
logical deduction as
p → q
q → r
\mathop{¬}r
⊢ p → r
\mathop{¬}r
⊢\mathop{¬}p
The general form in one line: Premise 1, premise 2
⊢
conclusion. In table form,
Premise 1
Premise 2
⊢ Conclusion.
Both are read as assuming premise one and premise two, infer the conclusion or
premise one and premise two entail the conclusion.
The ⊢
symbol is syntactic sugar meant to place emphasis where important.
p ⊢ q is the
same as ⊢ p → q
or just p → q,
but the former implies a deduction while the latter appears to be just a
statement.
Sometimes three dots, ∴,
is used instead of ⊢.
And sometimes (as in the text) neither appears in the tabular form. However,
symbolic logic is about removing ambiguity that comes from language. Using the
symbol helps disambiguate valid logical arguments from examples of invalid
arguments or fallacies.
When reasoning about reasoning itself, the set of premises in a rule often are represented
by Γ, so
Γ ⊢ q is a rule with a set
of premises Γ leading
to a single result q.
Some forms or structures of logical arguments have classical names. These names
came long before the symbolic form.
Modus ponens
p → q,p ⊢ q,
or
p → q
p
⊢ q
Modus tollens
p → q,\mathop{¬}q ⊢\mathop{¬}p,
or
p → q
\mathop{¬}q
⊢\mathop{¬}p
Disjunctive syllogism
p ∨ q,\mathop{¬}p ⊢ q,
or
p ∨ q
\mathop{¬}p
⊢ q
Hypothetical syllogism
(also called transitivity)
p → q,q → r ⊢ p → r,
or
p → q
q → r
⊢ p → r
We also can write De Morgan’s laws as laws of deduction, for example
\mathop{¬}(p ∨ q) ⊢\mathop{¬}p ∧\mathop{¬}q,
or
\mathop{¬}(p ∨ q)
⊢\mathop{¬}p ∧\mathop{¬}q .
Much of the reason why we care about the correct rules of deduction is to highlight
incorrect rules, or logical fallacies. A list of a few common fallacies follows. Note that
we include a symbol after the line in the tabular form; the negation of implication,
⊬, lets
you know we are talking about fallacies. The text does not use any symbol, so you
may end up seeing these fallacies as valid.
Fallacy of the converse
Given p → q
and q, we
cannot deduce p.
Symbolically, p → q,q ⊬ p
or
p → q
q
⊬ p .
Fallacy of the inverse
Given p → q
and \mathop{¬}p, we
cannot deduce \mathop{¬}q.
Symbolically, p → q,\mathop{¬}p ⊬ \mathop{¬}q
or
p → q
\mathop{¬}p
⊬ \mathop{¬}q .
Fallacy of the alternative disjunct
Given
p ∨ q and
p, we cannot
deduce \mathop{¬}q.
Symbolically, p ∨ q,p ⊬ \mathop{¬}q
or
p ∨ q
p
⊬ \mathop{¬}q .
With the exclusive-or operator ⊕,
we can conclude that only one disjunct is chosen. But the or operator
∨
allows both to occur at once.
A.