📗
MATH/CS 011: Study Guide
Type Study Guide
Class CS 011
Date @March 18, 2024 8:00 AM
Quarter Winter
MATH/CS 011: Study Guide
UCR’s Math/CS 011 - Introduction to Discrete Structures
Professor Kejia Zhu (Joe) [Winter 2024 Final Exam: Study Guide]
1. Logic and Propositions
1.1 Logic Analysis
⚔️ Knights & Knaves
Problem: On an island, you encounter two inhabitants, A and B.
MATH/CS 011: Study Guide 1
, A says, "B is a Knave."
B says, "A is a Knight."
Solution:
1. If A were a Knight, then A's statement "B is a Knave" would be true. This
implies that B cannot tell the truth. Given that B's statement is "A is a Knight,"
which in this case would be true, it creates a contradiction if B were indeed a
Knave, as Knaves cannot tell the truth.
2. If A were a Knave, then A's statement "B is a Knave" would be a lie, meaning B
must be a Knight. Since B claims that "A is a Knight," and if B were a Knight
(hence, always telling the truth), this would again create a contradiction
because we assumed A is a Knave.
To solve this paradox, analyze the logic more carefully:
If A's statement about B being a Knave were true, then A would be a Knight
(since Knights tell the truth). However, for B to say "A is a Knight" would also
be true, which cannot happen if B were a Knave, as Knaves cannot tell the
truth (a contradiction).
The only scenario that does not result in a logical contradiction is if A is a
Knave making a false statement about B, and B is a Knight, correctly
identifying A's status.
Therefore, the correct conclusion is that A is a Knave and B is a Knight , as this is
the only configuration that does not result in a contradiction.
1.2 Logical Symbols & Propositions
Symbols: ∃(exists), ∀(for all), →(implies).
MATH/CS 011: Study Guide 2
MATH/CS 011: Study Guide
Type Study Guide
Class CS 011
Date @March 18, 2024 8:00 AM
Quarter Winter
MATH/CS 011: Study Guide
UCR’s Math/CS 011 - Introduction to Discrete Structures
Professor Kejia Zhu (Joe) [Winter 2024 Final Exam: Study Guide]
1. Logic and Propositions
1.1 Logic Analysis
⚔️ Knights & Knaves
Problem: On an island, you encounter two inhabitants, A and B.
MATH/CS 011: Study Guide 1
, A says, "B is a Knave."
B says, "A is a Knight."
Solution:
1. If A were a Knight, then A's statement "B is a Knave" would be true. This
implies that B cannot tell the truth. Given that B's statement is "A is a Knight,"
which in this case would be true, it creates a contradiction if B were indeed a
Knave, as Knaves cannot tell the truth.
2. If A were a Knave, then A's statement "B is a Knave" would be a lie, meaning B
must be a Knight. Since B claims that "A is a Knight," and if B were a Knight
(hence, always telling the truth), this would again create a contradiction
because we assumed A is a Knave.
To solve this paradox, analyze the logic more carefully:
If A's statement about B being a Knave were true, then A would be a Knight
(since Knights tell the truth). However, for B to say "A is a Knight" would also
be true, which cannot happen if B were a Knave, as Knaves cannot tell the
truth (a contradiction).
The only scenario that does not result in a logical contradiction is if A is a
Knave making a false statement about B, and B is a Knight, correctly
identifying A's status.
Therefore, the correct conclusion is that A is a Knave and B is a Knight , as this is
the only configuration that does not result in a contradiction.
1.2 Logical Symbols & Propositions
Symbols: ∃(exists), ∀(for all), →(implies).
MATH/CS 011: Study Guide 2
