Слова, задающие сущности изучаемого мира

1.   Слова, задающие сущности изучаемого мира.

2.   Слова, задающие атрибуты / свойства этих сущностей, а также их поведение и отношения.

Первый тип слов называется термами, второй – предикатами.

Некие сущности и переменные определяются упорядоченными последовательностями конечной длины из букв и символов, исключая зарезервированные. Константы и переменные определяют отдельные объекты рассматриваемого мира. Последовательность из n констант или переменных (1 £ n < ¥), заключенная в круглые скобки, следующие за символом функции, имя которой задано некоторой конечной последовательностью букв, называется функцией.

Например, функция f(x, y) принимает некоторые значения, которые определяются значениями констант и переменных (аргументов функции), содержащимися под знаком функции. Эти значения, так же как и аргументы, являются некоторыми сущностями рассматриваемого мира. Поэтому все они объединяются общим названием терм (константы, переменные, функции).

Атомарным предикатом (атомом) называется последовательность из n (1 £ n <¥) термов, заключенных в круглые скобки, следующие за предикатным символом, имя которого выражается конечной последовательностью букв. Предикат принимает одно из двух значений true или false в соответствии со значениями, входящих в него термов.

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

Символы первого класса позволяют определять новый составной предикат, используя уже определенные предикаты. Различие между символами первого класса лежит в правилах, в соответствии с которыми определяются значения истинности или ложности составного предиката в зависимости от истинности или ложности элементарных предикатов. Символы ® и », вообще говоря избыточны так, как:

но используются т.к. ® эквивалентен фразе «Если А, то В», а » - «А и В эквивалентны».

В качестве символов второго класса используются " и $. Эти символы называются кванторами общности и существования, соответственно. Переменная, которая квантифицирована, т.е. к ней применен один из кванторов , называется связанной. Квантор общности является обобщением, аналогом конъюнкции, а квантор существования – обобщением, аналогом дизъюнкции на произвольное, не обязательно конечное множество.

Действительно, пусть  Тогда для любого предиката U выполняется:

Аналогом законов Де Моргана для кванторов являются:

Часто возникает ситуация, когда некоторые переменные связываются кванторами ", а все другие - $. В этом случае может возникнуть неоднозначность при интерпретации кванторов.

Пусть задан некоторый предикат U(x, y). Очевидно, что возможно восемь случаев связывания его кванторами существования и общности:

Необходимо дать интерпретацию этим восьми случаям.

Рассмотрим, например, предикат подсистема(x, y), который задает отношение x подсистема y. Пусть переменная x связана квантором общности, а y – квантором существования. В этом случае существует две интерпретации: 1. «Для всех x, существует y, для которых x подсистема», 2. «Существует y, что все x его подсистемы».

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

-           ("x)($y)подсистема(x, y) – все объекты являются подсистемами;

-           ($x)("y)подсистема(x,y) – существует объект, который является подсистемой любого объекта;

-           ("y)($x)подсистема(x, y) – для всякого объекта существует объект, являющийся его подсистемой;

-           ("x)($y)подсистема(x, y) – существует объект, который является чей-то подсистемой.

Сделаем некоторые важные обобщения.

1.Чтобы найти отрицание выражения, начинающегося с кванторов, надо каждый квантор заменить на его двойственный и перенести знак отрицания за кванторы. Отсюда:

2.Одноименные кванторы можно переставлять. Разноименные кванторы можно переставлять только в одну сторону. Отсюда:

Если  то

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

Если  то

Действительно, если существует y, что все x его подсистемы, то для всех x существует y, для которого x подсистемы. Однако, перестановка в обратную сторону неверна. Например:

Если  то  необязательно.

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

3.

Докажем эту равносильность.

В этой выкладке мы опирались на следующее утверждение:

Определение ППФ и семантика логики предикатов

Комбинируя два типа символов, можно рекурсивно определить составную формулу логики предикатов, называемую правильно построенной формулой (ППФ) или логической формулой.

1.   Атомарный предикат является ППФ.

2.   Если F и G являются ППФ, то  также ППФ.

3.   Если F(x) – ППФ, то ("x)F(x) и ($x)F(x) – ППФ.

4.   Все результаты, полученные применением конечного числа раз (1) – (3) являются ППФ. Ничто другое не является ППФ.

Формулы логики предикатов строятся безотносительно к понятиям задаваемой предметной области. Если решено, что этими формулами будет описываться конкретная предметная область, то должно быть установлено соответствие между понятиями предметной области и этими формулами. Это предполагает следующие действия:

1.         Устанавливаются соответствия между константами логики предикатов и сущностями этой области. Константы º Имена объектов.

2.         Устанавливаются соответствия между формулами и функциональными отношениями предметной области.

3.         Устанавливаются соответствия между атомарными предикатами и концептуальными отношениями предметной области.

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

1.         Задается непустое множество D, определяющее сущности рассматриваемой предметной области, и элементы из D определяются как константы или переменные.

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

3.         Каждому предикату n переменных назначается отношение, определенное на Dⁿ, и его значение – True или False.

Множество D, рассматриваемое с позиций логики предикатов, называется областью переменных.

Значения ППФ оцениваются следующим образом:

1.         Если известны значения логических формул F и G, то значения  оцениваются по таблице истинности.

Похожие работы

Общая терминология программирования

Скачать

71422

1

0

... программирование [application programming] — разработка и отладка программ для конечных пользователей, например бухгалтерских, обработки текстов и т. п.   Системное программирование [system programming] — разработка средств общего программного обеспечения, в том числе операционных систем, вспомогательных программ, пакетов программ общесистемного назначения, например: автоматизированных систем ...

Программирование и достижения компьютерной техники

Скачать

60551

0

0

... разработки программ, но и разработку пакетов прикладных программ. Эти разработки должны обеспечивать высокое качество и вестись примерно так же, как и выпуск промышленной продукции. Достижения компьютерной техники   1.         Универсальные настольные ПК Что такое настольный компьютер, объяснять никому не надо — это любимое молодежью устройство, чтобы красиво набирать тексты рефератов, а ...

Графические возможности программирования в курсе информатики

Скачать

110612

10

19

... набор процедур и функций языков программирования Basic и Pascal, позволяют управлять графическим режимом работы экрана, создавать разнооборазные графические изображения и выводить на экран текстовые надписи. ГЛАВА 2. ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ БАЗОВОЙ ШКОЛЫ (НА ПРИМЕРЕ BASIC И PASCAL)   2.1 Разработка мультимедиа курса «Графические возможности языков ...

Функциональное и логическое программирование

Скачать

11287

1

10

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