Доказательство. 1 страница

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

	A®B	гипотеза
	B®C	гипотеза
	A	гипотеза
	В	MP 3,1
	С	MP 4,2
	A®B, B®C, А ├ L C	1-5
	A®B, B®C ├ L А→C	Теорема дедукции

Следствие 3. (Правило сечения) A®(B®C), В ├ _L А→C

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

	A®(B®C)	гипотеза
	A	гипотеза
	B®C	MP 2,1
	В	гипотеза
	С	MP 4,3
	A®(B®C), В, А├ L C	1-5
	A®(B®C), В├ L А→C	Теорема дедукции

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

В этом разделе приведем теоремы, касающиеся свойств исчисления высказываний в целом. Приведем необходимые определения.

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

Формальная теория Т разрешима, если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой теории Т. Теория Т называется полуразрешимой, если существует алгоритм, который для любой формулы F выдает ответ «Да», если F – теорема, и может быть не выдает никакого ответа, если F не является теоремой.

Теорема. ├ _L А Û А – тавталогия

Доказательство. Докажем только необходимость утверждения. Нетрудно проверить, что аксиомы A₁, A₂, A₃, являются тавталогиями, а правило вывода modus ponens сохраняет тождественную истинность формул, т.е. из ТИ формул по правилу вывода получаются только ТИ формулы.

Следствие. Теория L – формально непротиворечива.

Доказательство. Поскольку все теоремы теории L – тавталогии, то отрицание тавтологии не есть тавтология. Следовательно, в теории L не существует одновременно теоремы и ее отрицания.

Теорема. Система аксиом теории L независима.

Теорема. Теория L является разрешимой теорией.

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

1.6 Методы проверки выводимости формул ИВ

В этом разделе приводятся некоторые методы проверки тождественной истинности формул ИВ или, как было показано, выводимости формул в ИВ.

Тривиальный метод заключается в проверке значений формулы при всевозможных значениях (интерпретациях) ее переменных. Однако при большом количестве переменных такой метод становится очень громоздким.

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

Метод Куайна представляет собой модификацию тривиального метода. Пусть < X 1, X 2,..., Xk > – множество высказывательных переменных в формуле F. Возьмем первую переменную X₁ и придадим ей, например, значение И (или Л). Подставим это значение в формулу F и выполним вычисления, которые могут возникнуть при такой подстановке. После выполнения вычислений получим формулу F’ с меньшим количеством переменных и применяем к ней описанную процедуру. Если на каком-то шаге получена формула, которая является тавталогией или противоречием независимо от значений высказывательных переменных, входящих в эту формулу, то алгоритм на этом шаге можно остановить. Таким образом, алгоритм Куайна приводит к рассмотрению меньшего количества интерпретаций, чем тривиальный алгоритм. Рассмотрим пример работы метода Куайна.

Пример 1. Проверить выводимость формулы (X&Y&Z)®(X®Y)&(X®Z) методом Куайна.

Положим I(X)=Л. Тогда I((0& Y&Z)®(0®Y)&(0®Z))=И при любой интерпретации Y и Z. Пусть теперь I(X)=И.

Тогда I((1& Y&Z)®(1®Y)&(1®Z))=I(Y&Z®Y&Z). Для полученной формулы повторим процедуру метода Куайна. Положим I(Y)=Л. Тогда I(0&Z®0&Z)=И при любой интерпретации Z. Положим I(Y)=И. Тогда I(1&Z®1&Z)= I(Z®Z)=И при любой интерпретации Z. Таким образом, данная формула является тавталогией, а значит выводима в ИВ.

Пример 2. Проверить выводимость (X&Y&Z) ├ (X®Y)&(X®Z) методом Куайна.

Сначала применим теорему дедукции к данной выводимости. По теореме дедукции можно проверять выводимость (X&Y&Z)®(X®Y)&(X®Z). Далее поступаем как в примере 1.

Пример 3. Проверить выводимость (X®Y) ├ (X®Y)&(X®Z) методом Куайна

Сначала применим теорему дедукции к данной выводимости. По теореме дедукции можно проверять выводимость (X®Y)→ (X®Y)&(X®Z).

Положим I(X)=Л. Тогда I((0®Y)→(0®Y)&(0®Z))=И при любой интерпретации Y и Z. Пусть теперь I(X)=И.

Тогда I((1®Y)→ (1®Y)&(1®Z))= I(Y→ Y& Z)= I ((YÚ Y)& (Y ÚZ))=

I (Y ÚZ). При I(Y)=И, I(Z)=И получаем, что формула ложна. Таким образом, формула не является тавталогией, а значит не выводима.

Рассмотрим теперь метод редукции распознавания тождественно истинных формул в ИВ. Он особенно удобен, когда в записи формул встречается много импликаций. Суть метода заключается в следующем. Пусть формула F имеет вид импликации, например, F=A®B. Допустим, что в некоторой интерпретации формула F принимает значение Л. Тогда в соответствии с таблицей истинности для импликации имеем I(A)=1, I(B)=0. Таким образом, проверка формулы F сводится к проверке формул А и В. После этого данный процесс применяется к формулам А и В и т.д.

Пример 4. Проверить выводимость формулы (X®(Y®Z))®((X®Y)®(X®Z)) методом редукции.

Пусть в некоторой интерпретации формула имеет значение Л. Тогда I(X®(Y®Z))=И, I((X®Y)®(X®Z))=Л. Применим теперь метод редукции к формуле (X®Y)®(X®Z). Если она в некоторой интерпретации имеет значение Л, то I(X®Y)=И, I(X®Z)=Л. Для формулы X®Z метод редукции дает I(X)=И, I(Z)=Л. Из I(X®Y)=И получаем, что I(Y)=И. Однако это приводит к противоречию с I(X®(Y®Z))=И. Таким образом, исходная формула не может быть ложной ни при какой интерпретации, т.е. формула является тавталогией, а следовательно выводима в ИВ.

Пример 5. Проверить выводимость формулы (X®(Y®Z)) ├ ((X®Y)®(X®Z)) методом редукции.

По теореме дедукции будем доказывать выводимость (X®(Y®Z))®((X®Y)®(X®Z)). Далее поступаем как в примере 4.

Пример 6. Проверить выводимость (X®Y) ├ (X®Y)&(X®Z) методом редукции.

Сначала применим теорему дедукции к данной выводимости. По теореме дедукции можно проверять выводимость (X®Y)→ (X®Y)&(X®Z). Пусть в некоторой интерпретации формула имеет значение Л. Тогда I(X®Y)=И, I((X®Y)&(X®Z))=Л. Отсюда I(X®Z)=Л и I(X)=И, I(Z)=И. Таким образом, существует интерпретация переменных (I(X)=И, I(Y)=И, I(Z)=И), при которой формула является ложной. Значит, формула не выводима в ИВ.

Наиболее известный классический алгоритм проверки выводимости формул в ИВ называется методом резолюций. В основе метода резолюций положена следующая теорема (доказательство от противного).

Теорема. Если Г, ØA├ _L B, где В – любое противоречие, то Г├ _L А.

Доказательство. Г, ØA├ _L B Û Г&ØA├ _L B Û ├ _L Г&ØA ®B Û Г&ØA ®B – тавталогия. Преобразуем эту формулу.

Г&ØA ®B≡Ø(Г&ØA)ÚВ≡Ø(Г&ØA) ≡ØГÚА≡Г®А. Следовательно, Г®А – тавталогия, тогда и только тогда, когда Г├ _L А.

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

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

Пример. Найдем множество предложений, соответствующих формуле

А®Ø(В®А)

Приведем формулу к КНФ.

А®Ø(В®А) ≡ØАÚØ(В®А) ≡ØАÚØ(ØВÚА) ≡ØАÚ(В&ØA) ≡(ØAÚB)&ØA

Таким образом, множество предложений состоит из двух формул ØAÚB, ØA.

Рассмотрим теперь правило резолюции, т.е. правило вывода, которое используется в методе резолюций. Пусть А и В – два предложения в ИВ и пусть А=РÚ А₁, а В=ØРÚ В₁, где Р – переменная, а А₁, В₁ – любые предложения (в частности, может быть пустые или состоящие только из одного литерала). Правило вывода называется правилом резолюции. Предложения А и В называются резольвируемыми (или родительскими), предложение А₁ÚВ₁ – резольвентой, а формулы Р, ØР – контрарными литералами.

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

Доказательство. Пусть I(A)= И и I(B)= И при некоторой интерпретации. Тогда если I(Р)= И, то В₁ ¹Æ и I(В₁)= И, а значит I(А₁Ú В₁)= И. Если же I(Р)= Л, то А₁ ¹Æ и I(А₁)= И, а значит I(А₁Ú В₁)= И.

Пусть нужно установить выводимость Г├ _LF. Воспользуемся доказательством от противного и будем доказывать выводимость Г, ØF├ _L Æ с помощью метода резолюций. Для этого каждая формула множества Г и формула ØF независимо преобразуются в множества предложений. В полученном совокупном множестве предложений отыскиваются резольвируемые предложения, к ним применяется правило резолюции и резольвента добавляется во множество предложений до тех пор, пока не будет получено пустое предложение. При этом возможны два случая:

· Среди текущего множества предложений нет резольвируемых. Это означает, что теорема опровергнута, т.е. формула F не выводима из множества формул Г.

· В результате очередного применения правила резолюции получено пустое предложение. Это означает, что теорема доказана, т.е. Г├ _LF.

Пример 7. Докажем методом резолюций теорему

├ _L (X&Y&Z)®(X®Y)&(X®Z).

Преобразуем во множество предложений отрицание целевой формулы

Ø((X&Y&Z)®(X®Y)&(X®Z))

Ø(Ø(X&Y&Z)Ú(ØXÚY)&(ØXÚZ))

Ø(ØXÚØYÚØZÚ(ØXÚY)&(ØXÚZ))

X&Y&Z&Ø((ØXÚY)&(ØXÚZ))

X&Y&Z&(Ø(ØXÚY)ÚØ(ØXÚZ))

X&Y&Z&(X&ØYÚX&ØZ)

X&Y&Z&X&(ØYÚØZ)

X&Y&Z&(ØYÚØZ)

Таким образом, множество предложений состоит из X, Y, Z, (ØYÚØZ). Теперь производим резольвирование

	X
	Y
	Z
	(ØYÚØZ)
	ØZ	ПР из 2 и 4
	Æ	ПР из 3 и 5

Поскольку получено пустое предложение, то исходная формула выводима в ИВ.

Пример 8. Докажем методом резолюций выводимость

(X&Y&Z) ├ _L (X®Y)&(X®Z).

Преобразуем во множество предложений отдельно гипотезу и отрицание целевой функции. Гипотеза дает предложения { X, Y, Z }. Отрицание целевой формулы дает следующие предложения { X, (ØYÚØZ) }, поскольку

Ø((X®Y)&(X®Z))

Ø(X®Y)ÚØ(X®Z)

(X&ØY)Ú(X&ØZ)

X&(ØYÚØZ)

Таким образом общее множество предложений X, Y, Z, (ØYÚØZ). Далее резольвируем как в примере 7.

Пример 9. Проверим методом резолюций выводимость

├ _L X®((X®Y)®(X®Z)).

Применим к выводимости теорему дедукции. Получим

X ├ (X®Y)®(X®Z).

Еще раз применим теорему дедукции. Это дает

X, X®Y├ X®Z.

Преобразуем к множеству предложений гипотезу и отрицание целевой формулы. Таким образом, получим предложения X,Ø XÚY, ØXÚZ.

Теперь производим резольвирование

	X
	Ø XÚY
	ØXÚZ
	Y	ПР из 1 и 2
	Z	ПР из 1 и 3

Таким образом, дальнейшее резольвирование невозможно и выводимость не доказуема.

Пример 10. Перевести рассуждение в логическую символику и проверить результат на правильность: Он сказал, что придет, если не будет дождя. Но идет дождь. Значит, он не придет.

Выделим отдельные высказывания и обозначим их.

А =”Он придет”

В =”Идет дождь”

Рассуждение состоит их двух гипотез

Он сказал, что придет, если не будет дождя = ØB®A

Но идет дождь = B

Вывод из этих гипотез

Значит, он не придет = ØА

Таким образом, в логической символике рассуждение выглядит так.

ØB®A, B ├ ØА

Проверим правильность рассуждения методом резолюций.

Множество предложений, соответствующее двум гипотезам и отрицанию вывода, состоит из следующих предложений ВÚА, В, А. Среди предложений нет резольвируемых, поэтому рассуждение ложное.

1.7 Понятие предиката

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

Рассмотрим простой пример. Из истинных высказываний «5<8» и «8<10» можно сделать вывод, что «5<10». При этом истинность следствия зависит не только от истинности посылок, но и от их внутреннего строения. Изменив вторую посылку на истинное высказывание «8 ≠ 10», уже нельзя сделать вывод, что «5<10». Таким образом, даже на таком простом примере видно, что существенную роль при логическом выводе играет внутреннее строение высказываний, а не только их значение истинности.

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

Каждое высказывание представляет собой некоторое суждение о предмете высказывания (субъекте) или взаимосвязи нескольких субъектов. В предыдущем примере высказывания касались отношения порядка между определенными натуральными числами. Предметы (субъекты), о которых делается суждение, могут быть самой различной природы. Множество субъектов, о которых делаются высказывания, называется предметной областью . Для обозначения субъектов будем использовать предметные переменные. Предикат – это языковое выражение, обозначающее какое-то свойство субъекта или отношение между субъектами. В современной логике предикатами называются функции, значениями которых служат высказывания. Предикатом мощности n (n-местным предикатом) P(x₁,..x_n), , определенным на предметной области , называют отображение набора предметных переменных x₁,..x_n во множество высказываний. Приведем примеры предикатов.

o Q= «5» – нульместный предикат, определенный на множестве натуральных чисел N

o Р(x₁)= «Натуральное число x₁ четное» – одноместный, определенный на множестве натуральных чисел N.

o D(x₁,x₂)= «Натуральное число x₁ делится (без остатка) на натуральное число x₂ » – двуместный предикат, определенный на множестве пар натуральных чисел N´N.

o M(x)= «x – мужчина», одноместный предикат, определенный на множестве всех людей.

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

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

(ØP)(x₁,..x_n):=Ø(P(x₁,..x_n))

(PÚQ)(x₁,..x_n):=(P(x₁,..x_n)ÚQ(x₁,..x_n))

(P&Q)(x₁,..x_n):=(P(x₁,..x_n)&Q(x₁,..x_n))

(P®Q)(x₁,..x_n):=(P(x₁,..x_n)®Q(x₁,..x_n))

(P~Q)(x₁,..x_n):=(P(x₁,..x_n)~Q(x₁,..x_n))

Пример. Пусть на множестве натуральных чисел N определены два предиката

Р(x)= «Натуральное число x делится на 2»

Q(x)= «Натуральное число x делится на 3»

Тогда

(PÚQ)(x):= P(x)ÚQ(x) = «Натуральное число x₁ делится на 2 или на 3»,

(P&Q)(x):= P(x)& Q(x) = «Натуральное число x₁ делится на 6»

Таким образом, (PÚQ)(5) = ЛÚЛ=Л, (P&Q)(120)=И&И=И

Предикаты P, Q мощности n, определенные на предметной области W называются логически эквивалентными (равносильными), если P(x₁,..x_n)º Q(x₁,..x_n) для любого набора предметных переменных x₁,..x_n.

Пример. Пусть предметная область – это множество слов {a, abbab, bbabb, aa}. На этом множестве заданы два предиката

Р(x)= «Слово x содержит букву b»

Q(x)= «Слово x имеет длину 5»

На данном множестве эти два предиката равносильны.

Теорема. Справедливы следующие логические эквивалентности для n-местных предикатов P и Q (1 и 0 – тождественно истинный и тождественно ложный предикаты соответственно)

	P≡P	Закон двойного отрицания
		Законы коммутативности
		Законы ассоциативности
		Законы дистрибутивности
		Законы идемпотентности
		Законы де Моргана
		Законы нуля и единицы
		Законы поглощения
		Закон противоречия
		Закон исключенного третьего

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

· Все дети должны смеяться

· Все люди смертны.

· Никто не забыт, и ничто не забыто.

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

Дадим определение операции кванторов. Пусть P – предикат мощности n, определенный на предметной области W. Поставим ему в соответствие (n-1)-местный предикат " x_i P(x₁,..x_n) («для всякого x_i P(x₁,..x_n)»). Этот (n-1)-местный предикат переменных x₁,..x_i-1, x_i+1,..x_n получен из исходного навешиванием квантора всеобщности. В естественном языке предикату " x P(x) соответствуют фразы

· Для любого x (имеет место) A

· A (x) при произвольном x

· Для всех x (верно) A (x)

· A (x), каково бы ни было x

· Для каждого x (верно) A (x)

· Всегда имеет место A (x)

· Каждый обладает свойством A

· Свойство A присуще всем

· Всё удовлетворяет A

· Любой объект является A

· Всякая вещь обладает свойством A

Пусть P – предикат мощности n, определенный на предметной области W. Поставим ему в соответствие (n-1)-местный предикат $ x_i P(x₁,..x_n) («существует x_i, что P(x₁,..x_n)»). Этот (n-1)-местный предикат переменных x₁,..x_i-1, x_i+1,..x_n получен из исходного навешиванием квантора существования. Говорят, что переменная x_i связана квантором существования (всеобщности). В естественном языке предикату $ x P(x) соответствуют фразы

· Для некоторых x (имеет место) A (x)

· Для подходящего x (верно) A (x)

· Существует x, для которого (такой, что) A (x)

· Имеется x, для которого (такой, что) A (x)

· Найдется x, для которого (такой, что) A (x)

· У некоторых вещей есть признак A

· Хотя бы для одного x (верно) A (x)

· Кто-нибудь относится к (есть) A

· По крайней мере, один объект есть A

Пример. Пусть имеется предикат D(x,y)= «x-y>0» на множестве целых чисел Z. Тогда можно получить новые одноместные предикаты.

D₁(x)= " y D(x,y) = «Для всякого y, x-y>0». Очевидно, что этот предикат тождественно ложный.

D₂(y)= $ x D(x,y) = «Существует x, x-y>0». Этот предикат тождественно истинный.

Пример. Пусть имеется предикат D(x,y)= «x+y>x» на множестве натуральных чисел N. Очевидно, что для любых х и у из данной предметной области предикат D(x,y) – истинный, т.е. " х " у D(x,y)º1. Если данный предикат определить на множестве действительных чисел, то " х " у D(x,y)º0, но " х $ у D(x,y)º1.

Пример. Записать в логической символике фразу: «Кто ищет, тот всегда найдет»

Можно перефразировать данное предложение следующим образом – «Каждый, кто ищет, тот всегда найдет». Обозначим предикаты A(x) = «х ищет», B(x) = «x найдет», определенные на предметной области, состоящей из всех людей. Тогда фраза в логической символике будет выглядеть следующим образом " х (A(x)→B(x)).