Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Сборник задач по математической логике и теории алгоритмов

Покупка
Основная коллекция
Артикул: 449800.07.01
Доступ онлайн
от 504 ₽
В корзину
Частному лицу
Бумажная книга
2 951 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽
Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов: I. Содержательная логика высказываний; II. Булевы функции; III. Содержательная логика предикатов; IV. Формальные логические теории; V. Элементы теории алгоритмов. В каждом параграфе подробно рассматриваются разнообразные типовые примеры и даются многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебниках: Игошин В.И. Математическая логика: Учеб. пособие. М.: ИНФРА-М, 2012. 399 с. +CD-R. (Высшее образование); Игошин В.И. Теория алгоритмов: Учеб. пособие. М.: ИНФРА-М, 2012. 318 с. (Высшее образование). Для студентов университетов, технических и педагогических вузов, обучающихся как на уровне бакалавриата, так и на уровне магистратуры по направлениям «Математика», «Информатика», «Прикладная математика и информатика», «Математика и компьютерные науки», «Бизнес-информатика», «Математик-педагог», «Учитель математики».

Сборник задач по математической логике и теории алгоритмов: Путеводитель по миру формальных рассуждений

Представленный сборник задач по математической логике и теории алгоритмов, автором которого является В.И. Игошин, представляет собой ценный ресурс для студентов, осваивающих фундаментальные концепции этих дисциплин. Рекомендованный Учебно-методическим объединением по образованию в области подготовки педагогических кадров, сборник ориентирован на студентов, обучающихся по направлению «Педагогическое образование» (квалификация Бакалавр), но его актуальность распространяется и на студентов других направлений, связанных с математикой и информатикой, включая бакалавриат и магистратуру.

Структура и содержание

Сборник охватывает ключевые разделы курса математической логики и теории алгоритмов, представленные в пяти главах:

  • Глава I: Содержательная логика высказываний. Этот раздел закладывает основы алгебры высказываний, рассматривает нормальные формы для формул и их применение в математической практике и рассуждениях.
  • Глава II: Булевы функции. Здесь представлены задачи, связанные с числом булевых функций, их свойствами, специальными классами (линейные, самодвойственные, монотонные, сохраняющие 0 и 1), а также их применением в релейно-контактных и функциональных схемах.
  • Глава III: Содержательная логика предикатов. В этой главе исследуются понятия предикатов, их множества истинности, классификация, операции над ними, а также формулы и тавтологии логики предикатов. Особое внимание уделяется применению логики предикатов в математической практике.
  • Глава IV: Формальные логические теории. Глава посвящена построению формализованных исчислений высказываний и предикатов, включая аксиоматику Генцена—Клини, правила вывода, теорему о дедукции, а также вопросы полноты, непротиворечивости и разрешимости.
  • Глава V: Элементы теории алгоритмов. В заключительной главе рассматриваются машины Тьюринга, вычислимые по Тьюрингу функции, примитивно рекурсивные и частично рекурсивные функции, а также нормальные алгоритмы Маркова.

Методологический подход

Ключевой особенностью сборника является его практическая направленность. Автор подчеркивает, что обучение математике немыслимо без решения задач, которые служат внешним фактором, направляющим познавательную активность учащихся. Задачи в сборнике классифицируются по уровню сложности, начиная от типовых упражнений для закрепления теоретических знаний и заканчивая нестандартными задачами, требующими творческого подхода. Особо отмечается наличие подробных решений для ряда задач, что способствует самостоятельному освоению материала студентами.

Целевая аудитория и актуальность

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

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

Текст подготовлен языковой моделью и может содержать неточности.

6
118
331
Игошин, В. И. Сборник задач по математической логике и теории алгоритмов : учебное пособие / В. И. Игошин. - Москва : КУРС : ИНФРА-М, 2027. - 392 с. - ISBN 978-5-906818-08-9. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2264968 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
В.И.ИГОШИН
УЧЕБНОЕ ПОСОБИЕ
Москва
КУРС 
СБОРНИК ЗАДАЧ
ПО МАТЕМАТИЧЕСКОЙ 
ЛОГИКЕ 
И ТЕОРИИ АЛГОРИТМОВ
Рекомендовано 
УМО по образованию в области подготовки 
педагогических кадров в качестве учебного пособия 
для студентов высших учебных заведений, 
обучающихся по направлению 6.44.03.01 
«Педагогическое образование» (квалификация Бакалавр)


УДК	510.6(075.8)
ББК	22.12я73
	
И26
Игошин В.И.
Сборник задач по математической логике и теории алгоритмов: учеб. пособие/ В.И. Игошин. — М.: КУРС: ИНФРА-М, 
ISBN 978-5-906818-08-9 (КУРС)
ISBN 978-5-16-011429-3 (ИНФРА-М, print)
ISBN 978-5-16-103684-6 (ИНФРА-М, online)
Сборник содержит задачи и упражнения по всем традиционным разделам 
курса математической логики и теории алгоритмов: I. Содержательная логика 
высказываний; II. Булевы функции; III. Содержательная логика предикатов; 
IV. Формальные логические теории; V. Элементы теории алгоритмов. В каждом 
параграфе подробно рассматриваются разнообразные типовые примеры и даются многочисленные задачи разного уровня сложности для самостоятельного 
решения. Теоретический материал изложен в учебниках: Игошин В.И. Математическая логика: Учеб. пособие. М.: ИНФРА-М, 2012. 399 с. + CD-R. (Высшее 
образование); Игошин В.И. Теория алгоритмов: Учеб. пособие. М.: ИНФРА-М, 
2012. 318 с. (Высшее образование).
Для студентов университетов, технических и педагогических вузов, обучающихся как на уровне бакалавриата, так и на уровне магистратуры по направлениям «Математика», «Информатика», «Прикладная математика и  информатика», «Математика и компьютерные науки», «Бизнес-информатика», 
«Математик-педагог», «Учитель математики».
УДК 510.6(075.8)
ББК 22.12я73
Р е ц е н з е н т:
Зав. кафедрой «Теоретические основы компьютерной безопасности 
и криптографии» Саратовского национального исследовательского 
государственного университета им. Н.Г.  Чернышевского профессор 
В.Н. Салий
И26
© Игошин В.И., 2016, 2019
© КУРС, 2016, 2019
ISBN 978-5-906818-08-9 (КУРС)
ISBN 978-5-16-011429-3 (ИНФРА-М, print)
ISBN 978-5-16-103684-6 (ИНФРА-М, online)
ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1
Оригинал-макет подготовлен в Издательстве «КУРС»
Подписано в печать 16.04.2019.
Формат 60×90/16. Бумага офсетная. Гарнитура Newton.
Печать цифровая. Усл. печ. л. 24,5.
Доп. тираж 100 экз. Заказ №
ТК 449800-524332-120517
ООО Издательство «КУРС»
127273, Москва, ул. Олонецкая, д. 17А, офис 104.
Тел.: (495) 203-57-83.
E-mail: kursizdat@gmail.com   http://www. kursizdat.ru


Предисловие
Обучение математике немыслимо без решения задач. Задача есть 
некий внешний фактор, воздействующий на учащегося и направляющий его познавательную активность. При обучении математике 
с помощью задач могут ставиться различные дидактические цели: 
закрепление приобретенных теоретических знаний, формирование 
определенных умений и навыков, повторение ранее изученного материала, подготовка к изучению теоретических вопросов, применение в других науках и в практике, контроль усвоения знаний.
Существуют различные способы классификации задач: задачи 
стандартные (типовые, задачи-упражнения), общий метод решения 
которых известен учащимся, и задачи нестандартные, нетиповые, 
хотя и основывающиеся на изученном материале, решение которых 
требует творческого подхода, неординарного мышления.
Чтобы обучение с помощью задач достигало поставленных целей, 
нужна тщательно продуманная система упражнений и задач. В такой 
системе должна быть правильно установлена последовательность 
задач с учетом особенностей и возможностей учащихся и принципа 
«от простого к сложному». Должно быть соблюдено разумное разнообразие упражнений и задач. При работе с задачами знания учащихся должны совершенствоваться при решении каждой новой задачи. Грамотно составленная система задач управляет процессом 
обучения, формирует умения и навыки на основе осмысленных знаний путем многократного повторения операций, действий, приемов, 
алгоритмов, составляющих предмет обучения.
Настоящий сборник задач составлен по двум тесно взаимосвязанным дисциплинам — ​математической логике и теории алгоритмов. 
Он предназначен для обучения в университетах, технических и педагогических вузах, в учебных заведениях среднего профессионального образования — ​колледжах, техникумах будущих специалистов, 
чья деятельность так или иначе связана с математикой и информатикой. Настоящий сборник представляет собой переработанный 
вариант ранее изданного задачника 1. Сборник задач призван осуществить практическую поддержку теоретических курсов математиче1	
Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: Учеб. пособие для студ. высш. учеб. заведений. ​М.: Академия, 2005, 
2006, 2007, 2008. 304 с.


ской логики и теории алгоритмов, изучаемых по учебным пособиям 
различной степени интенсивности 1.
Сборник состоит из пятнадцати параграфов, сгруппированных 
в  пять глав: I.  Содержательная логика высказываний; II. Булевы 
функции; III. Содержательная логика предикатов; IV. Формальные логические теории; V. Элементы теории алгоритмов. Каждый параграф 
разбит на тематические пункты (без нумерации). Весь параграф или 
некоторые его пункты предваряются краткими сведениями теоретического характера, в которых приводится система понятий и обозначений, используемых в параграфе. 
Внутри каждого пункта задачи расположены в порядке возрастания их сложности. Пункт начинается с достаточно стандартных задач, предназначенных для отработки положений теории на конкретных примерах, в частности, для реального уяснения сути тех или 
иных введенных понятий, реальной отработки тех или иных теоретически обоснованных методов. Далее обычно следуют задачи, решение которых возможно лишь при условии, что необходимые понятия и методы уяснены. В конце некоторых пунктов приводятся 
задачи, решение которых требует в определенной мере нестандартного подхода или необычного хода рассуждений. Впрочем, таких 
задач немного, и  мы не  задавались целью включить в  сборник 
их большое количество. 
Наше внимание, напротив, было сосредоточено на задачах первых двух типов. Специфика таких задач и самого курса математической логики обусловила следующее их строение: каждая задача имеет 
общее условие, к которому прилагается серия разнообразных начальных данных, т. е. каждая из них фактически представляет собой серию однотипных задач. Почти всегда для одной из задач (а иногда 
и для нескольких) каждой серии приводится подробное решение, 
которое студент может разобрать самостоятельно или под руководством преподавателя. 
Структура сборника позволяет преподавателю осуществить индивидуальный подход к обучению каждого студента, подготовив для 
1	
Игошин В. И. Математическая логика и теория алгоритмов: Учеб. пособие для 
студ. высш. учеб. заведений. ​М.: Академия, 2004, 2008, 2008, 2010. 448 с.; 
Игошин В. И. Математическая логика: Учеб. пособие. ​М.: ИНФРА-М, 2012. 
399 с. + CD-R (Высшее образование); Игошин В. И. Теория алгоритмов: Учеб. 
пособие. ​М.: ИНФРА-М, 2012. 318 с. (Высшее образование); Игошин В. И. 
Элементы математической логики: Учебник для студ. учреждений сред. проф. 
образования. ​М.: Академия, 2016. 320 с.; Игошин В. И. Теория алгоритмов: 
Учеб. пособие для студ. учреждений сред. проф. образования. ​М.: Академия, 
2013. 320 с.


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


Глава I
Содержательная  
логика высказываний
В первой главе объединены три параграфа. Первые два посвящены собственно алгебре высказываний — ​первый ее основам, а второй — ​нормальным формам для формул алгебры высказываний. 
В третьем параграфе рассматриваются применения алгебры высказываний в математической практике и в практике рассуждений.
§ 1. Основные понятия алгебры высказываний
Высказывания и операции над ними. Под высказыванием мы понимаем предложение, представляющее собой такое утверждение, о котором можно судить, истинно оно или ложно. На совокупности всех 
высказываний определяется функция истинности, принимающая 
значения в двухэлементном множестве {0, 1}:
	
l( )
,
P
P
P
= 1
если высказывание  истинно,
0, если высказывание  ложно.



Значение l( )
P  называется логическим значением или значением истинности высказывания P.
Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся высказываний строить новые:
1)  отрицание: ¬P (читается «не P»);
2)  конъюнкция: P
Q
∧
 (читается «P и Q», используется также иное 
обозначение: P & Q);
3)  дизъюнкция: P
Q
∨
 (читается «P или Q»);
4)  импликация: P
Q
→
 (читается «если P, то Q», или «из P следует Q», или «P достаточно для Q», или «Q необходимо для P»);
5)  эквивалентность: P
Q
↔
 (читается «P равносильно Q», или 
«P тогда и только тогда, когда Q», или «P необходимо и достаточно 
для Q»).
При этом логические значения результатов этих операций связаны с логическими значениями исходных высказываний так, как 


указано в следующих таблицах, называемых таблицами истинности 
соответствующих операций:
l(P)
l(
)
¬P
0
1
1
0
l( )
P
l( )
Q
l(
)
P
Q
∧
l(
)
P
Q
∨
l(
)
P
Q
→
l(
)
P
Q
↔
0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
1
1
Каждую из этих операций можно рассматривать как операцию 
над символами 0 и 1. Так, например, дизъюнкция и импликация задают соответственно следующие правила действий с указанными 
символами: 0
0
0
∨
=
, 0
1
1
∨
= , 1
0
1
∨
= , 1
1
1
∨
=  и 0
0
1
→
= , 0
1
1
→
= , 
1
0
0
→
=
, 1
1
1
→
= .
1.1.  Какие из следующих предложений являются высказываниями?
а)	 Москва — ​столица России.
б)	 Студент механико-математического факультета университета.
в)	 Треугольник ABC подобен треугольнику ′ ′ ′
A B C .
г)	 Луна есть спутник Марса.
д)	 2
3
5
+
- .
е)	 Кислород — ​газ.
ж)	Каша — ​вкусное блюдо.
з)	 Математика — ​интересный предмет.
и)	 Картины Пикассо слишком абстрактны.
к)	 Железо тяжелее свинца.
л)	 Да здравствуют музы!
м)	Треугольник называется равносторонним, если все его стороны равны.
н)	 Если в треугольнике все углы равны, то он равносторонний.
о)	 Сегодня плохая погода.
п)	 В романе А. С. Пушкина «Евгений Онегин» 136 245 букв.
р)	 Река Ангара впадает в озеро Байкал.
Решение. 
б)  Это предложение не является высказыванием, потому что оно 
ничего не утверждает о студенте.
в)  Предложение не является высказыванием: мы не можем определить, истинно оно или ложно, потому что не знаем, о каких 
именно треугольниках идет речь.


ж)  Предложение не является высказыванием, так как понятие 
«вкусное блюдо» слишком неопределенно.
п)  Предложение — ​высказывание, но для выяснения его значения истинности нужно затратить немало времени.
1.2.  Укажите, какие из высказываний предыдущей задачи истинные, а какие — ​ложные.
1.3.  Сформулируйте отрицания следующих высказываний; укажите значения истинности данных высказываний и их отрицаний.
а)	 Волга впадает в Каспийское море.
б)	 Число 28 не делится на число 7.
в)	 6
3
> .
г)	 4
5
≤
.
д)	 Все простые числа нечетны.
е)	
2 — ​рациональное число.
ж)	5
3
8
+
=
.
з)	 Африка — ​остров.
и)	 Все слова можно разделить на слоги.
к)	 Некоторые грибы несъедобны.
1.4.  Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие — ​нет (объясните, почему).
а)	 4
5 5
4
<
<
, 
.
б)	 6
9 6
9
<
≥
, 
.
в)	 «Треугольник ABC прямоугольный», «Треугольник ABC тупоугольный».
г)	 «Натуральное число n четно», «Натуральное число n нечетно».
д)	 «Функция f нечетна», «Функция f четна».
е)	 «Все простые числа нечетны», «Все простые числа четны».
ж)	«Все простые числа нечетны», «Существует простое четное 
число».
з)	 «Человеку известны все виды животных, обитающих на Зем- 
ле», «На Земле существует вид животных, неизвестный человеку».
и)	 «Существуют иррациональные числа», «Все числа рациональные».
к)	 «Если n делится на 3, то n делится на 9», «Если n не делится 
на 3, то n не делится на 9».
л)	 2
0 2
0
<
>
, 
.
Решение. 
л)  Высказывание «2
0
>
» не является отрицанием высказывания 
«2
0
<
», потому что требование не быть меньше 0 оставляет две воз
можности: быть равным 0 и быть больше 0. Таким образом, отрицанием высказывания «2
<
» является высказывание «2
0
≥
».
1.5.  Определите значения истинности следующих высказываний.
а)	 Санкт-Петербург расположен на Неве и 2
3
5
+
= .
б)	 7 — ​простое число и 9 — ​простое число.
в)	 7 — ​простое или 9 — ​простое число.
г)	 Число 2 четное или это число простое.
д)	 2
3
≤, 2
3
≥, 2 2
4
⋅
≤, 2 2
4
⋅
≥
.
е)	 2 2
4
⋅
=
 или белые медведи живут в Африке.
ж)	2 2
4
⋅
=
, и 2 2
5
⋅
≤, и 2 2
4
⋅
≥
.
з)	 2 — ​рациональное число или -5 — ​иррациональное число.
и)	 Фобос и Луна — ​спутники Марса.
к)	 У равнобедренного треугольника либо два, либо три угла равны 
между собой.
л)	 3 3
9
⋅
=
 и 4
7
11
+
=
.
Решение. 
л)  Так как оба простых высказывания, к которым применяется 
операция конъюнкции, истинны, поэтому на основании определения этой операции и их конъюнкция есть истинное высказывание.
1.6.  Определите значения истинности высказываний A, B, C, D, 
E, F, G, H, I, J, K, если высказывания а)–д) — ​истинные, а высказывания е)–л) — ​ложные:
а)	 A ∧
⋅
=
(
)
2 2
4 ;
б)	 B ∨
⋅
=
(
)
2 2
5 ;
в)	 C ∨
⋅
=
(
)
2 2
4 ;
г)	 ¬
∧
⋅
=
D
(
)
2 2
4 ;
д)	 ¬
∨
⋅
=
E
(
)
2 2
5 ;
е)	 F ∧
⋅
=
(
)
2 2
4 ;
ж)	G ∨
⋅
=
(
)
2 2
5 ;
з)	 H ∧
⋅
=
(
)
2 2
5 ;
и)	 ¬
∧
⋅
=
I
(
)
2 2
4 ;
к)	 ¬
∨
⋅
=
J
(
)
2 2
4 ;
л)	 K ∧
⋅
(2 2 = 4).
Решение. 
л) Конъюнкция высказываний есть ложное высказывание в случае, когда по меньшей мере одно из входящих в конъюнкцию составляющих высказываний (членов конъюнкции) ложно. В нашем случае 
второе составляющее высказывание «2 2
4
⋅
=
» истинно, а конъюнкция двух высказываний ложна. Поэтому первое составляющее 
высказывание K ложно.
1.7.  Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (a, b — ​действительные числа):
а)	 a b
⋅
≠0;
б)	 a b
⋅
= 0;
в)	 a
b
2
2
0
+
=
;
г)	
ab > 0;
д)	 a = 3;
е)	 a < 3;


ж)	 a > 3;
з)	 a
b
2
2
0
+
≠
;
и)	 a b ≠0;
к)	
ab ≤0;
л)	 a b = 0.
Решение. 
л)  Дробь равна нулю лишь в том случае, когда числитель равен 
нулю и знаменатель не равен нулю, т. е. (
)
(
)
a
b
=
∧
≠
0
0 .
1.8.  Определите значения истинности высказываний A, B, C, D, 
E, F, G, H, I, J, K, если высказывания а)–д) ложны, а высказывания 
е)–л) истинны.
а)	 Если 4 — ​четное число, то A.
б)	 Если B, то 6 — ​нечетное число.
в)	 Если 2 2
4
⋅
=
, то ¬C.
г)	 Если ¬D, то 2 2
5
⋅
= .
д)	 Если 6 — ​четное число, то ¬E.
е)	 Если F, то 4 — ​нечетное число.
ж)	Если 3 2
6
⋅
=
, то ¬G.
з)	 Если ¬H , то 2 2
5
⋅
= .
и)	 Если 2 — ​четное число, то I.
к)	 Если 3 — ​четное число, то J.
л)	 Если 4 — ​четное число, то K.
Решение. 
л) Импликация двух высказываний есть ложное высказывание 
лишь в единственном случае, когда посылка истинна, а заключение 
ложно. В данном случае посылка «4 — ​четное число» истинна, 
и по условию все высказывание также истинно. Поэтому заключение 
K ложным быть не может, т. е. K истинно.
1.9.  Определите значения истинности следующих высказываний.
а)	 Если 9 делится на 3, то 4 делится на 2.
б)	 Если 11 делится на 6, то 11 делится на 3.
в)	 Если 15 делится на 6, то 15 делится на 3.
г)	 Если 15 делится на 3, то 15 делится на 6.
д)	 Если Саратов расположен на Неве, то белые медведи обитают 
в Африке.
е)	 12 делится на 6 тогда и только тогда, когда 12 делится на 3.
ж)	4
5
>
 тогда и только тогда, когда -
> -
4
5.
з)	 15 делится на 6 тогда и только тогда, когда 15 делится на 3.
и)	 15 делится на 5 тогда и только тогда, когда 15 делится на 4.
к)	 Если 12 делится на 6, то 12 делится на 3.
л)	 11 делится на 6 тогда и только тогда, когда 11 делится на 3.


Доступ онлайн
от 504 ₽
В корзину
Частному лицу
Бумажная книга
2 951 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽