русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Исчисление предикатов

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

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

Высказывание, или предложение, или факт - это просто утверждение, которое может быть истинно или ложно. Примеры предложений:

ЕСЛИ Смит является специалистом по ЭВМ, ТО Смит – оптимист.

СМИТ является специалистом по ЭВМ.

Из этих правил можно сделать вывод:

Смит – оптимист.

Более формально  выразим это, применив запись:

ЕСЛИ Р то Q, P СЛЕДОВАТЕЛЬНО Q

где P и Q предыдущие правила. Обнаружив совпадение, человек может утверждать, что суждение имеет некоторую приемлемую логическую структуру, и следовательно, может сделать вывод о том, что заключение

Смит - -оптимист

справедливо. Полностью утверждение выглядит следующим образом:

ЕСЛИ Смит является специалистом по ЭВМ, ТО Смит – оптимист.

СМИТ является специалистом по ЭВМ.

СЛЕДОВАТЕЛЬНО

Смит – оптимист.

На обоснованности примера никак не сказывается, имеет ли содержание утверждения какой-либо смысл в реальном мире. Например, следующее утверждение справедливо, хотя и абсурдно:

ЕСЛИ Смит является специалистом по ЭВМ, ТО Смит – спит.

СМИТ является специалистом по ЭВМ.

СЛЕДОВАТЕЛЬНО

Смит – спит.

Факты можно переписать в виде предикатов:

является (смит, специалист по ЭВМ)

является (смит, оптимист)

является (смит, спящий)

Эти факты выражают единичные отношения, указанные слева от скобок, и перечисленные в скобках некоторые объекты, связываемые данным соотношением.

В исчислении предикатов именами отношений соответствует термин предикаты, а объектам – аргументы. Порядок аргументов должен всегда задаваться в соответствии с интерпретацией предиката, принятой в рамках предметной области. Предикат может иметь произвольное число аргументов. Отдельные высказывания могут объединятся в сложные высказывания с помощью логических  отношений И (and, &), ИЛИ (or, V), НЕ(not, ~) и импликация (-->). Использованный выше метод вывода носит латинское название modus ponens (модус поненс или сокращение утверждения). Его можно записать следующим образом:

Если истинно А и истинно А --> В, то можно вывести В.

Знак --> импликация (произносится влечет) применяется для формирования правил и читается «ЕСЛИ ...., ТО ......». Таким образом, из двух данных предложений можно вывести третье.

Некоторый объект может быть представлен как константа, т.е. как конкретный индивидуум, или как переменная, например:

является (Х, специалист по ЭВМ).

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

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

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

Если применяется квантор общности, то говорят, что утверждение истинно для всех X в некотором множестве. Иными словами, если подставить вместо X любое значение, то утверждение будет истинно.

Если в утверждение входят несколько кванторов, то приходится учитывать их взаимное расположение.

Пользуясь кванторами, можно представить предложение:

Все специалисты по ЭВМ является программистами.

следующим образом:

 (X) специалист по ЭВМ (X) -->программист(X).

Предложение

Некоторые специалисты по ЭВМ является оптимистами.

может быть представлено так:

 (X) специалист по ЭВМ (X) -->оптимист(X).

Порядок, в соответствии с которым вводятся квантифицируемые переменные, может влиять на смысл утверждения: Например, выражение

 (X)  (Y) служащий (X) -->руководитель(Y,X).

Может быть интерпретировано так:

У каждого служащего есть руководитель.

Если же изменить порядок следования кванторов, например

  (X)   (Y) служащие (X) -->руководитель(Y,X).

то изменится и утверждение

Есть такое лицо, которое руководит всеми.

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

  1. Modus  ponendo ponens (MPP): A--> B, A ? B (? означает "верно, что "или "имеет место").
  2. Modus tollendo tollens (MTT): A--> B, ~A ? ~B (например ЕСЛИ моя программа правильна, ТО она будет работать, моя программа НЕ будет работать, СЛЕДОВАТЕЛЬНО, она не правильна).
  3. Двойное отрицание (ДО): ~A ? ~(~ B) (например, моя программа работала СЛЕДОВАТЕЛЬНО, моя программа НЕ НЕ работала).
  4. Введения конъюнкции (ВК): А, B ? {A & B} (например, моя программа работала, она правильна, СЛЕДОВАТЕЛЬНО, моя программа работала И она правильна).
  5. Reductio ad absurdum (RAA): A--> B, A--> ~ B ? ~A (например, ЕСЛИ моя программа правильна, ТО она будет работать, ЕСЛИ моя программа правильна ТО она не будет работать, СЛЕДОВАТЕЛЬНО, моя программа не правильна).
  6. Специализации (С):  (X) W(X), A ? W(X) (например, все предметы, являющимися компьютерами, не надежны, «TIPTOP»- компьютер, СЛЕДОВАТЕЛЬНО, «TIPTOP» ненадежен).

Раскрывая скобки и приводя подобные члены, всегда можно привести формулу исчисления высказываний к одной из двух форм:

  1. Конъюнктивная нормальная форма. Формула записана в виде конъюнкции дизъюнктов (С1 И С2 И... СN). Каждый дизъюнкт является дизъюнкцией атомарных предложений или отрицаний таких предложений (Р1 ИЛИ НЕ Р2 ИЛИ ... РМ). Это помогает в рассуждениях, так как истинность всей формулы означает истинность каждого дизъюнкта в отдельности, что облегчает рассмотрение формулы.
  2. Дизъюнктивная нормальная форма. Формула записана в виде дизъюнкции выражений, каждое из которых является конъюнкцией атомарных предложений или их отрицаний. В такой форме часто бывает удобно записывать булевы выражения, описывающие переключательные схемы или условия наступления каких-либо событий. Пусть, например, мы хотим написать, что два члена комитета, состоящего из трех человек (Андерсон, Бейнс и Кларк), голосовали за некоторое предложение, а один голосовал против. Мы можем символически записать "Андерсон голосовал "за" в виде А, "Бейнс голосовал "за"- в виде В, и "Кларк голосовал против" в виде "НЕ С". Выражая эту возможность и две остальные в виде составного предложения в дизъюнктивной нормальной форме, можно написать

(А И В И НЕ C) ИЛИ (НЕ А И В И С) ИЛИ (А И С И НЕ В).

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

Просмотров:

Вернуться в оглавление:Экспертные системы



Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.