В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 17
Текст из файла (страница 17)
Отсюда (Ях) -1 А (х] ], „> - И. С другой «торопи, в этом случае (Ух)А(х) ] <,,> — — Л. Отсюда Пуух)А(х]]<,, „> =И. Равноснльность (1.8) доказана. Докажем теперь равносильность (1.9]. Прнмемнм равносильность (1.8) к формуле ПАИ). тпгла П (Ух) !А(х) тв ю(Ях) -]-] А(х) — (Ях)Л(х), н грззгсвнв равнаснльность П основных равноснльнсстсй лагпкп сысзззываннй, получнм -](Ях)А(х)= ] -](дх) ]А(х) (\х) ]Л(к).
2. Вынос хэозгора эа скобки. Пусть формула А(х) содержнт свободную веремснную х, фарнулз В ве садержцт переменной х п обе онн уаовлетворнюг в. 3 определенна формул (см. с. 74). Тогда (Ях)(А(х) АВ) — (Ях)Л(к) АВ; (дх)(А(х) АВ)мз (дх)А(х) АВ; (ях) (Л(х) д В) (ях)А(х] т) В; (1.]0) (ух) (А(х) ту В) = (рх)А(х! ]/В. Покажем первую нз этнх равноснльнсстей (остальные лоцаэынаготс» аналогична).
Пусть хг,,..., хг — все свободные переменные формулы (Ях) (А (х)ВВ). Тогда онн же н все свободные переменные формулы (Ях)А(х) ВВ. Рассмотрим пронзвольную интерпретацию с множествоч М. Пусть <пь..., а >, о,щМ,— прапзвольный набор значеннй свободных переменных хь, ..,, хгх Тац как формула В не содержит переменной к. то можно ойределить тначснне этой формулы на наборе <аь ..., а„> (точнее, «а его часта, аннюящейся в свободным переменным формулы В). Гела В] < „ > — — Л, то ((Ях]А(к) АВ)]< > Л, н дла любого элемента п яз множества М на наборе вначеннй <о.
аь..., а,> своих свободных персмсянык х, кг,,..., х;„ формула А(х) АВ принимает значение Л. Отсюда (Ях)(Л(х) 6 ВВ)(<э, „> Л. Е*хгг В<а, > И. та длп любого элемента и нз множества М на наборе <а, пь .. ° . о ) фоРму лы А(х) ВВ а А(х) прнннмают однаацавые нстннностные значеапя. Отсюда ((Ях)Л(х) АВ)], > (Ях)Л(х] ]<,, о„> (Ях)(А(х]ЬВ)1< >.
Заметам, что еслн не требовал чтобы формула В не содержала переменной х, то будут выполняться толька две равнаснльностн: (Тх)(А(х) ВВ(х)) (]гх)А(х) й (дх)В(х); (Ях) (А (х) ]/В (х) ) — (Ях) А (к) Ьг ( Ях) В (х) . 3. Перестонозко одноименных «ааягоровг (дд) (дх)А(„д) (Ух)(тдд)А(х, д)г (Яд)(Ях)А(х, д) (Ях)(ЯР)А(х, д). 4. Переилеяозахпс саяапнных лгреаенаых. Заменяя связан. аую переменную формулы А другой переменной, пе входящей в эту формулу, в цванторе н всюду в областя лейстзня ьэантаРа получаем формулу. Равносильную А. Ято утверждение легко доказывается иидукипей по дзиие формулы. Рассмотрим способ упрощения формул, опирающийся на приведенные равносильности.
Под длиной формулы здесь и далее будем понимать общее число входящих в нес символов преднкатов, логических символов и символов кванторов. Так, формглз (фх~)А<ей(хь хз) Ь (Яхв)Агпз(ха) имеет ллкну 5. Формулы, в которых пз логических символов имсютсн только символы Ь, 'Ь/ н 1. причем символ -1 встречается лишь перед свижьтаии предниатов, будем называть лриведеялылгг фориуламп. Пример 1.33. ! Аой(„)1/АГзгг(хь хз] 2. (т/х!)Аог (х ) й (Яхз) 1Аглз(хь хз]. 3, -1 (Агн,(х,) т/Аш,(щ)). 1. (Ух)Аш,(хь) щ (Ях,) -1 Аой(хз).
5. -1 ((Яхт)Ащг(ха] щ А"~з(хз). Первые две формулы — привеленнме, а остальные не являются приведенными. теорема 1.!7. Для любой формулы сритггтзугт равносильная ей приведенная формула, причем лложэсгво свободных в саязаннжх лэргиглиых этих форлул соелпдают. Такая провеленная формула называется приведенной формой данной формулы. Пользуясь равноснльностями логики выскааываиий, легко указать формулу, равносильную данной и солержащую пз логических символов только символы б, '1/ и 1.
Поэтому булем считать. что рассматриваемые формулы солержат только эти логические симеозы. Докажем это утверждение иидукцпей по длине формулы. При л 1 формула атомарная и, следовательно, приведенная. Прелположим, что для формул длины меньше я утверждение теоремы верно. Докажем его для формулы Р длины и. Обозначим длину формулы Р через д(Р). Формула Е имеет вид 6Ч///, 65Н, -16, ()/х)6(х) или (Ях) 6 (х). Случай!. Так кап д(6) 6л — 2, д(Н) (и — 2, то по индуктивному предположению существуют приведенные формы 6, и Н~ фоРмул 6 и Н соответственно, и множества свободных н связанных переменных формул 6, н 6, Н~ н Н совпадают.
Тогда 6й Н~ — формула, 6, Ч/ Н, = 6 т/Й. Отсюда 6~)/11~ — прпведенна» форма формулы 6~/ Н с тем же множествоы свободных и связанных переменных, что н 6)/Н. Слр юй 2 аналогичен случаю 1. Случил 3. Здесь формула 6 может иметь вил: 3.!) 6~'ь/Н; 32) 6~5НИ ЗЗ) -16П ЗА) (Ух)6,(х) пли 35) (Ях)6,(х). Ю Случай 31: -16пп 1616 )Нь где д( 16,)щл — 2, д(-)О,) щп — 2. По индуктивному предположению существуют ярнведепные формулы бт н Нь равносильные -16, я -1 Н, соответственно, н множества своболнмк н свнзанных переменных формул б, и бт, О~ п Ог совпадают. Тогда бей Оз — пряееденная форма формулы П б с тем же мпожетчвом свободных н связанных переменных.
Случай 3.2 аналогичен случаю 3.1. СлУчзй ЗЗ: -16 -1-16, бн где д(6,) и — 2. ПРнмепаа педуктивнсе предположение к формуле бь получаем прнведенпую форму формулы Пб с тем же множеством своболных н связанных переменных. Случай 3 4: -1 б= (Ях) -1 6,(с). где д( -16~(х) ) = и — 1. Пс янлуктивному предположению существует приведенная форму. ла С,(х), рзвнсснльная формул П 6,(х) с тем же множеством свяазнных п аюбодных перененныт. Тогда (Ях)бт(х) — требуемая приведенная форма формулы:Т С.
Случай З.б вналогнче» случаю 3.3. Случай 4. Формула б(х) нмсст длину п — 1. По нндунтнвному прехположенню существует приведенная форма 6,(х) этой формулы с тем же мгюжщтвом свободных н связанных переменных. Тогда (Ух) 6, (х) — требуемая нрнведенвая форма рмулы (Тгх)6(х). $ лучай У аналогичен случаю 4. Теорема дана~ада. Приведенная формула называется нормальной, еслн она не содержат символов кеанторое плн есе символы кванторов сгонт впереди (т. с.
логические символы п символы прелнкатов стоят в области действия каждого ввантора). Пример 1.34. 1. (Ьх)(Яхт)( 1Лой(х)ТссАмг(хн хт)) — нормальная формула. 2. (1 к,) -1 Аий (х,) Ь (Ях,) Аазз(хт) — преееденная формула. не являюшанся нормальной. Теорема 1.18. Для любой приведенной формулы существует рееносисьная тй нормальное формула той же длины.
Такзе формула наэывагтсн нормальной формой данной приведенной формулы. Доказательство провепем яндукнней по длине л формулы. Прн и 1 формула атомарная и, следовательно, нормальная. Предположим, что угвержденне теоремы верно для всех ормул длнны меньше п. докажем его для формул планы л. усть à — формула длины и.
Тогда формула Р имеет вид С'сУО, бйН, ~б, (Ух)С(х) нлн (Ях]б(х!. Т Скучав 1. По условны б ~/ Н вЂ” нрнведеннан формула. огда 6 н Н вЂ” тоже прнпеденные «юрмулы длины меньше и. о индуктивному предположению существуют равносильные пм нормальные формулы б, п Н, соответственно, где д(б,) д(б): (Н~) д(Н). Если формулы С, н Н, пе содержат спмволов е шзв 81 кнанторон, та 6~ 'тг' и — нормальна» бюрна длины л формулы 6 'тс' Н. Пусть, например. формула 6 содержат символ казнтора. Тада О, нмеет впд (т(х)бт(х), где д(бт(к)) д(бг) — ! [слу чао, когда 6, нмсег аид (Ях)бт(х), аналог»тел). Если пере. мснная х »кадит в формулу Нь то талька нак связанная перо не»на» (яначе нар)щаегсз определенна формупы).
Прнмепн» правила переименования связанных переменных, перейдем к формуле Нь равносольеой Н, и пе содержащей перенсююй х. Очевидна, Н, — прнпеденная формула тсд же длины, что н Нг. По правилу выноса квантора за сксбнн (Ых)бз(к) тl Н и(ух) (О (х) т) Нт). Так как д(бз(к) ьсбт) =д(00 — 14- +1.1-д(Н) я — 1, ю по зндунтнвиому предпсложснпго существует равпоскльпая сд нормзльнан формула р~(х) той же длины.
Тогда Гух) Г,(х) — нормальна» форма формулы От)Н той же данны. Слуеа» 2 аналогичен случаю 1. Случай Р. Так «ак формупа 16 приведе»лая, то б — атомарная формуле, н тогда !6 — нармальнаа фпрнула. Случай 4. Здесь 6(к) — ярнщденнан форнула, д(б(х)) л — 1. По индуктивному предположенню существует рааносильнаа еб нормальная формула 6,(х) той же дпн»м. Тогда (ух)6~(х) — пормальнеа форма формулы (ух)0(к) дюгпы ж Случад б аналог»чек случаю 4. Теорема дпказепа. Йз теорем !ЛУ п 1.18 «ытекает следующее утверждение. теорема 1лп. Для любой формулы существует ралносиленая еу норлальла» фор улп. 1.4.3.
Выполя»мосты Общеаначнмость Ресснатрон некоторую ннтерпретакию с мггсжсстаан М. Говорят, что формула Л оыпаллима о даяние пнтеряретац щ сел» сУщсстнУет набоР <аь ..., а ), аскеМ, значенпб спобаляих переменпык хс... „хг формулы Л такой, пг А)<с„е > —— И. Гонорнт, что формула А истинно в даияае интерпретацию сели сна арин»мает зоаченне И на любоч наборе <аь...т а,), а,щМ, значенпй своик свободных переменных хс, ..., хс„ Говорят, что формула А абираначкиа олн тожлестаенгю »стан»а (а логкке »реля»атон), есла онз нстнпна п каждан на. тсрпретаянн. Говорят, чта формул.
А аыполиима (в логике прсднкатос)', еслн существует ннтерпрстакия, п «сгорай Л выпопппмз. Формула А общсзначнна тогда и только тогда, магда фоу мула -)Л пе является выполнимой, » формула Л выполнима тогда н только тогда, когда формула -)А пе является обще апач»май. ат Очевидна, что сслн р я 0 — равнсснльпыс (в логике пре- двкатов) формулы, то Р- 6 — сбщезначнмая формула. Првмепнв зтс утвсрждснне к формулам, раввоснльносп которых доказана в рязд. 1.4.В пслу гнм обгдезвачнммс форчу- лы. Докажем сбшезпачпмссть некоторых лругвк формул. Утвержденве !.18. Формуле (Чх)А(х) ~А(р), (! .11) где лгрглзхлех р лс екодит е форлрлр А(к). общеэлочлма. Пусть к, лг, ..., к, — есе свсболпые переменнме формулы А(г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
