StudySmarter AI is coming soon!

:00Days
:00Hours
:00Mins
00Seconds

A new era for learning is coming soonSign up for free

Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q43E

Expert-verified

Discrete Mathematics and its Applications

Found in: Page 35

Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later

Short Answer

Show that, $\land, \lor$ and $\neg$ , ∨form a functionally complete collection of logical operators. [Hint: Use the fact that every compound proposition is logically equivalent to one in disjunctive normal form, as shown in Exercise 42.]

Let P be a compound proposition. Generate a proposition q in disjunctive normal form, which is equivalent to p.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step1: Definitions

Let p be a compound proposition.

We can generate its truth table, and according to the preceding exercise (42),

Step 2: Solution

Generate a proposition q in disjunctive normal form, which is equivalent to p.

The disjunctive normal form involves, $\neg, \lor$ and $\land$ only, which proves the statement,

given the definition of functionally complete collection of operators.

Most popular questions for Math Textbooks

Let p, q, and r be the propositions

p : Grizzly bears have been seen in the area.

q : Hiking is safe on the trail.

r : Berries are ripe along the trail.

Write these propositions using p, q, and r and logical connectives (including negations).

a)Berries are ripe along the trail, but grizzly bears have not been seen in the area. b) Grizzly bears have not been seen in the area and hiking on the trail is safe, but berries are ripe along the trail. c) If berries are ripe along the trail, hiking is safe if and only if grizzly bears have not been seen in the area. d) It is not safe to hike on the trail, but grizzly bears have not been seen in the area and the berries along the trail are ripe. e) For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area. f ) Hiking is not safe on the trail whenever grizzly bears have been seen in the area and berries are ripe along the trail.

Let p and q be the propositions “Swimming at the New Jersey shore is allowed” and “Sharks have been spotted near the shore,” respectively. Express each of these compound propositions as an English sentence

a) $\neg q$

b) $p \land q$

c) $\neg p \lor q$

d) $p \to \neg q$

e) $\neg q \to p$

f ) $\neg p \to \neg q$

g) $p \leftrightarrow \neg q$

h) $\neg p \land (p \lor \neg q)$

Use truth tables to verify the associative laws.

(a) $(p \lor q) \lor r \equiv p \lor (q \lor r)$ (b) $(p \land q) \land r \equiv p \land (q \land r)$

Construct a truth table for each of these compound propositions.

$a) p \to (\neg q \to r) b) \neg p \to (q \to r) c) (p \to q) \lor (\neg p \to r) d) (p \to q) \land (\neg p \to r) e) (p \leftrightarrow q) \lor (\neg q \leftrightarrow r) f) (\neg p \leftrightarrow \neg q) \leftrightarrow (q \leftrightarrow r)$

Show that $\neg$ and $\land$ form a functionally complete collection of logical operators.[Hint: First use De Morgan’s law to show that is logically equivalent to $\neg (\neg p \land \neg q)$ .

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free