21195

Алгоритмы решения логических задач

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-08-02

57 KB

35 чел.

PAGE  3

\\Лекция №8

8. Алгоритмы решения логических задач

8.1. Метод  резолюций\\

В основу современных методов решения логических задач положены формальные конструкции дедуктивной логики с использованием силлогизмов Аристотеля, основанных на логике утверждений (суждений). Например, из двух утверждений: "Все люди смертны" и "Аристотель – человек" следует вывод: "Аристотель смертен".

\\Используя дедуктивную логику, из двух или нескольких исходных аксиом, имеющихся в логической базе знаний, можно вывести очередное утверждение-следствие или доказать истинность (ложность) целевого утверждения (теоремы) путем использования определенных правил вывода. Этот процесс получения новых знаний из имеющихся аксиом называют логическим выводом на знаниях.

Основным методом решения логических задач на основе логического вывода является метод резолюций. Утверждение, выведенное из двух или нескольких аксиом с использованием метода резолюций, называется резольвентой. Этот метод был разработан Эрбраном в 1930г. и практически реализован Дж.Робинсоном в 1963г.

Основными типами логических задач, которые решаются с использованием метода резолюций, являются следующие:

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

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

Доказательство теорем с использованием метода резолюций осуществляется в следующем порядке.

1) Теорема доказывается от противного, т.е. в базу знаний вводится отрицание того утверждения, которое требуется доказать. Например: если требуется доказать теорему  P (а), то в базу знаний вводят  утверждение  ~ P (а).

2) Если один и тот же предикат (литерал) находится в составе одной аксиомы (фразы Хорна) и с отрицанием - в другой аксиоме, то эти аксиомы являются резольвентными (резолирующими), а резольвента образуется в результате объединения обеих аксиом с исключением дублирующих предикатов. Например,  две аксиомы P (х) ~ Q (y, z)  и  Q (y, z) ~ R (y, z)  являются  резольвентными  и  резольвента  записывается как  P (х) ~ R (y, z).

3)  Переменная может быть заменена константой или другим термом.  Например, две аксиомы  P (х)  ~ Q (а, b)  и  Q (x, y)  ~ R (x, y)  являются  резольвентными.  При этом  переменная  x сопоставляется  с константой а,  переменная  y - с константой  b,  а  резольвента записывается как  P (a)   ~ R (a, b).  В ней  переменные заменены константами.

4) Аксиома-факт может резолировать с любым предикатом аксиомы-правила по схеме, указанной в п.2. Например, из факта  Q (a, b)  и правила  P (x, y) ~ Q (x, y)  образуется  резольвента-факт  P (a, b).

5) Разные  константы  не  сопоставляются  одна  с  другой,  поэтому  аксиомы  P (a)  ~ Q(a, b) и   Q (а, c)  ~ R (b, с)   не являются  резольвентными.

6) Если в процессе доказательства теоремы получились любые две противоречивые аксиомы типа  P (а)  и  ~ P (а),  то их резолюцией является пустая фраза (противоречие) , которое означает, что предположение о ложности (отрицании) исходной теоремы неверно. \\Следовательно, теорема является истинной и процесс доказательства на этом заканчивается.

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


8.2. Пример использования метода резолюций

Рассмотрим пример использования метода резолюций для решения следующей задачи. Пусть база знаний о предметной области "Отцы и дети" состоит из фактов:

Боб является сыном Кости,

Костя является сыном Олега

и  правил:   если  x  является  сыном  y,  то x – потомок  y;

если  y  является  сыном  z,  то y – потомок  z;

если  x  является  потомком  y,   а  y – потомок  z,   то x – потомок  z.

Требуется доказать, что  Боб является потомком Олега.

В соотвествии с методом резолюций решение поставленной задачи может быть осуществлено следующим образом.

1) Введем константы:    B – Боб,   K – Костя,   O – Олег

и  предикаты:  S ( x, y )  -  x  является сыном  y;

P ( x, y )  -  x   является потомком  y.

2) Представим аксиомы (факты и правила) базы знаний в пренексной нормальной форме (7.2):

S ( B, K ); S ( K, O );

х у ( S ( x, y )    Р ( х, у ) );

х у ( S ( y, z )    Р ( y, z ) );

х у ( ( ( Р ( x, y )  & Р ( y, z ) )    Р ( х, z ) ).

Требуется доказать  истинность утверждения (теоремы):

Р ( B, O )      (8.1)

3) Исключая кванторы обобщения и учитывая преобразования табл.7.2, представим аксиомы базы знаний в виде фраз Хорна:

S ( B, K ) S ( K, O )

~ S ( x, y )    Р ( х, у )

~ S ( y, z )    Р ( y, z )

~ Р ( x, y )    ~ Р ( y, z )   Р ( х, z )

4) В соответствии с методом резолюций добавим к аксиомам базы знаний отрицание теоремы  (8.1):

~ Р ( B, O )       (8.2)

S ( B, K )       (8.3)

S ( K, O )       (8.4)

~ S ( x, y )    Р ( х, у )     (8.5)

~ S ( y, z )    Р ( y, z )      (8.6)

~ Р ( x, y )    ~ Р ( y, z )   Р ( х, z )    (8.7)

5) Применяя резолюцию к утверждениям (8.5) и (8.7), получим резольвенту:

~ S ( x, y )   ~ Р ( y, z )   Р ( х, z )    (8.8)

6) Сопоставляя в утверждениях (8.2) и (8.8)  переменные  x  с  B  и   z  с  O,  получим:

~ S (B, y )    ~ Р ( y, O )     (8.9)

7) Из (8.3) и (8.9) следует: ~ Р ( K, O )      (8.10)

8) Из (8.4) и (8.6) получим:    Р ( K, O )      (8.11)

9) Применяя резолюцию к утверждениям (8.10) и (8.11), получим пустую фразу.

Это означает, что теорема (8.1) является истинной.


8.3. Другие алгоритмы решения логических задач

Наряду с методом резолюций существуют другие алгоритмы решения логических задач, к числу которых относятся:

а) полный перебор возможных вариантов с целью нахождения оптимального решения;

б) эвристические методы исключения неперспективных вариантов с использованием эвристик – правил, не имеющих строгого математического обоснования;

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

Рассмотрим пример использования алгоритма полного перебора вариантов для решения задачи  экспертной системы (раздел 4.11)  по определению объекта, который:

а) имеет колеса;   б) не имеет винта;   в) не имеет крыльев;    г) возит грузы.

Эта задача в терминах предикатов, введенных в разделе 7.4, может быть сформулирована следующим образом: установить значение переменной x,  для которой истинно утверждение:

Q( x )  P( x, kls ) & ~ P( x, vnt ) & ~ P( x, krl ) & P( x, vgr ). (8.13)

Эту задачу можно решить методом прямого перебора утверждений базы знаний раздела 7.4, позволяющего установить, что истинное значение предиката Q(x), соответствующее истинному значению утверждения  (8.13), достигается для   x  grz.

Таким образом, искомым объектом является грузовик.

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

8.4. Особенности логического вывода на знаниях

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

28700. Слом старого государственного аппарата после Октябрьского вооруженного восстания1917г Упразднение органов буржуазного самоуправления. Роспуск Учредительного собрания 12.77 KB
  Руководство этим процессом осуществляли Всероссийские съезды Советов Петроградский ВРК ВЦИК НКВД и другие органы. когда Декретом ВЦИК и СНН упразднялись все сословия и сословные организации и учреждения. Председатель ВЦИК Я. Свердлов от имени ВЦИК и ЦК партии большевиков зачитал и предложил принять Декларацию прав трудящегося и эксплуатируемого народа.
28701. Военно-революционный комитет Петрограда и его роль в переходе власти к Советам. Создание милиции, судебных органов, ВЧК и Красной Армии, их компетенции и борьба против контрреволюции 14.26 KB
  Создание милиции судебных органов ВЧК и Красной Армии их компетенции и борьба против контрреволюции.10 вводится в действие приказ По рабочей милиции. НКВД и Наркомюст утвердили совместную инструкцию Об организации советской рабочекрестьянской милиции. Руководство органами милиции осуществляло Главное управление рабочекрестьянской милиции НКВД РСФСР.
28702. «Декларация прав трудящегося и эксплуатируемого народа», ее содержание и значение 12.2 KB
  Декларация прав трудящегося и эксплуатируемого народа ее содержание и значение. Декларация Прав Трудящегося И Эксплуатируемого Народа важнейший конституционный акт Советской республики законодательно закрепивший завоевания Октябрьской революции и провозгласивший основные принципы и задачи социалистического государства. Декларация была утверждена III Всероссийским съездом рабочих солдатских и крестьянских депутатов. Декларация состояла из четырех разделов.
28703. «Декларация прав народов России», ее содержание и значение 15 ноября 1917 г. 11.56 KB
  Декларация прав народов России ее содержание и значение 15 ноября 1917 г. Исполняя волю съездов Совет Народных Комиссаров решил положить в основу своей деяти по вопросу о национальностях России следующие начала: 1 Равенство и суверенноcть народов России. 2 Право народов России на свободное самоопределение вплоть до отделения и образования самостоятельного государства. 4 Свободное развитие национальных меньшинств и этнографических групп населяющих территорию России.
28704. Мероприятия Советского государства по созданию новой экономики. Национализация банков связи, транспорта, внешней торговли, крупной промышленности 13.92 KB
  ВСНХ принял постановление согласно котму все частные предпря с числом рабочих свыше 5 при наличии механического двигателя на предприятии или 10 без двигателя человек объявлялись национализированными. органа по рукву эккой страны учреждался Высший совет народного хозва ВСНХ. ВСНХ действовал в качестве органа при правве. ВСНХ д.
28705. Основные направления в развитии гражданского, уголовного, колхозного и трудового права с конца 50-х и до середины 80-х гг. XX в. 13.31 KB
  СССР 1977 г. СССР регулировала также личную собствсть граждан. Закрепляя право на труд Конституция СССР 1977 г. Одновременно в Конституции содержались положения об обязанности каждого гражданина СССР добросовестно трудиться в избранной им области строго соблюдать трудовую и производственную дисциплину.
28706. Разработка и принятие Конституции СССР 1977 г. Ее основные положения. Закрепление однопартийной системы в стране 12.86 KB
  Политическую основу СССР составляют Советы народных депутатов, Основой эк-кой системы признана социалистическая собст-ть на средства пр-ва. В Конст. констатировались построение развитого социалистического общества и создание общенародного гос.ва. В ней закреплялись «руководящая и направляющая» роль Коммунистической партии и новые формы
28707. Правовые взгляды 60 - 80-х гг. Развитие идеи социального общенародного государства и его правовой основы 12.99 KB
  Стабильность общго и госго строя в рассматриваемый период обусловливает и устойчивое развитие советского права для которого не свойственны какиелибо существенные изменения однако в связи с большим объемом нормативноправовых актов требуется проведение систематизации и кодификации. Завершаются проводившиеся более 20 лет работы по кодификации основных отраслей права. В самой системе права можно выделить три тенденции: 1 образование одной отрасли права в результате объединения различных актов регулирующих сходные группы отношений...
28708. Меры по укреплению законности, трудовой дисциплины, совершенствованию и углублению самоуправления народа и дальнейшей демократизации общества (1-ая половина 80-х гг. XX в.) 11.41 KB
  Меры по укреплению законности трудовой дисциплины совершенствованию и углублению самоуправления народа и дальнейшей демократизации общества 1ая половина 80х гг. Радикальная реформа общества начавшаяся сверху в 1985 г. Быстро происходи размежевание общества на демократов националпатриотов и коммунистов.