February 24, 2009

Описова логіка

Описова логіка (англ. Description logic) - сімейство мов для представлення баз знань, який можна використовувати для формулювання визначень понять предметної області у структурованій і формально-обґрунтованій формі. Описова логіка викоритовується для проектування онтологій у Семантичному Вебі.
Часто описову логіку ще називають Дескрипційною логікою.

Синтаксис описової логіки складається з:
  • Множина унарних предикатних символів, які позначають імена понять.
  • Множина бінарних зв'язків, які позначають імена відношень.
  • Рекурсивні визначення одних понять на основі імен інших понять та імен відношень, використовуючи конструктори.
До конструкторів можуть відноситись з одного боку операції над поняттями (аналогічно операціям над множинами: об'єднання, доповнення, перетин тощо) чи накладання обмежень на відношення (транзитивніть, рефлексивність, функціональність і т.п.).

Основні задачі описової логіки:
  • узагальнення - визначити на основі означень чи є одне поняття підпоняттям іншого
  • класифікація - визначити відповідності об'єкта поняттю
  • перевірка несуперечливості концепції - чи виконувані з точки зору логіки критерії визначення поняття
Однією з найважливіших характерних особливостей описових логік є їх акцент на практичну можливість логічного виведення. Рішення будь якої задачі здійснюється шляхом її опису з наступним виконанням запиту щодо того, чи є ця задача узагальненням однієї із кількох можливих категорій рішень. У стандартних системах логіки першого порядку часто неможливо передбачити час вироблення рішення, а користувачу найчастіше самостійно доведеться розробити представлення, яке дозволяє виключити множину висловлювань, які найімовірніше змусять систему потратити кілька тижнів щоб вирішити поставлену задачу. З іншого боку у описових логіках все спрямовано на забезпечення того, щоб перевірка узагальнення могла бути вирішена за час, поліноміально залежний від розміру описів.
UPD У статті О формальных основах OWL є доволі толковий опис описової логіки.
На основі цієї статті шпаргалка описових логік (FreeMind):

February 16, 2009

Задачі з прийняття рішень

1. Доведення з нульовим розголошенням (Zero-knowledge proof)
Суб'єкт A знає деяку інформацію - суб'єкт B хоче отримати цю інформацію, але перш ніж отримати цю інформацію B хоче впевнитись, що A справді знає цю інформацію, з іншого боку суб'єкт A поки не хоче розголошувати цю інформацію (наприклад, поки B не заплатить, але B заплатить тільки тоді, коли буде впевнений (на практиці з великою ймовірністю), що у A достовірна інфомація).
2. Задача упередженого порадника
Є всезнаючий порадник, у якого можна завжди проконсультуватись, але порадник хоч і все знає та не завжди говорить правду (відповідно до власних інтересів), задача полягає в тому, щоб на основі відповідей порадника прийняти правильне рішення (ТАК або НІ).
Виявляється є ефективне ЙМОВІРНІСНЕ рішення цієї задачі.