Экзаменационное задание по курсу_ИИС_Мухамедов Р.С.. Экзаменационное задание по курсу Интеллектуальные информационные системы

• Название: Экзаменационное задание по курсу Интеллектуальные информационные системы
• Дата: 10.03.2023
• Размер: 97.26 Kb.
• Имя файла: Экзаменационное задание по курсу_ИИС_Мухамедов Р.С..docx
• Тип: Документы; #978663

Экзаменационное задание по курсу

Интеллектуальные информационные системы

Вариант 11

Выполнил:

Студент Мухамедов Р.С.

Группа ИДзс-61-20

1. Сравнить свойства, которыми обладает формальная система Исчисление высказываний со свойствами, которыми обладает Исчисление предикатов 1 порядка как формальная система. Указать свойства, общие для обеих формальных систем. Какие свойства различаются?

Исчисление предикатов первого порядка является формальной системой и является расширением исчисления высказываний.

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

Пример:

Зная следующие высказывания p = «Все люди смертны» и q = «Сократ – человек», мы не можем доказать, что r = «Сократ смертен». Мы можем это указать явно: (p q) → r, однако данная формула не будет применима для других людей.

Для устранения этого недостатка необходимо высказывание Q разделить на две части: «Сократ» (субъект) и «человек» (свойство субъекта), – и записать в виде функции:

человек(Сократ).

Так как субъекты могут меняться, следовательно, константу «Сократ» можно заменить на переменную, например:

человек(x).

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

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

Квантор общности показывает, что формула справедлива для любого x. Пример: x(человек(x) → смертен(x))

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

Пример: x(птица(x) → летает(x))

Пример:

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

x y любит(x, y)	все любят всех
x y любит(x, y)	у всех есть любимый человек
y x любит(x, y)	у всех есть кто-то, кто его любит
x y любит(x, y)	есть такой человек, который любит всех
y x любит(x, y)	есть такой человек, кого любят все
x y любит(x, y)	есть такой человек, который кого-нибудь любит

Переменные, находящиеся в сфере действия кванторов, называются связанными, остальные переменные — свободными.

Пример:

В формуле x Q(x, y, z) P(y) переменная x - связанная, y, z — свободные переменные.

Рассмотрим исчисление предикатов как формальную систему.

Словарь — компонента T:

а) счетное множество предметных переменных x1, x2, …, xn …;

б) конечное (может быть и пустое) или счетное множество предметных констант а1, а2, …;

в) конечное (может быть и пустое) или счетное множество функциональных букв f1, f2, …, fk, …;

г) конечное (может быть и пустое) или счетное множество предикатных букв

А1, А2, …; д) символы логических операций ¬, →, , , ↔;

е) символы кванторов , ;

ж) скобки ( ) и запятая.

Правила построения синтаксически правильных формул — компонента L:

а) всякий атом есть формула. Атом — это константа, переменная, предикат, функция;

б) если F1 и F2 – формулы и х – предметная переменная, то каждое из выражений ¬F1, F1 → F2, F1 F2, F1 F2, F1 ↔ F2, х F1, х F1 есть формула.

Аксиомы — компонента Q:

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

а) х A(х)→ A(a).

Аксиома говорит о том, что если предикат A(х) истинен для любых х, то и для некоторого a из того же универсума истинность предиката должна сохраняться.

б) А(a) → х А(х).

Аксиома говорит о том, что если найдется такое a, что предикат A(a) будет истинным, то верно, что существует х, для которого A(х) истинно.

Правила вывода — компонента R:

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

1) Пусть F1 и F2 — две формулы исчисления предикатов. И пусть в F1 переменная х не входит, а в F2 входит в качестве свободной переменной. Пусть, наконец, формула F1 → F2 является выводимой, тогда выводима и формула

F1 → х F2.

2) Если х содержится в качестве свободной переменной в F1 и не содержится в таком виде в F2 и если F1 → F2 есть выводимая формула, то х F1 → F2 также является выводимой.

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

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

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

Независимость аксиом является другим примером свойства формальной системы, которое заслуживает изучения. Аксиомы формальной теории называются независимыми, если никакую из них нельзя вывести из остальных. Ещё одним свойством формальных систем является существование алгоритма, который по заданной формуле устанавливает её выводимость. Такие системы называются разрешимыми.

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

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

2. Сколемовские стандартные формы. Понятие дизъюнкта.

Ранее было показано, что отношение логического следования F₁, F₂, …, F_n |- B равнозначно общезначимости формулы |- F₁& F₂& …&F_nB или противоречивости (невыполнимости) F₁& F₂& …&F_n&B. Так как в дальнейшем в процедурах доказательства мы будем иметь дело только с невыполнимыми формулами, то без потери общности ограничимся ими.

Очевидно, что если формулы F и Ф равносильны, то F логически невыполнима тогда и только тогда, когда логически невыполнима Ф.

Благодаря этому утверждению и в силу того, что алгоритмы приведения к ПНФ сохраняют равносильность невыполнимых формул, мы ограничимся формулами, имеющими пренексный вид.

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

Формула F называется -формулой, если она представлена в ПНФ, причем кванторная часть состоит только из кванторов общности, т. е.

F=   x₁   x₂ …   x_r M,

где M – бескванторная формула.

Таким образом, возникает задача устранения кванторов существования в формулах, представленных в ПНФ. Это можно сделать путем введения сколемовских функций.

Пусть формула F представлена в ПНФ:

F= K₁ x₁ K₂ x₂ … K_r x_r M, где K_j { , }.

Пусть K_i (1 i r) – квантор существования в K₁ x₁ K₂ x₂ … K_r x_r . Если i=1, т.е. ни один квантор общности не стоит впереди квантора существования, то выбираем константу c из области определения М, отличную от констант, встречающихся в M, и заменяем х на с в М. Из префикса кванторсуществования K₁ x₁вычеркиваем. Если перед квантором существования K_i стоит  , , …,  кванторов общности, то выбираем m-местный функциональный символ f, отличный от функциональных символов в М, изаменяем х_iна f ( , , …, ), называемую сколемовской функцией, в М. Квантор существования K_i х_iвычеркиваем из префикса. Аналогично удаляются и другие кванторы существования в ПНФ. В итоге получаем  -формулу. Опишем алгоритм последовательного исключения кванторов существования.
Алгоритм Сколема

Шаг 1. Формулу представить в ПНФ.

Шаг 2. Найти наименьший индекс i такой, что K₁ , K₂ , … K_i все равны  , но K_i =  . Если i = 1, т. е. квантор   стоит на первом месте, то вместо х₁в формулу М подставить константу с, отличную от констант, встречающихся в М. Еслитакого i нет, то СТОП: формула F- является  -формулой.

Шаг 3. Взять новый (i – 1)-местный функциональный символ f_i, не встречающийся в F. Заменить F на формулу

 x₁   x₂ …   x_i-1 K_i+1 x_i+1,…, K_r x_r M[x₁, x₂, …, x_i-1, f (x₁, x₂, …, x_i-1), x_i+1, …, x_r].

Шаг 4. Перейти к шагу 2.

Таким образом, алгоритм Сколема, сохраняя свойство невыполнимости, приводит произвольную формулу, имеющую пренексный вид, к  -формуле.

Напомним, что атом или его отрицание называется литерой. Литера вида А называется положительной, а вида  А – отрицательной.

Рассмотрим теперь преобразование бескванторной части (матрицы) к виду так называемых дизъюнктов. Дизъюнктом называется формула вида

L₁  L₂  … L_k,

где L₁ ,L₂ ,…,L_k – произвольные литеры.

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

Другие названия дизъюнкции — логическое сложение, логическое ИЛИ или просто ИЛИ.

Дизъюнкция изучается в информатике при рассмотрении раздела алгебра логики.

В естественных языках дизъюнкцию заменяют союзом «или».

Дизъюнкты, соединенные знаком &, образуют конъюнктивную нормальную форму (КНФ). Существует простой алгоритм равносильного преобразования произвольной бескванторной формулы в КНФ. Представим его в развернутом виде.
Алгоритм приведения к КНФ

Шаг 1. Начало: дана формула F, составленная из литер с применением связок & и  . Предполагается, что в формуле исключены скобки между одинаковыми связками, т. е. нет выражений вида

Ф₁  (Ф₂  Ф₃), (Ф₁  Ф₂)  Ф₃

или

Ф₁ & (Ф₂ &Ф₃), (Ф₁ &Ф₂) &Ф₃.

Шаг 2. Найти первое слева в хождение двух символов  ( (или ) ). Если таких вхождений нет, то СТОП: формула F находится в КНФ.

Шаг 3. Пусть первым вхождением указанной пары символов является  (. Тогда взять наибольшие формулы Ф₁, Ф₂, …, Ф_r, ₁, ₂, …, _s такие, что в F входит формула F₁ = Ф₁  Ф₂  …  Ф_r  (₁& ₂& …& _s), которая связана с вхождением  (. Заменить формулу F на формулу (Ф₁  Ф₂  …  Ф_r  ₁)& (Ф₁  Ф₂  …  Ф_r  ₂) & …& (Ф₁  Ф₂  …  Ф_r  _s).

Шаг 4. Пусть первым вхождением является ) . Тогда взять наибольшие формулы Ф₁, Ф₂, …, Ф_r, ₁, ₂, …, _s такие, что в F входит формула F₁ = (₁& ₂& …& _s)   Ф₁  Ф₂  …  Ф_r, связанная с вхождением ) . Заменить F₁на (₁ Ф₁  Ф₂  …  Ф_r)& 2( Ф₁  Ф₂  …  Ф_r) & …& (_s  Ф₁  Ф₂  …  Ф_r).

Шаг 5. Перейти к шагу 2.

Итак, последовательным применением алгоритма приведения к ПНФ, алгоритма Сколема и алгоритма приведения к КНФ с сохранением свойства невыполнимости любая формула F может быть представлена набором дизъюнктов, объединенных кванторами общности. Такую формулу будем называть формулой, представленной в Сколемовской стандартной форме (ССФ). В дальнейшем формулы вида   x₁   x₂ …   x_r[D₁ & D₂& …& D_k] , где D₁ , D₂ , …, D_k - дизъюнкты, а x₁ , x₂, …, x_r - различные переменные, входящие в эти дизъюнкты, будет удобно представлять как множество дизъюнктов S ={ D₁ , D₂ , …, D_k }.
3. Решить задачу. Доказать методом резолюции справедливость рассуждения: Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель не был запуган, то Генри не покончил жизнь самоубийством. Следовательно, если Генри покончил жизнь самоубийством, то записка была найдена.

Решение:

Введем булевы переменные:

х – «свидетель не запуган»,

у – «Генри покончил самоубийством»,

z – «записка найдена».

Составим конъюнкцию посылок и посмотрим, не является ли она противоречием.

Здесь употреблено выражение «либо..., либо...», поэтому первое составное высказывание следует записать в виде ,  что эквивалентно . Конъюнкция посылок имеет вид:

=

=

=



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