1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

, Pk. Ясно,Pk, а зависиттолько от самой формулы Ф.СеквенцияS(P1, ... , Pk) видаS[P1, ... , Pk]k-местную операциюФ1,... , Фп 1- \llопределению совпадает с операцией Ф[Р1,Ф=(Ф1---+ (Ф2---+Из этого определениянаборе (б1,... , бk),такжена множестве {О,определяет1}, которая по... , Pk], где( ... ---+ (Фп---+ w) ... ))).видно,что секвенция Г1- \llистинна наесли на этом наборе либо одна из формул Г ложна,либо Ф истинна.СеквенцияSназывается тождествен.но истин.ной, если она ис­тинна па любом набореР1,... , Pk,(t1, ... , tk)значений истинности переменныхсреди которых содержатся все переменные, входящие вОчевидно, что это понятие также не зависит от выбора Р1,...

, Pk.S.§ 1.6. Семантика исчисления высказыванийТеорема1.6.3.Если секвенцияS41ИВ доказуема в ИВ, тоSтождественно истинна.До к аз ат ель ст в о индукцией по числу переходов в доказатель­ствеDсеквенцииSв виде дерева. Еслиаксиома, то утверждениеS -теоремы тривиально. Чтобы завершить доказательство теоремы, нужнопроверить, что правила1-12сохраняют тождественную истинностьсеквенций. Пусть, например,Гf-Ф; Гг-применение правила8.f- Ф-+ \Jif- \jiЕсли на некотором наборе истинности про­позициональных переменных все формулы из Г истинны, то по индук­ционному предположению Ф и Фпо определению операции-+-+ \Jiистинны на этом наборе.

Тогдаформула Ф тоже истинна.Проверка других правил такжепроста и предоставляется чита-отелю.Из теоремы1.6.3получаем другое доказательство следствия1.6.2.Qo /\ ~Qo - тождественно ложная формула.теоремы 1.6.3 секвенция f- Qo /\ ~Qo не доказуемаВ самом деле, ясно, чтоПоэтому в силув ИВ.СледствиеФ[Р1, ... , Pk] и1.6.4. Если Ф(Р1 , ... ,Рk)w[P1, ... , Pk] совпадают.Доказательство. Пусть Ф[б1,доказуема. По теореме1.6.3= w(P1, ... ,Pk),...

,бk]f-секвенция Ф=По условию Ф1.=f-ФФ тождественно истинна.По определению истинности секвенции получаем Ф[б1,логично из Ф[б1, ... ,бk]то функции1 получаем \Ji[б1, ... ,бk]... , бk]= 1.= 1.Ана­ООбозначение. Напомним, что для формулы Ф введены следующиеобозначения: Ф 1 = Ф, Ф 0 = ~Ф. Набор нулей и единиц (б1, ... , бп) частобудем обозначать через J.

Отметим, что при п = О это будет пустойнабор.Лемма 1.6.5. Элементарная дизъюнкция Ф видапринимает значение О на единственном наборе б-бп)) значений истинности переменных Р1,Pf= ((1 -V ... V P!nб1), ... , (1 -1... , Рп.P/iДо к аз ат ель ст в о. Формула Ф построена из формулприV. Из таблицы истинности для дизъюнкции следует,что если бы одна из формулприняла значение 1, то Ф такжеприняла бы значение 1.

Следовательно, Pi должна принимать значениепомощи операции(1-бi)-P/iо42Гл.Теорема1.6.61.Исчисление высказываний(о функциональной полноте ИВ). Пустьфункция, определенная на наборах (бо,f -... , бп) нулей и единиц ипринимающая нуль или единицу в качестве значений.Тогда су­ществует такая формула Ф ИВ, переменные которой содержатсясреди= f.Qo, ... , Qп и Ф[Qо, ... , Qп]До к аз ат ель ст в о. Еслиfчестве Ф можно взять формулуДля набора б= (бо, ... , бп)тождественно равна единице, то в ка­Qo V ~Qo.элементов множества {О,обозначим значение функции J(бо,Х= {((l -... , бп)-l} через f (б)Пусть множествобо), ...

, (l - бn))1 f(б)= О}не пусто. Возьмем в качестве Ф формулу вида(QgoлV ... V Q~n).бЕХДокажем, что Ф[бо, ... , бn] = О равносильно J(б) = О. Пусть Ф[б] = О.Так как Ф построена из конъюнктивных членов с помощью операции А,то существует конъюнктивный членw,который ложен на наборе б.Формула W имеет вид Qi~ V ... V Q~~, где (б0 , ... , б~) Е Х. В силупредыдущей леммы бi = (l - б~). i::;; п, следовательно,((l - бо), ...

, (l - бn)) = (бо, ... , б~) и f(б) = О.Пусть теперь f (б) = О. По предыдущей лемме конъюнктивный член wвида Q~l-бo) V ... V Q~l-бn) ложен на наборе б. Используя опять то, чтоФ построена из конъюнктивных членов (среди которых находитсяпри помощи операции А, заключаем, что Ф[бо,... , бn] =О.W)DУпражненияl.Предположим, что ваши вычислительные возможности состояттолько в следующем: если вам дают пару чисел б1, б2 Е { О,l},товы можете вычислить максимум mах(б1, б2) этих чисел, а когдавам дадут б Е {О, l }, то вы можете назвать б Е {О, l }, которыйне равен б.

Показать, что вы тогда способны вычислить любуюфункциюf,сопоставляющую наборам (бо,... , бn)нулей и еди­ниц нуль или единицу. А именно, для любой такой функцииso, ... , Sk, чтопарой (j, m) чисел,существует такая последовательностьi ::;; kэлемент Si является либолибо одним числом, меньшимнабору (бо,qo, ... , qkа) если... , бn)i.п, томеньшихi,При этом, если вы по заданномунулей и единиц напишете последовательностьнулей и единиц по следующему правилу:i ::;;fдля любогоqi= бi;§ 1.7.б} если пв) если п<i<i~ k и si= (j, m),то qi~ k и si< i,=qВоспользоваться теоремой2./\Фто qifто тогда qk будет значениемностью Ф43Характеризация доказуемых формул= max(qj, qm);8 ;,на наборе (бо,1.6.6,= ~(~Ф V ~Ф).)Показать, что если формулы Фследствием=Ф... , бп)- (Указание.1.6.4 и эквивалент­находятся в совершеннойк.

н. ф. (совершенной д. н. ф.} и содержат одни и те же перемен­ные, то{D(X)Е D(Ф)}= {К(Х)§ 1. 7.ТеоремаХЕ К(Ф)}11= {D(X)JХЕ К(Ф)} ({К(Х)1ХЕХЕ D(Ф)}).Характеризация доказуемых формул1. 7 .1.Пусть Фформула ИВ. Следующие три условия-эквивалентны:1). Ф доказуема в2). Для всякой Ф'ИВ.= Ф,находящейся в к. н. ф., и любого ее конъ­юнктивного члена Ф существует такая атомарная формула Р, чтоР, ~р Е D(Ф).3).Существует Ф'= Ф,находящаяся в к.

н. ф. и такая, что длялюбого ее конъюнктивного члена iJт существует такая атомарнаяформула Р, что Р, ~р Е D(Ф).До к аз ат ель ст в о.2) ===} 3) тривиально. 3) ===} 1) следует из1.5.8, 1.5.11 и 1.4.3 а).Докажем 1) ==> 2). Пусть формула Ф доказуема. Тогда доказуемаформула Ф' и по лемме 1.5.8 доказуем любой конъюнктивный член Флеммформулы Ф'. Предположим, что D(Ф) не содержит никакой атомарнойформулы Р вместе с ее отрицанием ~р_ Рассмотрим два множестваатомарных формул Х={РПо предположению, ХnУвсех подформул Р Е Х наI=Р Е D(Ф)} и У={Р1~р Е D(Ф)}.е.

Пусть Ф I получается из Ф заменойQoи всех Р Е У на~Q 0 .По теоремео подстановке Ф1 доказуема. Пусть Ф2 получается из Ф1 заменойнаQo. В силу леммы 1.4.5 б} и теоремы о замене имеем Ф2~~Qo= Ф 1•Следовательно, Ф2 доказуема. Очевидно, что D(Ф2)= {Qo}.ствиюQo доказуема. По1.5.5выполняетсяQo= Ф2.Значит, формулаПо след­теореме о подстановке получаем, что любая формула Х доказуема.

Этоневозможно в силу непротиворечивости ИВ.Теорема1.7.1Одает характеризацию доказуемых в ИВ формул, осно­ванную на строении эквивалентных им формул, находящихся в к. н. ф.Такую характеризацию назовем дедуктивной. Сейчас мы получим се­мантическую характеризацию доказуемых в ИВ формул, основаннуюна понятии истинности.Гл.44Лемма1.7.2.Исчисление высказываний1.Секвенция Г, Фf-Фтогда, когда доказуема секвенция Гf-доказуема тогдаФ----+До к аз ат ель ст в о непосредственно по правиламТеорема1.7.3и толькоФ.и7О8.(о полноте ИВ).

а). Для того чтобы формула ФИВ была доказуема в ИВ, необходимо и достаточно, чтобы Ф былатождественно истинной.б). Для того чтобы секвенциянеобходимо и достаточно, чтобыДо к аз ат ель ст в о.SSИВ была доказуема в ИВ,была тождественно истинной.НеобходимостьутверждаеттеоремаУтверждение б) следует из а), так как в силу леммыl. 7.2l .6.3.и опре­деления тождественной истинности секвенций и формул доказуемостьи тождественная истинность секвенции Ф 1, .•. , Фпf-Ф равносильныдоказуемости и тождественной истинности формулы Ф1----+ (Фп----+ Ф) ...

).Пусть Ф - тождественно истинная формула и Ф'----+ (Ф2----+ •.. ----+=Фнаходит­ся в к. н. ф. Предположим, что Ф не доказуема. Тогда Ф' тоже недоказуема. В силу леммl .5.8исуществует конъюнктивныйl .5. l lчлен Ф формулы Ф', для которого D(Ф) не содержит атомарной фор­мулы Р вместе с ее отрицанием ~р_и У= {Р1~р Е D(Ф)}. Тогда Хпринимают значение О,леммеl .6.5формулаПусть Хn У=а переменные из Уw принимает={РIРЕ D(Ф)}!25.

Если переменные из Х-значениеl,топозначение О. Так как Ф' построенаиз конъюнктивных членов (среди которых есть Ф) с помощью однойсвязки/\,то Ф' принимает значение О, когда переменные из Х при­нимают значение О, а из У-значениеl.Следовательно, Ф'тождественно истинная формула. В силу следствияl .6.4тоже не тождественно истинная. Получили противоречие.-неформула ФОЕсли задано исчисление и определено понятие истинности (семан­тика) формул этого исчисления, то говорят, что исчисление непро­тиворечиво по отношению к этой семантике, если в исчислениидоказуемы только истинные формулы. Если доказуемы все истинныеформулы, то говорят, что исчисление полно по отношению к этойсемантике.Кроме проблемы непротиворечивости и полноты важное значениеимеет проблема разрешимости исчисления. Говорят, что исчислениеразрешимо, если существует эффективная процедура (алгоритм), поз­воляющая для любой формулы Ф через конечное число шагов опреде­лить, доказуема Ф или нет.

Если такой процедуры не существует, тоговорят, что исчисление неразрешимо.Если истинность формул ИВ определить как тождественную истин­ность, то предыдущая теорема показывает, что ИВ полно и непроти-§ 1. 7.45Характеризация доказуемых формулворечиво по отношению к этой семантике. Очевидно, что за конеч­ное число шагов можно узнать, является ли данная формула Ф ИВтождественно истинной или нет. Так как тождественная истинностьи доказуемость Ф эквивалентны, то ИВ разрешимо.При задании исчисления с помощью схем аксиом и правил выводаестественновозникаетвопросонезависимостиэтихсхемаксиомиправил вывода.

Схема аксиом называется независимой в исчислении,если хотя бы один ее частный случай не доказуем в исчислении безэтой схемы. Правило вывода называют независимым в исчислении,если оно не является допустимым в исчислении без этого правила.Исчисление называется независимым, если все его схемы аксиом иправила вывода независимы.При построении исчисления часто стремятся получить его незави­симым. (Немаловажную роль здесь играют эстетические соображения.)В оставшейся части параграфа на примере ИВ будет изложен важныйметод доказательства независимости исчисленийПредложение1. 7 .4.1).ИВ независимо.До к аз ат ель ст в о. Так как в ИВ только одна схема аксиом, тоона независима. Для доказательства независимости правил вывода до­статочно для каждого правила а найти характеристическое свойство б,которым обладают все секвенции, доказуемые при помощи правил, от­личных от а, и которым некоторые доказуемые в ИВ секвенции не об­ладают. Мы ограничимся только формулировками характеристическихсвойств для правил1-12, оставляя необходимую проверку читателю.1-1 О будет тождествен­Характеристическим свойством для правилная истинность(§ 1.6)секвенций при новом определении для каждогоправила одной из логических операций/\, V,---+, ~ на множестве {О,Остальные операции при этом определяются по таблице1}.§ 1.6, а логи­ческая константа принимает значение О.

Характеристики

Список файлов книги