Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

57 Алфавит Пусть D – предметная область (множество), f: D  D  …  D  D – n- местная функция, p: - D  D  …  D  B={0,1} – n- местный предикат. Пусть также V – множество предметных переменных, C – множество предметных констант, F – множество функциональных (1,2,…- местных) символов, P – множество предикатных (1,2,…- местных) символов, {  ,  ,  ,  } – множество операций, {  ,  } – множество кванторов, {(,)} – множество вспомогательных символов. Тогда V  C  F  P  {  ,  ,  ,  }  {  ,  }  {(,)} – алфавит исчисления предикатов. Формулы Терм. 1. Всякая предметная переменная является термом. 2. Всякая предметная константа является термом. 3. Если f – n -местный функциональный символ, а t 1 ,…,t n – термы, то f(t 1 ,…,t n ) – терм. Атом. Если P – n -местный предикатный символ, t 1 ,…,t n - термы, то P (t 1 ,…,t n ) – атом (атомарная или простейшая формула). Формула. 1. Атом есть формула. 2. Если A и B – формулы, то (  A),(A  B),(A  B), (A  B) – формулы, причем все переменные в этих