In this video we talk about strategies for solving logic puzzles by reasoning and truth tables.

Textbook: Rosen, Discrete Mathematics and Its Applications, 7e

Playlist:

28.08.2021

45 Comments

On the first puzzle: A is a knave, and his statement "B is a knight" is false, which means that B is also a knave. Then B says that A and B are different kinds, which is also false, since both are knaves.
Both statements are false, thus both A and B are knaves.A B A's statement B's statement
T T T F
T F T T
F T F T
F F F F <—- only case where the logic works is where both A and B are stating false statements, therefore they are both knaves.

the party one seems easier as a while loop, where you can basically test for cases until a condition is met, and break from the loop…and never invite people named Samir to parties

13:00 The truth table is much easier to construct and solve if you just put the following six columns: j, s, k, j->s', s->k, k->j.1.) Put all possible combinations of T/F for each of j, s, and k columns. 2.) Then evaluate the three conditional statements for each possible outcome as T/F.3.) The solution then, is the rows where all three conditional statements are true (T). Example:j s k j->s' s->k k->jT T T F T TT T F F F TT F T T T T (valid)T F F T T T (valid)F T T T T FF T F T F TF F T T T FF F F T T T

im at my freshman yeah learning DM for software engineering, i couldnt understand my professor well , but thanks to your course im slowly getting the hang of it, your courses are amazing !

thanks for your explanation, mam. now, I got understand the idea of logic puzzle. I am a student in computer science and engineering. You got an student.from Bangladesh

I am so thankful I stumbled across your channel. I am in a discrete math class for computer engineering and I am in a different country so I'm learning it in my second language. I am so thankful I have some help in English now.

Solid explanation. I am so bad at logic, but this is helping! However, quick question: in the beginning, why do you do combinations of p ^ q? Why is it specifically "and"?

For the knights and knaves puzzle there is a really easy, really cool algebraic method (essentially algebra in the Galois field modulo 2, where the only numbers are 0 and 1, and 1+1=0). We use 0 to represent "false" and 1 for true; then you translate A says "B is a knight" by (A is a knave) + (B is a knight) = 1 (Why? Because is "A is a knave" is true, equal to 1, then "B is a knight" has to be false, equal to 0 to make the equation true; conversely, if "A is a knave" is false, then equal to 0, in order to make the equation true "B is a knight" has to be 1, that is true. Note that p+q=1 is an algebraic translation of p XOR q.)The second statement is (B is a knave) + (A is a knave XOR B is a knave) = 1, that is, (B is a knave) + (A is a knave) + (B is a knave) = 1. Because adding the same thing to itself in GF2 is 0, the second equation resolves to "A is a knave" = 1. From that, plugging in the first equation, "B is a knight" has to be 0, so B is also a knave.Once you understand how this works, a complete solution looks simply like this (with T for knight and F for Knave):1. A is F + B is T =12. B is F + (A is F + B is F) = 1From 2, A is F = 1; therefore, replacing in 1 + B is T = 1, so B is T = 0.

Lets start by assuming this (p) is true….How does one even come up with the idea to begin assuming things to solve math problems. 😅 I need some explanation there.

Hi Prof. Brehm, in your actual discrete math course, do you assign logic puzzles, like the ones covered in this video, for exams? I bought the textbook and student solution manual; I'm using this to self-teach the material and I want to make sure I'm not going too easy or too hard on myself – thanks!

Knights and Knaves question: Why did you copy truth values of p to person A's statement and truth values of q to person B's statement? I understand how you filled the possibilities columns and the column 4 and 6 but not why you set the table as you did. Thank you in advance for your help 🙂

The second example is confusing especially if you interchange the sentence structure on where the "if" is located. 1 and 2 supposed to be constructed differently yet they share are having the same conditional structure

these logic puzzles have me feeling so stupid… and i simply would not Invite Jasmine, Samir or Kanti.Update: No disrespect to Professor B. But this video helped me to understand logic puzzles, especially this one we are doing, much better: https://www.youtube.com/watch?v=v-c6Bx7qy6Q&t=115s . I believe its because i can see the terms Knights and Knaves that it made much more sense to me. Also to remember that knights always tell the truth and knaves always lie. Now I can proceed to Discrete Math – 1.2.3 Introduction to Logic Circuits :).

you dont need to fill the table, you can directly eliminate from the possibilities,for example, if you find j — >s eliminate / if you find s — > not k eliminate / if you find k — > not j eliminate. ull end up with the same results without filling all that table

In Video 1.2.1 Practice Q2, the term "ONLY IF" ended up reversing the hypothesis and the conclusion. Using that logic, in the above video 1.2.2, for the second example, should we not reverse the implication from S–>K to K–>S due to the use of the "ONLY IF" term – i.e. Samir will attend only if Kanti will be there implies K–>S. In which case, the solutions are (i) Jasmine attends and Samir and Kanti do not, (ii) Samir attends and Jasmine and Kanti do not, and (iii) all three do not attend. On a side note, your lecture videos are of much help and thanks a lot for posting these.

This puzzle haunted me for years. With a paper and a little bit of patience I solved it for myself. (Maybe that is childish but… I am so proud!). :)) Thank you for the class. You have a new student.

On the first puzzle: A is a knave, and his statement "B is a knight" is false, which means that B is also a knave. Then B says that A and B are different kinds, which is also false, since both are knaves.

Both statements are false, thus both A and B are knaves.A B A's statement B's statement

T T T F

T F T T

F T F T

F F F F <—- only case where the logic works is where both A and B are stating false statements, therefore they are both knaves.

the party one seems easier as a while loop, where you can basically test for cases until a condition is met, and break from the loop…and never invite people named Samir to parties

i dont understand 2:47

Yes, I finally understood this lecture. Thank you,🥰.

13:00 The truth table is much easier to construct and solve if you just put the following six columns: j, s, k, j->s', s->k, k->j.1.) Put all possible combinations of T/F for each of j, s, and k columns. 2.) Then evaluate the three conditional statements for each possible outcome as T/F.3.) The solution then, is the rows where all three conditional statements are true (T). Example:j s k j->s' s->k k->jT T T F T TT T F F F TT F T T T T (valid)T F F T T T (valid)F T T T T FF T F T F TF F T T T FF F F T T T

Professor Brehm! Do you suggest reading the textbook first and follow it up with your lecture or do you recommend reversing the order? Thank you.

Why y'all need these tables, can figure them out from a quick glance.

you are a blessing!

im at my freshman yeah learning DM for software engineering, i couldnt understand my professor well , but thanks to your course im slowly getting the hang of it, your courses are amazing !

thanks for your explanation, mam. now, I got understand the idea of logic puzzle. I am a student in computer science and engineering. You got an student.from Bangladesh

I am so thankful I stumbled across your channel. I am in a discrete math class for computer engineering and I am in a different country so I'm learning it in my second language. I am so thankful I have some help in English now.

The best videos on discrete math on the internet and outside the internet. Thank you!

Solid explanation. I am so bad at logic, but this is helping! However, quick question: in the beginning, why do you do combinations of p ^ q? Why is it specifically "and"?

For the knights and knaves puzzle there is a really easy, really cool algebraic method (essentially algebra in the Galois field modulo 2, where the only numbers are 0 and 1, and 1+1=0). We use 0 to represent "false" and 1 for true; then you translate A says "B is a knight" by (A is a knave) + (B is a knight) = 1 (Why? Because is "A is a knave" is true, equal to 1, then "B is a knight" has to be false, equal to 0 to make the equation true; conversely, if "A is a knave" is false, then equal to 0, in order to make the equation true "B is a knight" has to be 1, that is true. Note that p+q=1 is an algebraic translation of p XOR q.)The second statement is (B is a knave) + (A is a knave XOR B is a knave) = 1, that is, (B is a knave) + (A is a knave) + (B is a knave) = 1. Because adding the same thing to itself in GF2 is 0, the second equation resolves to "A is a knave" = 1. From that, plugging in the first equation, "B is a knight" has to be 0, so B is also a knave.Once you understand how this works, a complete solution looks simply like this (with T for knight and F for Knave):1. A is F + B is T =12. B is F + (A is F + B is F) = 1From 2, A is F = 1; therefore, replacing in 1 + B is T = 1, so B is T = 0.

Thanks!

Great explanation, thank you!

Lets start by assuming this (p) is true….How does one even come up with the idea to begin assuming things to solve math problems. 😅 I need some explanation there.

Hi Prof. Brehm, in your actual discrete math course, do you assign logic puzzles, like the ones covered in this video, for exams? I bought the textbook and student solution manual; I'm using this to self-teach the material and I want to make sure I'm not going too easy or too hard on myself – thanks!

15:56 DON'T INVITE ANYONE!!! Simplest solution ever (assuming that then they won't be "unhappy" with me )

Knights and Knaves question: Why did you copy truth values of p to person A's statement and truth values of q to person B's statement? I understand how you filled the possibilities columns and the column 4 and 6 but not why you set the table as you did. Thank you in advance for your help 🙂

πολύ χρήσιμο βίντεο ευχαριστώ πολυ!!

The second example is confusing especially if you interchange the sentence structure on where the "if" is located. 1 and 2 supposed to be constructed differently yet they share are having the same conditional structure

these logic puzzles have me feeling so stupid… and i simply would not Invite Jasmine, Samir or Kanti.Update: No disrespect to Professor B. But this video helped me to understand logic puzzles, especially this one we are doing, much better: https://www.youtube.com/watch?v=v-c6Bx7qy6Q&t=115s . I believe its because i can see the terms Knights and Knaves that it made much more sense to me. Also to remember that knights always tell the truth and knaves always lie. Now I can proceed to Discrete Math – 1.2.3 Introduction to Logic Circuits :).

very nicely explained

Great <3

I wish I could've had you a professor

hi can you suggest which video may really help for the first year of computer science as I am kind of preparing

American will be great again. Before that, everyone should come here to learn from professor Kimberly Brehm

This video is excellent. But from 9:17, I do not understand, could you give us more detail? Thank you.

is this discrete math taught in a first year of computer science?

this makes no sense to me 🙁

i wonder if people create truth tables in real life to figure out who and who not to invite

your videos are extremely helpful! thank you so much for making these

this is harder than Kant philosophy

you dont need to fill the table, you can directly eliminate from the possibilities,for example, if you find j — >s eliminate / if you find s — > not k eliminate / if you find k — > not j eliminate. ull end up with the same results without filling all that table

In Video 1.2.1 Practice Q2, the term "ONLY IF" ended up reversing the hypothesis and the conclusion. Using that logic, in the above video 1.2.2, for the second example, should we not reverse the implication from S–>K to K–>S due to the use of the "ONLY IF" term – i.e. Samir will attend only if Kanti will be there implies K–>S. In which case, the solutions are (i) Jasmine attends and Samir and Kanti do not, (ii) Samir attends and Jasmine and Kanti do not, and (iii) all three do not attend. On a side note, your lecture videos are of much help and thanks a lot for posting these.

i love the last possibility grow up butnone of ya are getting invited though

I hate when I go to a party and somebody is acting all Kanti.

i didnt understand anything at all. it just feels like you were arbitrary filling in values for the second table for the party planning thing

… when u need new friends

Outstanding video lecture.

This puzzle haunted me for years. With a paper and a little bit of patience I solved it for myself. (Maybe that is childish but… I am so proud!). :)) Thank you for the class. You have a new student.

Good headache, haha.

My good human Samir out here not getting invited in any forseeable circumstance smh 🤦♂️

reminds me of a logic problem from brilliant