Задача №20

На острове живут два племени: аборигены и пришельцы. Аборигены всегда говорят правду, а пришельцы всегда лгут. Путешественник, приехавший на остров, нанял островитянина в проводники. Они пошли и увидели другого островитянина. Путешественник послал проводника узнать, к какому племени принадлежит этот туземец.

Проводник вернулся и сказал: «Туземец говорит, что он абориген».

Кем был проводник: пришельцем или аборигеном.

ЛИТЕРАТУРА

1. Градштейн И. С. Прямая и обратная теоремы. Элементы алгебры логики. – 5-е изд. – М.: Изд-во «Наука», 1972. – 128с.

2. Гиндикин С. Г. Алгебра логики в задачах. – М.: Изд-во «Наука», 1972. – 288с.

3. Зияитдинов Р.Г. Решение логических задач: Учеб. Пособие – 2-е изд., перераб. и доп. – Тверь: Твер. Гос. ун-т 2004. – 144с.;ил.

4. Ивлев Ю.В. Логика. – М.: Логос, 1997. – 272 с.

5. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: Учебное пособие для ВУЗов. – М.: Академия, 2005. – 302 с.

6. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд-во Саратов. Ун-та, 1991. – 256 с.

7. Колмогоров А.И., Драгалин А.Г. Введение в математическую логику. – М.: Изд-во Моск. Ун-та, 1982. – 120с.

8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд., исправл. – М.:ФИЗМАТЛИТ, 2003. – 256с.

9. Лихтарников Л.М. Сто логических задач. Методические рекомендации для учителей математики школ. – В.Новгород: Новгород. Гос. пед. ин-т, 1990. – 111с.

10. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник–практикум и решения. – СПб.: Издательство «Лань», 1999. – 288 с.

11. Никольская И.Л. Знакомство с математической логикой. М.: Московский психолого-социальный институт: Флинта, 1998. – 128 с.

12. Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург 2005. – 416 с.

Содержание

ВВЕДЕНИЕ. 3

1. ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ. ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. ТАБЛИЦЫ ИСТИННОСТИ.. 4

1.1 Понятие высказывания. 4

1.2 Логические операции над высказываниями. 5

1.3 Формулы алгебры логики. 7

1.4 Решение типовых задач. 9

1.5 Задачи для самостоятельного решения. 14

2 РАВНОСИЛЬНЫЕ ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ.. 21

2.1 Три группы равносильностей. 21

2.2 Равносильные преобразования формул. 22

2.3 Примеры решения задач. 23

2.4 Задачи для самостоятельного решения. 24

3 ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ. СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ. ПРОБЛЕМА РАЗРЕШИМОСТИ.. 28

3.1 Функии алгебры логики. 28

3.2 Представление произвольной функции алгебры логики в виде формулы алгебры логики. 31

3.3 Совершенные нормальные формы алгебры логики. 33

3.3.1 Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ) 33

3.3.2 Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ) 34

3.4 Проблема разрешимости. 36

3.5 Примеры решения задач. 38

Проверочная работа № 3. 45

§ 7. Некоторые приложения алгебры логики. 48

7.1 Приложения алгебры логики в технике (релейно-контактные схемы) 48

7.2 Решение логических задач. 54

7.2.1 Решение логических задач средствами алгебры логики. 55

7.2.2 Решение логических задач табличным способом. 56

7.2.3 Решение логических задач с помощью рассуждений. 58

Проверочная работа № 4. 60

Контрольная работа. 72

ЛИТЕРАТУРА.. 92

учебное издание