В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007

ВБ!СШЕЕ ПРОФЕССИОНАПБНОЕ ОБРАЗОВАНИЕ В. И. ИГОШИН ЗАДАЧИ И УПРАЖНЕНИЯ ПО МАТЕМАТИЧЕСКОИ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ Допущено Министерством образования Российской Федерации в кочеопве учебного пособия дяя студентов высшик учебнык заведений, обучающикся по специальности Оз2100 еМатематина э 3-е издание, стереотипное Мосина т1здатепиский центр «гькадетик. 2007 УДК 510.6(076.5) ББК 22.12я73 И269 Рецензенты: декан факультета «Прикладная математика» Московского государственного открытого университета, д-р физ.-мат.

наук, проф. В.Х Кулиев; зав. кафедрой «Теоретические основы компьютерной безопасности и криптографии» Саратовского госуларственного университета, проф. В.Н. Салий Игошин В.И. И269 Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. вмсш. учеб. заведений / В.И. Игошин. — 3-е изд., стер.

— М.: Издательский центр «Академия», 2007. — 304 с. 18ВХ 5-7695-3728-0 Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов. В кюкдом параграфе подробно рассмотрены разнообразные типовые примеры и приведены многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебном пособии: Игошин В.И. Математическая логика и теория алгоритмов.

— М.: Издательский центр «Академия», 2004. Для студентов университетов, технических и педагогических вузов, обучаюшихся по специальностям «Математика», «Прикладная математика*. УДК 510.6(076.5) ББК 22.12я73 Оригинал-макет данного издания является собственностью Издательского центра «Академия», и его воспроизведение любым способом без согласия правообладателя заврещается © Игошин В.И.„2005 © Издательский центр «Академия», 2005 !ВВГ4 5-7855-3728-0 ПРЕДИСЛОВИЕ Обучение математике немыслимо без решения задач.

В процессе обучения задачи выполняют разнообразные функции— обучающую, развивающую, воспитывающую. Задача есть некий внешний фактор, воздействующий на учащегося и детерминирующий его познавательную активность. С точки зрения общей теории систем задачи рассматриваются как особый вид систем. В педагогической науке существует так называемый задачный подход к исследованию и построению деятельности, в том числе учебной и обучающей. Согласно этому подходу всякая деятельность индивидов, в том числе учащихся и учителей, имеет задачную структуру, т.е. осуществляется как решение специфических для нее (учебных) задач.

Поэтому и проектировать ее целесообразно как систему процессов решения разнообразных задач. Результативность обучения в конечном итоге определяется тем, какие именно задачи, в какой последовательности и какими способами решают учителя и учащиеся. Эту мысль отмечали Полив (Д. Пойа) и Сеге в предисловии к их книге «Задачи и теоремы из анализа»: «Настоящая книга отнюдь не представляет собой простого собрания задач.

Главное заключается в расположении материала: оно должно побуждать читателя к самостоятельной работе и прививать ему целесообразные навыки математического мышления. Мы потратили на достижение возможно более эффективного расположения материала гораздо больше времени, старания и скрупулезной работы, чем это на первый взгляд могло бы показаться необходимым.

Сообщение ряда новых сведений интересовало нас само по себе лишь во вторую очередь. В первую очередь мы желали бы способствовать выработке у читателя правильных установок, известной дисциплины мышления, что при изучении математики необходимо еще в большей мере, чем при изучении других наук»', Мы рассматриваем задачи как важнейшее средство обучения математике.

При обучении математике с помощью задач могут ставиться различные дидактические цели: подготовка к изучению теоретических вопросов, закрепление приобретенных теоретических ' Пой« Д. Математическое открытие: Пер. с англ. — М., 1970. знаний, формирование умений и навыков, повторение ранее изученного материала, применение в других науках и в практике, контроль усвоения знаний.

Существуют различные способы классификации задач: задачи стандартные (типовые, задачи-упражнения), общий метод решения которых известен учащимся, и задачи нестандартные, нетиповые, хотя и основывающиеся на изученном материале, решение которых требует творческого подхода, неординарного мышления. Для того чтобы обучение с помощью задач достигало поставленных целей, нужна тщательно продуманная система упражнений и задач.

В такой системе должна быть правильно установлена последовательность задач с учетом особенностей и возможностей учащихся и принципа «от простого к сложному». Должно быть соблюдено разумное разнообразие упражнений и задач. При работе с задачами знания учащихся должны совершенствоваться при решении каждой новой задачи. Грамотно составленная задача управляет процессом обучения, формирует умения и навыки на основе осмысленных знаний путем многократного повторения операций, действий, приемов, алгоритмов, составляющих предмет обучения.

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

Сборник задач призван осуществить практическую поддержку теоретических курсов математической логики и теории алгоритмов, изучаемых по учебному пособию' (в дальнейшем будем называть его «Учебник»), Настоящий сборник представляет собой существенно переработанный и расширенный вариант ранее изданного задачника: Игошин В.И. Задачник-практикум по математической логике. — М., 1986. Сборник состоит из четырнадцати параграфов, сгруппированных в пять глав: 1. Алгебра высказываний; П.

Булевы функции; П1. Формализованное исчисление высказываний; 1Ч. Логика предикатов; Ч. Элементы теории алгоритмов. Каждый параграф разбит на тематические пункты (без нумерации). Весь параграф или некоторые его пункты предваряются краткими сведениями теоретического характера, в которых приводится система понятий и обозначений, используемых в параграфе.

Внутри каждого пункта задачи расположены в порядке возрастания их сложности. Пункт начинается с достаточно стандартных задач, предназначенных для отработки на конкретных примерах положений теории, в частно- ' Игошин ДИ. Математическая логика и теория алгоритмов. — М., 2004. сти для реального уяснения сути тех или иных введенных понятий, реальной отработки тех или иных теоретически обоснованных методов. Далее обычно следуют задачи, решение которых возможно лишь при условии, что необходимые понятия и методы уяснены. В конце некоторых пунктов приводятся задачи, решение которых требует в определенной мере нестандартного подхода или необычного хода рассуждений.

Впрочем, таких задач немного, и мы не задавались целью включить в сборник большое количество таких задач. Наше внимание, напротив, было сосредоточено на задачах первых двух типов. Специфика таких задач и самого курса математической логики обусловила следующее их строение: каждая задача имеет общее условие, к которому прилагается серия разнообразных начальных данных, т.е. каждая из них фактически представляет собой серию однотипных задач. Почти всегда для одной из задач (а иногда и для нескольких) каждой серии приводится подробное решение, которое студент может разобрать самостоятельно или под руководством преподавателя. Структура сборника позволяет преподавателю осуществить индивидуальный подход к обучению каждого студента, подготовив для него индивидуальную выборку задач.

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

Сборник задач и упражнений будет полезен всем, кто приступает к изучению основ математической логики и теории алгоритмов в учебных заведениях самых разных профилей и уровней. В.И. Игошин Глава 1 АЛГЕБРА ВЫСКАЗЫВАНИЙ В первой главе объединены три параграфа. Первые два посвящены собственно алгебре высказываний: первый — ее основам, а второй — нормальным формам для формул алгебры высказываний. В третьем параграфе, рассматривается применение алгебры высказываний в математической практике и практике рассуждений. й 1. Основные понятия алгебры высказываний Высказывания и операпяи над ними. Под высказыванием мы понимаем предложение, представляющее собой такое утверждение, о котором можно судить, истинно оно или ложно. По совокупности всех высказываний определяется функция истинности, принимающая значения в двухэлементном множестве (О, 1): ~1, если высказывание Р истинно, 10, если высказывание Р ложно.

Значение А(Р) называется логическим значением или значением истинности высказывания Р. Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся высказываний строить новые: 1) отрицание: -зР(читается «не Р»); 2) конъюнкция: Р к 0 (читается «Р и Д», используется также иное обозначение: Р&. Д); 3) диэъюнкция: Р ч 0 (читается «Р или 0»); 4) импликацил: Р» 0 (читается «если Р, то Д», или «из Р следует Д», или «Р достаточно для Д», или «Д необходимо для Р»); 5) эквивалентность: Р++ 0 (читается «Р равносильно Д», или «Р тогда и только тогда, когда Д», или «Р необходимо и достаточно для Д»).

При этом логические значения результатов этих операций связаны с логическими значениями исходных высказываний так, как указано в следующей таблице (таблице истинности соответствующих операций): Каждую из этих операций можно рассматривать как операцию над символами 0 и 1. Так, например, дизъюнкция и импликация задают соответственно следующие правила действий с указанными символами: Оч0=0; Оч 1 = 1; 1~0= 1; 1 ч 1= 1;0-+0= 1; 0-+ 1=1; 1-+ 0=0; 1-+ 1= 1. 1.1. Какие из следующих предложений являются высказываниями: а) Москва — столица России; б) Студент механико-математического факультета университета; в) Треугольник АВС подобен треугольнику А'В'С'; г) Луна есть спугник Марса; д) 2+2 — 5; е) Кислород — газ; ж) Каша — вкусное блюдо; з) Математика — интересный предмет; и) Картины Пикассо слишком абстрактны; к) Железо тяжелее свинца; л) «Да здравствуют музы!»; м) Треугольник называется равносторонним, если все его стороны равны; н) Если в треугольнике все углы'равны, то он равносторонний; о) Сегодня плохая погода; п) В романе А.С.