X-PDF

Метод резолюций в исчислении высказываний

Поделиться статьей

Существует эффективный метод логического вывода – метод резолюции. Он основан на том, что выводимость формулы F из множества посылок F 1, F 2, F 3, …, Fn равносильна доказательству теоремы

├─ (F1 Ù F2 Ù F3 Ù… Ù Fn ® F),

формулу которой можно преобразовать так:

├─ (F1 Ù F2 Ù F3 Ù… Ù Fn ® F)

├─ ( Ú F)

├─ .

Следовательно, заключение F истинно тогда и только тогда, когда формула F1 Ù F2 Ù F3 Ù… Ù Fn Ù º0. Это возможно при значении 0 хотя бы одной из подформул Fi или .

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

F1 Ù F2 Ù F3 Ù… Ù Fn Ù º0.

Пусть и – дизъюнкты. Дизъюнкт называется резольвентой дизъюнктов D 1 и D 2 по переменной А и обозначается через res A(D 1, D 2). Резольвентой дизъюнктов D 1 и D 2 называется резольвента по некоторой переменной и обозначается через res (D 1, D 2), res (A, )=0. Если дизъюнкты D 1 и D 2 не содержат контрарных переменных, то резольвент у них не существует.

Пример. Если , , то , , не существует.

Утверждение. Если существует, то ├─ .

Пусть – множество дизъюнктов. Последовательность формул называется резолютивным выводом из S, если для каждой формулы (i =1,…, n) выполняется одно из условий:

1) .

2) существуют такие, что .

Теорема (о полноте метода резолюций). Множество дизъюнктов S противоречиво в том и только в том случае, когда существует резолютивный вывод из S, заканчивающийся 0.

Алгоритм вывода по методу резолюций.

Шаг 1. Придать отрицание заключению, т.е. .

Шаг 2. Привести все формулы посылок и отрицания заключения к конъюнктивной нормальной форме.

Шаг 3. Выписать множество дизъюнктов всех посылок и отрицания заключения S = { D 1, D 2, …, Dk }.

Шаг 4. Выполнить анализ пар множества S по правилу:

«если существуют дизъюнкты Di и Dj, один из которых (Di) содержит некоторую переменную, а другой (Dj) – отрицание этой переменной, то сформировать новый дизъюнкт – резольвенту, исключив контрарные переменные».

Шаг 5. Если в результате будет получена пустая резольвента – 0, то останов, в противном случае включить резольвенту в множество дизъюнктов S и перейти к шагу 4.

Шаг 6. Если нет возможности сформировать новые резольвенты, а пустую резольвенту не получили, то останов – формула не выводима из множества посылок в исчислении высказываний.

Примеры.

1. Работа автоматического устройства, имеющего три клапана А, В и С, удовлетворяет следующим условиям: если не срабатывают клапаны А или В или оба вместе, то срабатывает клапан С . если срабатывают клапаны А или В или оба вместе, то не срабатывает клапан С. Следовательно, если срабатывает клапан С, то не срабатывает клапан А.

1) – посылка .

2) – посылка .

3) – отрицание заключения .

4) множество дизъюнктов: S ={(А Ú C), (B Ú C), , , C, А }.

Построим резолютивный вывод, заканчивающийся 0.

1) .

2) .

Так доказано, что если срабатывает клапан С, то не срабатывает клапан А.

Представленная информация была полезной?
ДА
58.6%
НЕТ
41.4%
Проголосовало: 988

2. Доказать истинность заключения

1) A – посылка .

2) B – посылка .

3) – посылка .

4) – отрицание заключения .

5) множество дизъюнктов: S ={ A, B, (), C } .

6) .

7) S 1={ A, B, (), C, ()} .

8) .

9) S2 ={ A, B, (), C, (), } .

10) – пустая резольвента.

Так доказана истинность заключения по принципу резолюции.

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

Пример. Доказать истинность заключения

1) – посылка .

2) – посылка .

3) – посылка .

4) – отрицание заключения .

5) S ={ A, C, , , , }

6) .

7) .

8) .

9) .

10) – пустая резольвента.

Так доказана истинность заключения , граф доказательства изображен на рис.1.3.

 
 

Замечание. Метод резолюций достаточен для обнаружения возможной выполнимости данного множества – дизъюнктов S. Для этого включим в S все дизъюнкты, получающиеся при резолютивном выводе из S. Из теоремы о полноте метода резолюций вытекает

Следствие. Если множество дизъюнктов S содержит резольвенты всех своих элементов, то S выполнимо тогда и только тогда, когда 0Ï S.

Двойственным к правилу резолюций является правило согласия. Пусть , – конъюнкты. Положим , .

Пусть – множество конъюнктов. Последовательность формул называется выводом из S по правилу согласия, если для каждой формулы (i =1,…, n) выполняется одно из условий:

1) .

2) существуют такие, что .

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


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.6%
НЕТ
41.4%
Проголосовало: 988

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

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


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

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


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет