Courses

# Chapter 8 - Reasoning with Knowledge Notes | EduRev

## : Chapter 8 - Reasoning with Knowledge Notes | EduRev

``` Page 1

Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Page 2

Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 3

Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 4

Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 5

Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
Let c = clean child, d= dirty child
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!