Другое: План лекций (очень подробный)

Возможно не удалось распознать кодировку файла

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

Литература.

1. Клини. Математическая логика.

2. Мендельсон. Введение в математическую логику.

3. Чень, Ли. Математическая логика и автоматическое доказа-

тельство теорем.

4. Логика и компьютер (сборник под ред. Смирнова).

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

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