CMSC 250: Propositional Logic
Justin Wyss-Gallifent
September 16, 2021
1 Statements and Statement Variables . . . . . . . . . . . . . . . . 2
2 Negation, Disjunction, Conjunction . . . . . . . . . . . . . . . . . 3
2.1 Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Conjunctions . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Xor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 English Commentary . . . . . . . . . . . . . . . . . . . . . 5
3 Statement Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1 Basic Definition . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Order of Operations . . . . . . . . . . . . . . . . . . . . . 6
3.3 Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Double Negative . . . . . . . . . . . . . . . . . . . . . . . 7
4.3 DeMorgan’s Laws . . . . . . . . . . . . . . . . . . . . . . 8
4.4 Tautologies and Contradictions . . . . . . . . . . . . . . . 8
4.5 Summary of Common Logical Equivalences . . . . . . . . 9
4.6 Working with Logical Equivalences . . . . . . . . . . . . . 9
5 Conditional Statements . . . . . . . . . . . . . . . . . . . . . . . 10
5.1 Introduction and Definition . . . . . . . . . . . . . . . . . 10
5.2 Rewriting using Not and Or . . . . . . . . . . . . . . . . . 13
5.3 Negating a Conditional . . . . . . . . . . . . . . . . . . . 13
5.4 Converse . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.5 Contrapositive . . . . . . . . . . . . . . . . . . . . . . . . 14
5.6 Inverse of a Conditional . . . . . . . . . . . . . . . . . . . 14
5.7 A Fun Diagram . . . . . . . . . . . . . . . . . . . . . . . . 15
5.8 Biconditionals . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.9 Necessary and Sufficient . . . . . . . . . . . . . . . . . . . 16
6 Arguments and Argument Forms . . . . . . . . . . . . . . . . . . 16
6.1 Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Argument Forms . . . . . . . . . . . . . . . . . . . . . . . 17
6.3 Valid and Invalid Arguments . . . . . . . . . . . . . . . . 18
6.4 Modus Ponens and Modus Tollens . . . . . . . . . . . . . 20
6.5 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . 20
6.6 Using Rules of Inference . . . . . . . . . . . . . . . . . . . 21
1
1 Statements and Statement Variables
Definition 1.0.1. A statement (or proposition) is a sentence that is either true
or false but not both.
�
Note 1.0.1. Note that the words sentence, true, and false are technically unde-
fined here, and that’s okay. For now we’ll use an pretty obvious English language
interpretation.
�
Example 1.1. The sentence “2 + 2 = 4” is true and not false, hence it is a
statement.
�
Example 1.2. The sentence “1 + 1 = 0” is false and not true, hence it is a
statement.
�
Note 1.0.2. You might argue there’s some wiggle room here. If we are working
in Z2 then “1+1 = 0” is true. So in the background here there’s generally some
well-understood context necessary.
�
Compare these two:
Example 1.3. The sentence “x > 0” could be true or false, depending on the
value of x. The implicit context here is that the value of x is not just unknown,
but not fixed. It is therefore not a statement.
�
Example 1.4. On the other hand consider the sentence “Let x be the amount
of money in my wallet. Then x > 20.” The value of x is fixed and hence this is
a statement. The fact that you don’t know if it’s true or false doesn’t matter,
as it certainly is one or the other of those.
�
Note 1.0.3. Formally we might say that in the first case x is a variable but in
the second case it’s an (unknown) fixed constant.
�
Definition 1.0.2. A statement variable is a variable which represents an un-
known statement. We’ll use letters like p and q. We can then say, for example,
that p will be true or false depending on what p represents.
�
2
2 Negation, Disjunction, Conjunction
There are three formal symbols we’ll use to build more complicated statements
out of simpler ones. Now we are talking about statements, so we’re building
things out of sentences which we know are either true or false.
2.1 Negation
Definition 2.1.1. If p is statement or statement variable then ∼ p is read “not
p” and is the negation of p. It is defined according to:
∼ p =
{
true if p is false
false if p is true
�
Example 2.1. Suppose we have our statement:
p : 2 + 2 = 4
Then we know p is true and hence ∼ p is false.
�
Note 2.1.1. Arguably we have:
∼ p :∼ (2 + 2 = 4)
But we can easily see that we might prefer to write:
∼ p : 2 + 2 6= 4
The fact that these are equivalent is obvious here, but might not be for more
complicated examples.
�
Example 2.2. If p is a statement variable (representing an unknown statement)
and I tell you that p is true, then you know that ∼ p is false.
�
2.2 Disjunctions
Definition 2.2.1. If p and q are statements or statement variables then p ∨ q
is read “p or q” and is the disjunction of p and q. It is defined according to:
p ∨ q =
{
true if one or both of p and q is true
false if p is false and q is false
3
�
Example 2.3. Suppose we have two statements:
p : 2 + 2 = 4
q : 4 + 5 = 1
Then we know p is true and q is false and hence p ∨ q is true.
�
Example 2.4. Suppose we have two statements:
p : 2 + 2 = 5
q : 4 + 5 = 1
Then we know p is false and q is false and hence p ∨ q is false.
�
Example 2.5. If p and a are statement variables (representing unknown state-
ments) and I tell you that both are true, then you know that p ∨ q is true.
�
2.3 Conjunctions
Definition 2.3.1. If p and q are statements or statement variables then p ∧ q
is read “p and q” and is the conjunction of p and q. It is defined according to:
p ∧ q =
{
true if both of p and q are true
false if one or both of p and q is false
�
Example 2.6. Suppose we have two statements:
p : 2 + 2 = 4
q : 4 + 5 = 1
Then we know p is true and q is false and hence p ∨ q is false.
�
Example 2.7. Suppose we have two statements:
p : 2 + 2 = 4
q : 4 + 5 = 9
Then we know p is true and q is true and hence p ∨ q is true.
�
Example 2.8. If p and a are statement variables (representing unknown state-
ments) and I tell you that p is false and q is true, then you know that p ∧ q is
false.
�
4
2.4 Xor
We use xor to mean one or the other but not both. We won’t really use this
much because it can be written in terms of ∼, ∨, and ∧. However there are
various ways to denote this including p⊕ q and p Y q.
2.5 English Commentary
It’s important to note that mathematics is precise but English is not. In English
the word “or” is usually implied to be exclusive. For example when we say “I
will eat chicken or steak.” we usually mean one or the other but not both. In
mathematics, however, “or” includes both.
There are also words in English which we might have to pause to translate. Two
of these are:
p but q means p and q
Example 2.9. The sentence “I am tired but I will browse reddit some more”
really means “I am tired and I will browse reddit some more”.
�
And:
Neither p nor q means ∼ p and ∼ q. Alternatively (∼ p) ∧ (∼ p).
Example 2.10. The sentence “It is neither snowing nor raining” really means
“It is not snowing and it is not raining”.
�
3 Statement Forms
3.1 Basic Definition
Definition 3.1.1. Now that we have our three basic building blocks, ∼, ∨, and
∧, we can use these along with statement variables to build statement forms.
�
Example 3.1. If p, q, and r are statement variables then ∼ (p ∨ r) ∧ q is a
statement form.
�
Note 3.1.1. Just to clarify an oftentimes confusing difference, from now on
we’ll use the term statement form to include single statement variables. If we
want to refer specifically to the statement variables which make up a statement
form we’ll say component statement variables.
Thus p is a statement form, p∧ q is a statement form, and in the second case p
and q are component statement variables within that statement form.
5
�
Whether a statement form is true or false depends on the truth of its com-
ponent statement variables and can be quite hard to determine. In order to
facilitate our understanding we’ll (soon) define and draw truth tables to explore
all possibilities.
3.2 Order of Operations
Negation takes precedence over conjunction and disjunction but neither conjuc-
tion nor disjunction takes precedence over the other, so parentheses are needed.
Example 3.2. ∼ p ∨ q is unambiguous, it means the same as (∼ p) ∨ q.
�
Example 3.3. ∼ (p ∨ q) is different than the above.
�
Example 3.4. p∨q∧r is ambiguous. It’s not clear which of ∨ or ∧ is managed
first. We need to write either (p ∨ q) ∧ r or p ∨ (q ∧ r) depending on which we
mean, because they’re different.
�
3.3 Truth Tables
Definition 3.3.1. A truth table is a table which starts by listing all possible
combinations of T/F values for the component statement forms (or variables)
and using these to determine the T/F values for the entire statement form. Usu-
ally, when necessary or just plain helpful, intermediate columns for intermediate
statement forms are included.
�
Example 3.5. Here are truth tables for ∼ p, p ∨ q, and p ∧ q:
p ∼ p
T F
F T
p q p ∨ q
T T T
T F T
F T T
F F F
p q p ∧ q
T T T
T F F
F T F
F F F
�
Example 3.6. Here is a truth table for ∼ p ∨ q. It is helpful to have a column
for ∼ p.
6
p q ∼ p ∼ p ∨ q
T T F T
T F F F
F T T T
F F T T
�
Truth tables can get a bit out of control. If there are n statement variables then
there will be 2n rows since there will be 2n possible combinations of T/F for
the n statement variables.
Example 3.7. Here is a truth table for the statement form (p ∨ q) ∧ (∼ r). It
is helpful to have a column for statement form p ∨ q and perhaps one for the
statement form ∼ r.
p q r p ∨ q ∼ r (p ∨ q) ∧ (∼ r)
T T T T F F
T T F T T T
T F T T F F
T F F F T F
F T T T F F
F T F T T T
F F T T F F
F F F F T F
�
4 Logical Equivalence
4.1 Definition
Definition 4.1.1. We say that two statement forms are logically equivalent,
written using ≡, when they have the same T/F value for every single possible
T/F value combination of their component statement variables. A truth table
can help us see if this is the case.
�
What follows are some classically important logical equivalences.
4.2 Double Negative
Example 4.1. Observe that ∼ (∼ p) ≡ p. While this is intuitively obvious,
here’s a truth table:
p ∼ p ∼ (∼ p)
T F T
F T F
7
We see that the columns for p and ∼ (∼ p) are exactly the same, which estab-
lishes the equivalency.
�
4.3 DeMorgan’s Laws
Two very important logical equivalences are DeMorgan’s Laws. Before giving
the Laws, look at this example:
Example 4.2. Observe that ∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q). Here’s a truth table:
p q ∼ p ∼ q p ∨ q ∼ (p ∨ q) (∼ p) ∧ (∼ q)
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
We see that the columns for ∼ (p ∨ q) and (∼ p) ∧ (∼ q) are exactly the same,
which establishes the equivalency.
�
Theorem 4.3.1. DeMorgan’s Laws: If p and q are statements or statement
forms then we have:
∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q)
∼ (p ∧ q) ≡ (∼ p) ∨ (∼ q)
Proof: The first is shown in the truth table above. You should try the second!
QED
4.4 Tautologies and Contradictions
Definition 4.4.1. A tautology is a statement form which is always true for all
T/F values of its statement variables. If X is a tautology we’ll just write X ≡ t.
In a truth table we’ll see a column full of T .
�
Example 4.3. The simplest of tautologies is p∨ ∼ p.
�
Definition 4.4.2. A contradiction is a statement form which is always false for
all T/F values of its statement variables. If X is a contradiction we’ll just write
X ≡ c. In a truth table we’ll see a column full of F .
�
Example 4.4. The simplest of contradictions is p∧ ∼ p.
�
8
4.5 Summary of Common Logical Equivalences
Here are the most important logical equivalences. Some are obvious, some not
so much. We have not proved most of them. You should try them using truth
tables.
Commutative Laws p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative Laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive Laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Identity Laws p ∧ t ≡ p p ∨ c ≡ p
Negation Laws p∨ ∼ p ≡ t p∧ ∼ p ≡ c
Double Negative Law ∼ (∼ p) ≡ p
Idempotent Laws p ∧ p ≡ p p ∨ p ≡ p
Universal Bound Laws p ∨ t ≡ t p ∧ c ≡ c
DeMorgan’s Laws ∼ (p ∧ q) ≡ (∼ p) ∨ (∼ q) ∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q)
Absorption Laws p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Negation of t and c ∼ t ≡ c ∼ c ≡ t
4.6 Working with Logical Equivalences
Once we have some logical equivalences we can use them to find others.
The first thing to note is that the component statement variables in the state-
ment forms above are just that, variables, and so the above logical equivalences
will still hold if the component statement variables are replaced by other state-
ment forms.
Example 4.5. We have the identity law p ∧ t ≡ p. Think of the statement
variable p as a placeholder, so think X ∧ t ≡ X for any statement form X.
Thus, for example, we get all of the following:
(∼ p) ∧ t ≡∼ p
and
(p ∨ q) ∧ t ≡ p ∨ q
and
(∼ p ∧ q) ∧ t ≡∼ p ∧ q
�
In addition we can build new laws.
Example 4.6. Let’s show that ∼ (∼ p ∧ q) ∧ (p ∨ q) ≡ p.
9
∼ (∼ p ∧ q) ∧ (p ∨ q) ≡ (∼ (∼ p)∨ ∼ q) ∧ (p ∨ q) DeMorgan’s Law
≡ (p∨ ∼ q) ∧ (p ∨ q) Double Negative Law
≡ p ∨ (∼ q ∧ q) Distributive Law (backwards)
≡ p ∨ c Negation Law
≡ p Identity Law
�
5 Conditional Statements
5.1 Introduction and Definition
In mathematics statements and statement forms often contain implications:
If p then q.
Definition 5.1.1. If p and q are statements or statement forms then we can
construct the conditional statement or statement form p → q (also called the
implication) read as “if p then q” or “p implies q”. Here p is the hypothesis or
antecedent and q is the conclusion or consequent.
�
We’re first interested in whether this statement is true or not. Keep in mind
that we’re not interested in whether p is true or q is true but rather whether
p→ q is true.
In order to understand whether this statement is true or not it is critically
important (to help avoid confusion) to understand that the nature of “If p then
q” is not really causal, even though it often can be thought of that way.
In other words saying that p→ q is true does not mean that p being true must
cause q to be true but rather that whenever p is true then q is also true.
Now let’s consider some situations for the statement form p→ q.
1. First, consider this example:
Example 5.1. Let’s put:
p : I open my eyes between 1pm and 2pm
q : It will be daytime
Then p→ q becomes:
If I open my eyes between 1pm and 2pm then it will be daytime.
10
This example is clearly true. Note that from a causal perspective opening
your eyes between 1pm and 2pm doesn’t make it daytime.
�
We see here that whenever p is true we find that q is also true then it
seems reasonable to say that p→ q is true.
Two other examples which suggest the same:
Example 5.2. Let’s put:
p : I arrive at Union Station at 9am for the 9am train to NYC
q : The train will be there
Then p→ q becomes:
If I arrive at Union Station at 9am for the 9am train to NYC then the
train will be there.
Also true. Note again that from a causal perspective I didn’t cause the
train to be there.
�
Example 5.3. Let’s put:
p : x > 3
q : x + 2 > 5
In this case we’ll say that x is an unknown fixed real number. Then p→ q
becomes:
If x > 3 then x + 2 > 5.
Again, also true. In this example we might think that the relationship is
arguably causal but really it’s not. This example is simply saying that
whenever x > 3 then it will also be the case that x + 2 > 5. Imagine
infinitely many x’s lying around. If you pick one up and it’s greater than
3, then x + 2 will be greater than 5.
�
2. Second, consider this example:
Example 5.4. Let’s put:
p : My first name is Justin
q : My last name is Time
Then p→ q becomes:
11
If my first name is Justin then my last name is Time.
This is clearly false. My first name is Justin but my last name isn’t Time.
�
We see here that when p is true and q is false it seems reasonable to say
that p→ q is false.
3. Third, consider these examples:
Example 5.5. Let’s put:
p : x is a real number with x2 < 0 q : I am a muppet Then p→ q becomes: If x is a real number with x2 < 0 then I am a muppet. � Example 5.6. Let’s put: p : x is a real number with x2 < 0 q : I am a human Then p→ q becomes: If x is a real number with x2 < 0 then I am a human. � Hmmm. Are these statements true? The hypotheses are not true. So what should we say about the conditionals? The way we address this is to understand that p→ q can only be said to be false if p is true and q is false. When p itself is false we say that p→ q is true. It’s a special kind of true, called vacuously true. To summarize, p→ q obeys the following truth table: p q p→ q T T T T F F F T T F F T 12 5.2 Rewriting using Not and Or The truth table above lets us also understand the following logical equivalence: p→ q ≡∼ p ∨ q Stop for a minute and consider that this makes sense if we think about the condition under which each is false: p→ q is false when p is true and q is false. ∼ p ∨ q is false when ∼ p is false (p is true) and q is false. 5.3 Negating a Conditional One reason for recognizing that p→ q ≡∼ p ∨ q is that it allows us to negate: ∼ (p→ q) ≡∼ (∼ p ∨ q) ≡ p∧ ∼ q Again, this makes sense, as it is not the case that p→ q precisely when p is true and q is false. Please keep in mind that when the conclusion it itself a statement form that we may wish to go further. In the following two examples we’re not saying that you must go further but rather that the logical equivalences all hold. Example 5.7. Consider the negation of p→ (q∨ ∼ r). We use one of DeMor- gan’s Laws as well: ∼ (p→ (q∨ ∼ r)) ≡ p∧ ∼ (q∨ ∼ r) ≡ p ∧ (∼ q ∧ r) � Example 5.8. Consider the negation of p→ (q → r) in which we can go further still. ∼ (p→ (q → r)) ≡ p∧ ∼ (q → r) ≡ p ∧ (q∧ ∼ r) ≡ (p ∧ q)∧ ∼ r ≡∼ ((p ∧ q)→ r) � 13 5.4 Converse Most theorems in mathematics are conditionals. There are one or more hypoth- esis which are assumed and generally one conclusion which we wish to prove. For most theorems we might also be interested in whether the “reverse” is true. Definition 5.4.1. The converse of p→ q is the conditional q → p. � Example 5.9. The converse of “If it is raining then it is cloudy” is “If it is cloudy then it is raining”. � Note 5.4.1. These converse and the original are not logically equivalent. � 5.5 Contrapositive Definition 5.5.1. The contrapositive of p→ q is the conditional ∼ q →∼ p. � Example 5.10. The contrapositive of “If it is raining then it is cloudy” is “If it is not cloudy then it is not raining”. � Note 5.5.1. The contrapositive is in fact logically equivalent to the original conditional. In other words p→ q ≡∼ q →∼ p. � 5.6 Inverse of a Conditional Definition 5.6.1. The inverse of p→ q is the conditional ∼ p→∼ q. � Example 5.11. The inverse of “If it is raining then it is cloudy” is “If it is not raining then it is not cloudy”. � Note 5.6.1. The inverse is not logically equivalent to the original but is equiv- alent to the converse. � 14 5.7 A Fun Diagram In reality since we can take converses, contrapositives, and inverses of any con- ditional we can see the process in the following diagram: p→ q q → p ∼ q →∼ p ∼ p→∼ q inverse 6≡ 6≡converse 6≡ converse ≡ contrapositive ≡ contrapositive 6≡ inverse 5.8 Biconditionals Definition 5.8.1. If p and q are statments or statement forms then we can construct the biconditional statement or statement form p ↔ q, read as “p if and only q” and often written as “p iff q”. The biconditional is the conjunction of p→ q and its converse q → p. In other words: p↔ q ≡ (p→ q) ∧ (q → p) � Note 5.8.1. There are other logically equivalent ways to think about the bi- conditional, for example: p↔ q ≡ (p ∧ q) ∨ (∼ p∧ ∼ q) This should make intuitive sense; either they’re both true or they’re both false, bit this can also be proved using logical equivalences that we already know: p↔ q ≡ (p→ q) ∧ (q → p) Definition ≡ (∼ p ∨ q) ∧ (∼ q ∨ p) Logical Equivalence ≡ ((∼ p ∨ q)∧ ∼ q) ∨ ((∼ p ∨ q) ∧ p) Distributive Laws ≡ ((∼ p∧ ∼ q) ∨ (q∧ ∼ q)) ∨ ((∼ p ∧ p) ∨ (q ∧ p)) Distributive Laws ≡ ((∼ p∧ ∼ q) ∨ c) ∨ (c ∨ (q ∧ p)) Negation Laws ≡ (∼ p∧ ∼ q) ∨ (q ∧ p) Identity Laws � 15 5.9 Necessary and Sufficient The terms “necessary” and “sufficient” in English correspond to conditionals in mathematics. Consider the statement: It is sufficient for me to get a 60% or more to pass the class. This statement basically means: If I get a 60% or more then I will pass the class. Thus we see: p is sufficient for q means p→ q On the other hand consider the statement: It is necessary for me to buy apples to make an apple pie. This statement basically means two equivalent things: If I don’t buy apples then I will not make apple pie. And: If I make apple pie then I bought apples. Thus we see: p is necessary for q means ∼ p→∼ q and is logically equivalent to q → p. 6 Arguments and Argument Forms 6.1 Arguments Suppose I make the following argument about someone named Frank. You don’t know Frank, or anything about him: Frank is over 40 years old. If Frank is over 40 years old then Frank is happy. Therefore: Frank is happy You would probably agree that this argument is valid. Let’s ponder what we mean by this for a minute. You might stop and ask “Is Frank actually over 40 years old? Maybe not!” but would that affect whether the argument is valid? Well, what might “valid mean? 16 Suppose we identified the first two statements as hypotheses and the last one as a conclusion: Frank is over 40 years old. Hypothesis If Frank is over 40 years old then Frank is happy. Hypothesis Therefore: Frank is happy Conclusion We might suggest that this argument is valid not because it’s all true but be- cause if the hypotheses are both true, then we can conclude for sure that the conclusion is also true. On the other hand consider this argument: Frank is over 40 years old. Hypothesis If Frank owns a motorcycle then Frank is happy. Hypothesis Therefore: Frank is happy Conclusion We might suggest that this argument is not valid because even if the two hy- potheses are true we cannot conclude for certain that the conclusion is true. We make these sorts of arguments all the time and the goal of this section is to formalize them. 6.2 Argument Forms Definition 6.2.1. An argument form consists of a collection of statement forms, called hypotheses, and an additional single statement form, called a conclusion � We write an argument form with one statement form per line and with the symbol ∴ (read “therefore”) before the final statement, which is the conclusion. Example 6.1. The following is an argument form with two hypotheses (and one conclusion). You might recognize that it’s a general form of the opening argument from the section: p Hypothesis p→ q Hypothesis ∴ q Conclusion � Example 6.2. The following is another one, not as familiar: q Hypothesis p ∨ q Hypothesis ∴ p→ q Conclusion 17 � 6.3 Valid and Invalid Arguments Informally, we are interested in whether the hypotheses together imply the con- clusion. Example 6.3. In this example again: q Hypothesis p ∨ q Hypothesis ∴ p→ q Conclusion We are interested in whether this statement is true:[ q ∧ (p ∨ q) ] → [ p→ q ] � More generally if the hypotheses are hyp1, hyp2, ... , hypn and the conclusion is conc, we are interested in whether this statement is true:[ hyp1 ∧ hyp2 ∧ ... ∧ hypn ] → [ conc ] We know that this implication is (vacuously) true when hyp1 ∧hyp2 ∧ ...∧hypn is false, meaning when one or more of the hypi is false, and so we only need to focus on the following situation: When all of the hypotheses hyp1, hyp2, ... , hypn are true, is the conclusion conc true, too? [ hyp1 ∧ hyp2 ∧ ... ∧ hypn ] ︸ ︷︷ ︸ When these are all true... → [ conc ]︸ ︷︷ ︸ ...is this true? This leads to the following definition: Definition 6.3.1. An argument form is valid if, whenever the hypotheses are all true, the conclusion must also be true. An argument form is invalid if there are one or more situations in which the hypotheses are all true but the conclusion is false. � One way to determine whether an argument form is valid is to write out a truth table which has one row for each combination of the component statement variables. We then inspect the rows in which the hypotheses are all true. If, for each of those rows, the conclusion is true, then the argument is valid. On the other hand if there are one or more rows in which the hypotheses ar all true but the conclusion is false then the argument is invalid. 18 Example 6.4. Consider the following argument form again: q p ∨ q ∴ p→ q Here is a truth table for all possible p and q which also displays p∨q and p→ q: p q p ∨ q p→ q T T T T T F T F F T T T F F F T Now examine all the rows in which both q and p ∨ q are true: p q p ∨ q p→ q T T T T T F T F F T T T F F F T Observe that in both of these rows, p → q is also true. Thus the argument is valid. � On the other hand: Example 6.5. Consider the following argument form: p p ∨ q ∴ p→ q This has the same truth table as the previous example. Let’s examine all the rows in which both q and p ∨ q are true p q p ∨ q p→ q T T T T T F T F F T T T F F F T Observe that in one of these rows, p→ q is false. Thus the argument is invalid. � 19 6.4 Modus Ponens and Modus Tollens The two most common valid argument forms are modus ponens and modus tollens. Definition 6.4.1. The argument form modus ponens is: p→ q p ∴ q � Stop and think about this and it makes perfect sense. If you know that p → q and p, then you can conclude q. Similarly: Definition 6.4.2. The argument form modus tollens is: p→ q ∼ q ∴ ∼ p � Again, clearly if you know p→ q and ∼ q, then you can conclude ∼ p. 6.5 Rules of Inference Definition 6.5.1. A rule of inference is a valid argument form. � For example, modus ponens and modus tollens are rules of inference. Here are the most common rules of inference: Modus Ponens Modus Tollens Generalization p→ q p→ q p p ∼ q ∴ p ∨ q ∴ q ∴ ∼ p Specialization Conjunction Elimination p ∧ q p p ∨ q ∴ p q ∼ p ∴ p ∧ q ∴ q Transitivity Cases Contradiction p→ q p ∨ q ∼ p→ c q → r p =⇒ r ∴ p ∴ p→ r q =⇒ r ∴ r 20 6.6 Using Rules of Inference We can use rules of inference to build new rules, and on and on and on, thereby showing that an argument form is valid. We do this by using the hypotheses along with known rules of inference to contruct new hypotheses, and we continue this until we get our conclusion. Keep in mind with these rules of inference that p, q, etc. can be not just statement variables but statement forms. Example 6.6. Here is a really simple argument form: p p→ q q → r ∴ r Before being very organized just think about this intuitively. We have three hypotheses: p, p→ q and q → r. Suppose that all three of these are true. Since p is true and p → q is true, this means q must be true, too, by modus ponens. This is a new hypothesis we can add to the mix. Then since q is true and q → r is true, this means r is true, too, by modus ponens again. Then we have our conclusion. This can be approached in a more organized manner. First we write down the hypotheses we’re given, and number them: p (1) p→ q (2) q → r (3) Then we observe that modus ponens applies to (1) and (2) to yield the conclusion q so we add this to our list: p (1) p→ q (2) q → r (3) q (4) Modus Ponens using (1) and (2) Then we observe that modus ponens applies to (4) and (3) to yield the conlusion r so we add this to our list: 21 p (1) p→ q (2) q → r (3) q (4) Modus Ponens using (1) and (2) r (5) Modus Ponens using (4) and (3) Thus we have reached r and the conlusion holds, thus the argument form is valid. � Of course we don’t need to rewrite the entire list each time, we simply build onto it as we go. Here is another example: Example 6.7. Consider the following argument form: p ∨ q q → r p ∧ s→ t ∼ r ∼ q → u ∧ s ∴ t To see that this is valid, we start with the hypotheses and build from there: p ∨ q (1) q → r (2) p ∧ s→ t (3) ∼ r (4) ∼ q → u ∧ s (5) ∼ q (6) Modus Tollens using (2) and (4) p (7) Eliminiation using (1) and (6) u ∧ s (8) Modus Ponens using (5) and (6) s (9) Specialization using (8) p ∧ s (10) Conjunction using (7) and (9) t (11) Modus Ponens using (10) and (3) � 22 Statements and Statement Variables Negation, Disjunction, Conjunction Negation Disjunctions Conjunctions Xor English Commentary Statement Forms Basic Definition Order of Operations Truth Tables Logical Equivalence Definition Double Negative DeMorgan's Laws Tautologies and Contradictions Summary of Common Logical Equivalences Working with Logical Equivalences Conditional Statements Introduction and Definition Rewriting using Not and Or Negating a Conditional Converse Contrapositive Inverse of a Conditional A Fun Diagram Biconditionals Necessary and Sufficient Arguments and Argument Forms Arguments Argument Forms Valid and Invalid Arguments Modus Ponens and Modus Tollens Rules of Inference Using Rules of Inference