DISCRETE_MATHEMATICS___CHEN.PDF

(2463 KB) Pobierz
dm01-ls
DISCRETE MATHEMATICS
W W L CHEN
W W L Chen, 1982.
This work is available free, in the hope that it will be useful.
Any part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including
photocopying, recording, or any information storage and retrieval system, with or without permission from the author.
c
Chapter 1
LOGIC AND SETS
1.1. Sentences
In this section, we look at sentences, their truth or falsity, and ways of combining or connecting sentences
to produce new sentences.
A sentence (or proposition) is an expression which is either true or false. The sentence “2+ 2= 4”
is true, while the sentence “ π is rational” is false. It is, however, not the task of logic to decide whether
any particular sentence is true or false. In fact, there are many sentences whose truth or falsity nobody
has yet managed to establish; for example, the famous Goldbach conjecture that “every even number
greater than 2is a sum of two primes”.
There is a defect in our definition. It is sometimes very di*cult, under our definition, to determine
whether or not a given expression is a sentence. Consider, for example, the expression “I am telling a
lie”; am I?
Since there are expressions which are sentences under our definition, we proceed to discuss ways of
connecting sentences to form new sentences.
Let p and q denote sentences.
Definition.
(CONJUNCTION) We say that the sentence p
∧
q ( p and q ) is true if the two sentences
p , q are both true, and is false otherwise.
Example 1.1.1.
The sentence “2+ 2= 4 and 2+ 3 = 5” is true.
Example 1.1.2.
The sentence “2+ 2= 4 and π is rational” is false.
Definition.
(DISJUNCTION) We say that the sentence p
∨
q ( p or q ) is true if at least one of two
sentences p , q is true, and is false otherwise.
Example 1.1.3.
The sentence “2+ 2= 2or 1 + 3 = 5” is false.
†
This chapter was first usedin lectures given by the author at Imperial College, University of London, in 1982.
1–2
W W L Chen : Discrete Mathematics
Example 1.1.4.
The sentence “2+ 2= 4 or π is rational” is true.
q is true, we may assume that the sentence p is false and use
this to deduce that the sentence q is true in this case. For if the sentence p is true, our argument is
already complete, never mind the truth or falsity of the sentence q .
To prove that a sentence p
∨
Definition. (NEGATION) We say that the sentence p (not p ) is true if the sentence p is false, and
is false if the sentence p is true.
Example 1.1.5.
The negation of the sentence “2+ 2= 4” is the sentence “2+ 2
= 4”.
Example 1.1.6.
The negation of the sentence “ π is rational” is the sentence “ π is irrational”.
q (if p , then q ) is true if the sentence
p is false or if the sentence q is true or both, and is false otherwise.
(CONDITIONAL) We say that the sentence p
→
q is false precisely when the sentence p is
true and the sentence q is false. To understand this, note that if we draw a false conclusion from a true
assumption, then our argument must be faulty. On the other hand, if our assumption is false or if our
conclusion is true, then our argument may still be acceptable.
It is convenient to realize that the sentence p
→
Example 1.1.7.
The sentence “if 2+ 2= 2, then 1 + 3 = 5” is true, because the sentence “2+ 2= 2”
is false.
Example 1.1.8.
The sentence “if 2+ 2= 4, then π is rational” is false.
Example 1.1.9.
The sentence “if π is rational, then 2+ 2= 4” is true.
Definition.
(DOUBLE CONDITIONAL) We say that the sentence p
↔
q ( p if and only if q ) is true
if the two sentences p , q are both true or both false, and is false otherwise.
Example 1.1.10.
The sentence “2+ 2= 4 if and only if π is irrational” is true.
Example 1.1.11.
The sentence “2+ 2
= 4 if and only if π is rational” is also true.
If we use the letter T to denote “true” and the letter F to denote “false”, then the above five
definitions can be summarized in the following “truth table”:
p q p
∧
q p
∨
q p p
→
q p
↔
q
T T
T
T F
T
T
T F F
T F
F
F
F T F
T
T
T
F
F F F
F T
T
T
Remark. Note that in logic, “or” can mean “both”. If you ask a logician whether he likes tea or coffee,
do not be surprised if he wants both!
q ) is true if exactly one of the two sentences p , q is true,
and is false otherwise; we have the following “truth table”:
The sentence ( p
∨
q )
∧
( p
∧
p q p
∧
q p
∨
q p
∧
q ( p
∨
q )
∧
( p
∧
q )
T T
T
T
F
F
T F F
T
T
T
F T F
T
T
T
F F F
F
T
F
Remark.
Definition.
Remark.
Example 1.1.12.
584781890.003.png 584781890.004.png
Chapter 1 : Logic and Sets
1–3
1.2. Tautologies and Logical Equivalence
Definition.
A tautology is a sentence which is true on logical ground only.
p ) are both tautologies.
This enables us to generalize the definition of conjunction to more than two sentences, and write, for
example, p
The sentences ( p
∧
( q
∧
r ))
↔
(( p
∧
q )
∧
r ) and ( p
∧
q )
↔
( q
∧
∧
q
∧
r without causing any ambiguity.
p ) are both tautologies.
This enables us to generalize the definition of disjunction to more than two sentences, and write, for
example, p
The sentences ( p
∨
( q
∨
r ))
↔
(( p
∨
q )
∨
r ) and ( p
∨
q )
↔
( q
∨
∨
q
∨
r without causing any ambiguity.
Example 1.2.3.
The sentence p
∨
p is a tautology.
Example 1.2.4.
The sentence ( p
→
q )
↔
( q
→
p ) is a tautology.
Example 1.2.5.
The sentence ( p
→
q )
↔
( p
∨
q ) is a tautology.
Example 1.2.6.
The sentence ( p
↔
q )
↔
(( p
∨
q )
∧
( p
∧
q )) is a tautology; we have the following “truth
table”:
p q p
↔
q ( p
↔
q ) ( p
∨
q )
∧
( p
∧
q ) ( p
↔
q )
↔
(( p
∨
q )
∧
( p
∧
q ))
T T
T
F
F
T
T F F
T
T
T
F T
F
T
T
T
F F
T
F
F
T
The following are tautologies which are commonly used. Let p , q and r denote sentences.
DISTRIBUTIVE LAW. The following sentences are tautologies:
(a) ( p
∧
( q
∨
r ))
↔
(( p
∧
q )
∨
( p
∧
r )) ;
(b) ( p
∨
( q
∧
r ))
↔
(( p
∨
q )
∧
( p
∨
r )) .
DE MOR GA N L A W. The following sentences are tautologies:
(a) ( p
∧
q )
↔
( p
∨
q ) ;
(b) ( p
∨
q )
↔
( p
∧
q ) .
INFERENCE LAW. The following sentences are tautologies:
(a) (MODUS PONENS) ( p
∧
( p
→
q ) )
→
q ;
(b) (MODUS TOLLENS) (( p
→
q )
∧
q )
→
p;
(c) (LAW OF SYLLOGISM) (( p
→
q )
∧
( q
→
r ))
→
( p
→
r ) .
These tautologies can all be demonstrated by truth tables. However, let us try to prove the first
Distributive law here.
Suppose first of all that the sentence p
∧
( q
∨
r ) is true. Then the two sentences p , q
∨
r are both
r is true, at least one of the two sentences q , r is true. Without loss of
generality, assume that the sentence q is true. Then the sentence p
∨
∧
q is true. It follows that the sentence
( p
∧
r ) is true.
Suppose now that the sentence ( p
∨
( p
∧
∧
q )
∨
( p
∧
r ) is true. Then at least one of the two sentences ( p
∧
q ),
( p
∧
r ) is true. Without loss of generality, assume that the sentence p
∧
q is true. Then the two sentences
p , q are both true. It follows that the sentence q
∨
r is true, and so the sentence p
∧
( q
∨
r ) is true.
r ) are either both true or
both false, as the truth of one implies the truth of the other. It follows that the double conditional
( p
It now follows that the two sentences p
∧
( q
∨
r ) and ( p
∧
q )
∨
( p
∧
∧
( q
∨
r ))
↔
(( p
∧
q )
∨
( p
∧
r )) is a tautology.
Example 1.2.1.
Example 1.2.2.
true. Since the sentence q
q )
584781890.005.png 584781890.006.png
1–4
W W L Chen : Discrete Mathematics
Definition.
We say that two sentences p and q are logically equivalent if the sentence p
↔
q is a
tautology.
Example 1.2.7.
The sentences p
→
q and q
→
p are logically equivalent. The latter is known as the
contrapositive of the former.
Remark.
The sentences p
→
q and q
→
p are not logically equivalent. The latter is known as the
converse of the former.
1.3. Sentential Functions and Sets
In many instances, we have sentences, such as “ x is even”, which contains one or more variables. We
shall call them sentential functions (or propositional functions).
Let us concentrate on our example “ x is even”. This sentence is true for certain values of x , and is
false for others. Various questions arise:
(1) What values of x do we permit?
(2) Is the statement true for all such values of x in question?
(3) Is the statement true for some such values of x in question?
To answer the first of these questions, we need the notion of a universe. We therefore need to
consider sets.
We shall treat the word “set” as a word whose meaning everybody knows. Sometimes we use the
synonyms “class” or “collection”. However, note that in some books, these words may have different
meanings!
The important thing about a set is what it contains. In other words, what are its members? Does
it have any?
If P is a set and x is an element of P , we write x
P .
A set is usually described in one of the two following ways:
(1) by enumeration, e.g.
∈
denotes the set consisting of the numbers 1 , 2 , 3 and nothing else;
(2) by a defining property (sentential function) p ( x ). Here it is important to define a universe
U to which all the x have to belong. We then write P =
{
1 , 2 , 3
}
{
x : x
∈
U and p ( x ) is true
}
or, simply,
P =
.
The set with no elements is called the empty set and denoted by
x : p ( x )
}
∅
.
Example 1.3.1.
N
=
{
1 , 2 , 3 , 4 , 5 , ...
}
is called the set of natural numbers.
Example 1.3.2.
Z
=
{
...,
−
2 ,
−
1 , 0 , 1 , 2 ,...
}
is called the set of integers.
Example 1.3.3.
{
x : x
∈ N
and
−
2 <x< 2
}
=
{
1
}
.
Example 1.3.4.
{
x : x
∈ Z
and
−
2 <x< 2
}
=
{−
1 , 0 , 1
}
.
Example 1.3.5.
{
x : x
∈ N
and
−
1 <x< 1
}
=
∅
.
1.4. Set Functions
Suppose that the sentential functions p ( x ), q ( x ) are related to sets P , Q with respect to a given universe,
i.e. P =
{
x : p ( x )
}
and Q =
{
x : q ( x )
}
. We define
(1) the intersection P
∩
Q =
{
x : p ( x )
∧
q ( x )
}
;
(2) the union P
∪
Q =
{
x : p ( x )
∨
q ( x )
}
;
(3) the complement P =
{
x : p ( x )
}
; a nd
(4) the difference P
\
Q =
{
x : p ( x )
∧
q ( x )
}
.
{
584781890.001.png
Chapter 1 : Logic and Sets
1–5
The above are also sets. It is not di*cult to see that
(1) P
∩
Q =
{
x : x
∈
P and x
∈
Q
}
;
(2) P
∪
Q =
{
x : x
∈
P or x
∈
Q
}
;
(3) P =
{
x : x
∈
P
}
; and
.
We say that the set P is a subset of the set Q , denoted by P
\
Q =
{
x : x
∈
P and x
∈
Q
}
⊆
Q or by Q
⊇
P , if every element
of P is an element of Q . In other words, if we have P =
{
x : p ( x )
}
and Q =
{
x : q ( x )
}
with respect to
U .
We say that two sets P and Q are equal, denoted by P = Q , if they contain the same elements, i.e.
if each is a subset of the other, i.e. if P
⊆
Q if and only if the sentence p ( x )
→
q ( x ) is true for all x
∈
P .
Furthermore, we say that P is a proper subset of Q , denoted by P
⊆
Q and Q
⊆
⊂
Q or by Q
⊃
P ,if P
⊆
Q and
P
= Q .
The following results on set functions can be deduced from their analogues in logic.
DISTRIBUTIVE LAW. If P, Q, R are sets, then
(a) P
∩
( Q
∪
R )=( P
∩
Q )
∪
( P
∩
R ) ;
(b) P
∪
( Q
∩
R )=( P
∪
Q )
∩
( P
∪
R ) .
DE MORG A N L A W. If P,Q are sets, then with respect to a universe U,
(a) ( P
∩
Q )= P
∪
Q ;
(b) ( P
∪
Q )= P
∩
Q.
We now try to deduce the first Distributive law for set functions from the first Distributive law for
sentential functions.
Suppose that the sentential functions p ( x ), q ( x ), r ( x ) are related to sets P , Q , R with respect to a
given universe, i.e. P =
{
x : p ( x )
}
, Q =
{
x : q ( x )
}
and R =
{
x : r ( x )
}
. Then
P
∩
( Q
∪
R )=
{
x : p ( x )
∧
( q ( x )
∨
r ( x ))
}
and
( P
∩
Q )
∪
( P
∩
R )=
{
x :( p ( x )
∧
q ( x ))
∨
( p ( x )
∧
r ( x ))
}
.
Suppose that x
∈
P
∩
( Q
∪
R ). Then p ( x )
∧
( q ( x )
∨
r ( x )) is true. By the first Distributive law for
sentential functions, we have that
( p ( x )
∧
( q ( x )
∨
r ( x )))
↔
(( p ( x )
∧
q ( x ))
∨
( p ( x )
∧
r ( x )))
is a tautology. It follows that ( p ( x )
∧
q ( x ))
∨
( p ( x )
∧
r ( x )) is true, so that x
∈
( P
∩
Q )
∪
( P
∩
R ). This
gives
P
∩
( Q
∪
R )
⊆
( P
∩
Q )
∪
( P
∩
R ) .
(1)
Suppose now that x
∈
( P
∩
Q )
∪
( P
∩
R ). Then ( p ( x )
∧
q ( x ))
∨
( p ( x )
∧
r ( x )) is true. It follows from the
first Distributive law for sentential functions that p ( x )
∧
( q ( x )
∨
r ( x )) is true, so that x
∈
P
∩
( Q
∪
R ).
This gives
( P
∩
Q )
∪
( P
∩
R )
⊆
P
∩
( Q
∪
R ) .
(2)
The result now follows on combining (1) and (2).
1.5. Quantifier Logic
Let us return to the example “ x is even” at the beginning of Section 1.3.
Suppose now that we restrict x to lie in the set
Z
of all integers. Then the sentence “ x is even” is
only true for some x in
Z
. It follows that the sentence “some x
∈ Z
are even” is true, while the sentence
“all x
∈ Z
are even” is false.
(4) P
some universe U , then we have P
584781890.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin