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

В.И.ИГОШИН

УЧЕБНОЕ ПОСОБИЕ

Москва
КУРС 
ИНФРА-М 
2019

СБОРНИК ЗАДАЧ

ПО МАТЕМАТИЧЕСКОЙ 
ЛОГИКЕ 
И ТЕОРИИ АЛГОРИТМОВ

Рекомендовано  
УМО по образованию в области подготовки  
педагогических кадров в качестве учебного пособия  
для студентов высших учебных заведений,  
обучающихся по направлению 6.44.03.01  
«Педагогическое образование» (квалификация Бакалавр)

УДК 510.6(075.8)
ББК 22.12я73
 
И26

Игошин В.И.
Сборник задач по математической логике и теории алгоритмов: учеб. пособие/ В.И. Игошин. — М.: КУРС: ИНФРА-М, 
2019. — 392 с. — (Бакалавриат).

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
+
- .

е) Кислород — газ.
ж) Каша — вкусное блюдо.
з) Математика — интересный предмет.
и) Картины Пикассо слишком абстрактны.
к) Железо тяжелее свинца.
л) Да здравствуют музы!
м) Треугольник называется равносторонним, если все его сто
роны равны.

н) Если в треугольнике все углы равны, то он равносторонний.
о) Сегодня плохая погода.
п) В романе А.С. Пушкина «Евгений Онегин» 136245 букв.
р) Река Ангара впадает в озеро Байкал.
Решение.
б) Это предложение не является высказыванием, потому что оно 

ничего не утверждает о студенте.

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

ж) Предложение не является высказыванием, так как понятие 

«вкусное блюдо» слишком неопределенно.

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

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
0
<
» является высказывание «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.