Полнота ― это понятие, которое используется в различных областях, включая математику, логику и информатику. В этой статье мы рассмотрим вопрос о том, можно ли навести полноту, и какие есть различные типы полноты.
Функциональная полнота
Функциональная полнота ⸺ это характеристика выразительных возможностей класса функций или формальных выражений. Система булевых функций называется функционально полной, если она не содержится целиком ни в одном из пяти замкнутых классов: T0, T1, L, S и M.
- T0 ― класс функций, сохраняющих константу 0
- T1 ― класс функций, сохраняющих константу 1
- L ― класс линейных функций
- S ― класс самодвойственных функций
- M ⸺ класс монотонных функций
Чтобы система булевых функций была функционально полной, она должна содержать хотя бы одну функцию, не сохраняющую константу 0, хотя бы одну функцию, не сохраняющую константу 1, хотя бы одну нелинейную функцию, хотя бы одну несамодвойственную функцию и хотя бы одну немонотонную функцию.
Полнота по Тьюрингу
Полнота по Тьюрингу ― это понятие, используемое в теории вычислимости. Исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нем можно реализовать любую вычислимую функцию.
Это означает, что тьюринг-полный исполнитель может вычислить любую функцию, которая может быть вычислена на любом другом исполнительном устройстве.
Непрерывность множества действительных чисел
Непрерывность множества действительных чисел ⸺ это свойство, которое означает, что совокупность действительных чисел представляет собой упорядоченное поле;
Это свойство важно в математике, поскольку оно позволяет использовать действительные числа для описания непрерывных величин, таких как длины, площади и объёмы.
Понимание этих концепций важно для работы в различных областях, включая математику, логику и информатику.