Ma 262: Discrete Mathematics II

QUESITON 1: Use truth tables to answer the following.[pic 1]

1. Verify that the proposition p ꓦ ¬(p ꓥ q) is a tautology.

Solution:

Therefore p ꓦ ¬(p ꓥ q) is a tautology since all the outcomes are TRUE

(b) Verify that the proposition (p ꓥ q) ꓥ ¬(p ꓦ q) is a contradiction.

Solution:

Therefore (p ꓥ q) ꓥ ¬(p ꓦ q) is a contradiction since all the outcomes are FALSE

(c) Prove that the operation of disjunction can be written in terms of the operations of conjunction and negation, i.e. p ꓦq ≡ ¬(¬p ꓥ¬q).

Solution:

[pic 4]

Therefore p ꓦq is equivalent to  ¬(¬p ꓥ¬q) because they both have the same outcome

QUESTION 2:  Consider the following statements and express each of these statement using quantifiers. Then form the negation of the statement so that no negation precedes a quantifier. After that express the negation in Simple English.

A : Every cow has four legs.

Let C(x) be the predicate “x is a cow”   and     let L(x) be the predicate “x has four legs”

So this can be expressed as ∀x[C(x) → L(x)] which is also equivalent to ∀x[¬C(x) ꓥ L(x)]

Therefore the negation for the above expression is ∃x[C(x) ꓦ ¬L(x)]

or in simple English is There is a cow that does not have four legs

B : There is a Bus with two wheels.

Let B(x) be the predicate “x is a Bus”    and   Let W(x) be the predicate “x with two wheels”

So this can be expressed as ∃x[B(x) ꓥ W(x)]

Therefore the negation for the above expression is ∀x[¬B(x) ꓦ ¬W(x)]

or in simple English is No Buses with two wheels

C : All Fijians can fly.

Let F(x) be the predicate “x is a Fijian”   and    Let G(x) be the predicate “x can fly”

So this can be expressed as  ∀x[F(x) → G(x)]  which also equivalent to  ∀x[¬F(x) ꓥ G(x)]

Therefore the negation for the above expression is  ∃x[F(x) ꓦ ¬G(x)]

or in simple English is There is a Fijian who can not fly

D : It is impossible to find a Tongan speaking Tuvaluan.

Let T(x) be the predicate “x is a Tongan”  and   Let S(x) be the predicate “x can speak Tuvaluan”

This can be expressed as  ∀x[T(x) → ¬S(x)]  which is also equivalent to  ∀x[¬T(x) ꓦ ¬S(x)]

Therefore the negation for the above expression is  ∃x[T(x) ꓥ S(x)]

or in simple English is  There is a Tongan who can speak Tuvaluan

E : There is a horse in Tokelau that could sing and dance.

Let H(x) be the predicate “x is an horse”, S(x) be the predicate “x that can sing” and D(x) be the predicate “x that can dance”

So now we can expressed the above as ∃x[H(x) ꓥ S(x) ꓥ D(x)]

Therefore the negation for the above expression is  ∀x[¬H(x) ꓦ ¬S(x) ꓦ ¬D(x)]

or in simple English is  Every horse in Tokelau either cannot sing or it can’t dance

QUESTION 3:

 (A) There are variations of proof by contradiction and they are all examples of what we refer to as indirect proofs. In this exercise, you are asked to use different indirect proof to give slightly different contradiction. It illustrates the rich possibilities that indirect proof provides for us and they also show why indirect proof can be confusing. There is no set of instructions or formulas to follow or memorize but, rather, you ask yourself whether assuming the opposite of what you are trying to prove gives an insight in to why the assumption makes no sense.

Consider the statement “If x² + x − 2 = 0, then x ≠ 0”. Let p be the statement

“x² + x − 2 = 0”, and q be the statement “x ≠ 0”. Thus, the given statement is “p → q”.

i. Assume p is true and q is false and derive a contradiction.

If the statement is False, it leads to a contradiction, so the statement is false when x² + x – 2 = 0 and x = 0. Substituting zero into x² + x – 2 = (0)2 + 0 - 2 will give us -2. This is a contradiction to  

x² + x – 2 = 0 because if x² + x – 2 = 0, then x ≠ 0  ■

ii. Assume p is true and q is false and derive a contradiction of a known fact.