Лекция дискрет 10
.pdfАлла |
Если я пойду, то пойдёт и Бэлла |
Бэлла |
Если я пойду, то пойдёт Валя |
|
или Алла не пойдёт |
Валя |
Если Галя не пойдёт, то пойдёт |
|
Алла, а я не пойду |
Галя |
Если я пойду, то пойдёт и Алла |
АБ
Б(В ¬А)
¬Г (А & ¬В)
Г А
А |
Б В Г |
КА |
КБ |
КВ |
КГ |
||
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
А |
Б В Г |
КА |
КБ |
КВ |
КГ |
||
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
Задача
Некая страна населена жителями, каждый из которых либо всегда говорит правду, либо всегда лжёт. На все вопросы они отвечают только «да» и «нет».
К развилке дорог, одна из
которых ведёт в столицу, а другая – не ведёт, подошёл путешественник, направляющийся в столицу. Указателей на развилке нет, зато гуляет гражданка, которая согласна ответить, увы, лишь на один вопрос…...
Какой вопрос ей задать, чтобы правильно выбрать путь в столицу ?
|
Интерпретация логической |
Значения переменной |
|
|
переменной |
|
|
|
|
|
|
x |
Гражданка всегда говорит правду |
1 - да |
0 - нет |
y |
Чтобы попасть в столицу, нужно |
1 - да |
0 - нет |
|
пойти по дороге в левую сторону |
|
|
|
|
|
|
Вопрос: верно ли, что f(x,y) = 1? Мы хотим получить ответ «да» тогда и только тогда, когда дорога в левую сторону действительно приведёт в столицу
x |
y |
Желаемый ответ на вопрос |
Необходимое значение f(x,y) |
|
|
|
|
0 |
0 |
Нет |
1 |
0 |
1 |
Да |
0 |
1 |
0 |
Нет |
0 |
|
|
|
|
1 |
1 |
Да |
1 |
|
|
|
|
Итак, спросим: верно ли, что ψ9 (x,y) [x y, x y] равно 1