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

Вид материала

Документы

Содержание Решение логических задач средствами алгебры логики Браун: «Я совершил это. Джон не виноват». Джон Исчисление высказываний Логическим исчислением Классическое исчисление высказываний Правило одновременной подстановки Натуральное исчисление высказываний Исключение конъюнкта Понятие выводимости

Подобный материал:

• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.
• Лекция Логические основы компьютеров , 369.25kb.
• Алгебра логики. Определение формы сложных высказываний, построение таблиц истинности, 132.48kb.
• Функции алгебры логики, 47.25kb.
• Алгебра логики и логические основы компьютера Алгебра логики (булева алгебра), 39.45kb.
• Программа дисциплины Математическая логика Семестр, 13.41kb.
• Логика высказываний. Основные понятия и определения. Логические функции одной и двух, 6.36kb.
• Основы математической логики. Алгебра логики (булева алгебра), 59.39kb.
• Программа курса «Математическая логика и теория алгоритмов», 37.76kb.
• 1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции., 38.38kb.

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

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

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

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

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

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

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

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

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

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

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). В общем случае будем обозначать подстановку (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;
   

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