Алгебра логики высказываний Основные понятия


Решение логических задач средствами алгебры логики



бет6/7
Дата17.06.2016
өлшемі0.9 Mb.
#143069
1   2   3   4   5   6   7

Решение логических задач средствами алгебры логики

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

В качестве примера рассмотрим одну из элемен­тарных логических задач. По подозрению в совершенном преступле­нии задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоиз­вестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом – ложь. Вот, что они утверждали:

Браун: «Я совершил это. Джон не виноват».

Джон: «Браун не виноват. Преступление совершил Смит».

Смит: «Я не виноват, виновен Браун».

Необходимо определить имена старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Решение этой задачи начинается с введения обозначений: буквами Б, Д и С обозначим высказывания: «виноват Браун», «виноват Джон» и «виноват Смит» соответст­венно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций:

Б   Д,  БС, Б   С,

из которых, по условию задачи, две ложны, а одна ис­тинна. Поэтому будет истинной формула



L = (Б   Д)  ( БС)  (Б   С).

Таблица истинности этой формулы имеет вид:




Б


Д


С


Б   Д

БС

Б   С

L

0

0

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

1

0

1

0

1

1

0

0

1

0

1

1

1

0

1

1

0

0

1

1

1

0

0

0

1

1

1

1

1

0

0

0

0

Из таблицы видно, что формула L истинна в пяти из восьми случаев. Случай, представленный в пятой строке, следует ис­ключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит усло­вию задачи. В строках 4, 6 и 7 оказываются истинными по два высказывания: Д и С, Б и С, Б и Д, соответственно, что также противоречит условию задачи. Следователь­но, справедлив случай 7, то есть преступник – Смит. Он – известный мошенник, и оба его высказывания лож­ны: Б   С  0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон – уважаемый в городе старик, а Браун – Малоизвестный чиновник.




Исчисление высказываний


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


Логическим исчислением или просто исчислением называют четверку, которая включает в себя:

  • Алфавит (совокупность используемых символов);

  • Синтаксические правила построения формул в алфавите;

  • Аксиомы (общезначимые формулы или тождественно истинные формулы);

  • Правила вывода по аксиомам производных формул или теорем.

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



Классическое исчисление высказываний



Исчислением высказываний называют исчисление, в котором в качестве алфавита взят алфавит логики высказываний, в качестве синтаксических правил – синтаксические правила логики высказываний, в качестве аксиом – некоторое множество общезначимых формул, а в качестве правил – правила Modus ponens и правило подстановки.
В классическом исчислении высказываний приняты следующие аксиомы:

  1. α  (  α),

  2. (α  (  γ))  (( α  )  (α  γ)),

  3. (α  )  α,

  4. (α  )  ,

  5. α  (α  ),

  6.   (α  ),

  7. (α  )  ((α  γ)  (α  (  γ)),

  8. (α  γ)  ((  γ)  ((α  )  γ)),

  9. (α  )  (  α),

  10. α  α,

  11. α  α.

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



  • Modus ponens. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации: α, α├ .

  • Правило одновременной подстановки. Из формулы α(р), где рпеременная, выводима формула α(R), где R – формула, получаемая заменой в α(р) каждого вхождения переменной р на формулу R: α (р) ├ α (R). В общем случае будем обозначать подстановку (x1,…, xn  α1,…, αn).

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



Натуральное исчисление высказываний

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



  • Исключение конъюнкта. Из истинности конъюнкции следует истинность любого ее конъюнкта:

α1  α2  …  αn ├ αi.

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

α1, α2, …, αn ├ α1  α2  …  αn.

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

α1 ├ α1  α2  …  αn.

  • Исключение двойного отрицания. Из истинности двойного отрицания формулы следует истинность ее самой:

α ├ α.

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

α  ,  ├ α.

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

α  ,   γ ├ α  γ.

Понятие выводимости

Пусть имеется конечная совокупность формул H = {A1, A2 ,…, An}. Говорят, что формула B выводима из совокупности H (можно записать как BH), если:



  1. либо BH,

  2. либо B – доказуемая формула исчисления высказываний,

  3. либо B получается по правилу Modus ponens из формул C и CB, которые выводимы из совокупности H.



Примеры

Рассмотрим, как можно установить доказуемость формул, используя правило подстановки и правило Modus ponens.

Доказать AAA


  1. Возьмем аксиому (α  γ)  ((  γ)  ((α  )  γ)) и сделаем в ней подстановку (α, γ,   A, A, A). Получим: (AA)  ((AA)  ((AA)  A));

  2. Докажем выводимость AA:

    1. Возьмем аксиому (α  (  γ))  (( α  )  (α  γ)) и сделаем в ней подстановку (α, γ,   x, y, x). Получим: (x  (yx))  ((xy)  (xx));

    2. Из аксиомы x  (yx) и правила Modus ponens имеем: (xy)  (xx);

    3. Выполним подстановку (y  x). Получим: (x  x)  (xx);

    4. Из аксиомы x  x и правила Modus ponens имеем: xx;

  3. Из формулы xx и правила Modus ponens имеем: (AA)  ((AA)  A);

  4. Аналогично: (AA)  A;

Формула доказана.



Достарыңызбен бөлісу:
1   2   3   4   5   6   7




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

    Басты бет