Список индивидуальных данных

Лабораторная работа №2. Логические модели представления знаний. Метод аналитических таблиц.

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

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

Теоретическая часть

При работе метода аналитических таблиц (или метода семантических таблиц) отсутствует необходимость приведения формулы к КНФ. Метод работает с формулами, представленными в ДНФ. При этом метод работает с четырьмя основными логическими связками конъюнкция, дизъюнкция, отрицание и импликация. Данный метод, как и метод резолюций, относится к методам опровержения, то есть для доказательства общезначимости (доказуемости) формулы доказывается тождественная ложность ее противоречие . Идея метода основывается на следующих утверждениях:

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

2. Для дизъюнкции двух формул необходимо выяснить равенство нулю обеих формул.

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

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

формулы конъюнктивного вида	формулы дизъюнктивного вида

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

Правила построения дерева:

1. Если формула вида , то обе половинки и строятся в одной ветке.

2. Если формула вида , то половинки и расщепляются на две ветки.

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

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

- каждая ветка либо замкнется (замкнутая аналитическая таблица), то есть получатся контрарные пары, что тождественно пустому дизъюнкту;

- либо никаких расщеплений дальше уже сделать нельзя.

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

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

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

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

Общая постановка задачи

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

Список индивидуальных данных

1. Докажите методом аналитических таблиц схемы логически верных рассуждений:

1.1. Закон противоречия ;

1.2. Правило контрапозиции: ;

1.3. Правило сложной контрапозиции: ;

1.4. Правило сечения: ;

1.5. Правило импортации: ;

1.6. Правило экспортации: .

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

2.1. Если кто-нибудь может решить эту задачу, то и любой математик может ее решить. Олег – математик, но не может решить эту задачу. Следовательно, задачу не сможет решить никто.

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

2.3. Каждый из первокурсников знаком с кем-либо из спортсменов. Некоторые из первокурсников не знакомы ни с одним любителем подледного лова. Следовательно, ни один спортсмен не является любителем подледного лова.

2.4. Всякий, кто может решить эту задачу – математик. Олег – математик, но не может решить эту задачу. Следовательно, задачу не может решить никто.

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

2.6. Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

2.7. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.

2.8. Если Джонс не встречал этой ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Эксперты установили, что убийство произошло до полуночи. Следовательно, Смит был убийцей.

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

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

2.11. Если кто-нибудь может решить эту задачу, то и какой-нибудь математик может ее решить. Олег – математик, но не может решить задачу. Следовательно, задачу не может решить никто.