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

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

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

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

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

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

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

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

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

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

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

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

Из таблицы видно, что формула 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). В общем случае будем обозначать подстановку (x₁,…, x_n  α₁,…, α_n).
  

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

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

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

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

α₁  α₂  …  α_n ├ α_i.

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

α₁, α₂, …, α_n ├ α₁  α₂  …  α_n.

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

α₁ ├ α₁  α₂  …  α_n.

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

α ├ α.

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

α  ,  ├ α.

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

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

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

Пусть имеется конечная совокупность формул H = {A₁, A₂ ,…, A_n}. Говорят, что формула B выводима из совокупности H (можно записать как B├ H), если:

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

Примеры

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

Доказать A  A  A

1. 
   Возьмем аксиому (α  γ)  ((  γ)  ((α  )  γ)) и сделаем в ней подстановку (α, γ,   A, A, A). Получим: (A  A)  ((A  A)  ((A  A)  A));
   
2. 
   Докажем выводимость A  A:
   
   1. 
      Возьмем аксиому (α  (  γ))  (( α  )  (α  γ)) и сделаем в ней подстановку (α, γ,   x, y, x). Получим: (x  (y  x))  ((x  y)  (x  x));
      
   2. 
      Из аксиомы x  (y  x) и правила Modus ponens имеем: (x  y)  (x  x);
      
   3. 
      Выполним подстановку (y  x). Получим: (x  x)  (x  x);
      
   4. 
      Из аксиомы x  x и правила Modus ponens имеем: x  x;
      
3. 
   Из формулы x  x и правила Modus ponens имеем: (A  A)  ((A  A)  A);
   
4. 
   Аналогично: (A  A)  A;
   

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

жүктеу/скачать 0.9 Mb.

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