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

 

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

 

 

Для данного примера минимальная  ДНФ равна y Ú Ø x.

 

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

 

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

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

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

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

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

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

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

Б Ù Ø Д, Ø Б Ù С, Б Ù Ø С,

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

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. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон – уважаемый в городе старик, а Браун – Малоизвестный чиновник.

 

 

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

 

 

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

 

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

• Алфавит (совокупность используемых символов);
• Синтаксические правила построения формул в алфавите;
• Аксиомы (общезначимые формулы или тождественно истинные формулы);
• Правила вывода по аксиомам производных формул или теорем.

 

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

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

 

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

 

В классическом исчислении высказываний приняты следующие аксиомы:

1. α ® (b ® α),
2. (α ® (b ® γ)) ® (( α ® b) ® (α ® γ)),
3. (α Ù b) ® α,
4. (α Ù b) ® b,
5. α ® (α Ú b),
6. b ® (α Ú b),
7. (α ® b) ® ((α ® γ) ® (α ® (b Ù γ)),
8. (α ® γ) ® ((b ® γ) ® ((α Ú b) ® γ)),
9. (α ® b) ® (Øb ® Øα),
10. α ® ØØα,
11. ØØα ® α.

 

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

• Modus ponens. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации: α, α®b├ b.
• Правило одновременной подстановки. Из формулы α(р), где р – переменная, выводима формула α(R), где R – формула, получаемая заменой в α(р) каждого вхождения переменной р на формулу R: α (р) ├ α (R). В общем случае будем обозначать подстановку (x₁,…, x_n ò α₁,…, α_n).

 

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

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

 

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

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

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

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

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

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

α₁ ├ α₁ Ú α₂ Ú … Ú α_n.

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

ØØα ├ α.

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

α Ú b, Øb ├ α.

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

α Ú b, Øb Ú γ ├ α Ú γ.

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

 

Пусть имеется конечная совокупность формул 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. Возьмем аксиому (α ® γ) ® ((b ® γ) ® ((α Ú b) ® γ)) и сделаем в ней подстановку (α, γ, b ò A, A, A). Получим: (A ® A) ® ((A ® A) ® ((A Ú A) ® A));
2. Докажем выводимость A ® A:
1. Возьмем аксиому (α ® (b ® γ)) ® (( α ® b) ® (α ® γ)) и сделаем в ней подстановку (α, γ, b ò 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;

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

 

Логика предикатов

 

 

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

 

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

 

Например, рассмотрим высказывание «7 – простое число». Эту фразу  в логике высказываний можно представить с помощью логической переменной, предположим a. Для того, чтобы представить на языке логики другое высказывание «13 – простое число» понадобится другая переменная. Таким образом, для описания простых чисел нам понадобится столько логических переменных, сколько существует простых чисел. На языке логики предикатов эта фраза может быть представлена так: простое_число(7). А весь набор подобных фраз: простое_число(значение). В данном примере простое_число – это предикатный символ, 7 – объектная константа, а значение – объектная переменная.

 

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

Объектные константы

 

Объектная константа или просто константа взаимнооднозначно сопоставляется в процессе интерпретации с каким-либо одним объектом и обозначается строкой символов, начинающихся с прописной буквы.

Объектные переменные

 

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

Функции

 

Если некоторый объект в точности соответствует множеству других, то используют функции. Например, если объектами являются двоичные цифры и десятичные цифры, то любому двоичному можно однозначно сопоставить десятичное, и выразить это сопоставление в виде функции преобразование_2_в_10(x, y, z), где x, y, z – двоичные числа, а значение функции – десятичное. Выражение преобразование_2_в_10 называют функциональным символом. Функция в логике предикатов не предполагает обязательного наличия алгоритма вычисления ее значения по аргументам. Она лишь задает с помощью констант и переменных определенное отношение между объектами, соответствующими ее аргументам, и каким-то одним объектом.

Термы

 

Константы, переменные и функции  являются темами. Как именно выбирать термы для представления знаний – решать разработчику. Рассмотрим, например, среду, состоящую из объектов птицы и крылья. Пусть, также, нам известно, что птицы имеют крылья. Введем константы, обозначающие конкретных птиц: Воробей, Синица, Голубь, и константу Крылья. Введем переменную х, определенную на множестве птиц. Функциональный символ  имеет ставит во взаимно однозначное соответствие любой птице объект крылья. Функция имеет (х) задаёт отношение между объектом крылья и какой-либо птицей х. Если х = Воробей, то имеет (Воробей) = Крылья. Функция может и не содержать аргументов, то есть иметь один функциональный символ. Термы, не содержащие аргументов, то есть константы, переменные и функции без аргументов называют элементарными термами.

Предикатный символ

 

Как и в случае с функцией предикаты  начинаются с предикатного символа и следующими за ним в скобках упорядоченного набора переменных или констант, соответствующих объектам, которые находятся в поименованном отношении. С помощью предикатов задаются произвольные отношения между объектами, если аргументов несколько. Если аргумент только один, то предикат описывает свойство объекта, заданного аргументом. Так, например, если два человека Маша и Саша являются братом и сестрой, то это отношение может быть выражено с помощью предиката брат_сестра (Маша, Саша). Предикат может принимать значение Истинно или Ложь. Если предикат Истинен, то отношение имеет место, иначе – не имеет. Отношение между птицами и крыльями также может быть выражено с помощью предиката. Пусть предикат крылья(х) Истинен, если х имеет крылья, тогда при х = Воробей конструкция крылья(Воробей) будет представлять знания о том, что у Воробья есть крылья.