Связанные понятия
Логика второго порядка в математической логике — формальная система, расширяющая логику первого порядка возможностью квантификации общности и существования не только над переменными, но и над предикатами. Логика второго порядка несводима к логике первого порядка. В свою очередь, она расширяется логикой высших порядков и теорией типов.
Логика высказываний , или пропозициональная логика (лат. propositio — «высказывание»), или исчисление высказываний — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные.
Конструктивная математика — абстрактная наука о конструктивных процессах, человеческой способности осуществлять их, и об их результатах — конструктивных объектах.
Классическая логика — термин, используемый в математической логике по отношению к той или иной логической системе, для указания того, что для данной логики справедливы все законы (классического) исчисления высказываний, в том числе закон исключения третьего.
Форма́льная систе́ма (форма́льная тео́рия, аксиоматическая теория, аксиоматика, дедуктивная система) — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Теория моделей — раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.
Теория типов — математически формализованная база для проектирования, анализа и изучения систем типов данных в теории языков программирования (раздел информатики). Многие программисты используют это понятие для обозначения любого аналитического труда, изучающего системы типов в языках программирования. В научных кругах под теорией типов чаще всего понимают более узкий раздел дискретной математики, в частности λ-исчисление с типами.
Аксио́мы Пеа́но — одна из систем аксиом для натуральных чисел, введённая в XIX веке итальянским математиком Джузеппе Пеано.
Класс — термин, употребляемый в теории множеств для обозначения произвольных совокупностей множеств, обладающих каким-либо определенным свойством или признаком. Более строгое определение класса зависит от выбора исходной системы аксиом. В системе аксиом Цермело — Френкеля определение класса является неформальным, тогда как другие системы, например, система аксиом фон Неймана — Бернайса — Гёделя, аксиоматизируют определение «собственного класса» как некоторого семейства, которое не может быть элементом...
Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.
Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.
Теория доказательств — это раздел математической логики, представляющий доказательства в виде формальных математических объектов, осуществляя их анализ с помощью математических методов. Доказательства обычно представляются в виде индуктивно определённых структур данных, таких как списки и деревья, созданных в соответствии с аксиомами и правилами вывода формальных систем. Таким образом, теория доказательств является синтаксической, в отличие от семантической теории моделей. Вместе с теорией моделей...
Математическое доказательство — рассуждение с целью обоснования истинности какого-либо утверждения (теоремы), цепочка логических умозаключений, показывающая, что при условии истинности некоторого набора аксиом и правил вывода утверждение верно. В зависимости от контекста, может иметься в виду доказательство в рамках некоторой формальной системы (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при необходимости...
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
Ра́венство (отношение равенства) в математике — бинарное отношение, наиболее логически сильная разновидность отношений эквивалентности.
Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.
Аксио́ма (др.-греч. ἀξίωμα «утверждение, положение») или постула́т — исходное положение какой-либо теории, принимаемое в рамках данной теории истинным без требования доказательства и используемое при доказательстве других её положений, которые, в свою очередь, называются теоремами.
Многозна́чная ло́гика — тип формальной логики, в которой допускается более двух истинностных значений для высказываний. Первую систему многозначной логики предложил польский философ Ян Лукасевич в 1920 году. В настоящее время существует очень много других систем многозначной логики, которые в свою очередь могут быть сгруппированы по классам. Важнейшими из таких классов являются частичные логики и нечёткие логики.
Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.
Метаматематика — раздел математической логики, изучающий основания математики, структуру математических доказательств и математических теорий с помощью формальных методов. Термин «метаматематика» буквально означает «за пределами математики».
Вполне упорядоченное множество — линейно упорядоченное множество M такое, что в любом его непустом подмножестве есть минимальный элемент, другими словами, это фундированное множество с линейным порядком.
Выска́зывание в математической логике — предложение, выражающее суждение. Если суждение, составляющее содержание (смысл) некоторого высказывания, истинно, то и о данном высказывании говорят, что оно истинно. Сходным образом ложным называют такое высказывание, которое является выражением ложного суждения. Истинность и ложность называются логическими, или истинностными, значениями высказываний.Высказывание должно быть повествовательным предложением, и противопоставляются повелительным, вопросительным...
Мно́жество — одно из ключевых понятий математики; это математический объект, сам являющийся набором, совокупностью, собранием каких-либо объектов, которые называются элементами этого множества и обладают общим для всех их характеристическим свойством. Изучением общих свойств множеств занимаются теория множеств, а также смежные разделы математики и математической логики.
Каррирование (от англ. currying, иногда — карринг) — преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Возможность такого преобразования впервые отмечена в трудах Готтлоба Фреге, систематически изучена Моисеем Шейнфинкелем в 1920-е годы, а наименование получило по имени Хаскелла Карри — разработчика комбинаторной логики, в которой сведение к функциям одного аргумента носит основополагающий характер.
Комбина́торная ло́гика — направление математической логики, занимающееся фундаментальными (то есть не нуждающимися в объяснении и не анализируемыми) понятиями и методами формальных логических систем или исчислений. В дискретной математике комбинаторная логика тесно связана с лямбда-исчислением, так как описывает вычислительные процессы.
Опера́ция — отображение, ставящее в соответствие одному или нескольким элементам множества (аргументам) другой элемент (значение). Термин «операция» как правило применяется к арифметическим или логическим действиям, в отличие от термина «оператор», который чаще применяется к некоторым отображениям множества на себя, имеющим замечательные свойства.
Тео́рия мно́жеств — раздел математики, в котором изучаются общие свойства множеств — совокупностей элементов произвольной природы, обладающих каким-либо общим свойством. Создана во второй половине XIX века Георгом Кантором при значительном участии Рихарда Дедекинда, привнесла в математику новое понимание природы бесконечности, была обнаружена глубокая связь теории с формальной логикой, однако уже в конце XIX — начале XX века теория столкнулась со значительными сложностями в виде возникающих парадоксов...
Математи́ческая структу́ра — название, объединяющее понятия, общей чертой которых является их применимость к множествам, природа которых не определена. Для определения самой структуры задают отношения, в которых находятся элементы этих множеств. Затем постулируют, что данные отношения удовлетворяют неким условиям, которые являются аксиомами рассматриваемой структуры.
В логике логи́ческими опера́циями называют действия, вследствие которых порождаются новые понятия, с использованием уже существующих. В более узком смысле, понятие логической операции используется в математической логике и программировании.
Подробнее: Логическая операция
Интуициони́зм — совокупность философских и математических взглядов, рассматривающих математические суждения с позиций «интуитивной убедительности». Различаются две трактовки интуиционизма: интуитивная убедительность, которая не связана с вопросом существования объектов, и наглядная умственная убедительность.
Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И».
Модальная логика (от лат. modus — способ, мера) — логика, в которой кроме стандартных логических связок, переменных и/или предикатов есть модальности (модальные операторы).
Автоматическое доказательство (англ. Automated Theorem Proving, ATP, а также Automated deduction) — доказательство, реализованное программно. В основе лежит аппарат математической логики. Используются идеи теории искусственного интеллекта. Процесс доказательства основывается на логике высказываний и логике предикатов.
Структурная индукция — конструктивный метод математического доказательства, обобщающий математическую индукцию (применяемую над натуральным рядом) на произвольные рекурсивно определённые частично упорядоченные совокупности. Структурная рекурсия — реализация структурной индукции в форме определения, процедуры доказательства или программы, обеспечивающая индукционный переход над частично упорядоченной совокупностью.
Теоре́ма (др.-греч. θεώρημα «доказательство, вид; взгляд; представление, положение») — утверждение, выводимое в рамках рассматриваемой теории из множества аксиом посредством использования конечного множества правил вывода.
Проблема остановки (или проблема останова) — это одна из центральных проблем в теории алгоритмов, которая может неформально быть поставлена в виде...
Зависимый тип (англ. dependent type) в информатике и логике — тип, который зависит от некоторого значения. Зависимые типы играют ключевую роль в интуиционистской теории типов и построении функциональных языков программирования таких как ATS, Agda и...
Доказательство «от противного » (лат. contradictio in contrarium) в математике — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса. Этот способ доказательства основывается на истинности закона двойного отрицания в классической логике.
Алгебраическая комбинаторика — это область математики, использующая методы общей алгебры, в особенности теории групп и теории представлений, в различных комбинаторных контекстах и, наоборот, применяющая комбинаторные техники к задачам в алгебре.
Дедеки́ндово сече́ние (или у́зкая щель) — один из способов построения вещественных чисел из рациональных.
Теория вычислимости , также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической...
Преде́л — одно из основных понятий математического анализа. Различают предел последовательности и предел функции.
Переме́нная — атрибут физической или абстрактной системы, который может изменять своё, как правило численное, значение. Понятие переменной широко используется в таких областях как математика, естественные науки, техника и программирование. Примерами переменных могут служить: температура воздуха, параметр функции и многое другое.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.
Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Конти́нуум-гипо́теза (проблема континуума, первая проблема Гильберта) — выдвинутое в 1877 году Георгом Кантором предположение о том, что любое бесконечное подмножество континуума является либо счётным, либо континуальным. Другими словами, гипотеза предполагает, что мощность континуума — наименьшая, превосходящая мощность счётного множества, и «промежуточных» мощностей между счетным множеством и континуумом нет, в частности, это предположение означает, что для любого бесконечного множества действительных...