Исчисления высказываний и предикатов

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

ние алгоритма всегда завершается, какая бы стратегия ни была принята при выборе p и с. Если N – число атомов, первоначально присутствующих в S (c учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.

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

Показано, что любую предметную область можно представить в виде фраз Хорна. Для этого любую формулу в описании предметной области необходимо преобразовать в КНФ (конъюнктивную нормальную форму – конъюнкцию элементарных дизъюнкций) и далее каждую элементарную дизъюнкцию представить в виде фразы Хорна.

Пример. Пусть предметная область описана в виде

{ A v (B & D), B →C, A v D }. Представим её в виде фраз Хорна.

A v (B & D) ≡ ( A v B) & ( A v D). Этому высказыванию соответствует две фразы Хорна ( A v B) и ( A v D).

B→C ≡B v C .

A v D – является фразой Хорна.

Итак, имеем предметную область, описанную фразами Хорна: { A v B, A v D, B v C, A v D}

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 21 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

1.7. Примеры использования метода резолюций в логике высказываний

Метод резолюций применяется в качестве механизма доказательства при реализации принципа дедукции.

Для доказательства того, что некое заключение C является логическим следствием множества гипотез {H1, …Hn}, нужно применить резолюцию к множеству {H1,… Hn,¬C}. Эти гипотезы и отрицание заключения должны иметь вид дизъюнкций.

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

Например, выясним, является ли логически правильным следующее простое рассуждение. Студент пойдёт домой (p) или останется в университете (q). Он не останется в университете. Следовательно, студент пойдёт домой. (Буквами обозначены имеющиеся в этом рассуждении простые высказывания).

Запишем это рассуждение символически с помощью указанных в скобках букв: p q, ¬q, p. Истинность следствия будет определяться истинностью имеющихся высказываний, {p q, ¬q} = p.

Применим принцип дедукции: {p q, ¬q, ¬p} = 0. Невыполнимость множества докажем с помощью резолюций:

1.p q,

2.¬q,

3.¬p,

4.p (1,2).

5.0.(ЛОЖЬ)

Можно считать, что данное рассуждение логически правильное.

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 22 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

Контрольные задания

1.Выяснить, являются ли логически правильными следующие рассуждения. Доказательство провести методом прямого вывода, методом «от противного».

2.Выразить описание задачи через фразы Хорна и провести доказательства, используя метод резолюций.

1.Или Пётр и Иван братья, или они однокурсники. Если Пётр и Иван братья, то Сергей и Иван не братья. Если Пётр и Иван однокурсники, то Иван и Михаил также однокурсники. Следовательно или Сергей и Иван не братья, или Иван и Михаил однокурсники.

2.Если Петр не встречал Ивана, то либо Иван не был на лекциях, либо Пётр лжёт. Если Иван был на лекциях, то Пётр встречал Ивана, и Сергей был в читальном зале после лекций. Если Сергей был в читальном зале после лекций, то либо Иван не был на лекциях, либо Пётр лжёт. Следовательно, Иван не был на лекциях.

3.Наша футбольная команда либо выигрывает матч, либо проигрывает, либо сводит его к ничьей. Если матч выигран или проигран, то он не перенесён. Команда матч не выиграла и не свела его к ничьей. Следовательно, матч не перенесён и проигран

4.Если Джон не встречал этой ночью Смита, то либо Джон был убийцей, либо Джон лжет. Если Смит не был убийцей, то Джон не встречал Смита этой ночью, и убийство имело место после полуночи. Если же убийство имело место после полуночи, то либо Смит был убийцей, либо Джон лжет. Следовательно, Смит был убийцей.

5.Известно, что хроничные сепульки всегда латентны или бифуркальны.

Какие из следующих утверждений в этом случае истинны:

a)сепульки не хроничны только в случае отсутствия у них свойства латентности;

b)латентность сепулек не является необходимым условием их хроничности или бифуркальности;

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 23 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

c)хроничность сепулек является достаточным условием их латентности или бифуркальности;

d)для нехроничности сепулек необходимо отсутствие у них как бифуркальности, так и латентности.

1.8. Непротиворечивость аксиом

Множество аксиом H1, H2, … ,Hm называется непротиворечивым, если найдётся такой набор истинностных значений входящих в него элементарных высказываний, на котором все аксиомы истины. Иначе множество аксиом про-

тиворечиво.

Приведенное в примере 1 множество аксиом непротиворечиво, так как на наборе значений, где A=T, B=F, C=T и D=T, каждая аксиома принимает значение "истина".

Противоречием называется высказывание, которое ложно во всякой предметной области. Противоречие будем обозначать как A& A (это высказывание является и простейшим примером противоречия) или как 0. Для более сложных высказываний проверку на то, является ли высказывание противоречием, проверяется так же, как высказывания на общезначимость, через построение таблицы. Значение функции в этом случае должно быть равным F.

Если множество аксиом противоречиво, то высказывание

A1&A2&…&Am будет противоречием.

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

Кроме проверки множества аксиом на непротиворечивость, возникает задача проверки это множество на достоверность.

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

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 24 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

можно использовать такой приём. Будем считать, что свидетельства людей, не совершивших преступление, истинны, а свидетельства преступников – ложны. Тогда каждое свидетельство породит две аксиомы, имеющие вид импликаций: ЕСЛИ A невиновен ТО его свидетельство верно, и ЕСЛИ A преступник ТО его свидетельство – ложно.

1.9. Аксиоматизация логики высказываний

Любая математическая система основывается на множестве аксиом, т.е. выражений, считающихся общезначимыми и множестве правил вывода, т.е. механизмов, позволяющих строить новые общезначимые выражения. Такие выражения называют теоремами. Доказательством теорем называется последовательность из аксиом, правил вывода и уже доказанных теорем, позволяющих получить новую теорему. Важно, что логические правила, которые используются для вывода новых теорем из аксиом и ранее доказанных в данной системе теорем, не порождали в качестве «теорем» ложные высказывания.

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

Необходимо предложить такие формализмы, которые бы определяли все процедуры и не требовали дополнительно никаких ссылок на смысловое содержание. В вышеприведённых примерах мы решали задачу вывода исходя из того, что известны понятия И, ИЛИ, ЕСЛИ ТО и др., которые использовались при выводе. Так, если аксиома определена как A&B, то, исходя из смысла этой операции, выводилась истинность высказываний A и B. В исчислении высказы-

ваний операция И определяется явно в виде двух аксиом: (A&B)→A, (A&B)→B. Это позволяет организовать вывод, не прибегая к рассмотрению смысла фраз.

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

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 25 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

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

H1, H2,…, Hn	гипотезы
	заключение
C

Гипотезы представляют собой перечень высказываний или посылок. Умозаключение правильно, если всякий раз, когда H1, H2,… Hn истинны, то истинно и С. Правильность умозаключения можно проверить, построив таблицу истинности и показать, что всякий раз, когда гипотезы истинны, истинно и заключение.

Таблица 1.3

					Силлогизм						Название силлогизма
			P→Q, P								Modus Ponens
											(способ спуска или правило отделения)
					Q
			P→Q, ¬Q								Modus Tollens
											(доказательство от противного)
					¬P
			P→Q, Q→R								Транзитивность импликации
					P→R
			P v Q, ¬P								Дизъюнктивный силлогизм
					Q
			P v Q,P→(R&¬R)								Исключающий выбор
					Q

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 26 из 44

Если A студент УГТУ-УПИ, то А посещает занятия , A посещает занятия, значит A – студент УГТУ-УПИ.

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

Продолжение таблицы 1

P→Q, R→Q, P v R

Простая конструктивная дилемма

Q

P→Q, R→S, P v R

Сложная конструктивная дилемма

QvS

P→Q, P→S, ¬Q v¬S

Простая деструктивная дилемма

¬P

P→Q, R→S, ¬Q v¬S

Сложная деструктивная дилемма

¬P v¬R

¬P→(R&¬R)

Сведение к абсурду

P

Рассмотрим пример использования правила вывода Modus Ponens . Пусть P и Q заданы следующим образом: P– «A является студентом УГТУУПИ», Q– «A посещает занятия»,

так что P→Q: если A студент УГТУ-УПИ, то А посещает занятия. Предположим, A – Петров Василий, и он посещает занятия. Нужно показать, что он – студент УГТУ-УПИ.

Правило Modus Ponens даёт

P→Q, P

Q

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

P→Q, ¬R →¬Q, ¬R

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 27 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

¬P

Доказательство:

1.P→Q – гипотеза;

2.¬R →¬Q – гипотеза;

3.¬R – гипотеза;

4.¬Q – 2, 3, правило Modus Ponens;

5.¬Q →¬P – 1 и Закон контрапозиции: P→Q ≡ ¬Q →¬P;

6.¬P – 4, 5 и правило Modus Ponens.

Контрольные задания

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

ным:

а) ¬P v Q, ¬P v S, ¬S

¬P

b) ¬P v ¬Q, R v ¬Q,¬P

Rv¬ P

c)P→Q, P→S, Q v S

P

d) ¬(S & T), ¬Z→T

S→Z

e)P→Q, ¬R→¬Q, ¬R

¬P

f)¬P v Q, R v ¬Q,P, S

R v S

g) S v T, T→R, S →Z, R v Z

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 28 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

2. Исчисление предикатов

2.1 Предикаты

Логика высказываний позволяет формализовать лишь малую часть множества рассуждений. Высказывания, описывающие некоторые свойства объектов, или отношения между объектами выходят за рамки логики высказываний. Например, мы не сможем судить о логической правильности такого простого рассуждения: «Каждое натуральное число является корнем некоторого квадратного уравнения. Число 5 –натуральное. Следовательно, 5 является корнем некоторого квадратного уравнения».

Логика предикатов начинается с анализа строения высказываний, которые выражают тот факт, что объекты обладают некоторыми свойствами, или находятся между собой в некоторых отношениях. Понятие «свойства» и понятие «отношения» рассматриваются как частный случай общего понятия «предиката». Объекты, о которых говорится в высказывании, называются термами или предметными константами.

Предметные константы, подобно константам в математике, определяют значения, которые могут быть приписаны в высказываниях предметным переменным. При этом каждой переменной соответствует своё множество предметных констант. Например, если речь идет о студенческой группе, то переменной ФАМИЛИЯ соответствует множество констант – конкретных фамилий студентов группы, переменой ОЦЕНКА – множество констант {отл., хор., удовл., неуд.}, переменной ВУЗ – множество имен ВУЗов. Над переменными и константами определяются функции так же, как и в математике, т.е. как однозначное отображение декартово произведения X1×X2× …Xm Y, где Xi и Y – имена предметных переменных.

Пример функции F: X1×X2 Y, где X1 – вес товара, X2– его цена, а Y–

стоимость, которая определяется как Y=X1 X2.

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 29 из 44

Битюцкий В.П., Папуловская Н.В. Математическая логика. Исчисление высказываний и предикатов

Определение. Предикатом называется функция, аргументы которой принимают значения из некоторого множества, а сама функция – значение 0 («ложь») или 1 («истина»).

Пример предиката: ФАМИЛИЯ = «Петров». Здесь ФАМИЛИЯ – переменная, «Петров» – константа.

Предикаты, в которых описывается некоторое свойство объекта, называется предикат-свойство. Если предикат определяет отношение между несколькими объектами, то такой предикат называется предикат-отношение. В зависимости от того, между скольким числом объектов устанавливаются отношения, различают двуместные, трёхместные и n-местные отношения

Предикат называется n-местным ( n= 1,2 … ), если соответствующая функция есть функция от n-аргументов. Высказывание – не что иное, как предикат без аргумента, или предикат с нулевым числом мест.

Примеры.

1.Бинарные предикаты: x,y,z N, P(x,y) = (x>y), R(x, y) = (x = y2), Q(x, y)= «x делит y»;

2.Трёхместные: P(x,y,z) = «число x является НОД (наибольший общий делитель) чисел y и z» , R(x,y,z) = (z = x + y).

Предикатную функцию P(x, y) можно рассматривать как функцию, определённую на декартовом квадрате N2. Множество тех пар (x, y) для которых данная функция принимает значение истины, есть область истинности предиката P(x, y). Табличную запись функции называют матрицей предиката.

ГОУ ВПО УГТУ-УПИ – 2005

Стр. 30 из 44