Дискретная математика: различия между версиями
СВ (обсуждение | вклад) (Новая страница: «== Основы теории множеств == * Множества * Диаграммы Эйлера-Венна * Прямое произведени...») |
СВ (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Основы теории множеств == | == Основы теории множеств == | ||
* [[Множества]] | * [[Множества]] | ||
* [[Парадокс Рассела]] | * [[Парадокс Рассела]] | ||
* [[Аксиомы ZFC]] | * [[Аксиомы ZFC]] | ||
| Строка 14: | Строка 12: | ||
* [[Сочетания]] | * [[Сочетания]] | ||
* [[Треугольник Паскаля]] | * [[Треугольник Паскаля]] | ||
* [[Бином Ньютона]] | * [[Бином Ньютона]] | ||
* [[Мультимножества]] | * [[Мультимножества]] | ||
| Строка 34: | Строка 31: | ||
* [[Формулы]] | * [[Формулы]] | ||
* [[Основные тождества]] | * [[Основные тождества]] | ||
* [[Разложение функции по переменным]] | |||
* [[Дизъюнктивная нормальная форма]] | * [[Дизъюнктивная нормальная форма]] | ||
* [[Конъюнктивная нормальная форма]] | * [[Конъюнктивная нормальная форма]] | ||
* [[Полином Жегалкина]] | * [[Полином Жегалкина]] | ||
* [[Полнота системы функций]] | * [[Полнота системы функций]] | ||
| Строка 48: | Строка 45: | ||
== Исчисление высказываний == | == Исчисление высказываний == | ||
* [[Пример задачи логики высказываний]] | |||
* [[Формальные теории]] | |||
* [[Формальная теория исчисление высказываний]] | |||
* [[Теоремы исчисления высказываний]] | |||
* [[Теорема о полноте исчисления высказываний]] | |||
* [[Независимость аксиом исчисления высказываний]] | |||
== Исчисление предикатов == | == Исчисление предикатов == | ||
* [[Пример задачи логики предикатов]] | |||
* [[Формальная теория исчисление предикатов]] | |||
* [[Интерпретация]] | |||
== Алгоритмы == | == Алгоритмы == | ||
Текущая версия на 14:33, 25 октября 2026
Основы теории множеств
- Множества
- Парадокс Рассела
- Аксиомы ZFC
- Бинарные отношения
- Отношение эквивалентности
- Отношение порядка
- Лексикографический порядок
Комбинаторика
- Размещения
- Сочетания
- Треугольник Паскаля
- Бином Ньютона
- Мультимножества
- Мультиномиальная формула Ньютона
- Разбиения множеств
- Композиция натурального числа
- Разбиения натурального числа
- Перестановки
- Группа перестановок
- Циклы перестановки
- Тип перестановки
- Принцип включения-исключения
- Задача о беспорядках
- Мощность объединения множеств
- Число целочисленных решений системы неравенств
Булевы функции
- Булевы функции
- Формулы
- Основные тождества
- Разложение функции по переменным
- Дизъюнктивная нормальная форма
- Конъюнктивная нормальная форма
- Полином Жегалкина
- Полнота системы функций
- Функции, сохраняющие ноль
- Функции, сохраняющие единицу
- Двойственные функции
- Самодвойственные функции
- Монотонные функции
- Линейные функции
- Критерий полноты системы функций
Исчисление высказываний
- Пример задачи логики высказываний
- Формальные теории
- Формальная теория исчисление высказываний
- Теоремы исчисления высказываний
- Теорема о полноте исчисления высказываний
- Независимость аксиом исчисления высказываний
Исчисление предикатов
Алгоритмы
- Понятие алгоритма
- Машина Тьюринга
- Стандартные конфигурации машины Тьюринга
- Вычислимые функции
- Алгоритмически неразрешимые задачи
- Сложность алгоритмов
- Полиномиальная сводимость
- Классы задач в форме распознавания свойств
- NP-полные задачи
- Задача коммивояжера