Подпись (логика) - Signature (logic) - Wikipedia

В логика, особенно математическая логика, а подпись перечисляет и описывает нелогические символы из формальный язык. В универсальная алгебра, подпись перечисляет операции, которые характеризуют алгебраическая структура. В теория моделей, подписи используются для обеих целей. Они редко становятся явными в более философских трактовках логики.

Определение

Формально (односортированный) подпись можно определить как тройку σ = (S_func, S_rel, ар), где S_func и S_rel не пересекаются наборы не содержащие никаких других основных логических символов, называемых соответственно

• функциональные символы (примеры: +, ×, 0, 1) и
• символы отношения или же предикаты (примеры: ≤, ∈),

и функция ar: S_func ${\displaystyle \cup }$ S_rel → ${\displaystyle \mathbb {N} }$ который присваивает натуральное число, называемое арность к каждой функции или символу отношения. Символ функции или отношения называется п-ary, если его арность п. Нулевой (0-ary) функциональный символ называется постоянный символ.

Подпись без функциональных символов называется реляционная подпись, а подпись без символов отношения называется алгебраическая подпись.^[1]А конечная подпись подпись такая, что S_func и S_rel находятся конечный. В более общем плане мощность сигнатуры σ = (S_func, S_rel, ar) определяется как | σ | = |S_func| + |S_rel|.

В язык подписи - это набор всех правильно сформированных предложений, построенных из символов в этой подписи вместе с символами в логической системе.

Прочие соглашения

В универсальной алгебре слово тип или же тип сходства часто используется как синоним слова «подпись». В теории моделей сигнатуру σ часто называют словарный запасили отождествляется с (первого порядка) язык L которому он предоставляет нелогические символы. Тем не менее мощность языка L всегда будет бесконечно; если σ конечно, то | L | будет ℵ₀.

Поскольку формальное определение неудобно для повседневного использования, определение конкретной подписи часто сокращается неформальным образом, например:

"Стандартная подпись для абелевы группы есть σ = (+, -, 0), где - унарный оператор ".

Иногда алгебраическая подпись рассматривается как просто список арностей, например:

«Тип подобия абелевых групп равен σ = (2,1,0)».

Формально это определило бы функциональные символы подписи как что-то вроде ж₀ (нулевой), ж₁ (унарный) и ж₂ (двоичный), но в действительности используются обычные имена даже в связи с этим соглашением.

В математическая логика, очень часто символы не могут быть нулевыми,^{[нужна цитата ]} поэтому постоянные символы должны рассматриваться отдельно, а не как нулевые функциональные символы. Они образуют набор S_const не пересекаться с S_func, на котором функция арности ар не определено. Однако это только усложняет дело, особенно в доказательствах индукцией по структуре формулы, когда необходимо рассматривать дополнительный случай. Любой символ нулевого отношения, который также не разрешен таким определением, может быть эмулирован символом унарного отношения вместе с предложением, выражающим, что его значение одинаково для всех элементов. Этот перевод не работает только для пустых структур (которые часто исключаются по соглашению). Если разрешены нулевые символы, то каждая формула логика высказываний также формула логика первого порядка.

Пример использования бесконечной подписи S_func = {+} ∪ {f_а: а ∈ F} и S_rel = {=}, чтобы формализовать выражения и уравнения о векторное пространство над бесконечным скалярным полем F, где каждая f_а обозначает унарную операцию скалярного умножения на а. Таким образом, подпись и логика могут быть отсортированы по одному, а сортировка выполняется только по векторам.^[2]

Использование подписей в логике и алгебре

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

В структура, интерпретация связывает символы функций и отношений с математическими объектами, которые оправдывают их имена: интерпретация псимвол функции ж в структуре А с домен А это функция ж^А: А^п → А, и интерпретация псимвол -арное отношение - это отношение р^А ⊆ А^п. Здесь А^п = А × А × ... × А обозначает п-складывать декартово произведение домена А с собой, и так ж на самом деле п-арная функция, и р ан п-арное отношение.

Многосортные подписи

Для многосортной логики и для многосортные структуры подписи должны кодировать информацию о сортах. Самый простой способ сделать это - через типы символов которые играют роль обобщенных артерий.^[3]

Типы символов

Позволять S - набор (своего рода), не содержащий символов × или →.

Типы символов более S это определенные слова в алфавите ${\displaystyle S\cup \{\times ,\to \}}$: типы реляционных символов s₁ × … × s_п, и функциональные типы символов s₁ × … × s_п→s ′, для неотрицательных целых чисел п и ${\displaystyle s_{1},s_{2},\dots ,s_{n},s'\in S}$. (За п = 0 выражение s₁ × … × s_п обозначает пустое слово.)

Подпись

Подпись (многосортная) - это тройная (S, п, тип) состоящий из

• множество S своего рода,
• множество п символов, и
• тип карты, который ассоциируется с каждым символом в п тип символа над S.

Примечания

1. Мокадем, Риад; Литвин, Витольд; Риго, Филипп; Шварц, Томас (сентябрь 2007 г.). «Быстрый поиск строки на основе nGram по данным, закодированным с использованием алгебраических подписей» (PDF). 33-я Международная конференция по очень большим базам данных (VLDB). Получено 27 февраля 2019.
2. Георгий Гретцер (1967). «IV. Универсальная алгебра». В Джеймсе С. Эбботе (ред.). Тенденции в теории решеток. Принстон / Нью-Джерси: Ван Ностранд. С. 173–210. Здесь: с.173.
3. Многосортная логика, первая глава в Конспект лекций по процедурам принятия решений, написано Калоджеро Дж. Зарба.

Рекомендации

• Burris, Stanley N .; Санкаппанавар, Х. (1981). Курс универсальной алгебры. Springer. ISBN  3-540-90578-2. Бесплатное онлайн-издание.
• Ходжес, Уилфрид (1997). Более короткая модельная теория. Издательство Кембриджского университета. ISBN  0-521-58713-1.

внешняя ссылка

• Стэнфордская энциклопедия философии: "Теория моделей "-к Уилфред Ходжес.
• PlanetMath: Вход "Подпись "описывает концепцию для случая, когда не вводятся никакие сортировки.
• Бэйли, Жан, "Введение в алгебраическую спецификацию абстрактных типов данных. "