Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Логіка другого порядку



План:


Введення

Логіка другого порядку в математичній логіці - формальна система, що розширює логіку першого порядку [1] можливістю квантифікації спільності і існування не тільки над атомами, а й над предикатами. Логіка другого порядку несводима до логіки першого порядку. У свою чергу, вона розширюється логікою вищих порядків і теорією типів.


1. Мова і синтаксис

Формальні мови логіки другого порядку будуються на основі безлічі функціональних символів \ Mathcal {F} і безлічі предикатних символів \ Mathcal {P} . З кожним функціональним і предикатних символів пов'язана арность (число аргументів). Також використовуються додаткові символи

  • Символи індивідуальних змінних, зазвичай \ X, y, z, x_1, y_1, z_1, x_2, y_2, z_2, і т. д.
  • Символи функціональних змінних \ F, G, H, F_1, G_1, H_1, F_2, G_2, H_2, . Кожній функціональної змінної відповідає деяке позитивне число - арность функції.
  • Символи предикатних змінних \ P, R, S, P_1, R_1, S_1, P_2, R_2, S_2, . Кожній предикатной змінної відповідає деяке позитивне число - арность предиката.
  • Пропозіціональние зв'язку: \ Lor, \ land, \ neg, \ to ,
  • Квантори спільності \ Forall та існування \ Exists ,
  • Службові символи: дужки і кома.

Перераховані символи разом з символами \ Mathcal {P} і \ Mathcal {F} утворюють алфавіт логіки першого порядку. Більш складні конструкції визначаються індуктивно.

  • Терм - це символ змінної, яка має вигляд \ F (t_1, \ ldots, t_n) , Де \ F - Функціональний символ арності \ N , А \ T_1, \ ldots, t_n - Терми або \ F (t_1, \ ldots, t_n) , Де \ F - Функціональна мінлива арності \ N , А \ T_1, \ ldots, t_n - Терми.
  • Атом - має вигляд \ P (t_1, \ ldots, t_n) , Де p - Предикатний символ арності \ N , А \ T_1, \ ldots, t_n - Терми або \ P (t_1, \ ldots, t_n) , Де P - Предикатна змінна арності \ N , А \ T_1, \ ldots, t_n - Терми.
  • Формула - це чи атом або одна з наступних конструкцій: \ Neg A, (A_1 \ lor A_2), (A_1 \ land A_2), (A_1 \ to A_2), \ forall x A, \ exists x A, \ forall FA, \ exists FA, \ forall PA, \ exists PA , Де \ A, A_1, A_2 - Формули, а \ X, F, P - Індивідуальна, функціональна і предикатна змінні.

2. Семантика

У класичній логіці інтерпретація формул логіки другого порядку задається на моделі другого порядку, що визначається наступними даними.

  • Базове безліч \ Mathcal {D} ,
  • Семантична функція σ , Яка відображає
    • кожен n -Арний функціональний символ f з \ Mathcal {F} в n -Арную функцію \ Sigma (f): \ mathcal {D} \ times \ ldots \ times \ mathcal {D} \ rightarrow \ mathcal {D} ,
    • кожен n -Арний предикатний символ p з \ Mathcal {P} в n -Арное ставлення \ Sigma (p) \ subseteq \ mathcal {D} \ times \ ldots \ times \ mathcal {D} .

3. Властивості

На відміну від логіки першого порядку, логіка другого порядку не має властивостей повноти і компактності. Також в цій логіці є невірним твердження теореми Левенгейма - Сколема.

Примітки

  1. Shapiro (1991) and Hinman (2005) give complete introductions to the subject, with full definitions.

Література

  1. Henkin, L. (1950). "Completeness in the theory of types". Journal of Symbolic Logic 15 (2): 81-91.
  2. Hinman, P. (2005). Fundamentals of Mathematical Logic. AK Peters. ISBN 1-56881-262-0.
  3. Shapiro, S. (2000). Foundations without Foundationalism: A Case for Second-order Logic. Oxford University Press. ISBN 0-19-825029-0.
  4. Rossberg, M. (2004). "First-Order Logic, Second-Order Logic, and Completeness". in V. Hendricks et al., Eds .. First-order logic revisited. Berlin: Logos-Verlag.
  5. Vaananen, J. (2001). "Second-Order Logic and Foundations of Mathematics". Bulletin of Symbolic Logic 7 (4): 504-520.



Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Кібернетика другого порядку
Поверхня другого порядку
Крива другого порядку
Крива другого порядку
Логіка першого порядку
Логіка першого порядку
Параметр порядку
Функція вищого порядку
Життєпис Едуарда Другого
© Усі права захищені
написати до нас