Лекции: Лекции ТХТ
Описание
Характеристики лекций
Список файлов
- Лекции ТХТ.TXT 97,35 Kb
- Прочти меня!!!.txt 136 b
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.
Литература.
1. С.Клини. Математическая логика.
2. Э.Мендельсон. Введение в математическую логику.
3. Ч.Чень, Р.Ли. Математическая логика и автоматическое дока-
зательство теорем.
4. В.А.Смирнов и др. Логика и компьютер. Вып 3., 1996.
5. Братко. Программирование на языке ПРОЛОГ для искусственно-
го интеллекта.
6. Логическое программирование (сборник статей под ред. В.Н.
Агафонова).
7. J.W.Lloyd. Foundations of Logic Programming, 1987.
План лекций.
Часть I. Математическая логика.
$1. Язык логики предикатов.
Синтаксис языка логики предикатов: алфавит; термы; формулы. Алфа-
вит языка представляет собой объединение алфавитов: 1) переменных
(предметных); 2) функциональных символов; 3) предикатных символов; 4)
логических связок (конъюнкция &, дизъюнкция V, импликация >, отрицание
); 4) кванторов (квантор общности A., квантор существования E.); 5)
вспомогательных символов (скобки и запятые). Каждому предикатному и
функциональному символу сопоставлено число n>=0, называемое его мест-
ностью. Терм - это переменная или выражение f(t1,...,tn), где f -
n-местный функциональный символ, а t1,...,tn - термы. Формула A - это
выражение P(t1,...,tn), где P - n-местный предикатный символ, а
t1,...,tn - термы, или выражение, построенное из других формул с при-
менением логической связки или квантора: C, (C&B), (CVB), (C>B), A.x
С, E.x C, где B и C - формулы, а x - переменная. Эта логическая связка
(квантор) называется главной (или внешней) связкой формулы A.
Понятия, описывающие кванторную структуру формулы: пусть Q -
квантор; подформула B формулы QxB называется областью действия кванто-
ра Q по переменной x; переменная x называется свободной в формуле C,
если не входит в область действия никакого квантора по x; в формуле
QxB квантор Q связывает все свободные вхождения переменной x в формулу
B. Формула называется замкнутой, если содержит только связанные вхож-
дения переменных.
Семантика языка логики предикатов: интерпретация; истинность в
интерпретации формулы B(x1,...,xn) со свободными переменными x1,...,xn
на наборе b1,...,bn (запись I|=B[b1,...,bn] означает, что в интерпре-
тации I формула B истинна, если каждая ее свободная переменная xi при-
нимает значение bi).
Интерпретация I - это, во-первых, некоторое множество D, называе-
мое областью интерпретации; во-вторых, множество всюду определенных
n-местных функций f^ из D в D, сопоставленных n-местным функциональным
символам f; и в-третьих, множество всюду определенных n-местных функ-
ций P^ из D в множество истинностных значений {истина,ложь}, сопостав-
ленных n-местным предикатным символам Р. После того, как эти три мно-
жества зафиксированы, значения термов и формул в I определяются следу-
ющим образом. Пусть x1,...,xn - список переменных, содержащий все пе-
ременные терма t, а b1,...,bn - элементы D. Значение t на наборе
b1,...,bn определяется так: если t есть переменная xi, то
xi[b1,...,bn] = bi; если t имеет вид f(...,tj,...), то
f(...,tj,...)[b1,...,bn] = f^(...,tj[b1,...,bn],...). (Т.е. каждый
терм интерпретируется как сложная функция из D в D). Пусть x1,...,xn -
список переменных, содержащий все свободные переменные формулы B, а
b1,...,bn - элементы D. Формула В истинна в интерпретации I на наборе
b1,...,bn (I|=B[b1,...,bn]) в следующих случаях. Если B есть
P(...,ti,...), то I|=B[b1,...,bn] <=> P^(...,ti[b1,...bn],...)=истина.
Если В есть A, то I|=B[b1,...,bn] <=> не верно, что I|= A[b1,...,bn].
Если В есть A&C (AVC), то I|=B[b1,...,bn] <=> I|= A[b1,...,bn] и (или)
I|= С[b1,...,bn]. Если В есть A>C, то I|=B[b1,...,bn] <=> из I|=
A[b1,...,bn] следует I|= С[b1,...,bn] (т.е. не верно, что I|=
A[b1,...,bn] или I|= С[b1,...,bn]). Если В есть A.xC (E.xC), то
I|=B[b1,...,bn] <=> для любого (какого-то) b0 формула С(x0,x1,...,xn)
истинна в I на наборе b0,b1,...,bn: I|= C[b0,b1,...,bn]. Таким обра-
зом, каждая формула B интерпретируется как сложная функция из D в мно-
жество {истина,ложь}.
Замечания: 1) область интерпретации выбирается произвольно, пре-
дикатные и функциональные символы интерпретируются в каждой интерпре-
тации по-разному, а логические связки и кванторы интерпретируются
всегда одинаково (причем логические связки - в соответствии с истин-
ностными таблицами); 2) истинностные значения формул A.xB и E.xB не
зависят от значения x; 3) в каждой интерпретации формула со свободными
переменными представляет собой истинностную функцию от этих пременных,
а замкнутая формула принимает определенное истинностное значение; 4)
определение семантики позволяет вычислять истинностные значения логи-
ческих формул в конечных интерпретациях (делая это, можно, в частнос-
ти, убедиться в адекватности формальной семантики: интуитивное и фор-
мальное истинностные значения большинства формул совпадают); 5) в со-
держательной математике обычно используются определенным образом про-
интерпретированные варианты языка логики предикатов, а в математичес-
кой логике рассматриваются произвольные интерпретации каждого языка;
6) если в интерпретации I формула В не зависит существенно от перемен-
ной x, то истинностные значения формул В, A.xB и E.xB совпадают.
Ясно, что 0-местная функция - это константа. Вопрос: что такое
0-местный предикат? С учетом определения семантики, это выражение,
принимающее ровно одно из значений истина/ложь в каждой данной интерп-
ретации (в отличие от логических констант T - "истина" и - "ложь",
принимающих соответствующие истинностные значения во всех интерпрета-
циях). Такие предикаты можно рассматривать как пропозициональные пере-
менные, принимающие значения из множества {истина,ложь}. Если рассмат-
ривать только 0-местные предикаты, язык логики предикатов превращается
в язык логики высказываний (т.к. в 0-местных предикатах нет "мест" для
термов, оказываются избыточными алфавиты переменных и функциональных
символов, а в силу зам.6 бесполезны кванторы). В языке остаются пропо-
зициональные переменные и логические связки. Поэтому семантика языка
логики высказываний может быть полностью определена в терминах истин-
ностных таблиц. Каждая строка таблицы соответствует одной интерпрета-
ции, а таблица в целом - совокупности всех интерпретаций (следователь-
но, их число конечно).
Итак, истинность формулы со свободными переменными в каждой ин-
терпретации зависит от значений ее свободных переменных. Такое понима-
ние истинности логических формул соответствует "истинностному смыслу"
строгих определений (определение - это логическое суждение, истинное
на множестве определяемых объектов); "истинностному смыслу" уравнений,
рассматриваемых как логические формулы (формула, состоящая из двух
термов, соединенных знаком "=", называется уравнением, если стоит воп-
Файл скачан с сайта StudIzba.com
При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник
Начать зарабатывать