Discrete Mathematics Answers

Find the simplest form of given Boolean expressions using algebraic methods.

i. A(A+B) + B(B+C) + C(C+A)

ii. (A+|B|)(B+C) + (A+B)(C+|A|)

iii. (A+B)(AC+A|C|)_+AB +B

iv. |A|(A+B) + (B+A)(A+|B|)

A says “If B is a knight, then I am a knave”, B says nothing.

(a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm.

Show your steps.

Translate these system specifications into English where the predicate

S(x, y) is “x is in state y” and where the domain for x and y consists of all systems

and all possible states, respectively.

(a) ∃S(x, open)

(b) ∀x(S(x, malfunctioning) ∨ S(x, diagnostic))

(c) ∃xS(x, open) ∨ ∃xS(x, diagnostic)

1

For each of the given statements:

1 - Express each of the statements using quantifiers and propositional functions.

2 - Form the negation of the statement so that no negation is to the left of the quantifier.

3 - Express the negation in simple English. (Do not simply use the words “it is not

the case that...”).

(a) Some drivers do not obey the speed limit.

(b) All Swedish movies are serious.

(c) No one can keep a secret.

(d) No monkey can speak French.

(e) There is someone in the class who does not have a good attitude.

For each of the following compound propositions give its truth table and derive an

equivalent compound proposition in disjunctive normal formal (DNF) and in conjunc￾tive normal form (CNF).

(a) (p → q) → r

(b) (p ∧ ¬q) ∨ (p ↔ r)

all swedish movies are serious

Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”