Chapter 1 Logic Basic

154

Discrete Mathematics

CHAPTER 1

Translate the statement “The sum of two positive integers is always positive” into a logical
expression.

Consider these statements, of which the first three are premises and the fourth is a valid conclusion.

“All hummingbirds are richly colored.”
“No large birds live on honey.”
“Birds that do not live on honey are dull in color.”

“Hummingbirds are small.”

Let P (x), Q(x), R(x), and S(x) be the statements “x is a hummingbird,” “x is large,” “x lives on
honey,” and “x is richly colored,” respectively. Assuming that the domain consists of all birds,
express the statements in the argument using quantifiers and P (x), Q(x), R(x), and S(x).

Show that the premises "It is not sunny this afternoon and it is colder than yesterday," "We will go swimming only if it is sunny," "If we do not go swimming, then we will take a canoe trip," and "If we take a canoe trip, then we will be home by sunset" lead to the conclusion "We will be home by sunset."

Show that the premises "A student in this class has not read the book," and "Everyone in this class passed the first exam" imply the conclusion "Someone who passed the first exam has not read the book."

Show that the premises “Everyone in this discrete mathematics class has taken a course in
computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken
a course in computer science.”

Show that the premises “A student in this class has not read the book,” and “Everyone in this
class passed the first exam” imply the conclusion “Someone who passed the first exam has not
read the book.”

Give a proof by contradiction of the theorem “If 3n + 2 is odd, then n is odd.”

Prove the fundamental theorem of algebra(by contradiction)

Solution of problems

** Solution of 3: **

Let $p$ be the proposition "It is sunny this afternoon," $q$ the proposition "It is colder than yesterday," $r$ the proposition "We will go swimming," $s$ the proposition "We will take a canoe trip," and $t$ the proposition "We will be home by sunset." Then the premises become $\neg p \wedge q, r \rightarrow p, \neg r \rightarrow s,$ and $s \rightarrow t .$ The conclusion is simply $t .$ We need to give a valid argument with premises $\neg p \wedge q, r \rightarrow p, \neg r \rightarrow s,$ and $s \rightarrow t$ and conclusion $t$

Step Reason

$\neg p \wedge q$
Premise
$\neg p$
Simplification using (1)
$r \rightarrow p$
Premise
$\neg r \quad$
Modus tollens using (2) and (3)
$ \neg r \rightarrow s $
Premis
$s \quad$
Modus ponens using (4) and (5)
$s \rightarrow t$
Premise
$t \quad$ Modus ponens using (6) and (7)

Note that we could have used a truth table to show that whenever each of the four hypotheses is true, the conclusion is also true. However, because we are working with five propositional variables, $p, q, r, s,$ and $t,$ such a truth table would have 32 rows.

Solution of 4:

Let $C(x)$ be $ x$ is in this class, " $B(x)$ be " $x$ has read the book, " and $P(x)$ be " $x$ passed the first exam." The premises are $\exists x(C(x) \wedge \neg B(x))$ and $\forall x(C(x) \rightarrow P(x))$. The conclusion is $\exists x(P(x) \wedge \neg B(x))$. These steps can be used to establish the conclusion from the premises.

Step Reason

$\exists x(C(x) \wedge \neg B(x))$
Premise
$C(a) \wedge \neg B(a) \quad$
Existential instantiation from (1)
$C(a) \quad$
Simplification from (2)
$\text { } \forall x(C(x) \rightarrow P(x)) $
Premise
$C(a) \rightarrow P(a)$
Universal instantiation from (4)
$P(a)$
Modus ponens from (3) and (5)
$\neg B(a)$
Simplification from (2)
$P(a) \wedge \neg B(a) \quad$ Conjunction from (6) and (7)
$\exists x(P(x)\wedge \neg B(x))$

**Solution of 6 : **
Solution: Let $C(x)$ be " $x$ is in this class," $B(x)$ be $ x$ has read the book," and $P(x)$ be " $x$ passed the first exam." The premises are $\exists x(C(x) \wedge \neg x))$ and $\forall x(C(x) \rightarrow P(x)) $. The is$\exists x(P(x) \wedge \neg B(x))$.

Step Reason

$\exists x(C(x) \wedge \neg B(x))$ Premise
$C(a) \wedge \neg B(a)$ Existential instantiation from (1)
$C(a) $ Simplification from (2)
$\forall x(C(x) \rightarrow P(x))$ Premise
$C(a) \rightarrow P(a)$ Universal instantiation from (4)
P(a) Modus ponens from (3) and (5)
$\neg B(a) $ Simplification from (2)
$P(a) \wedge \neg B(a)$ Conjunction from (6) and (7)
$ \exists x(P(x) \wedge \neg B(x))$ Existential generalization from (8)

**Solution of 8 : **
We need to prove that every non-constant single-variable polynomial with complex coefficients has at least one complex root.
If there is no complex root on the complex plane ,then we have $P(z)^{-1}$ is a holomorphic function on the entire complex plane.As $|P(z)|^{-1} $ is bounded by $M$,let $f(z)=1/P(z),$the inequality holds
$ \qquad \qquad \displaystyle f
^\prime(z)\leq \frac{n! M}{R}$
Then let $R$ tends to infinity
$ f^\prime (z)=0,z\in \mathbb C $.This shows that $ P(z) $ is a constant function.A contradiction.