рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Семантика исчисления предикатов

Реферат Курсовая Конспект

Выберите учебное заведение

Семантика исчисления предикатов

Семантика исчисления предикатов - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Исчисление Предикатов (Так Же Как И Исчисление Высказываний) Являются, Прежде...

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

Английское слово «predicate» переводится на русский язык как «сказуемое». Рассмотрим предложение: «Гамлет пронзил Лаэрта мечом». В нем слово «Гамлет» является подлежащим, «пронзил» – сказуемым, «Лаэрта» и «мечом» – дополнениями. На языке предикатов это можно выразить так:

пронзил(гамлет, лаэрт, меч). (4.1)

Здесь пронзил– это предикат, а гамлет, лаэрт, меч – его термы. Такая запись похожа на обозначение функции, пронзил– аналог имени функции, а гамлет, лаэрт, меч – что-то вроде ее аргументов. Причем эти «аргументы» не равноправны между собой. «Гамлет» – это агент (тот, кто действует), он записан первым. «Лаэрт» – это объект действия, и он записан вторым. А «меч» – это инструмент, он стоит на третьем месте. В принципе, термы предиката могут быть представлены и в ином порядке (например, вначале «инструмент», потом «объект» и затем «агент»). Однако, приняв такой порядок, мы должны строго придерживаться его в дальнейшем. Форма (4.1) эквивалентна структуре, показанной на рис. 4.1, называемой падежным фреймом (case frame).

Рис. 4.1. Падежный фрейм предложения «Гамлет пронзил Лаэрта мечом»

Существуют компьютерные программы, использующие падежные фреймы для анализа высказываний с целью понимания их смысла. При разборе предложения программа выделяет в нем глагол и ищет в базе знаний соответствующий ему падежный фрейм. Затем она связывает значение агента, объекта и тому подобного с соответствующими узлами падежного фрейма. После этой процедуры становится ясно, что Гамлет – это человек, поражающий своего соперника с помощью меча. Эти лингвистические отношения запоминаются отдельно от реального предложения и даже от языка, на котором сформулировано предложения.

Таким образом, предикат – это форма представления информации, связывающая символы (слова) с объектами реального мира (или литературного произведения). Кроме того, он содержит информацию об истинности рассматриваемого утверждения. Высказывание может быть истинным или ложным. Если герой трагедии Гамлет действительно пронзил Лаэрта мечом, то выражение (4.1) идентифицируется как истинное. В противном случае оно будет ложным. Предположим что мы захотели использовать этот предикат с другими константами:

пронзил(ахилл, гектор, копье),

что равнозначно предложению: «Ахилл пронзил Гектора копьем». В общем случае мы можем записать

пронзил(X, Y, Z), (4.2)

где X, Y, Z – переменные. Разумеется, выражение (4.2) будет принимать значение «истина» не для всего возможного набора переменных, а только в том случае, если этот набор отвечает каким-то реальным (или изображаемым в литературном произведении) событиям.

Рассмотрим еще два предиката:

любит(саша, таня),

любит(нина, женя, люда).

Это два разных предиката, хотя они и имеют одинаковые имена. В первом случае мы имеем двухместный предикат, а во втором – трехместный. В этом и заключается причина отличия, обычно в таком случае и семантика предикатов тоже немного различная. В исчислении предикатов нет места двусмысленностям.

Приведем примеры одноместных предикатов: прекрасная(осень), вкусное(яблоко), отвратительный(скрежет). Эти предикаты описывают свойства объектов. А многоместные предикаты – соответственно отношения между объектами.

В исчислении предикатов помимо собственно самих предикатов используются еще и функции в привычном для нас смысле. Отличие между первыми и вторыми заключается в том, что предикаты возвращают значения алгебры логики: True и False (T и F), а функции – числовые значения. Например, функция плюс(два, пять) возвращает числовое значение семь, хотя по внешнему виду она ничем не отличается от предиката. Функция не может быть ни истинной, ни ложной.

Реальный мир (или воображаемый мир), литературное произведение (или математическая теория) наполнены множеством вещей, событий или местоположений. Язык сопоставляет этому многообразию определенные слова. Все, что мы описываем с помощью высказываний называется областью определения D. Истинность выражений зависит от соответствия констант, переменных, предикатов и функций объектам и отношениям в области определения.

Пусть область определения D – представляет из себя некоторое непустое множество. Интерпретация на D – это связывание логических объектов из D с каждой константой, переменной, предикатом и функциональным символом в выражении исчисления предикатов на основе следующих правил.

1. Каждой константе ставится в соответствие элемент из D.

2. Каждой переменной ставится в соответствие непустое подмножество из D; оно является областью допустимых значений для этой переменной.

3. Каждая функция f арности (числа операндов) m определяется для m параметров из D и задает отображение из в D.

4. Каждый предикат p арности n определяется для n параметров из D и задает отображение из в {T, F}.

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

«Если в воскресенье не будет дождя, Петя пойдет в гости к другу».

погода(дождь, воскресенье)пойдет_в_гости(петя, друг)

«Все баскетболисты – высокие».

X(баскетболист(X)высокий(X))

«Два плюс три равно пяти».

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ... Литература...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Семантика исчисления предикатов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Счетные и несчетные числовые множества
Теория множеств появилась в конце 19 века благодаря работам немецкого математика Георга Кантора (1845-1918). Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики.

Позиционные и непозиционные системы
Системой счисления называется метод записи чисел в виде комбинаций графических символов. Число – это некоторая абстрактная сущность для описания количества, а цифры – знаки, ис

Десятичная система
Существуют различные позиционные системы исчисления, отличающиеся между собой количеством используемых знаков. Чтобы различать числа в разных системах исчисления, в конце числа ставят индекс – симв

Двоичная система
Двоичная (бинарная) система счисления является самой простой из всех позиционных систем. Она содержит только два символа 0 и 1, и используется в компьютерной технике благодаря своей простоте и высо

Код Грея
Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является о

Троичная система счисления
Троичная система счисления– позиционная система счисления с целочисленным основанием равным 3. Она существует в двух вариантах: несимметричная и симметричная трои

Восьмеричная и шестнадцатеричная системы счисления
Позиционную систему счисления можно построить по любому основанию. Однако наибольшее практическое значение имеют: двоичная, десятичная, восьмеричная и шестнадцатеричная. Причем, последние две испол

Канторово множество
Математика изобилует парадоксальными объектами. Одним из них является канторово множество. Оно описывается следующим образом. Рассмотрим единичный отрезок, показанный на рис. 3.1. Удалим из

Ковер Серпинского и снежинка Коха
Ковер Серпинского получается из единичного квадрата удалением средней части (1/3, 2/3)*(1/3, 2/3), затем удалением из каждого квадрата (i/3, i+1/3)*(j/3, j+1/3) с

Стохастические фракталы
Стохастические фракталы получаются в том случае, если в итерационном процессе случайным образом менять какие-либо параметры. При этом получаются объекты, очень похожие на природные – несимметричные

Энтропийная размерность
Пусть X – компактное пространство с метрикой d. Тогда множество называется r-плотным

Фрактал Мандельброта
Существует бесконечное множество различных фракталов. Один из них носит имя Мандельброта. Фрактал Мандельброта – это множество точек на комплексной плоскости, для которых итеративная последо

Виды доказательства
Древние греки сформулировали основные правила логического доказательства. Они различали два вида доказательства: дедукцию и индукцию. Дедукция – это доказательство от общего

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

Булевы функции
Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества

Предикаты
Применяемые в математике высказывания обычно представляют собой описание свойств каких-либо математических объектов или описаний отношений, существующих между этими объектами. Для анализа закономер

Равно(плюс(два, три), пять)
«Некоторые люди любят грибы» X(личность(Х)

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

Правило резолюции
Правило резолюции (лат. resolutio – решение ): если выражения PA

Парадокс Рассела
Задание множеств характеристическим предикатом может приводить к противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента. Рассмотрим множество всех множ

Сравнение множеств
Множество содержится в множестве

Свойства операций над множествами
Пусть задан универсум . Тогда

Проблема континуума
Кантор был первым, кто стал рассматривать мощности (кардинальные числа) бесконечных множеств. Мощность счетного множества он обозначил древнееврейской буквой «алеф» с нулевым индексом:

Сумма нечетных чисел
Математическая индукция играет огромную роль в дискретной математике (именно в силу ее дискретного характера). Полученные этим методом доказательства в данной области математики почти столь же наде

Сумма натуральных чисел
А теперь используем метод индукции для доказательства того, что сумма первых n положительных целых чисел равна

Снова считаем подмножества
Доказывая теорему 5.1. мы неявно пользовались методом математической индукции. Теперь пришло время применить его явно. Итак, мы подозреваем, что число всех подмножеств множества из n элемент

Биномиальные коэффициенты
Слово бином означает выражение, состоящее из двух членов, например: x + y. Бином является частным случаем полинома. Биномом Ньютона наз

Треугольник Паскаля
Французский математик Блез Паскаль (1623-1662) составил таблицу из биномиальных коэффициентов. Она получилась треугольной, поскольку с увеличением степени бинома количество коэффициентов также увел

Бином Ньютона для дробных и отрицательных показателей
Формула бинома Ньютона (6.1) для целых положительных показателей была известна задолго до Исаака Ньютона (1643-1727), но им в 1676 году была указана возможность распростране

Гамма-функция
Биномиальная теорема определяет биномиальные коэффициенты через факториалы чисел n и k:

Размещения без повторений
Общее число размещений без повторений из n элементов по k элементов обычно обозначается так:

Сочетания без повторений
Число различных сочетаний без повторений обычно обозначается так: . Или так

Размещения с повторением
Если мы выбираем из множества n элементов размещения с повторениями k элементов, то в данном случае k может превосходить n. Теорема 7.3. Об

Сочетания с повторением
Теорема 7.4. Общее число сочетаний с повторениями k элементов, взятых из совокупности n различных элементов, равно

Формула Стирлинга
Рассматривая комбинаторные задачи, мы часто сталкиваемся с факториалами. Факториал – это очень быстро растущая функция, она растет быстрее экспоненты. При достаточно больших n (n >

Подстановки
Взаимно однозначная функция называется подстановкой на

Задача Фибоначчи
Итальянский математик Леонардо Фибоначчи жил в 13 столетии и одним из первых в Европе стал использовать арабские (индийские) цифры. Он придумал несколько искусственную задачу о кроликах, которых вы

Сумма чисел Фибоначчи
Определим сумму первых n чисел Фибоначчи. 0 = 0, 0+1 = 1, 0+1+1 = 2, 0+1+1+2 = 4, 0+1+1+2+3 = 7, 0+1+1+2+3+5 = 12, 0+1+1+2+3+5+

Формула для чисел Фибоначчи
Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле .

Простые числа
Все натуральные числа, большие единицы, распадаются на два класса. К первому относятся числа, имеющие ровно два натуральных делителя, единицу и самого себя, ко второму – все остальные. Числа первог

Алфавитное кодирование
Кодирование может сопоставлять код всему сообщению из множества

Помехоустойчивое кодирование
Пусть имеется канал связи C, содержащий источник помех: , где S – множес

Модулярная арифметика
В этом разделе все числа – целые. Говорят, что число a сравнимо по модулю n с числом b (обозначение

Шифрование с открытым ключом
Шифрование с открытым ключом производится следующим образом. 1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d