Математическая логика, индукция, перестановки, СЛАУ и матричные уравнения

1. Математическая логика и теория множеств

Кванторы логики предикатов

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

Квантор всеобщности ($\\forall$): запись $\\forall x \\, P(x)$ истинна тогда и только тогда, когда $P(x)$ принимает значение «истина» для каждого элемента $x \\in U$.

Квантор существования ($\\exists$): запись $\\exists x \\, P(x)$ истинна, если в универсуме $U$ существует хотя бы один элемент $x_0$, для которого $P(x_0)$ истинно.

Законы отрицания кванторов (правила де Моргана для кванторов) переводят один квантор в другой с инверсией предиката:

Операции над множествами

Пусть $A$ и $B$ — подмножества универсального множества $U$. Базовые операции определяются через логические связки:

Объединение ($A \\cup B$): $A \\cup B = \\{x \\in U \\mid x \\in A \\lor x \\in B\\}$. Элемент принадлежит объединению, если он содержится хотя бы в одном из множеств.

Пересечение ($A \\cap B$): $A \\cap B = \\{x \\in U \\mid x \\in A \\land x \\in B\\}$. Элемент принадлежит пересечению, если он содержится одновременно в обоих множествах.

Декартово (прямое) произведение ($A \\times B$): $A \\times B = \\{(a, b) \\mid a \\in A \\land b \\in B\\}$. Множество всех упорядоченных пар. Мощность прямого произведения конечных множеств равна произведению мощностей: $|A \\times B| = |A| \\cdot |B|$.

Законы теории множеств (Дистрибутивность)

Операции над множествами подчиняются законам дистрибутивности, связывающим различные операции между собой:

Пересечение относительно объединения:

Объединение относительно пересечения:

Декартово произведение относительно пересечения:

Метод доказательства равенства множеств через логические эквивалентности

Для доказательства тождества $X = Y$ применяются два стандартных метода. Первый метод состоит в доказательстве взаимного включения: проверяются условия $X \\subseteq Y$ (из $x \\in X \\implies x \\in Y$) и $Y \\subseteq X$ (из $x \\in Y \\implies x \\in X$).

Второй метод использует непрерывную цепочку логических эквивалентностей. Например, доказательство закона $A \\cap (B \\cup C) = (A \\cap B) \\cup (A \\cap C)$:

По закону дистрибутивности конъюнкции относительно дизъюнкции в логике высказываний:

---

2. Метод математической индукции и комбинаторное суммирование

Принцип математической индукции (ПМИ)

Пусть $P(n)$ — предикат, определенный для всех натуральных чисел $n \\in \\mathbb{N}$. Метод доказательства утверждения $\\forall n \\in \\mathbb{N} \\, P(n)$ состоит из двух обязательных шагов:

База индукции: проверяется истинность утверждения для начального значения $n = 1$ (или наименьшего допустимого $n_0$).

Индукционный переход: формулируется индукционное предположение о том, что $P(k)$ истинно для некоторого произвольного $k \\ge 1$, и на его основе строго доказывается истинность $P(k + 1)$.

Если оба шага выполнены, то по аксиоме индукции предикат $P(n)$ истинен для всех $n \\ge n_0$.

Суммирование первых $n$ натуральных чисел

Рассматривается сумма $S_n = \\sum_{k=1}^n k = 1 + 2 + 3 + \\dots + n$.

1. Доказательство формулы $S_n = \\frac{n(n+1)}{2}$ через ПМИ

База индукции ($n = 1$): $S_1 = 1$, по формуле $\\frac{1 \\cdot (1 + 1)}{2} = 1$. База выполняется.

Индукционное предположение: пусть для некоторого $k \\ge 1$ выполняется $S_k = \\frac{k(k+1)}{2}$.

Индукционный переход ($k \\to k + 1$):

Формула верна для $k+1$. Переход доказан.

2. Аналитический вывод методом Гаусса / Эйлера

Запишем сумму дважды: в прямом и обратном порядке: Почленное сложение двух равенств дает $n$ слагаемых, каждое из которых равно $(n + 1)$:

3. Геометрический / визуальный метод доказательства

Ступенчатая фигура из квадратных блоков со сторонами $1, 2, \\dots, n$ содержит $S_n$ единичных клеток. Две одинаковые такие фигуры складываются в прямоугольник со сторонами $n$ и $n + 1$, общая площадь которого составляет $n(n + 1)$ клеток. Следовательно, площадь одной фигуры равна $\\frac{n(n+1)}{2}$.

Справочные формулы суммирования высших степеней

Сумма квадратов:

Сумма кубов:

---

3. Теория перестановок и подстановок (Симметрическая группа $S_n$)

Определение подстановки множества ${1, \dots, n}$ и двухстрочная запись

Подстановкой множества $M = \\{1, 2, \\dots, n\\}$ называется биективное отображение $\\sigma: M \\to M$. Для записи подстановки используется двухстрочная матрица: В первой строке записываются исходные элементы, во второй — их образы при отображении $\\sigma$. Порядок столбцов не влияет на значение подстановки.

Общее количество различных подстановок на множестве из $n$ элементов равно факториалу $|S_n| = n!$.

Инверсии и чётность подстановок

Пара элементов $(i, j)$ образует инверсию в подстановке $\\sigma$, если $i < j$, но $\\sigma(i) > \\sigma(j)$. Число всех инверсий второй строки при стандартно упорядоченной первой строке обозначается $I(\\sigma)$.

Знак (чётность) подстановки: определяется величиной $\\text{sgn}(\\sigma) = (-1)^{I(\\sigma)}$.

Если $I(\\sigma)$ чётно, подстановка называется чётной ($\\text{sgn}(\\sigma) = +1$).

Если $I(\\sigma)$ нечётно, подстановка называется нечётной ($\\text{sgn}(\\sigma) = -1$).

Теорема о разбиении и свойства транспозиций

Транспозиция $(i \\, j)$: подстановка, которая меняет местами два элемента $i$ и $j$, оставляя остальные неподвижными. Любая транспозиция меняет четность подстановки на противоположную: $\\text{sgn}(\\sigma \\circ (i \\, j)) = -\\text{sgn}(\\sigma)$.

Теорема о равном разбиении: при $n \\ge 2$ симметрическая группа $S_n$ содержит ровно $\\frac{n!}{2}$ чётных подстановок (образующих знакопеременную группу $A_n$) и ровно $\\frac{n!}{2}$ нечётных подстановок.

Операции над подстановками

Композиция (произведение): умножение $\\pi \\circ \\sigma$ означает последовательное применение отображений: сначала $\\sigma$, затем $\\pi$, то есть $(\\pi \\circ \\sigma)(k) = \\pi(\\sigma(k))$.

Обратная подстановка ($\\sigma^{-1}$): отображение, восстанавливающее исходный порядок: $\\sigma \\circ \\sigma^{-1} = \\sigma^{-1} \\circ \\sigma = e$, где $e$ — тождественная подстановка. Для нахождения $\\sigma^{-1}$ в двухстрочной записи меняются местами первая и вторая строки, после чего столбцы сортируются по возрастанию новой верхней строки.

Алгебраические уравнения в группе подстановок

Умножение подстановок некоммутативно ($AB \\neq BA$ в общем случае). Решение линейных уравнений в $S_n$ требует строгого учета стороны умножения:

Уравнение $Ax = B$: умножаем обе части слева на $A^{-1}$:

Уравнение $xA = B$: умножаем обе части справа на $A^{-1}$:

---

4. Системы линейных алгебраических уравнений (СЛАУ)

Основные определения и матричная форма записи

Система $m$ линейных уравнений с $n$ неизвестными имеет общий вид:

В матричной форме система записывается как $AX = B$, где:

Решением системы называется упорядоченный набор чисел $(c_1, \\dots, c_n)$, при подстановке которых каждое уравнение системы обращается в верное числовое тождество.

Геометрический смысл СЛАУ ($2 \\times 2$)

Для системы двух уравнений с двумя неизвестными каждое уравнение задает прямую линию на плоскости $\\mathbb{R}^2$:

Пересечение в одной точке: прямые пересекаются, система имеет ровно 1 решение.

Параллельные несовпадающие прямые: прямые не имеют общих точек, система не имеет решений.

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

Классификация систем по числу решений

Совместные системы: имеют хотя бы одно решение.

- Определенные: имеют ровно одно решение. - Неопределенные: имеют бесконечно много решений ($\\infty$).

Несовместные системы: не имеют решений (множество решений пусто: $\\emptyset$).

Эквивалентность систем

Две СЛАУ называются эквивалентными (равносильными), если их множества решений полностью совпадают. Преобразования системы (перестановка уравнений, умножение уравнения на ненулевое число, прибавление одного уравнения к другому) переводят исходную систему в эквивалентную.

---

5. Метод Гаусса и ступенчатые матрицы

Элементарные преобразования строк

Элементарными преобразованиями строк матрицы называются следующие операции:

$R_i \\leftrightarrow R_j$: перестановка $i$-й и $j$-й строк местами.

$R_i \\to c R_i$ ($c \\neq 0$): умножение строки на ненулевой скаляр.

$R_i \\to R_i + \\lambda R_j$ ($i \\neq j$): прибавление к $i$-й строке $j$-й строки, умноженной на число $\\lambda$.

Ступенчатый вид (Row Echelon Form, REF)

Матрица находится в ступенчатом виде, если выполнены условия:

Все нулевые строки (если они есть) расположены ниже всех ненулевых строк.

Первый ненулевой элемент каждой строки (называемый ведущим элементом или пивотом) расположен строго правее ведущего элемента предыдущей строки.

Ранг матрицы $\\text{rank}(A)$ равен количеству ненулевых строк в ее ступенчатом виде (или максимальному числу линейно независимых строк/столбцов).

Главные и свободные неизвестные

Главные (базисные) неизвестные: переменные $x_j$, столбцы которых содержат ведущие элементы (пивоты).

Свободные неизвестные: переменные $x_k$, столбцы которых не содержат ведущих элементов. Количество свободных неизвестных равно $n - r$, где $r = \\text{rank}(A)$.

Алгоритм метода Гаусса и Гаусса–Жордана

Прямой ход метода Гаусса: элементарными строковыми операциями расширенная матрица $(A \\mid B)$ приводится к ступенчатому виду (REF), обнуляя коэффициенты под каждым пивотом.

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

Приведенный ступенчатый вид (RREF, метод Гаусса–Жордана): каждый ведущий элемент делается равным 1, а все остальные элементы в столбце ведущего элемента обнуляются сверху и снизу.

Теорема Кронекера–Капелли и структура решений

Система $AX = B$ совместна тогда и только тогда, когда ранг основной матрицы равен рангу расширенной матрицы:

Однородные СЛАУ ($AX = 0$): всегда совместны, так как обладают тривиальным нулевым решением $X = 0$. Если число неизвестных $n$ строго больше числа уравнений $m$ ($n > m$), то $\\text{rank}(A) \\le m < n$, и однородная система гарантированно имеет нетривиальные (ненулевые) решения.

Теорема о структуре общего решения неоднородной СЛАУ:

где $X_0$ — произвольное фиксированное частное решение неоднородной системы $AX = B$, а $Y_{\\text{одн}}$ — общее решение соответствующей однородной системы $AY = 0$, представляющее собой линейную комбинацию $n - r$ фундаментальных решений.

Элементарные матрицы

Каждому элементарному преобразованию строк соответствует умножение слева на невырожденную элементарную матрицу:

Перестановка строк: умножение слева на матрицу $P_{ij}$.

Умножение строки на $c$: умножение слева на диагональную матрицу $D_i(c)$.

Прибавление строки: умножение слева на матрицу сдвига $L_{ij}(\\lambda)$.

Строковые элементарные преобразования матрицы $A$ задаются умножением слева ($E \\cdot A$), а столбцовые элементарные преобразования — умножением справа ($A \\cdot E$).

---

6. Определители (детерминанты) и метод Крамера

Определитель 2-го порядка

Для квадратной матрицы размера $2 \\times 2$ определитель равен разности произведений элементов главной и побочной диагоналей:

Определитель 3-го порядка и правило Саррюса

Определитель матрицы $3 \\times 3$ вычисляется по формуле:

Геометрическое правило треугольников (правило Саррюса): слагаемые со знаком «$+$» образуются главной диагональю и двумя треугольниками с основаниями, параллельными главной диагонали; слагаемые со знаком «$-$» образуются побочной диагональю и двумя соответствующими треугольниками.

Метод Крамера

Пусть дана система $n$ линейных уравнений с $n$ неизвестными $AX = B$, где матрица $A$ квадратная ($n \\times n$). Обозначим $\\Delta = \\det(A)$ — главный определитель системы, а $\\Delta_i$ — вспомогательный определитель, полученный заменой $i$-го столбца матрицы $A$ на столбец свободных членов $B$.

Формулы Крамера: если $\\Delta \\neq 0$, система является совместной и определенной, а ее единственное решение вычисляется по формуле:

Исследование совместности системы по определителям

$\\Delta \\neq 0$: система совместна и определена (единственное решение).

$\\Delta = 0$, но существует хотя бы один $\\Delta_i \\neq 0$: система несовместна (решений нет, так как $0 \\cdot x_i = \\Delta_i \\neq 0$).

$\\Delta = 0$ и все $\\Delta_i = 0$ ($i = 1, \\dots, n$): метод Крамера не дает ответа. Система либо неопределенна (имеет бесконечно много решений), либо несовместна. Для окончательного исследования требуется применить метод Гаусса.

---

7. Матричные уравнения

Матричные уравнения видов $AX = B$ и $XA = B$

Пусть $A$ — невырожденная квадратная матрица размера $n \\times n$ ($\\det(A) \\neq 0$), для которой существует единственная обратная матрица $A^{-1}$, удовлетворяющая условию $A A^{-1} = A^{-1} A = E$.

Уравнение $AX = B$: умножаем обе части равенства слева на $A^{-1}$:

Уравнение $XA = B$: умножаем обе части равенства справа на $A^{-1}$:

Решение уравнения $XA = B$ через транспонирование

Свойство транспонирования произведения матриц $(CD)^T = D^T C^T$ позволяет свести уравнение с правым умножением к уравнению с левым умножением: Обозначив $Y = X^T$, $C = A^T$ и $D = B^T$, получаем стандартное уравнение $CY = D$, откуда $Y = C^{-1}D$, а искомая матрица $X = Y^T$.

Метод расширенной блочной матрицы

Решение уравнения $AX = B$ без прямого вычисления $A^{-1}$ выполняется методом Гаусса–Жордана над блочной матрицей $(A \\mid B)$: Поскольку строковые элементарные преобразования эквивалентны умножению слева на матрицу $A^{-1}$, левый блок $A$ переходит в $A^{-1}A = E$, а правый блок $B$ переходит в $A^{-1}B = X$.

Поиск обратной матрицы методом Гаусса–Жордана

Для произвольной квадратной матрицы $A$ порядка $n$ составляется расширенная блочная матрица $(A \\mid E)$ размера $n \\times 2n$, где $E$ — единичная матрица порядка $n$. С помощью элементарных преобразований строк левая половина матрицы приводится к единичному виду: Если в процессе приведения в левой половине матрицы образуется полностью нулевая строка, то $\\text{rank}(A) < n$, $\\det(A) = 0$, и матрица $A$ является вырожденной (обратная матрица $A^{-1}$ не существует).