В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 19
Текст из файла (страница 19)
откуда (Бкг)А(хг) ~В(<п, „„> И. Справедливость доказываемого утвержления дла правила вывода 4 почти очевилна. Теорема 4.24, Любая емеодилпл з псчзслепии ярсдикогое ФоРмула общеэначшю. Этз теорема вьпекает из утвержлевий 1.22 п 1.23. Пример 1.36.
Докажем общезначимость формулы (Бх)(Чхг)А(хь кВ ~ (Чхг)(Бхг]А(х кг). Для этого покажем, что эта формула является теоремой псчослекия предпкатов, т. е. 1- (Бк ) (Чхг) Л (щ хг) ~ (Чх ) (Бх ) А (х„хВ. Построим этгл вынод: .(1) г- (ЪхВА(х„зг) ~А(хь х,) (аксиома 4); (2) 1- Л (х,. х,) ~ (Бхь) А(хь х,) (аксиома 5); (3) Я ~В, В=гС,-А ~С (по теореме 1.20); (4) — (ЧхВА (хг, хг)~(Бхз)А(хз, к,) ((3) пРимеиена к (1) м (2)) (3) г- (Бх,) (Чх,)А(хь х,)~(Бхз)Л(хь, х,) (правило вывода 3 применено з (4)); (6) г- (Бх)(укАА(хь хг) ~ (Чх,)(Бкз)А(хь кг) (правило вывода 2 применено к (3)); (7) 1 — (Бх ) (Чхг)Л(хг, «г) л (Чкг) (Яхз) А(кь х ) (правило мывода 4 применено к (6)); (8) 1- (Бхг) (Чхг)А (хг, хВ =г (Чхг)(Бхг)А(х„хг) (правило вм-.
мода 4 применено к (7]]. Теорема 1.22. Исчисление лредпкатое непротиворечиво. Действительно, в силу теоремы 1.21 невозможно охновремсн° о -А 1Л. Прпвелем без доказательства формулировку теоремы, обрат. иоб теореме 1.21. Теорема Геделя ( о коллеге исчисления предпкягое). Всякая общезнпчзипя формула емеодпзга з исчислении предиквгов. Задачи н упражиемия 1. Б]дуг ли следующие выражения формуламн, п если это формулы, та какие переменные в ник ивляются свободггымгс з какие связанными: .а) (Чх,) (Бх,) (Чхз]Аг'гг(хь хь хэ щ) г б) (Чх )Агиг(хь хз] ~ [Бх,)Лгзг~(хг, хг); в) (Бх](Бхз) (Лгзгз(хь хз) ЬАгзгз(хз, зф)? нз 2. В той же ннтереретации Ч1, что н и примере 4.5, записать.
формулы, выражающие следующие утвержлсння: а) х — нечетное число; б) я < у; в) х — наибольший общий делитель х и р; г) ассоциативность сложения; д) бесконсчвость мпожества простых чисел; е) конечность множества простых чисел; ж] существование навбоиьшего натурального числа. Будут лн бюрмулы «е» и «ж» истинны в лаиыой интерпретация] 3. Пусть М вЂ” множество точек прнмых п плоскостей трек- мерного евклидова пространства. Рассыотрим нптерпреташяо.
М <М, (>, где ] — соответствие, сопоставляющее прсдикатпмм символам Р,(х), Рз(х), Рз[х]. ф(х, р), Я(х, р] следующие иредпкатн: Р,(х) г«х — точка»; Р,[х):«х — прямая»; Р [х]: «х — плосиость»; 4(х, у): «х лежит иа р»; ]((х, р)! «х сов-' падает с и». Записать е этой интерпретации йюрмулы, выражающие слелуювгие утвержденна: а) через каждые дее точки можно провести прямую и притом единственную, если этн две точки различны; б) через каждые тре точки, не лежащие иа оляой прямой» ыажно провести шшнственную плоскость. 4.
В петерпретацип Мз (см, пример !.31, п. 3) записать утверждение а таы, что функция ((х) равномерно-непрерывна иа отрезке. Прн каком условии, наложенном яа функцию Цх), в этой интерпретации истинна формула (Яб) (Уе) (Чтг) ['тх~) О. (х) 6 В (х) Ь )( (а) Ь (Р~ (хь хь б) ш шб, (хь хь е))? 5. В интерпретации М - <Л[, (>, где М - Р(4), А — некг тоРос множество, ] — саотвештвпс, сопоставлиющее преднкатному символу Р(х, р) прсдпкат хщр, записать, что.' а) х— пересечение р и х; б) х — объедннмп~е р н х! в) х !Я; г) х А; д) х — дополнение д. б.
Доказать нлп опровергнуть следующие равносальисснв (формула В не содержит вхождений переменной х): а) (Ях)(А(х) юВ]шз()гх)А(х) шВ; б) (Ях) (А(х) шВ) [Ях)А(х) щВ; в) (Чгх) (В ш А (х) ) В щ [ух) А (х); г) (Ях)(ВшА(х)) — «Вш (Ях)Л(х). 7. Доказать, что следующие формулы равноснлыты: а) (Ух)(А(х) ЙС(х)) (Ях)А(х) Ь (Ух]С(х); б) (Ях) (А(х) )У С( ]]= [Ях)А(х] 17 (Ях)С(х). 3.
Для слслующид формул указать приведенную нормальную форму: а] (Ях)(ур)Ащ~(х. Р) ю (Ух)(ЯР)А«гй(х, р); б) (Ух)Аог~(х) ю (члх)(ЯР)Ав~ (х, р). 9. В интерпретацняк примера !.3! записать утверждение о точ, что: а) число А не есть предел функпия цх) при х х«; б) функция ((х) разрывна в точке хь !о. Привести примеры формул, раеиосмльных в ннтерпрегаш«ях <М, )> с двухэлементным множеством М. И 11. Выполнимы ли следующие формулм: а) (Ух)А>'»(х); б) (Их) (Уу) (А'»'(», х) й (А'Я>(х, ь)); в) (Их)Ао>,(х) юАи>,(у)? 12. Будут ли общезначиммми следующие формулы: а) (Ух) А (х) ю А (у); б) А (х) ю (Т>у) А (у); в) (Их)А(х) (Рх)А(х)> г) (Их)(уу)А(х, у)-(Ру)(Их)А(х у)У 13.
Выполнимы ли следующие формулы: а) (>>х) (Иу) (А>'>(х)--)А»'(у)); б) (Иу) (Рх)(А> (х)- -)А >(у))1 1.3. ЭФФЕКТИВНАЯ ВЫЧИСИИМОСТЬ Для решения ряда однотипных задач иногда целесообразно использовать чисто механические вычислительные процессы.
С их помощью искомме величины вычисляются воследовательно нз данных величин ио определенным праввлам. Описание таких процессов принято называть алгоритмами. Вообще говоря, пад алгоритмом интуитивно понимается некоюрое формальное предписание, действуя согласно иоторому можно получить решение задачи. Типичимми примсрамн алгоритмов служат решения следующих задач: !) нахожденке наибольшего общего делителя двух положительных иатуралмшх чисел; 2) извлечение квадратного корня нз радионального числа с заданной степенью точности; 3) вычисление ранга целочисленной матрицы; 4) определение тождественной истинности формулм логики вмсказмваний. Перечисленные алгоритмы имеют ряд общих черт, которые естественно считать присущими любому алгоритму: 1) злементарнссть шагов алгоритма: реиижие задачи разбивается па зтаоы, кажлмй иа которых должен быть простым н локальным; 2) детерминированность алгоритма: после вмполиеиия очередною агава однозначно определено, что делать иа следующем агапе; 3) направленность алгоритма: должно быть указано, что считать результатом применения алгоритма; 4) массовость алгоритма: алгоритм служит для решения ие какой-то одной задачи, а целого класса однотипных задач.
Интуитивное понятие алгоритма, хотя и ие строго. на на. столько ясно, что всегда можно определить, является ли данный ео прпцссс алгоритмом. Поэтому удовлетворительным доказетельством с)жествовавня алгоритма счнтается описание фактпческого процесса решения какой-лнбо задачи. Однако для некопгрых ггзвестных проблем (например, дл» проблемы установления обпгезнашмостн фпрмул логики прела»атон) не удавалгюь найти разрсшаюшего алгорптма. Безуспешные пппмткп найти такое алгорнгмы привел» ь прелполсжснгоо, что пх не существует.
Ио для того чтобы доказать. нес)в!сот»о»анне алгорнтна, надо точно знать, что такое алгоритм. Начн»ая с 30-х голов было прелложено несколько уточнений понятия алгоритма. Считается, что вс» овн »остаточно полно птражашт основные чер~ы ннтуптнвного понятия алгоргп на.
Действкгсльна, все фсРмалыгые определення алгорнтма в неьотором смысле зкаевалснтны друг другу, все алгоритмы в точном смысле являются алгоргыыамп в ннтунтквном смысле, н, ьак показывает опыт, все пзвестные алгоритмы можно задать алгорнтмамн в точном смысле. Для алгорнтмпческнх проблем тнкнчной является. пакрнмер. снтуацк», «огла требуется найти алгорнтм для вычнсленпя чнслгпой функцнн /(хь..., х ), зав»сягцей от пелочнслепкых значснпй аргументов хь ..., х .
Числовые фупкшп!, звачення «оторых мпжпо вы шслять посредством некоторого (единогп длк лампой фупквнп) алгорнтма, каэываютс» аычпслалылв фр»ьчилмп, Принято считать, по /(хь..., х,) эффективно эычжлима. еслп нмеется какая-нибудь меланнческа» пропедура (азгорктм), слелуя которой ыожнп найтя значсяпп /(й».... А ). кггдз нзшстны значения йь..., И„ аргументов. Посколь") авиэтке алгорнтма н!гтуптнвггць то к понятие пычвслнмой фукхпнп ннтунтввпо. Ниже мы рассмстрнм некоторое уточнение понятна вычеслнмой функцвп — частично рееурснв»ые фупкннп.
Затем о»рсделвм уточнение понятия алгоритма, связанное с машинами ТьюРинг», что позвопнт нам доказать неразрешпмость некоторых алгорптмн !ескггх проблем. !.б.(. Реяурснвиые функцнн Бувем рассматрнвать тплько чнсловые функцнв. т. е. фунхцпп, аргументы и значения которых принадлежат мнпжестау натуРа.тьных чксел йг (в теор»к рекурснвных функций полагают О, 1, 2,...). Иначе говоря, частичкой кпслоеой и-местной Функцией /(хь .... х ) называется функ!Пи, опрепеленпа» па некотором подмножестве й( Р)" с натуральными .гначепнямн. Если область определенна совпадает с мпожес!еом Ф", т.
е. /: йг й(, то говорят, что функцвя / всюду пнрцделепиая, и пр»т»»ком случае — частично определенна». В1 Например, Цх, д) -к+ у — всюду определенная дауместмая функция, ((х, д) =к — д — частнчиа пиределеиная функции (оиа определена, кпгда х)д). Рекурсивным определением функции принято называть таксе .ее опрсделеипе, при котором значения фуньщри для даииык аргумеиюв апрелеляются зиачеииями той же функции для более простых аргументов или же значеинями более простых .функций.
Простейшим примерим рекурсивиого оиределеция являратся числа Фиббоиачи, представляющие спбпй иоследовательпасть шсел )(и), удовлетворяющих услпвиям ((О] = 1, ЦП=(,Цл+2)=Цл)+Цл+Рд 1, 1,2,3.3 3,!3... Опи!псм класс числовых функций, играющих щхьма важпую рпль в математический лпгике. Следуюшпе всюду определенные числовые функции назовем лросгейщилир 1) 5(х) х+ 1 — прибавление единицы; 2) О(х) =0 — иуль-фуикцвя; 3) ! (хь..., х ) х гл=1,..., л, — проектируюрцая фрикции. Все эти функции вычислимы в ннтуитивиом смысла Определим теперь апсратпры. Оии пбладают тем свпйствам, пп. применяя их к фуикциям, вычпслиммм в иитуятивиом смысле, получаем функции, также вычислимые а иитуитивиом смысле.
1. Олгрогор сулсряоэичии. Гпеорят, чтп л-мествая фупкция ф(к,..., х ) получена с помощью оператора суперпозвнии из лг-местной функция р(хь..., х ) и л-местных фуикюрй Ц(кь ..., х„),..., ( (хь ..., х ). если ф(хь ° ., х ) в(((х,..., х ),..., ( (хь..., х„)). (1.12) 2. Олепигор иримигиенод рекурсии. Говорят, что (и+1)- .местная фуикцяя )(хь..., к, д) получена из и-местной функции Р(хь..., к„) и [л+ 2)-местиой фУикцин Ррхь ., к„, д, а) с помощью оператора примитивной рекурсии, если ее эпачеии» можно вычислить по следующей схеме (схеме примитивной реку сии): Цкь ..,, х,, 0) = ч (хь ..., х ); У(хь ..., к„ д 1 !) = 2(хь , х й, Цхь ..., т„, д)). (1.!3) При л = 0 схема примитивной рекурсии имеет вид ЦО) =а; Цд -и 11 - ф (д, Цд) ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
