Исчисление высказываний. В математической логике высказыванием



Дата24.07.2016
өлшемі152 Kb.
#219906

  • Исчисление высказываний. В математической логике высказыванием называется такое предложение, выражающее мысль, которая является либо истинной, либо ложной. Истинность и ложность являются логическими значениями высказывания. Принято соглашение обозначать высказывания прописными латинскими буквами A, B, C, ...с индексами и без индексов и называть пропозициональными. Имя - это слово или словосочетание, обозначающие какой либо предмет мысли и используемое в качестве логического подлежащего или логического сказуемого в высказываниях типа « А есть В ». Функтор- выражение, которое на основе других выражений, называемых аргументами, образует новое, более сложное осмысленное выражение. (смотри читаемые специальные курсы).

  • Логические операции и их основные формы. Логические операции:

отрицание A (обозначения: A, ~A, A) или дополнение к A;

конъюнкция или логическое умножение A и B (обозначения: A B; A B; A &B);

дизъюнкция или логическое сложение A и B (обозначение A B);

импликация (обозначение: A B; A B);

эквиваленция или эквивалентность (обозначение: A  B);

Символы логических операций , , , , , называются пропозициональными знаками и приоритет их выполнения слева направо -наивысший, а ≡ -наинизший. С помощью логических операций образуются сложные высказывания (смотри читаемые специальные курсы).



  • Исчисление высказываний. Логические категории. В математической логике высказыванием называется такое предложение, выражающее мысль, которая является либо истинной, либо ложной. Истинность и ложность являются логическими значениями высказывания. Принято соглашение обозначать высказывания прописными латинскими буквами A, B, C, ...с индексами и без индексов и называть пропозициональными. Высказывания бывают простые и сложные.

  • Например, Треугольник - геометрическая фигура. Луна- -Спутник Земли. Земля – планета. Это простые высказывания бывают простые и сложные. Сложные высказывания образуются из простых, с помощью функторов ( связок). Сложное высказывание принято называть именем функтора( ОТРИЦАНИЕ ВЫСКАЗЫВНИЯ (p и q ), КОНЪЮНКЦИЕЙ ВЫСКАЗЫВАНИЯ, ДИЗЪЮНКЦИЕЙ(слабой, сильной),ИМПЛИКАЦИЕЙ высказываний, ЭКВИВАЛЕНЦИЕЙ). Имя - это слово или словосочетание, обозначающие какой либо предмет мысли и используемое в качестве логического подлежащего или логического сказуемого в высказываниях типа « А есть В ». Функтор - выражение, которое на основе других выражений, называемых аргументами, образует новое, более сложное осмысленное выражение. Например, функтор «неверно, что», «Если, то», «И», «или», «либо, либо», «тогда и только тогда, когда» с помощью которых образуются высказывания из других высказываний (смотри читаемые специальные курсы)

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

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

  • Логический закон. ( он же называется логической истиной). можно определить так: это логическая форма, которая порождает истинное предложение при любой подстановке вместо переменных их значений формы , являющиеся логическими законами, обладают следующим замечательным свойством: их использование позволяет находится в рамках истинного значения и, что особенно важно, на основе истинных знаний продвигаться к новым знаниям, которые также будут истинными. Рассуждения, форма которых – логический закон, называется правильным. Различие между правильностью и истинностью отчетливо проявляется в тех случаях, когда правильные рассуждения приводят к ложным заключениям. Это возможно тогда, когда исходные данные являются ложными. Познавательные ошибки, связанные с неверным представлениями о действительном положении дел, называются содержательными. Эта ошибка может быть результатом заблуждения, т.е. несоответствующего, одностороннего, но непреднамеренного, отражения предметов и явлений в сознании человека, или продуктом лжи, дезинформации как целенаправленного действия. Ошибки, связанные с нарушением правильности мышления, называются формальными или логическими. Они делятся на паралогизмы и софизмы. Паралогизм – это непреднамеренная логическая погрешность. Она, как правило, является продуктом невысокой логической культуры человека. Софизм – это преднамеренное нарушение требования логики, прием интеллектуального мошенничества, связанный с попыткой ложь выдать за истину.

  • Логические операции и их основные формы. Логические операции:

отрицание A( обозначения: A, ~A, A) или дополнение к A;

конъюнкция или логическое умножение A и B(обозначения: A B;



A B; A &B);

дизъюнкция или логическое сложение A и B (обозначение A B) ;

импликация (обозначение: A B; A B);

эквиваленция или эквивалентность (обозначение: A  B);



  • Символы логических операций , , , , , называются пропозициональными знаками. С помощью логических операций образуются сложные высказывания. Пропозициональная форма. Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством логических операций, называется формулой алгебры логики или пропозициональной формой (смотри читаемые специальные курсы).

  • Нормальные формы. На функциональном языке все программы представляются в виде выражений, а процесс выполнения заключается в определении значения этого выражения ( это называется оценкой выражения). Оценка выражения производится путем упрощения (такая часть выражения называется редексом, причем сам редекс также является отдельным выражением). Операция упрощения называется РЕДУКЦИЕЙ. Преобразование некоторого выражения Е в выражение F посредством многократной редукции записывается как E  F. Процесс редукции завершается, когда выражение, преобразованное редукцией, не содержит больше редекса.

Выражение, не содержащее редекса называется нормальной формой ( нормальная форма является результатом оценки). Например, при оценке выражения записанного в префиксной форме ( +(/6 2) (* 2 5)) сначала выбирают его редуцируемые части (/6 2)(*2 5) и упрощаются соответственно до 3 и 10. При этом не имеет значения очередность редукции частей (/6 2) (*2 5). Кроме того, обе части могут быть проредуцированны одновременно. Если редукция выполняется последовательно слева направо, то процесс оценивания записывается следующим образом:

( +(/6 2) (*2 5))  (+3(*2 5)) (+3 10),

Полученное в результате редукции выражение (+3 10) также является редуцируемым, поэтому имеем (+3 10)13. Результат 13 невозможно упростить, поэтому он считается нормальной формой (смотри читаемые специальные курсы).



  • Правила образования тавтологий и противоречий. Имеются специальные правила по этому поводу (смотри читаемые специальные курсы).

  • Переход от одной формы представления функции к другой. Имеются специальные правила по этому поводу (смотри читаемые специальные курсы).

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

Формулы логики высказываний, составленные по этим правилам ,называются правильно построенными формулами или просто формулами. Если в какую либо формулу вместо ее переменных подставить константы, то эта подстановка называется конкретизацией. Формулы истинные на всех наборах значений своих аргументов, называются общезначимыми. Если какая-либо формула α является общезначимой, то этот факт обычно записывается с использованием знака ╞ общезначимости, который ставится перед формулой: ╞ α. Проверку формулы на общезначимость можно осуществить с помощью таблицы истинности. Общезначимость формул называемых импликативными формулами, является важным свойством для получения заключения об истинности, называемого заключением, при истинности ,называемого посылкой.

В логике высказываний общезначимые формулы обычно называются законами логики высказываний. Наиболее известные следующие законы:

1.Коммутативные

α1 & α2 ≡ α2 & α1

α1  α2 ≡ α2 α1

2. Дистрибутивные

α1 & (α2 α3) ≡ (α1 & α2))  ( α1 & α3)

α1  (α2 & α3) ≡ (α1 α2))  ( α1 v α3)

3.Ассоциативные

α1 & (α2  α3) ≡ (α1 & α2)) & α3

α1  (α2  α3) ≡ (α1 α2))  α3

4.Законы Де Моргана

┐(α1 & α2)) ≡ (┐α1  ┐α3)

┐(α1  α2)) ≡ (┐α1 & ┐α3)

5.Законы двойного отрицания

┐(┐ α1) ≡ α1

Здесь α - любая правильно построенная формула.

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



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

Если формулы α1, α2,…, αm истинны на некотором множестве конкретизаций в данной среде, то формула α выводима из них, если она также истинна на всех конкретизациях этого множества. Факт выводимости записывают с помощью символа выводимости ├:

α1, …, αm ├ α.

Исчисление высказываний. Логическим исчислением, или просто исчислением, называют совокупность, которая включает в себя : алфавит (совокупность используемых символов), синтаксические правила построения формул в алфавите, аксиомы ( общезначимые исходные формулы), правила вывода по аксиомам производных формул или теорем. Правила вывода α ├ β имеют дело непосредственно с формулами, позволяя по истинности одних формул, делать заключения об истинности других. Символы α и β в правиле вывода обозначают одну или несколько формул, α называется условием, а β –следствием. Если в условии или следствии формул несколько они записываются через запятую. Если в качестве алфавита логического исчисления взять алфавит логики высказываний, в качестве синтаксических правил синтаксические правила логики высказываний, в качестве аксиом- некоторое множество общезначимых формул, например, законов, а в качестве правил всего два правила: модус поненс и подстановки, указанные ниже, то в результате получим исчисление, называемое обычно исчислением высказываний. Классическим исчислением высказываний принято называть исчисление, аксиомы которого являются следующие общезначимые формулы:

1. A ( B ) A

2. (A B) ((A(B C)) (A C))

3. ( A  B) A

4. ( A  B) B

5. A (A  B)

6 B (A B)

7. A (B (A B)

8. (A C) ((B C) ((A B) C))

9. (A B) ((A B) A


  1. ┐┐A A

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

Поэтому, если нам удастся достаточно адекватно интерпретировать эти законы в какой-либо среде, то исчисление высказываний может служить основой для рассуждений об этой среде. Классическое вычисление высказываний использует два правила вывода: модес поненс и правило подстановки.



Вывод в логике высказываний. Наряду с вопросом о правильности высказываний (рассуждений) логика высказываний рассматривает вопросы вывода и правила вывода.

Вывод – это процедура получения нового высказывания на основе одного или более уже принятых высказываний.

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

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

A1,, A2, A3,…,An , а заключение В запишем так A1,, A2, A3,…,An ├ B. Читается так: “ Из посылок вида A1, A2, A3,…,An можно (разрешено) выводить заключение В”

Модус поненс (правило отделения)- латинское название. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации:

α, α β ├ β

Если в процессе доказательства справедливости какой-либо сложной формулы удалось ее свести к правилу отделения, считаем что доказательство состоялось



Правило подстановки. Из формулы α (p) выводима формула α (P) , получаемая подстановкой в формулу α (p) вместо каждого вхождения переменной p формулы P:

α (p) ├α (P).

На практике, удобнее использовать не законы логики высказываний, а правила, их заменяющие, тогда логическое исчисление называют натуральным исчислением высказываний. В натуральном исчислении высказываний, помимо правил модес поненс и подстановки, используют следующие ОСНОВНЫЕ правила:

1 Правило исключения (удаления) конъюнкта (УД).

Из истинности конъюнкции следует истинность любого ее конъюнкта A1,, A2, A3,…,An ├Aii . Пример. Каждый студент сдает A1 = экзамен и A2 = зачеты ├ Каждый студент сдает экзамены



2.Правило введения конъюнкции (ВК).

Из списка истинных формул следует истинность их конъюнкции:

A1,, A2, A3,…,An ├ A1 A2 A3,…,An.

Пример. A1 ,= Подул ветер; A2=Пошел дождь ├ (A1 , A2) = Подул ветер и пошел дождь.

3.Правило введения дизъюнкции (ВД).

Из истинности формулы следует истинность ее дизъюнкции с любыми другими формулами:

Ai A1  A2  A3… An

Пример. A1 =Иванов читает, A2 = Иванов размышляет ├ (A1, A2) = Иванов читает или размышляет

4.Правило исключение (удаления) двойного отрицания. Из истинности двойного отрицания формулы следует истинность ее самой: ┐┐A ├ A

Пример. Неверно, что это число не простое ├ это число простое.

Формулы в которых конъюнкты стоят с отрицанием или без него называют элементарными конъюнкциями. Элементарную конъюнкцию, в которую входит по одному разу каждая переменная, определяющая состояние среды, с отрицанием или без отрицания называют полной конъюнкцией, или КОНСТИТУЕНТОЙ.

5.Простая резолюция (удаление дизъюнкта). Из истинности дизъюнкции и отрицания одного из ее дизъюнктов следует истинность формы, получающейся из дизъюнкции удалением этого дизъюнкта:

A B, ┐B ├А

Пример А = Ошибся защитник или В = вратарь, В = вратарь не ошибся ├ А = ошибся защитник

6. Резолюция. Из истинности двух дизъюнкций, одна из которых содержит дизъюнкт, а другая – его отрицание, следует формула, являющаяся дизъюнкцией исходных формул без упомянутого дизъюнкта и его отрицания

A B, ┐B C├ A C или эквивалентно ┐A B, BC├ ┐ A C

7 Правило введения двойного отрицания(ВДО) Из истинности высказывания А можно вывести дважды отрицаемое высказывание А ├ ┐┐ A

8 Правило удаления импликации (Уи). Из наличия импликации А В и ее посылки(антецедента)А выводить заключение (консеквент) В

А В, А ├ В

Пример. А = Стоит туманная погода, В = аэропорт закрыт. Если А =стоит туманная погода, то В = аэропорт закрывается, А=Стоит туманная погода ├ В=Аэропорт закрыт
9 Правило введения эквиваленции (ВЭ). Из импликативного высказывания А В и обратного по отношению к нему высказывания В А выводить высказывание эквивалентности.

А В, В А ├ А В



10 Правило удаления эквиваленции (УД). Из высказывания эквивалентности вида А В можно выводить как импликативное высказывание вида А В, так обратное ему импликативное высказывание В А

А В ├ А В, В А


Очень часто в практической деятельности применяются наиболее употребительные косвенные(производные) правила, которые выводятся из основных:

  1. Правило отрицания дизъюнкции.

┐ (А  В ) ├ ┐А ┐В или ┐А ┐В ├ ┐ (А В )

  1. Правило отрицания конъюнкции.

┐ (А  В ) ├ ┐А ┐В или ┐А ┐В ├ ┐ (А В )

  1. Правило контрапозиции. А В ├ ┐А ┐В

  2. Правило отрицания импликации ┐А В ├ А ┐В или А ┐В ├ ┐( А В)




  1. Правило сложной контрапозиции. (А  В ) С├ (А ┐С) ┐В

  2. Правило импортации. А (В С) ├ (А В) С

  3. Правило экспортации. (А  В) С ├А С)

  4. Правило «рассуждения по случаям». А  В, А С, В С ├ С

  5. Правило конструктивной диллеммы А В, С D, А С ├В D

  6. Правило деструктивной дилеммы. А В, С D, ┐В ┐D ├ ┐ А  ┐ С

Построение доказательств (логический вывод) в логике высказываний.

Логика это наука о способах доказательств. В логике высказываний все доказательства строятся на отношении порядка, т.е. на отношении, которое существует между причиной и следствием. Здесь уже отдельные звенья цепи доказательства связаны с символом импликации. Символ импликации ( ) при логическом выводе мы будем заменять на символ ├ или ( ═>). Вместо символа объектной конъюнкции ( ) будем использовать субъективный символ метаконъюнкции (,), а вместо объективной дизъюнкции ( ) субъективную метадизъюнкцию (;). Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующего причинно - следственного отношения:

P1, P2 ,…, Pn-1, Pn ├ C ( 1 )

где Pi –посылка(причина), С-заключение ( следствие) Читается так «Если посылки P1, P2 ,…, Pn-1, Pn истинны, то заключение С тоже истинно”,.или по другому: “ Если причины P1, P2 ,…, Pn-1, Pn имели место, то будет иметь место и следствие С”. Чтобы не спутать объектное высказывание(предложение) с субъектным высказыванием, справедливость которого мы намереваемся установить, условимся предложения типа (1) называть клаузой (clause). Клауза –это метапредложение, в котором использовано отношение порядка, оформленное через символ метаимпликации ├. Как отношение эквивалентности, отношение порядка удовлетворяет трем законам:

рефлексивности: А ═> А;

антисимметричности: если А ═>В , то В ═>А;

транзитивности: если А ═>В и В ═>С, то А ═>С . В отличие от эквивалентности отношение порядка предполагает выполнение закона антисимметричности, который можно записать так: если А ├ В и В ├ А, то А=В.

Клауза есть именно формальная запись доказываемого предложения. Вместо букв в ней можно подставлять объектные высказывания, и тогда клауза наполняется конкретным содержанием, которое именуется семантикой или легендой.

Пример клаузы: А В, А ═> В. Если принять, что А= Сверкнула молния, В=грянул гром, то можно составить следующую легенду: Известно, что если сверкнула молния, то после этого грянет гром, молния сверкнула. Следовательно, должен грянуть гром. Клаузы типа (1) называют хорновскими, ее используют в языке логического программирования ПРОЛОГ. Произвольную клаузу всегда можно свести путем эквивалентных преобразований к хорновскому виду. Существует пять конкретных методов доказательства справедливости логических клауз: аксиоматический метод, метод таблиц истинности, метод резолюций, метод Вонга и метод натурального исчисления.


Метод натурального исчисления.

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



  1. Правило введения конъюнкции (ВК).

  2. Правило удаления конъюнкции (УК).

  3. Правило введения дизъюнкции (ВД).

  4. Правило удаления дизъюнкции (УД).

  5. Правило введения импликации (ВИ).

  6. Правило удаления импликации (УИ).

  7. Правило введения отрицания (ВО).

  8. Правило удаления отрицания (УО).

9. Правило введения эквивалентности (ВЭ).

10. Правило удаления эквивалентности (УЭ).

Кроме перечисленных 10 правил имеется еще одно базовое правило (БП), которое сформулируем словами: во-первых любая посылка может выступать в роли следствия, т. е.
A,B,C =>A, A,B,C =>B, A,B,C =>C.
будут всегда истинными и не требуют доказательства, т.к. удовлетворяют аксиоме порядка, во-вторых, в перечень посылок истинной клаузы всегда можно добавить новые посылки, т.е. если клауза A,B,C =>Х верна, то будут истинными и все клаузы, построенные на ее основе - A,B,C,D =>Х, A,B,C …..=>Х. В обобщенной форме базовое правило можно записать так:

P,Y =>X


где X- любая посылка из P, а Y- произвольная посылка.

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

1 (A  B) ((A  ┐B)  ┐A)

доказательство

1. A,A B ├B, (УИ)

2. A,A ┐B ├ ┐B, (УИ)

3. A,A B, A ┐B, ├B, (1,БП)

4.A, A ┐B, A B, ├ ┐B, (2,БП)

5.A, A B, A ┐B, ├ 0 (3,4,УО)

6.A B, A ┐B, ├ ┐A, (5,ВО)

7.A B ├ ( A ┐B) ┐ A, (6,ВИ)

8.1 (A  B) ((A  ┐B)  ┐A) (7,ВИ)

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

МЕТОД РЕЗОЛЮЦИЙ.

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

X  A, Y  ┐A ├ X Y

При последовательном применении принципа резолюции происходит уменьшения числа букв, вплоть до их полного исчезновения. При этом исходная клауза конструируется в форме конъюнктивного противоречия: P1, P2, P1, P2,…, Pn ⊢ 0.


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

A, A B ├ B или 0  A, ┐A  B, ┐B  0 ├ 0

Здесь три дизъюнкта: 0  A, ┐A B, ┐ B  0. Cклеивая их последовательно, получаем в результате ноль, который говорит о не совместимости заключения и посылок. Это и свидетельствует о справедливости исходной клаузы. Принцип резолюций целиком заменяет аксиому порядка, поскольку сама эта аксиома может быть доказана в рамках метода резолюций. Действительно

A, B ⊢ A, A, B, ┐ ­­­­A ⊢ 0, 0, B ⊢ 0

Пусть дана клауза:

┐A B, C  A, B C A

Приведем ее в нормальную конъюнктивную форму

A  B, C  A, ┐B  C, A 0

Выпишем по порядку все посылки и далее начнем их склеивать согласно очередности. Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов получим:


  1. A  B,

  2. C A,

  3. ┐B  ┐C,

  4. ┐A,

  5. A ┐C, (1,3)

  6. B, (1,4)

  7. A  ┐ B, (2,3)

  8. C, (2,4)

  9. A, (2,5)

  10. ┐C, (3,6)

  11. ┐B, (3,8)

  12. ┐C, (4,5)

  13. ┐B, (4,7)

  14. 0 (4,9)

или короче

5. B, (1,4)

6. С, (2,4)

7. ┐B, (3,6)

8. 0 (5,7)

Вывод с помощью подстановки.

Пусть имеются высказывания:



  1. а вс

  2. с евсс

  3. с d

  4. d пробел

  5. в пробел

  6. есс d

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

cad ebccad e ccad dad ad bcd cd dd d пробел.



Метод Вонга

В этом методе используется сконструированная конъюнктивно- нормальная форма представления исходной клаузы, а аксиому порядка заменой клаузы Вонга.

X,L X;R

Здесь X пробегает некоторые буквы, входящие в клаузу, а L и R- определенные комбинации дизъюнктов и коннъюнктов. Конструктивная процедура доказательства сводится к последовательному разбиению дизъюнктов и конъюнктов таким образом, чтобы слева и справа от метаимпликации появилась одна и та же буква Х. Если в результате такого разбиения все конечные клаузы приобретают вид клаузы Вонга, то и исходная клауза была составлена верно. Разберем метод Вонга на примере доказательства справедливости правила отделения:

A, A B B или A, ┐ A  B B

Здесь имеется один дизъюнкт, который можно подвергнуть разбиению. После его разбиения получим две новых клаузы: A, ┐ A  B (1) и A, B B(2).

Вторая клауза удовлетворяет и аксиоме порядка и клаузе Вонга. В качестве Х в ней выступает В, а L=A and R =0.Первая же клауза тоже будет удовлетворять необходимым требованиям, но только после того, как Терм Ф из левой части Клаузы с противоположным знаком перенести в правую часть. Тогда будем иметь:

A А; В

где Х=А, L =1, R = B.

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

X Y, (X Y) U, Z (Y W )  (W X )  (Z X).

Приведем ее в соответствующую конъюнктивно- дизъюнктивную нормальную форму:

X Y, ┐X Y U, ┐ Z ┐Y W  W  ┐ X; Z; X.

Далее произведем разбиение первого дизъюнкта, в результате получим две производные клаузы:



        1. X , ┐X Y U, ┐ Z ┐Y W  W  ┐ X; Z; X.

        2. Y , ┐X Y U, ┐ Z ┐Y W  W  ┐ X; Z; X.

Клауза(1) отбрасывается, так как она удовлетворяет клаузе Вонга. Разбивая следущий дизъюнкт клаузы(2), получаем еще три новых клаузы.

2.1 Y , ┐X, ┐ Z  Y W  W  ┐ X; Z; X.

2.2 Y ,Y, ┐ Z  Y W  W  ┐ X; Z; X.

2.3 Y ,U, ┐ Z  Y W  W  ┐ X; Z; X.


Клаузы (2.1)и (2.2) сводятся к одной клаузе –

2.1 Y , ┐ Z  Y W  W  ┐ X; Z; X.


Произведем ее разбиение:

2.1.1 Y , ┐ Z  W  ┐ X; Z; X.

2.1.2 Y , ┐ Y  W  ┐ X; Z; X.

2.1.3 Y , W  W  ┐ X; Z; X.

Первые две клаузы удовлетворяют клаузе Вонга. У клаузы (2.1.3) нужно разбивать конъюнкт-

2.1.3.1. Y , W  W; ┐ Z; X. 2.1.3.2. Y , W  ┐X; ┐ Z; X.



Теперь обе клаузы имеют вид клаузы Вонга. Осталась еще ветвь 2.3.Она отличается от рассматриваемой ветви 2.1 наличием непарного терма U , который однако, не может повлиять на конечный результат т.е. разбиение клаузы(2.2) практически полностью совпадает с разбиением клаузы (2.1). Следовательно исходная клауза записана верно. Недостатком метода Вонга, как и метода резолюций , является то , что исходная клауза должна иметь нормальную дизъюнктивную или конъюнктивную форму. Этот недостаток преодолен в методе натурального исчисления.

(смотри читаемые специальные курсы).

  • Исчисление предикатов. Пропозициональная функция - это выражение, содержащее переменные и превращающиеся в высказывание при подстановке вместо этих переменных соответствующих аргументов. Примерами пропозициональных функций могут служить: « Если p, то q ». Это выражение превращается в высказывание, если вместо p и q подставить, например, высказывания: « Телу придать скорость более 7,9 км/сек», « Тело становится спутником Земли». Пропозициональная функция, аргументами, которой являются имена(предметные переменные), называется предикатом. Предикат - это функция от любого числа аргументов, принимающая истинностные значения: истина или ложь (И или Л; 1 или 0). Аргументы принимают значения из произвольного конечного или бесконечного множества M, называемого предметной областью. Если Р есть n - местная предикатная переменная, а Хi ,…, Хn предметные переменные (аргументы предиката), то выражение Р(Х­12 ,…,Хn) есть атомарная (элементарная) формула. Эта формула трактуется как высказывание, гласящее, что объекты Х12 ,,…,Хn связаны отношением Р. Например, высказывание «Сидоров работает преподавателем» может быть представлено предикатом(формулой):РАБОТАЕТ ( СИДОРОВ,ПРЕПОДАВАТЕЛЬ).Имя РАБОТАЕТ – есть предикат (или его еще называют Предикатный символ).В скобках указываются переменные или константы, соответствующие объектам находящимся в поименованном отношении. Выражение предикатный символ(терм,терм,…,терм) называют АТОМОМ.



П

Достарыңызбен бөлісу:




©www.dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет