МАЛЫЙ МЕХМАТ МГУ

Занятие 11.  Математическая логика

Математическая логика имеет дело с утверждениями. Утверждением называется предложение, относительно которого можно определить истинно оно или ложно.

Если A и B - утверждения, то можно строить новые утверждения с помощью следующих операций.

ОперацияОпределениеОбозначение
ОтрицаниеНе AШA
КонъюнкцияA и BA Щ B
ДизъюнкцияA или BA \/ B
ИмпликацияЕсли A, то BA Ю B

Если утверждение A истинно, а утверждение B ложно, то импликация A Ю B ложна; во всех остальных случаях импликация истинна (в частности, даже в том случае, если оба утверждения A и B ложны!).

Сформулируйте самостоятельно, в каких случаях истинны отрицание, конъюнкция и дизъюнкция.

Часто в задачах встречаются рыцари и лжецы. Рыцари произносят только истинные утверждения, а лжецы - только ложные.

1.  

При любом ли значении x истинно следующее утверждение: «если 3x – x2 = 1, то |x|/x = 1»?
 

2.  

Путешественник приехал в страну, где имеются всего два города. В одном из них живут рыцари, а в другом - лжецы. При этом жители одного города могут приезжать в гости в другой город. В одном из городов путешественник встретил местного жителя. Можно ли задав ему один вопрос (на который можно ответить "да" или "нет"), выяснить
а) в каком городе он находится,
б) жителем какого города является встреченный абориген?
 

3.  

Между Колей и Сашей, увлекающимися решением логических задач, произошёл следующий разговор:
Коля: Я купил три полки для книг и расставил на них все свои учебники. Когда я сосчитал, сколько книг стоит на каждой полке и перемножил эти три числа, у меня получилось 72. Ты ведь знаешь, сколько у меня учебников?
Саша: Да, знаю.
Коля: Тогда скажи, сколько книг стоит на каждой полке?
Саша: У меня не хватает данных.
Коля: Полка, где было меньше всего книг, выглядела хуже остальных, и я поставил туда вазу с цветами.
Саша: Теперь мне ясно, вот ответ ...
И Саша точно сказал, сколько книг стоит на каждой полке. Скажите и Вы.
 

4.  

За круглым столом сидят рыцари и лжецы — всего 12 человек. Каждый произнёс: «Все, кроме меня и моих соседей — лжецы». Сколько рыцарей и сколько лжецов сидело за столом?
 

5.  

Вася задумал число 1, 2 или 3. Петя хочет отгадать задуманное число, задав один вопрос, допускающий три ответа: «да», «нет» или «не знаю». Какой вопрос следует задать?
 

6.  

Каждый из четырех гномов - Беня, Веня, Женя, Сеня - либо всегда говорит правду, либо всегда врет. Мы услышали такой разговор: Беня - Вене: «Ты врун»; Женя - Бене: «Сам ты врун»; Сеня - Жене: «Да оба они вруны, - (подумав), - впрочем, ты тоже». Кто из них говорит правду?
 

7.  

Предположим, что следующие утверждения истинны:

  • Среди людей, имеющих телевизоры, есть такие, которые не являются малярами;
  • люди, каждый день купающиеся в бассейне, но не являющиеся малярами, не имеют телевизоров.
Является ли в таком случае истинным утверждение, что не все владельцы телевизоров каждый день купаются в бассейне?
 
8.  

Про некоторую фигуру на плоскости известно, что она переходит в себя при повороте на угол 48°. Можно ли утверждать, что она переходит в себя при повороте на а) 72°; б)90°?
 

9.  

Сколько существует пятизначных чисел, получаемых из числа 12345 перестановкой цифр и у которых чётные цифры не стоят рядом?
 

10.  

Имеются две шкатулки, в одной из которых лежит ключ. На первой шкатулке написано: «Ключ находится во второй шкатулке». На второй написано: «Одно из двух утверждений, записанных на этих шкатулках, истинно, а второе ложно». В какой из шкатулок находится ключ?