Introduction to Logic and Compound Statements

 
 
Logic
 
 
An 
argument
 is a sequence of statements aimed at
demonstrating the truth of an assertion.
 
The assertion at the end of the sequence is called the
conclusion
, and the preceding statements are called
premises
.
 
To have confidence in the conclusion that you draw from
an argument, you must be sure that the premises are
acceptable on their own merits or follow from other
statements that are known to be true.
 
Logical Form and Logical Equivalence
 
 
Fill in the blanks below so that argument (b) has the same
form as argument (a). Then represent the common form of
the arguments using letters to stand for component
sentences.
 
a
.
 
I
f
 
J
a
n
e
 
i
s
 
a
 
m
a
t
h
 
m
a
j
o
r
 
o
r
 
J
a
n
e
 
i
s
 
a
 
c
o
m
p
u
t
e
r
 
s
c
i
e
n
c
e
 
 
 
 
m
a
j
o
r
,
 
t
h
e
n
 
J
a
n
e
 
w
i
l
l
 
t
a
k
e
 
M
a
t
h
 
1
5
0
.
 
J
a
n
e
 
i
s
 
a
 
c
o
m
p
u
t
e
r
 
 
 
 
s
c
i
e
n
c
e
 
m
a
j
o
r
.
 
T
h
e
r
e
f
o
r
e
,
 
J
a
n
e
 
w
i
l
l
 
t
a
k
e
 
M
a
t
h
 
1
5
0
.
b
.
 
I
f
 
l
o
g
i
c
 
i
s
 
e
a
s
y
 
o
r
 
 
 
 
 
 
 
 
 
 
,
 
t
h
e
n
 
 
 
 
 
 
 
 
 
 
.
 
 
 
 
I
 
w
i
l
l
 
s
t
u
d
y
 
h
a
r
d
.
 
 
 
 
T
h
e
r
e
f
o
r
e
,
 
I
 
w
i
l
l
 
g
e
t
 
a
n
 
A
 
i
n
 
t
h
i
s
 
c
o
u
r
s
e
.
 
Example 1 – 
Identifying Logical Form
 
Example 1 – 
Solution
 
1. I (will) study hard.
 
2. I will get an A in this course.
    
Common form: 
If 
p
 or 
q
, then
 r
.
                             
q
.
                             Therefore, 
r
.
 
 
Statements
 
In any mathematical theory, new terms are defined by
using those that have been previously defined. However,
this process has to start somewhere.
 
In logic, the words 
statements
, 
true
, and 
false
 are the initial
undefined terms.
 
Definition
: A 
statement
 (or 
proposition
) is a sentence that is
true or false but not both.
 
 
Compound Statements
 
We now introduce three symbols that are used to build more
complicated logical expressions out of simpler ones.
“~” denotes 
not
G
i
v
e
n
 
a
 
s
t
a
t
e
m
e
n
t
 
p
,
 
t
h
e
 
s
e
n
t
e
n
c
e
 
~
p
 
i
s
 
r
e
a
d
 
n
o
t
 
p
 
o
r
I
t
 
i
s
 
n
o
t
 
t
h
e
 
c
a
s
e
 
t
h
a
t
 
p
 
a
n
d
 
i
s
 
c
a
l
l
e
d
 
t
h
e
 
n
e
g
a
t
i
o
n
 
o
f
 
p
 denotes 
and
G
i
v
e
n
 
a
n
o
t
h
e
r
 
s
t
a
t
e
m
e
n
t
 
q
,
 
t
h
e
 
s
e
n
t
e
n
c
e
 
p
 
 
q
 
i
s
 
r
e
a
d
 
p
a
n
d
 
q
 
a
n
d
 
i
s
 
c
a
l
l
e
d
 
t
h
e
 
c
o
n
j
u
n
c
t
i
o
n
 
o
f
 
p
 
a
n
d
 
q
.
denotes 
or
T
h
e
 
s
e
n
t
e
n
c
e
 
p
 
 
q
 
i
s
 
r
e
a
d
 
p
 
o
r
 
q
 
a
n
d
 
i
s
 
c
a
l
l
e
d
 
t
h
e
d
i
s
j
u
n
c
t
i
o
n
 
o
f
 
p
 
a
n
d
 
q
.
 
 
Compound Statements
 
I
n
 
e
x
p
r
e
s
s
i
o
n
s
 
t
h
a
t
 
i
n
c
l
u
d
e
 
t
h
e
 
s
y
m
b
o
l
 
~
 
a
s
 
w
e
l
l
 
a
s
 
 
o
r
 
,
t
h
e
 
o
r
d
e
r
 
o
f
 
o
p
e
r
a
t
i
o
n
s
 
s
p
e
c
i
f
i
e
s
 
t
h
a
t
 
~
 
i
s
 
p
e
r
f
o
r
m
e
d
 
f
i
r
s
t
.
 
In other words, ~ has higher precedence than 
 and 
.
For instance, ~
p
 
 
q
 = (~
p
) 
 
q
.
 
 
Compound Statements
 
In logical expressions, as in ordinary algebraic expressions,
the order of operations can be overridden through the use
of parentheses.
Thus ~(
p
 
 
q
) represents the negation of the conjunction
of 
p
 and 
q
.
In this, as in most treatments of logic, the symbols 
 and 
are considered coequal in order of operation, and an
expression such as 
p
 
 
q
 
 
r
 is considered ambiguous.
This expression must be written as either (
p
 
 
q
) 
 
r
 or
 
p
 
 (
q
 
 
r
) to have meaning.
 
Example 2 – 
Translating from English to Symbols: But and Neither-Nor
 
Write each of the following sentences symbolically, letting
h
 = “It is hot” and 
s
 = “It is sunny.”
a
.
 
I
t
 
i
s
 
n
o
t
 
h
o
t
 
b
u
t
 
i
t
 
i
s
 
s
u
n
n
y
.
b
.
 
I
t
 
i
s
 
n
e
i
t
h
e
r
 
h
o
t
 
n
o
r
 
s
u
n
n
y
.
 
Solution:
a
.
 
T
h
e
 
g
i
v
e
n
 
s
e
n
t
e
n
c
e
 
i
s
 
e
q
u
i
v
a
l
e
n
t
 
t
o
 
I
t
 
i
s
 
n
o
t
 
h
o
t
 
a
n
d
 
i
t
 
i
s
 
 
 
 
s
u
n
n
y
,
 
w
h
i
c
h
 
c
a
n
 
b
e
 
w
r
i
t
t
e
n
 
s
y
m
b
o
l
i
c
a
l
l
y
 
a
s
 
~
h
 
 
s
.
 
b
.
 
T
o
 
s
a
y
 
i
t
 
i
s
 
n
e
i
t
h
e
r
 
h
o
t
 
n
o
r
 
s
u
n
n
y
 
m
e
a
n
s
 
t
h
a
t
 
i
t
 
i
s
 
n
o
t
 
h
o
t
 
 
 
 
a
n
d
 
i
t
 
i
s
 
n
o
t
 
s
u
n
n
y
.
 
T
h
e
r
e
f
o
r
e
,
 
t
h
e
 
g
i
v
e
n
 
s
e
n
t
e
n
c
e
 
c
a
n
 
b
e
 
 
 
 
w
r
i
t
t
e
n
 
s
y
m
b
o
l
i
c
a
l
l
y
 
a
s
 
~
h
 
 
~
s
.
 
 
Truth Values
 
In Example 2 we built compound sentences out of
component sentences and the terms 
not
, 
and
, and 
or
.
 
I
f
 
s
u
c
h
 
s
e
n
t
e
n
c
e
s
 
a
r
e
 
t
o
 
b
e
 
s
t
a
t
e
m
e
n
t
s
,
 
h
o
w
e
v
e
r
,
 
t
h
e
y
 
m
u
s
t
h
a
v
e
 
w
e
l
l
-
d
e
f
i
n
e
d
 
t
r
u
t
h
 
v
a
l
u
e
s
t
h
e
y
 
m
u
s
t
 
b
e
 
e
i
t
h
e
r
 
t
r
u
e
o
r
 
f
a
l
s
e
.
 
We now define such compound sentences as statements
by specifying their truth values in terms of the statements
that compose them.
 
 
S
t
a
t
e
m
e
n
t
 
F
o
r
m
:
 
a
n
 
e
x
p
r
e
s
s
i
o
n
 
m
a
d
e
 
u
p
 
o
f
 
a
b
s
t
r
a
c
t
s
t
a
t
e
m
e
n
t
 
v
a
r
i
a
b
l
e
s
 
(
p
,
 
q
,
 
r
,
 
e
t
c
.
)
 
a
n
d
 
l
o
g
i
c
a
l
 
c
o
n
n
e
c
t
i
v
e
s
(
~
,
 
,
 
,
 
e
t
c
)
.
 
Statement Form: 
~
p
 
 
q
 
Statement: 
It is not hot and it is sunny
 
Statement: 
~
p
 
 
q 
where 
p
 = “It is hot” and 
q
 = “It is sunny.”
 
T
r
u
t
h
 
t
a
b
l
e
:
 
f
o
r
 
s
t
a
t
e
m
e
n
t
 
f
o
r
m
s
;
 
a
l
l
 
c
o
m
b
i
n
a
t
i
o
n
s
 
o
f
 
t
r
u
t
h
v
a
l
u
e
s
 
f
o
r
 
s
t
a
t
e
m
e
n
t
 
v
a
r
i
a
b
l
e
s
.
Statement Form
 
 
Truth Table
 
Truth Table for ~
p
 
Truth Table for 
p
 
 
q
 
Truth Table for 
p
 
 
q
 
 
Construct the truth table for the statement form
(
p
 
 
q
) 
 ~(
p
 
 
q
).
 
Note that when 
or
 is used in its exclusive sense, the
statement “
p
 or 
q
” means “
p
 or 
q
 but not both” or “
p
 or 
q
and not both 
p
 and 
q
,” which translates into symbols as
(
p
 
 
q
) 
 ~(
p
 
 
q
).
 
This is sometimes abbreviated
 
Example 4 – 
Truth Table for Exclusive Or
 
Example 4 – 
Solution
 
Set up columns labeled 
p
, 
q
, 
p
 
 
q
, 
p
 
 
q
, ~(
p
 
 
q
), and
(
p
 
 
q
) 
 ~(
p
 
 
q
).
 
 
 
 
 
 
Fill in the 
p
 and 
q
 columns with all the logically possible
combinations of T’s and F’s. Then use the truth tables for 
and 
 to fill in the 
p
 
 
q
 and 
p
 
 
q
 columns with the
appropriate truth values.
T
r
u
t
h
 
T
a
b
l
e
 
f
o
r
 
E
x
c
l
u
s
i
v
e
 
O
r
:
 
(
p
 
 
q
)
 
 
~
(
 
p
 
 
q
)
 
Example 4 – 
Solution
 
Next fill in the ~(
p
 
 
q
) column by taking the opposites of
the truth values for 
p
 
 
q
.
 
Finally, fill in the (
p
 
 
q
) 
 ~(
p
 
 
q
) column by considering
the truth table for an 
and
 statement together with the
computed truth values for 
p
 
 
q
 and ~(
p
 
 
q
).
cont’d
T
r
u
t
h
 
T
a
b
l
e
 
f
o
r
 
E
x
c
l
u
s
i
v
e
 
O
r
:
 
(
p
 
 
q
)
 
 
~
(
 
p
 
 
q
)
 
 
Logical Equivalence
 
 
Logical Equivalence
 
The statements
               6 is greater than 2 and 2 is less than 6
 
are two different ways of saying the same thing. Why?
Because of the definition of the phrases 
greater than 
and
less than
. By contrast, although the statements
(1) Dogs bark and cats meow
and
(2) Cats meow and dogs bark
are also two different ways of saying the same thing, the
reason has nothing to do with the definition of the words.
 
 
Logical Equivalence
 
It has to do with the logical form of the statements.
 
Any two statements whose logical forms are related in the
same way as (1) and (2) would either both be true or both
be false.
 
You can see this by examining the following truth table,
where the statement variables 
p
 and 
q
 are substituted for
the component statements “Dogs bark” and “Cats meow,”
respectively.
 
 
Logical Equivalence
 
The table shows that for each combination of truth values
for 
p
 and 
q
, 
p
 
 q 
is true when, and only when, 
q
 
 
p
 is true.
 
In such a case, the statement
forms are called 
logically
equivalent
, and we say
that (1) and (2) are
logically equivalent
statements
.
 
 
 
 
 
 
 
T
e
s
t
i
n
g
 
W
h
e
t
h
e
r
 
T
w
o
 
S
t
a
t
e
m
e
n
t
 
F
o
r
m
s
 
P
 
a
n
d
 
Q
 
A
r
e
L
o
g
i
c
a
l
l
y
 
E
q
u
i
v
a
l
e
n
t
 
1
.
 
C
o
n
s
t
r
u
c
t
 
a
 
t
r
u
t
h
 
t
a
b
l
e
 
w
i
t
h
 
o
n
e
 
c
o
l
u
m
n
 
f
o
r
 
t
h
e
 
t
r
u
t
h
 
 
 
 
v
a
l
u
e
s
 
o
f
 
P
 
a
n
d
 
a
n
o
t
h
e
r
 
c
o
l
u
m
n
 
f
o
r
 
t
h
e
 
t
r
u
t
h
 
v
a
l
u
e
s
 
o
f
 
Q
.
 
Logical Equivalence
 
 
Logical Equivalence
 
2
.
 
C
h
e
c
k
 
e
a
c
h
 
c
o
m
b
i
n
a
t
i
o
n
 
o
f
 
t
r
u
t
h
 
v
a
l
u
e
s
 
o
f
 
t
h
e
 
s
t
a
t
e
m
e
n
t
 
 
 
 
v
a
r
i
a
b
l
e
s
 
t
o
 
s
e
e
 
w
h
e
t
h
e
r
 
t
h
e
 
t
r
u
t
h
 
v
a
l
u
e
 
o
f
 
P
 
i
s
 
t
h
e
 
s
a
m
e
 
 
 
 
a
s
 
t
h
e
 
t
r
u
t
h
 
v
a
l
u
e
 
o
f
 
Q
.
 
 
 
 
 
a
.
 
I
f
 
i
n
 
e
a
c
h
 
r
o
w
 
t
h
e
 
t
r
u
t
h
 
v
a
l
u
e
 
o
f
 
P
 
i
s
 
t
h
e
 
s
a
m
e
 
a
s
 
t
h
e
 
 
 
 
 
 
 
 
t
r
u
t
h
 
v
a
l
u
e
 
o
f
 
Q
,
 
t
h
e
n
 
P
 
a
n
d
 
Q
 
a
r
e
 
l
o
g
i
c
a
l
l
y
 
e
q
u
i
v
a
l
e
n
t
.
 
 
 
 
b
.
 
I
f
 
i
n
 
s
o
m
e
 
r
o
w
 
P
 
h
a
s
 
a
 
d
i
f
f
e
r
e
n
t
 
t
r
u
t
h
 
v
a
l
u
e
 
f
r
o
m
 
Q
,
 
 
 
 
 
 
 
 
t
h
e
n
 
P
 
a
n
d
 
Q
 
a
r
e
 
n
o
t
 
l
o
g
i
c
a
l
l
y
 
e
q
u
i
v
a
l
e
n
t
.
 
Example 6 – 
Double Negative Property: 
(
p
)
 
 p
 
Construct a truth table to show that the negation of the
negation of a statement is logically equivalent to the
statement, annotating the table with a sentence of
explanation.
 
Solution:
 
 
Logical Equivalence
 
There are two ways to show that statement forms 
P
 and 
Q
are 
not
 logically equivalent.
1.
Use a truth table to find rows for which their truth values
differ.
2.
Find concrete statements for each of the two forms, one
of which is true and the other of which is false.
 
The next example illustrates both of these ways.
 
 
Show that the statement forms ~(
p
 
 
q
) and ~
p
 
 ~
q
 are not
logically equivalent.
 
Solution:
a
.
 
T
h
i
s
 
m
e
t
h
o
d
 
u
s
e
s
 
a
 
t
r
u
t
h
 
t
a
b
l
e
 
a
n
n
o
t
a
t
e
d
 
w
i
t
h
 
a
 
s
e
n
t
e
n
c
e
 
 
 
 
o
f
 
e
x
p
l
a
n
a
t
i
o
n
.
Example 7 – 
Showing Nonequivalence
 
Example 7 – 
Solution
 
b
.
 
T
h
i
s
 
m
e
t
h
o
d
 
u
s
e
s
 
a
n
 
e
x
a
m
p
l
e
 
t
o
 
s
h
o
w
 
t
h
a
t
 
~
(
p
 
 
q
)
 
a
n
d
 
 
 
 
~
p
 
 
~
q
 
a
r
e
 
n
o
t
 
l
o
g
i
c
a
l
l
y
 
e
q
u
i
v
a
l
e
n
t
.
 
L
e
t
 
p
 
b
e
 
t
h
e
 
 
 
 
s
t
a
t
e
m
e
n
t
 
0
 
<
 
1
 
a
n
d
 
l
e
t
 
q
 
b
e
 
t
h
e
 
s
t
a
t
e
m
e
n
t
 
1
 
<
 
0
.
 
    Then
 
    which is true.
 
    On the other hand,
 
    which is false.
cont’d
 
Example 7 – 
Solution
 
    This example shows that there are concrete statements
    you can substitute for 
p
 and 
q
 to make one of the
    statement forms true and the other false.
 
    
Therefore, the statement forms are not logically
    equivalent.
cont’d
 
 
Logical Equivalence
 
T
h
e
 
f
o
l
l
o
w
i
n
g
 
t
w
o
 
l
o
g
i
c
a
l
 
e
q
u
i
v
a
l
e
n
c
e
s
 
a
r
e
 
k
n
o
w
n
 
a
s
D
e
 
M
o
r
g
a
n
s
 
l
a
w
s
.
 
 
Write negations for each of the following statements:
a
.
 
J
o
h
n
 
i
s
 
6
 
f
e
e
t
 
t
a
l
l
 
a
n
d
 
h
e
 
w
e
i
g
h
s
 
a
t
 
l
e
a
s
t
 
2
0
0
 
p
o
u
n
d
s
.
b
.
 
T
h
e
 
b
u
s
 
w
a
s
 
l
a
t
e
 
o
r
 
T
o
m
s
 
w
a
t
c
h
 
w
a
s
 
s
l
o
w
.
 
Solution:
a
.
 
J
o
h
n
 
i
s
 
n
o
t
 
6
 
f
e
e
t
 
t
a
l
l
 
o
r
 
h
e
 
w
e
i
g
h
s
 
l
e
s
s
 
t
h
a
n
 
2
0
0
 
p
o
u
n
d
s
.
 
b
.
 
T
h
e
 
b
u
s
 
w
a
s
 
n
o
t
 
l
a
t
e
 
a
n
d
 
T
o
m
s
 
w
a
t
c
h
 
w
a
s
 
n
o
t
 
s
l
o
w
.
Since the statement “neither 
p
 nor 
q
” means the same as
“~
p
 and ~
q
,” an alternative answer for (b) is “Neither was
the bus late nor was Tom’s watch slow.”
Example 9 – 
Applying De Morgan’s Laws
 
 
According to De Morgan’s laws, the negation of
                             p
: Jim is tall and Jim is thin
is                        ~
p
:
 
Jim is not tall or Jim is not thin
 
because the negation of an 
and
 statement is the 
or
 statement
in which the two components are negated.
 
Unfortunately, a potentially confusing aspect of the English
language can arise when you are taking negations of this
kind. Note that statement 
p
 can be written more compactly as
                           p
:
 
Jim is tall and thin.
Example 11 –
 A Cautionary Example
 
Example 11 –
 A Cautionary Example
 
When it is so written, another way to negate it is
                    ~
(p
)
:
 
Jim is not tall and thin.
But in this form the negation looks like an 
and 
statement
.
 
Doesn’t that violate De Morgan’s laws?
 
Actually no violation occurs. The reason is that in formal
logic the words 
and
 and 
or
 are allowed only between
complete statements, not between sentence fragments.
cont’d
 
 
Example 11 –
 A Cautionary Example
 
One lesson to be learned from this example is that when
you apply De Morgan’s laws, you must have complete
statements on either side of each 
and
 and on either side of
each 
or
.
 
cont’d
 
Tautologies and Contradictions
 
 
 
 
 
 
 
 
 
According to this definition, the truth of a tautological statement and the
falsity of a contradictory statement are due to the logical structure of the
statements themselves and are independent of the meanings of the
statements.
 
A statement form is 
satisfiable
 if it is not a contradiction.
 
Example 13 – 
Logical Equivalence Involving Tautologies and Contradictions
 
I
f
 
t
 
i
s
 
a
 
t
a
u
t
o
l
o
g
y
 
a
n
d
 
c
 
i
s
 
a
 
c
o
n
t
r
a
d
i
c
t
i
o
n
,
 
s
h
o
w
 
t
h
a
t
p
 
 
t
 
 
p
 
a
n
d
 
p
 
 
c
 
 
c
.
 
Solution:
 
 
Summary of Logical Equivalences
 
A number of logical equivalences are summarized in
Theorem 2.1.1 for future reference.
 
 
Use Theorem 2.1.1 to verify the logical equivalence
 
 
Solution:
Use the laws of Theorem 2.1.1 to replace sections of the
statement form on the left by logically equivalent
expressions.
 
Each time you do this, you obtain a logically equivalent
statement form.
Example 14 –
 Simplifying Statement Forms
 
Continue making replacements until you obtain the
statement form on the right.
 
Example 14 – 
Solution
cont’d
Slide Note
Embed
Share

Understanding logic, statements, and compound statements, starting from undefined terms like statements, true, and false to building complex logical expressions using symbols such as ~, &, and |. Exploring how order of operations impacts logical expressions and how to translate English sentences into symbolic form. Discussion on statement forms and truth tables in logic.


Uploaded on Aug 03, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Logic 1

  2. Statements In any mathematical theory, new terms are defined by using those that have been previously defined. However, this process has to start somewhere. In logic, the words statements, true, and false are the initial undefined terms. Definition: A statement (or proposition) is a sentence that is true or false but not both. 5

  3. Compound Statements We now introduce three symbols that are used to build more complicated logical expressions out of simpler ones. ~ denotes not Given a statement p, the sentence ~p is read not p or It is not the case that p and is called the negation of p denotes and Given another statement q, the sentence p q is read p and q and is called the conjunction of p and q. denotes or The sentence p q is read p or q and is called the disjunction of p and q. 6

  4. Compound Statements In expressions that include the symbol ~ as well as or , the order of operations specifies that ~ is performed first. In other words, ~ has higher precedence than and . For instance, ~p q = (~p) q. 7

  5. Compound Statements In logical expressions, as in ordinary algebraic expressions, the order of operations can be overridden through the use of parentheses. Thus ~(p q) represents the negation of the conjunction of p and q. In this, as in most treatments of logic, the symbols and are considered coequal in order of operation, and an expression such as p q r is considered ambiguous. This expression must be written as either (p q) r or p (q r) to have meaning. 8

  6. Example 2 Translating from English to Symbols: But and Neither-Nor Write each of the following sentences symbolically, letting h= It is hot and s= It is sunny. a. It is not hot but it is sunny. b. It is neither hot nor sunny. Solution: a.The given sentence is equivalent to It is not hot and it is sunny, which can be written symbolically as ~h s. b. To say it is neither hot nor sunny means that it is not hot and it is not sunny. Therefore, the given sentence can be written symbolically as ~h ~s. 9

  7. Statement Form Statement Form: an expression made up of abstract statement variables (p, q, r, etc.) and logical connectives (~, , ,etc). Statement Form: ~p q Statement: It is not hot and it is sunny Statement: ~p q where p= It is hot and q= It is sunny. Truth table: for statement forms; all combinations of truth values for statement variables. 11

  8. Truth Table Truth Table for ~p Truth Table for p q Truth Table for p q 12

  9. Example 4 Truth Table for Exclusive Or Construct the truth table for the statement form (p q) ~(p q). Note that when or is used in its exclusive sense, the statement p or q means p or qbut not both or p or q and not both p and q, which translates into symbols as (p q) ~(p q). This is sometimes abbreviated 13

  10. Logical Equivalence 16

  11. Logical Equivalence The statements 6 is greater than 2 and 2 is less than 6 are two different ways of saying the same thing. Why? Because of the definition of the phrases greater than and less than. By contrast, although the statements (1) Dogs bark and cats meow and (2) Cats meow and dogs bark are also two different ways of saying the same thing, the reason has nothing to do with the definition of the words. 17

  12. Logical Equivalence It has to do with the logical form of the statements. Any two statements whose logical forms are related in the same way as (1) and (2) would either both be true or both be false. You can see this by examining the following truth table, where the statement variables p and q are substituted for the component statements Dogs bark and Cats meow, respectively. 18

  13. Logical Equivalence The table shows that for each combination of truth values for p and q, p q is true when, and only when, q p is true. In such a case, the statement forms are called logically equivalent, and we say that (1) and (2) are logically equivalent statements. 19

  14. Logical Equivalence Testing Whether Two Statement Forms P and Q Are Logically Equivalent 1. Construct a truth table with one column for the truth values of P and another column for the truth values of Q. 20

  15. Logical Equivalence 2. Check each combination of truth values of the statement variables to see whether the truth value of P is the same as the truth value of Q. a. If in each row the truth value of P is the same as the truth value of Q, then P and Q are logically equivalent. b. If in some row P has a different truth value from Q, then P and Q are not logically equivalent. 21

  16. Example 6 Double Negative Property: (p) p Construct a truth table to show that the negation of the negation of a statement is logically equivalent to the statement, annotating the table with a sentence of explanation. Solution: 22

  17. Logical Equivalence There are two ways to show that statement forms P and Q are not logically equivalent. 1. Use a truth table to find rows for which their truth values differ. 2. Find concrete statements for each of the two forms, one of which is true and the other of which is false. The next example illustrates both of these ways. 23

  18. Example 7 Showing Nonequivalence Show that the statement forms ~(p q) and ~p ~q are not logically equivalent. Solution: a. This method uses a truth table annotated with a sentence of explanation. 24

  19. Example 7 Solution cont d b. This method uses an example to show that ~(p q) and ~p ~q are not logically equivalent. Let p be the statement 0 < 1 and let qbe the statement 1 < 0. Then which is true. On the other hand, which is false. 25

  20. Example 7 Solution cont d This example shows that there are concrete statements you can substitute for p and q to make one of the statement forms true and the other false. Therefore, the statement forms are not logically equivalent. 26

  21. Logical Equivalence The following two logical equivalences are known as De Morgan s laws. 27

  22. Example 9 Applying De Morgans Laws Write negations for each of the following statements: a. John is 6 feet tall and he weighs at least 200 pounds. b.The bus was late or Tom s watch was slow. Solution: a. John is not 6 feet tall or he weighs less than 200 pounds. b.The bus was not late and Tom s watch was not slow. Since the statement neither p nor q means the same as ~p and ~q, an alternative answer for (b) is Neither was the bus late nor was Tom s watch slow. 28

  23. Example 11 A Cautionary Example According to De Morgan s laws, the negation of p: Jim is tall and Jim is thin is ~p:Jim is not tall or Jim is not thin because the negation of an and statement is the or statement in which the two components are negated. Unfortunately, a potentially confusing aspect of the English language can arise when you are taking negations of this kind. Note that statement p can be written more compactly as p :Jim is tall and thin. 29

  24. Example 11 A Cautionary Example cont d When it is so written, another way to negate it is ~(p ):Jim is not tall and thin. But in this form the negation looks like an and statement. Doesn t that violate De Morgan s laws? Actually no violation occurs. The reason is that in formal logic the words and and or are allowed only between complete statements, not between sentence fragments. 30

  25. Example 11 A Cautionary Example cont d One lesson to be learned from this example is that when you apply De Morgan s laws, you must have complete statements on either side of each and and on either side of each or. 31

  26. Tautologies and Contradictions According to this definition, the truth of a tautological statement and the falsity of a contradictory statement are due to the logical structure of the statements themselves and are independent of the meanings of the statements. A statement form is satisfiable if it is not a contradiction. 32

  27. Example 13 Logical Equivalence Involving Tautologies and Contradictions If t is a tautology and c is a contradiction, show that p t p and p c c. Solution: 33

  28. Summary of Logical Equivalences A number of logical equivalences are summarized in Theorem 2.1.1 for future reference. 34

  29. Example 14 Simplifying Statement Forms Use Theorem 2.1.1 to verify the logical equivalence Solution: Use the laws of Theorem 2.1.1 to replace sections of the statement form on the left by logically equivalent expressions. Each time you do this, you obtain a logically equivalent statement form. 35

  30. Example 14 Solution cont d Continue making replacements until you obtain the statement form on the right. 36

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#