Математическая логика

МАТЕМАТИЧЕСКАЯ 
ЛОГИКА
А.В. СИГАЛ
Е.А. ЛУКЬЯНОВА
Москва
ИНФРА-М
2027
УЧЕБНОЕ ПОСОБИЕ

УДК 510.6(075.8)
ББК 22.12я73
 
С34
Сигал А.В.
С34  
Математическая логика : учебное пособие / А.В. Сигал, Е.А. Лукьянова. — Москва : ИНФРА-М, 2027. — 247 с. — (Высшее образование). — DOI 10.12737/2269450.
ISBN 978-5-16-022475-6 (print)
ISBN 978-5-16-115180-8 (online)
В учебном пособии изложены основные разделы дисциплины «Математическая логика». Содержит изложение теоретических сведений, проиллюстрированных подробным разбором конкретных примеров, задания 
для самостоятельного решения студентами.
Предназначено для студентов высших учебных заведений, обучающихся по направлениям подготовки укрупненных групп «Математика 
и механика», «Компьютерные и информационные науки», «Информатика 
и вычислительная техника».
УДК 510.6(075.8)
ББК 22.12я73
Р е ц е н з е н т ы:
Смирнов Н.В., доктор физико-математических наук, профессор, заведующий кафедрой моделирования экономических систем факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета;
Цурков В.И., доктор физико-математических наук, профессор, заведующий отделом сложных систем Федерального исследовательского центра «Информатика и управление» Российской академии 
наук, академик Российской академии естественных наук 
ISBN 978-5-16-022475-6 (print)
ISBN 978-5-16-115180-8 (online)
© Сигал А.В., Лукьянова Е.А., 
2026
Рекомендовано к печати Ученым советом Крымского федерального 
университета имени В.И. Вернадского (протокол № 6 от 24.06.2026)

 
 
ОСНОВНЫЕ СОКРАЩЕНИЯ И ОБОЗНАЧЕНИЯ 
 
АНФ — алгебраическая нормальная форма; 
ДНФ — дизъюнктивная нормальная форма; 
ИВ — исчисление высказываний; 
ИП — исчисление предикатов; 
ИППП — исчисление предикатов первого порядка; 
КНФ — конъюнктивная нормальная форма; 
НОД — наибольший общий делитель; 
ПНФ — предваренная нормальная форма; 
ППФ — правильно построенная формула; 
СДНФ — совершенная дизъюнктивная нормальная форма; 
СКНФ — совершенная конъюнктивная нормальная форма; 
УНФ — универсальная нормальная форма; 
ФНП — функция нескольких переменных; 
ЭД — элементарная дизъюнкция; 
ЭК — элементарная конъюнкция; 
 — квантор всеобщности: «для любого», «для каждого», «для всех»; 
 — квантор существования: «существует», «имеется», «найдется»; 
! — квантор существования и единственности: «существует и притом единственный»; 
 — пустое множество, то есть множество, которому не принадлежит ни один 
объект; пустое отношение; 
= — знак равенства; 
 — знак неравенства; 
 — знак тождественного равенства; знак равносильности высказываний; 
 — знак следования утверждений: «если…, то»; 
 — знак равносильности утверждений: «тогда и только тогда», «если и только если», «необходимо и достаточно»; 

I
i
iA

 — объединение множеств  Ai для всех значений индекса, принадлежащих 
множеству  I; 

I
i
iA

 — пересечение множеств  Ai для всех значений индекса, принадлежащих 
множеству  I; 
F — формула  F является общезначимой формулой; 
− A — формула  A является теоремой (формула  A есть теорема, формула  A является выводимой); 
= F (p; q; r;…) — указанная формула  F (p; q; r;…) является тавтологией; 
x = {n  Z   x – n   0,5} — ближайшее целое число к действительному числу  x; 
x =
n
max{n  Z  n  x} — функция пола (целая часть) действительного числа  x; 

 
x =
n
min {n  Z  n  x} — функция потолка действительного числа  x; 
a  A — объект  a принадлежит множеству  A (a является элементом множества  
A); 
a  A — объект  a не принадлежит множеству  A (a не является элементом множества  A); 
A  B (A  B) — множество  A включено во множество  B (множество  B включает множество  A;  A — подмножество  B;  B — надмножество  A); 
A  B — множество  A не является подмножеством множества  B; 
A = B — указанные множества равны (совпадают); 
A =  — заданное множество  A является пустым множеством; 
A  B — указанные множества не равны (не совпадают); 
A   — заданное множество  A является непустым множеством, то есть заданное множество  A не является пустым множеством; 
AB — объединение указанных множеств; 
AB — пересечение указанных множеств; 
A \ B или  B \ A — разность соответствующих множеств; 
A  B = A  B — симметричная (симметрическая) разность указанных множеств; 
A  B — прямое (декартово) произведение указанных множеств, то есть множество всех упорядоченных пар (a; b) = a; b,  a  A,  b  B; 
ab — композиция (суперпозиция) подстановок  a,  b; 
A1, A2,…, An− A — из формул  A1,  A2,…,  An следует формула  A; 
A — дополнение (до универсума) указанного множества  A; 
n
kA — символ  n-местных предикатов (в исчислении предикатов); 
k
n
A — число размещений из  n элементов по  k (в комбинаторике); 
k
n
A~ — число размещений с повторениями из  n элементов по  k; 
a = (a1; a2;…; an) —  n-мерный вектор, заданный координатами  a1,  a2,…,  an; 
A = {a1; a2;…; ak} — множество, которому принадлежат указанные элементы; 
A = {a  P (a)} — множество всех объектов  a, для которых выполняется (справедливо) указанное требование (условие)  P (a); 
A = Amn = (aij) — прямоугольная матрица размерности  mn; 
A = An = Ann = (aij) — квадратная матрица порядка  n, то есть матрица размерности  nn; 
An —  n-я степень указанного множества, то есть множество всех векторов  (точек) вида  a = (a1; a2;…; an),  ai  A,  i =
n
,1
; 
Al — стандартный алфавит исчислений; 
A / R — фактор-множество множества  A для отношения  R  A2; 
aRb — элементы  a,  b находятся в отношении  R; 
B = {0; 1} — бинарное множество, то есть двухэлементное множество двоичных 
цифр; 
Bul (A) — булеан указанного множества; 

 
i =
k
,1
 (j =
n
,1
) —  i (j) принимает все натуральные значения от  1 до  k (n); 
c = card (R)  — континуум: мощность множества  R всех действительных чисел; 
card (A) = card A — мощность (кардинальное число) указанного множества; 
Cn(n1; n2; …; nk) — число соответствующих разбиений множества; 
!
k
n
k
n
C
k
k
n
=






=
 — число сочетаний из  n элементов по  k; 
k
k
n
n
k
n
k
n
C
C
C
1
1
1
~
−
+
−
−
+
=
=
 — число сочетаний с повторениями из  n элементов по  k; 
D ( f ) — область определения функции  y = f (x); 
Dom R — область определения отношения  R; 
E ( f ) — область значений функции  y = f (x); 
en — тождественная подстановка степени  n; 
E = En = (ij) — единичная матрица порядка  n; 
F1,…, Fs= H — формула  H — логическое следствие формул  F1,…,  Fs; 
Im R — область значений отношения  R; 
IP — множество истинности предиката  P (x1, x2,…, xn); 
JR — матрица отношения  R; 
F (R) — поле отношения  R; 
n
kf — символ  n-местных функций (в исчислении предикатов); 
k
nf — число всех сочетаний с повторениями из  n элементов по  k, в которых 
каждый из имеющихся  n элементов обязательно встречается хотя бы один раз; 
M0[ f (x)] — множество нулевых наборов булевой функции  f (x); 
M1[ f (x)] — множество единичных наборов булевой функции  f (x); 
N = {1; 2; 3;…} — множество всех натуральных чисел; 
n ! — факториал числа  n, где  n  Z0; 
P = {2; 3; 5; 7; 11; 13; 17; 19; 23; 29;…} — множество всех простых чисел; 
Pn — число перестановок из  n; 
Pn(k1; k2; …; kn) — число перестановок с повторениями из  n элементов; 
Q =




N
Z n
m
n
m
,
 — множество всех рациональных чисел; 
R = (– : ) — множество всех действительных чисел; 
RS — композиция (суперпозиция) отношений  R,  S; 
R –1 — обратное отношение (инверсия) к отношению  R  A  B; 
Rn — степень отношения  R  A2; 
Ra = {b  aRb} — сечение отношения  R  A2 по фиксированной первой компоненте  a  A; 
TrCl(R) — транзитивное замыкание отношения  R  A2; 
U — универсальное отношение; 
UP — область возможных значений предиката  P (x1, x2,…, xn); 

 
X  Y — множества  X,  Y являются эквивалентными (равномощными) множествами; 
x = (x1; x2;…; xn) — набор булевых переменных, то есть вектор  x  B n; 
x = f –1( y) — функция  f –1:Y → X, обратная к функции  f: X → Y; 
x  y — дизъюнкция (логическая сумма, «x ИЛИ  y»); 
x  y — конъюнкция (логическое произведение, «x И  y»); 
x → y — импликация («ЕСЛИ  x, ТО  y»); 
x  y = xy — сумма по модулю 2 (строгая дизъюнкция, «ИЛИ  x, ИЛИ  y»; 
x  y — стрелка Пирса, «НЕ-ИЛИ», «ИЛИ-НЕ»); 
x  y — штрих Шеффера («НЕ-И», «И-НЕ»); 
x  y = x  y — эквивалентность («x ТОГДА И ТОЛЬКО ТОГДА, КОГДА  y»); 
x  y (mod z) — сравнение чисел  x,  y по модулю  z; 
x =  x — отрицание (инверсия, «НЕ  x»); 
m
x (
m
x ) —  x в убывающей (возрастающей) факториальной степени  m; 
x mod y — бинарная операция  mod для заданных действительных чисел  x,  y; 
xy — действительное число  x кратно действительному числу  y; 
x y — действительное число  x не кратно действительному числу  y; 
y = f (x) — функция  f: X → Y; 
Z = {…; – 2; – 1; 0; 1; 2;…} — множество всех целых чисел; 
Z0 = {0; 1; 2;…} — множество всех целых неотрицательных чисел; 
− A —  A является следствием  :  A есть следствие  ; 
A — диагональным отношением на множестве  A; 
ij — символ Кронекера, равный  1, если индексы равны, то есть  jj = 1, когда  
i = j, и равный  0, если индексы не равны, то есть когда  i  j; 
 — символ произведения числовых выражений; символ конъюнкции (логического произведения) выражений от булевых переменных; 
k-формула — класс функций ИП в зависимости от особенностей префикса 
ПНФ; 
 — символ суммы числовых выражений; символ дизъюнкции (логической 
суммы) выражений от булевых переменных; 
k-формула — класс функций ИП в зависимости от особенностей префикса 
ПНФ; 
 — универсальное множество, универсум; 
0 = card (N)  — мощность счетного множества, то есть мощность множества  N 
всех натуральных чисел; 
n — кардинальные числа бесконечных множеств, где  n  Z0. 
 

 
 
 
ПРЕДИСЛОВИЕ 
 
Учебное пособие предназначено прежде всего для студентов, обучающихся по направлениям подготовки укрупненных групп «Математика и механика», 
«Компьютерные и информационные науки», «Информатика и вычислительная 
техника», а также для студентов других направлений подготовки, изучающих 
дисциплину «Математическая логика». В результате изучения дисциплины 
«Математическая логика» обучающиеся должны приобрести компетенции, необходимые в будущей профессиональной деятельности для самостоятельного 
системного применения методов и моделей, основанных на положениях математической логики, их практической реализации на компьютерной технике, при 
этом обучающиеся должны: 
знать 
• 
основные элементы теории множеств, основные понятия и категории математической логики; 
уметь 
• 
применять средства математической логики при решении логических задач; 
владеть 
• 
математическим аппаратом математической логики. 
Математическая логика, часто называемая формальной логикой или теорией доказательств, представляет собой науку, изучающую законы и формы корректных рассуждений. В учебном пособии изложены основные разделы классической (традиционной) теории математической логики. 
Считается, что первые работы по логике появились в V веке до н.э. Впервые как самостоятельную науку ее сформулировал древнегреческий философ 
Аристотель (384–322 годы до н.э.) в своих сочинениях, традиционно называемых «Органон» (инструмент, метод). В этих сочинениях Аристотель систематизировал сведения о логике, известные до него. С тех пор формальная логика 
просуществовала без особых изменений около двух тысячелетий. Со временем 
возникла идея, что, записывая рассуждения математическими формулами, цепь 
логических выводов можно заменить формальными «вычислениями». В Средние века были попытки создания машин «логического вывода». 
Идея построения универсального языка для всей математики и формализации на базе такого языка математических доказательств выдвигалась в XVII веке немецким ученым, юристом, дипломатом и изобретателем Готфридом Вильгельмом Лейбницем (1646–1716). Но только в середине XIX веке появились 
первые научные работы по алгебраизации аристотелевой логики: статья «Первые понятия логики, подготовительные к изучению геометрии», опубликованная в 1839 году шотландским математиком и логиком, первым президентом 
(1866 год) Лондонского математического общества О. де Мо́рганом, и статья 
«Математический анализ логики, или опыт исчисления дедуктивных умозаключений», опубликованная в 1847 году английским математиком и логиком 

 
Дж. Булем. В 1854 году Буль издал основополагающую работу по началам математической логики «Исследования законов мышления, на которых основаны 
математические теории логики и вероятностей». 
Огастес (или Август) де Мо́рган (1806–1871) по праву считается основоположником логической теории отношений, а Джордж Буль (1815–1864) — отцом 
математической логики. Именем Джорджа Буля назван важнейший раздел математической логики: булева алгебра, то есть алгебра логики. Основными операциями булевой алгебры являются дизъюнкция (операция «ИЛИ»), конъюнкция (операция «И»), отрицание (операция «НЕ»). 
Новую эпоху в истории математической логики ознаменовало издание в 
1879 году немецким математиком, логиком и философом Г. Фреге революционного труда «Исчисление понятий, или подражающий арифметике формальный язык чистого мышления». Фридрих Людвиг Готлоб Фреге (1848–1925) 
ввел в язык алгебры кванторы и разработал логику предикатов. Только после 
этого возникла реальная возможность применить язык логики к вопросам оснований математики, а затем распространить на всю математику. 
В это же время, то есть в XIX веке, получили широкое распространение 
исследования неевклидовой геометрии, которые сильно поколебали уверенность математиков в абсолютной надежности геометрической интуиции, на которой базировалась евклидова геометрия. Сомнениям в надежности геометрической интуиции способствовало также то, что в результате развития исчисления бесконечно малых математики натолкнулись на неожиданные примеры 
всюду непрерывных функций, не имеющей производной не в одной точке. Появилась потребность отделить понятие действительного числа от неясного понятия «величина», которое было основано на геометрической интуиции. Эта 
задача была решена разными путями в работах немецких математиков Карла 
Вейерштрасса, Рихарда Дедекинда и Георга Кантора. Они показали возможность «арифметизации» анализа и теории функций, в результате чего в качестве 
фундамента всей классической математики стала рассматриваться арифметика 
целых чисел. В 1888 году Р. Дедекиндом была предпринята первая попытка аксиоматизации натурального ряда чисел, которая в 1889 году была существенно 
развита итальянским математиком Джузеппе Пеано (1858–1932). При этом 
Дж. Пеано создал более удобную символику для логического языка. Позже этот 
язык был усовершенствован в трехтомном фундаментальном труде «Принципы 
математики» (1910–1913) британских математиков, логиков и философов Бертрана Рассела (1872–1970) и Альфреда Уайтхеда (1861–1947), в котором была 
предпринята попытка сведения всей математики к логике. Но эта попытка не 
увенчалась успехом, так как оказалось невозможным вывести из чисто логических аксиом существование бесконечных множеств. Хотя логистическая программа Фреге–Рассела в основаниях математики так и не достигла своей главной цели приведения математики к логике, в их работах был создан богатый 
логический аппарат, без которого оформление математической логики как полноценной математической дисциплины было бы невозможно. 

 
Предмет современной математической логики разнообразен. Прежде всего, 
следует отметить исследование логических и логико-математических исчислений, из которых основным является классическое исчисление предикатов. Здесь 
следует отметить вклад австрийского математика и логика Курта Фридриха Гёделя (1906–1978). Еще в 1930 К. Гёдель доказал теорему о полноте исчисления 
предикатов, согласно которой множество всех чисто логических утверждений 
математики совпадает с множеством всех выводимых в исчислении предикатов 
формул. Эта теорема показала, что исчисление предикатов является логической 
системой, на базе которой можно формализовать математику. На базе исчисления предикатов строятся различные логико-математические теории, представляющие собой формализацию содержательных математических теорий: арифметики, анализа, теории множеств, теории групп и др. Огромное влияние на 
представление об основаниях математики оказали две теоремы о неполноте, 
сформулированные и доказанные Куртом Гёделем. 
Наряду с элементарными теориями рассматриваются также теории высших порядков, в которых допускаются также кванторы по предикатам, предикаты от предикатов и т.д. Традиционными вопросами, которые исследуются 
для тех или иных формальных логических систем, являются исследования 
структуры выводов в этих системах, выводимость тех или иных формул, вопросы непротиворечивости и полноты рассматриваемых систем. 
Курс математической логики для студентов математических и информационных направлений подготовки имеет своей целью изложить основы этой 
науки, а также познакомить студентов с формализованным аксиоматическим 
методом построения математических теорий, охватывающим применение разнообразных логические средства, его основными составными частями такими, 
как логический язык, аксиомы и их системы, правила вывода, проблемы непротиворечивости, полноты, разрешимости теорий. 
Структурно учебное пособие состоит из трех крупных частей: «Раздел I. 
Необходимые сведения из комбинаторики и теории множеств», «Раздел II. Введение в булеву алгебру и исчисление высказываний», «Раздел III. Исчисление 
предикатов и бинарные отношения». 
Авторы выражают благодарность профессорам Наталье Владимировне 
Апатовой, Николаю Васильевичу Смирнову и Владимиру Ивановичу Цуркову 
за внимание к данной работе и ценные советы, позволившие улучшить содержание учебного пособия. 
Авторы надеются, что учебное пособие будет полезно студентам вузов, 
обучающимся по укрупненным группам направлений подготовки «Математика 
и механика», «Компьютерные и информационные науки», «Информатика и вычислительная техника», а также для студентов других направлений подготовки, 
изучающих дисциплину «Математическая логика», например, для студентов, 
обучающихся по укрупненной группе направлений подготовки «Управление в 
технических системах». 

 
 
РАЗДЕЛ  I.  НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ КОМБИНАТОРИКИ  
И ТЕОРИИ МНОЖЕСТВ 
 
Глава 1. 
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ 
 
Комбинаторика — это математическая наука, посвященная решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет 
способ построения некоторой конструкции из элементов исходного множества, 
называемой комбинацией элементов данного множества или комбинаторной 
конфигурацией. Целью комбинаторного анализа является изучение комбинаторных конфигураций, в частности, изучение вопросов их существования, алгоритмов построения, а так же решение задач выбора и расположения элементов заданного множества, задач размещения и перечислительных задач различных комбинаторных конфигураций. 
Для определенности в этой главе будем считать, что комбинаторные конфигурации составляются из элементов одного и того же заданного конечного 
множества  = {1; 2;…; n}, состоящего из n различных элементов 1, 2,…, 
n, где n — заданное натуральное число. Наиболее важными комбинаторными 
конфигурациями являются перестановки, циклы, размещения и сочетания. 
 
1.1. ФАКТОРИАЛЬНЫЕ СТЕПЕНИ 
 
Определение. Убывающей факториальной степенью числа  x, где  x  R,  
m  N, называют величину, определяемую равенствами 
0
x = 1 (x  0), 
 

−
=
−
=
1
0
)
(
m
k
m
k
x
x
= x  (x – 1)  (x – 2) … (x – m + 1), 
(1.1) 
 
)
(
...
)
2
(
)1
(
1
)
(
1
1
m
x
x
x
k
x
x
m
k
m
+


+

+
=
+
=

=
−
. 
(1.2) 
Определение. Возрастающей факториальной степенью числа  x, где  
x  R,  m  N, называют величину, определяемую равенствами 
0
x = 1 (x  0), 
 

−
=
+
=
1
0
)
(
m
k
m
k
x
x
= x  (x + 1)  (x + 2) … (x + m – 1), 
(1.3) 
 
)
(
...
)
2
(
)1
(
1
)
(
1
1
m
x
x
x
k
x
x
m
k
m
−


−

−
=
−
=

=
−
. 
(1.4) 
Записи 
m
x , 
m
x читаются «„икс” в убывающей степени „эм”», «„икс” в возрастающей степени „эм”», соответственно.