В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 53
Текст из файла (страница 53)
В заключение будут рассмотрены примеры функций, для вычисления которых строятся нормальные алгоритмы в расширенных алфавитах. Речь пойдет о числовых функциях, а для кодировки чисел словами будет использоваться десятичная система счисления, т.е. алфавит, состоящий из десяти букв (цифр): А = (О, 1, 2, ..., 9). Его будем называть основным алфавитом. 1420. Сконструируйте нормальный алгоритм в алфавите А = (Ц, вычисляющий следующую функцию: а),Ях) = х + 1; (1, если х делится на 3, б) <рз(х) =~ ' 10, если х не делится на 3. Указание.
См. Учебник, примеры 34.6, 34.7. 14.21. Какую функцию вычисляет нормальный алгоритм: а) Л-+.Л; б) Л-+Л? 14.22. Сконструируйте нормальный алгоритм, вычисляющий словарную функцию 7(ы) = ии, заданную на словах в алфавите А, которая к каждому слову и в алфавите А приставляет справа фик- сированное слово и (возможно, также в алфавите А). Решение. В качестве алфавита для требуемого нормального алгоритма возьмем алфавит В = А о (2) = (О, Ц .~ (2) = (О, 1, 2). Рассмотрим нормальный алгоритм в алфавите В со следующей схемой: 20 -+ 02, 21 -+ 12, 2 -+ . и, Л вЂ” ~ 2.
Применим данный алгоритм, например, к слову и = 01101 в алфавите А. На первом 253 шаге применяется последняя подстановка схемы, что дает слово 201101. На каждом последующем шаге будут применяться поочередно первые две подстановки данной схемы, в результате чего символ 2 будет меняться местами с символами 0 и 1 до тех пор, пока не достигнет правого края данного слова: 011012.
Теперь работает заключительная подстановка 2 -+ . и, которая дает слово 01101и = и и. 14.23. В алфавите В = А ~г (а, Ь), являющемся расширением алфавита А, рассмотрим нормальный алгоритм, задаваемый схемой (читается по столбцам): ОЬ -+ Ь9 аО -+ Оа Оа -+ ОЬ 1Ь -+.0 а1 -+ 1а 1а-+ 1Ь 2Ь -+. 1 а2 -+ 2а 2а-+ 2Ь ЗЬ -+.2 аЗ -+ За За-» ЗЬ 4Ь -+.3 а4 -+ 4а 4а-+4Ь 5Ь -«.4 а5 -+ 5а 5а-+ 5Ь 6Ь -+.5 аб -+ ба ба-+6Ь 7Ь -+.6 а7 -+ 7а 7а-+ 7Ь 8Ь -+.7 а8 -« 8а 8а-+ 8Ь 9Ь -+.8 а9 -+ 9а 9а-+ 9Ь Л-«а. Применив его к следующим словам, постарайтесь понять, что он вычисляет функцию Ях) = х — 1: а) 146; б) 50; в) 210; г) 1000; д) 90; е) 360; ж) 400; з) 1998; и) 770; к) 1280; л) 3000. Р е ш е н и е.
л) Алгоритм работает следующим образом. На первом шаге применяется самая последняя подстановка: 3000 ~ а3000. Далее начинают работать подстановки из второго столбца, меняя местами букву а с соседними справа цифрами данного числа до тех пор, пока а не займет крайнее правое положение: а3000 ~ ~ ЗаООО ~ ЗОа00 300аО ~ 3000а. Теперь срабатывает одна из подстановок третьего столбца (в данном случае — первая)„фактически меняя букву а на букву Ь: 3000а = ЗОООЬ. Наконец, срабатывает одна из подстановок первого столбца.
Если бы перерабатываемое слово завершалось цифрой, отличной от О, то сработала бы одна из заключительных подстановок, последняя цифра была бы заменена цифрой, на единицу меньшей, а алгоритм закончил бы свою работу. В данном случае слово завершается цифрой О. Поэтому срабатывает первая подстановка первого столбца: ЗОООЬ ~ ЗООЬ9. Поскольку и предпоследняя цифра в перерабатываемом слове равна О, то алгоритм снова применяет первую подстановку, меняя местами 0 и Ь и заменяя 0 на 9.
Так будет происходить до тех пор, пока левее буквы Ь не окажется цифра, отличная от 0: ЗООЬ9 ~ ЗООЬ99 =» ЗЬ999. Теперь срабатывает одна из заключительных подстановок: ЗЬ999 =» 2999. Укажем последовательности переработки некоторых слов: а) 146 ~ а146 ~ 1а46 ~ 14аб =» 146а ~ 146Ь = 145; б) 50 ~ а50 ~ 254 ~ 5аО ~ 50а = 50Ь ~ 5Ь9 ~ 49; и) 770 ~ а770 = 7а70 =« 77аО =« = 770а =« 770Ь = 77Ь9 ~ 769.
14.24. В алфавите 3 = А «(а, Ь, с), являющемся расширением алфавита А, рассмотрим нормальный алгоритм, задаваемый схемой: ОЬ -+.2 аО -+ Оа Оа -+ ОЬ Ос -+. 1 1Ь -+. 3 а1 -+ 1а 1а -+ 1Ь 1с -+ . 2 2Ь -+ . 4 а2 -+ 2а 2а -» 2Ь 2с -+ . 3 ЗЬ -+.5 аЗ -+ За За -+ ЗЬ Зс -+.4 4Ь -+ . 6 а4 -+ 4а 4а -+ 4Ь 4с -» . 5 5Ь -+.7 а5 -» 5а 5а -+ 5Ь 5с -+.6 6Ь -«.8 аб -+ ба ба -+ 6Ь бс -+.7 7Ь -«.9 а7 -+ 7а 7а -+ 7Ь 7с -+.8 8Ь -+ сО а8 -+ 8а 8а -+ 8Ь 8с -+.9 9Ь вЂ » с1 а9 -+ 9а 9а -+ 9Ь 9с -+ сО с -+.1 Л-+ а.
Применив его к следующим словам, постарайтесь понять, что он вычисляет функцию Дх) = х+ 2: а) 173; 6) 28; в) 999; г) 568; д) 898; е) 998; ж) 98; з) 9; и) 1000; к) 1998; л) 546. Решен и е. а) 173 ~ а173 ~ 1а73 ~ 17а 3 =«173а =«17ЗЬ =«175. б) 28 ~ а28 ~ 2а8 =« 28а =« 28Ь =« 2сО =« 30. в) 999 =« а999 ~ 9а99 =« 99а9 ~ 999а =« 999Ь ~ 99с1 =« 9с01=« =« с001 =« 1001.
г) 568 ~ а568 ~ 5а68 ~ 56а8 ~ 568а 568Ь ~ 5бсО =« 570. д) 898 =« а898 =« 8а98 =« 89а8 =« 898а =« 898Ь => 89сО =« 8с00 =« 900. 14.25. В алфавите В = А «(а, Ь, с), являющемся расширением алфавита А, рассмотрим нормальный алгоритм, задаваемый схемой: аО-+ Оа Оа -+ ОЬ ОЬ -+ с8 Ос -» с9 а1 -+ 1а 1а -+ 1Ь 1Ь -+ с9 1с -«. 0 а2-+ 2а 2а-+ 2Ь 2Ь-+.0 2с -«.1 аЗ -+ За За -+ ЗЬ ЗЬ -+ . 1 Зс -+ . 2 а4 -+ 4а 4а -+ 4Ь 4Ь -+.2 4с -+.3 а5 -+ 5а 5а -+ 5Ь 5Ь -«.3 5с -+ .4 аб -+ ба ба -+ 6Ь 6Ь -+.4 бс -».5 а7 -+ 7а 7а -+ 7Ь 7Ь -+.5 7с -+.6 а8 -« 8а 8а -+ 8Ь 8Ь -+.б 8с -+.7 а9 †« 9а 9а -+ 9Ь 9Ь -+.7 9с -+.8 Л-+ а.
Применив его к следующим словам, постарвйтееь понять, что он вычисляет функцию 7(х) = х — 2: а) 64; б) 71; в) 192; г) 501; д) 1001; е) 240; ж) 99; з) 101; и) 700; к) 16; л) 2. Р е ш е н и е. а) 64 ~ а64 =«ба4 ~ 64а ~ 64Ь =«62. б) 71 = а71 ~ 7а1 =« 71а =« 71Ь ~ 7с9 =« 69. в) 192 = а192 =« 1а92 ~ 19а2 ~ 192а ~ 192Ь =« 190. г) 501 =«а501 =«5а01 =«50а1 ~ 501а ~ 501Ь ~ 50с9 ~ 5с99 ~ 499. 255 д) 1001 ~ а1001 ~ 1а001 = 10а01 => 100а1 ~ 1001а 1001Ь = => 100с9 ~ 10с99 => 1с999 ~ 0999.
е) 240 ~ а240 ~ 2а40 ~ 24аО ~ 240а => 240Ь ~ 24с8 => 238. 14.26. Сконструируйте нормальные алгоритмы, вычисляющие функции: а) /;(х) = х+ 5; б) Я~(х) = х — 5; в),7'(х) = х + 7; г) 7;(х) = = х — 7. Пользуйтесь при этом трехэлементным расширением В = = А ~з (а, Ь, с» основного (цифрового) алфавита А = (О, 1, 2, ..., 9». 14.27. Сконструируйте нормальный алгоритм, вычисляющий функцию 7(х) = 10х. У к а з а н и е. Можно обойтись одноэлементным расширением В = А н (а» основного алфавита А.
Его начало должно быть таким же, как и у алгоритмов задач 14.23 — 14.25. После того как мы пришли к слову эа, нужно каждое подслово вида 7га, где Ь е А, заменить на подслово хО. 14.28. Составьте нормальный алгоритм в трехэлементном расширении В = А ~ (а, Ь, с» основного алфавита А, вычисляющий функцию 7(х) = 2х. Решение.
Его начало такое же, как и у алгоритмов задач 14.23 — 14.25. После перехода и => аа ~ ша ~ шЬ (первые два столбца подстановок в задаче 14.25) нужно приступить к поразрядному умножению на 2. Для цифр О, 1, 2, 3, 4 это выглядит так: ОЬ -+ ЬО, 1Ь -+ Ь2, 2Ь -+ Ь4, ЗЬ -+ Ьб, 4Ь -+ Ь8. При удвоении остальных цифр приходится единицу переносить в следующий разряд.
Для запоминания этого применяется дополнительная буква с расширенного алфавита: 5Ь -+ сО, 6Ь -+ с2, 7Ь -+ с4, 8Ь -+ сб, 9Ь -+ с8. Если мы к следующему разряду подошли с буквой Ь, то в нем происходят только что описанные замены. Если же мы подошли с буквой с, то там выполняются следующие подстановки: Ос -~ Ы, 1с -+ ЬЗ, 2с †> Ь5, Зс -+ Ь7, 4с -+ Ь9, 5с -+ с1, бс -+ сЗ, 7с -+ с5, 8с -+ с7, 9с -+ с9.
После того как мы добрались от младшего разряда перерабатываемого числа до старшего, должен произойти останов. Если мы вышли за число с буквой Ь, то выполняется заюпочительная подстановка Ь -+ . Л. Если мы вышли с буквой с, то выполняется заключительная подстановка с -+ . 1. Например, а) 24 => а24 ~ 2д4 ~ 24а ~ 24Ь ~ 2Ь8 ~ Ь48 ~ 48; б) 39 => а39 ~ За9 ~ 39а => 39Ь ~ Зс8 =~ Ь78 ~ 78; в) 85 ~ а85 ~ => 8а5 ~ 85а =~ 85Ь => 8сО ~ с70 => 170. 14.29. Сконструируйте нормальный алгоритм в четырехэлементном расширении В= А н (а, Ь, с, В» основного алфавита А, вычисляющий функцию 7(х) = Зх. ОТВКтЫ $1 1. Высказываниями являются предложения: а), г), е), к), н), п), р).
2. Истинные высказывания: а), е), н). Отметим здесь сразу же, что вопросы о том, является или нет то или иное предложение высказыванием и является ли данное высказывание истинным или ложным, не относится к сфере математической логики, а лежит за ее пределами, в сферах тех наук и явлений, о которых собственно повествуют данные предложения. 3. а) Волга не впадает в Каспийское море; б) 28 делится на 7; в) 6 < 3; г) 4 > 5; д) Не все простые числа нечетны; е) Г2 иррациональное число; ж) Сумма 5 + 3 не равна 8; з) Африка— не остров; и) Не все слова можно разделить на слоги; к) — некоторые грибы съедобны.
4. Отрицаниями друг друга являются высказывания в парах б), г), ж), з), и). 5. Истинны высказывания а), в), г), е), ж), з), к). б. Истинны высказывания А, В, 1, 1; высказывания С и Н могут быть любыми, остальные — ложны. 7. а) (а~О)л(Ь~О); б) (а =0) ~ (Ь= 0); в) (а=О) л(Ь=О); г) ((а > 0) л (Ь > 0)) ч ((а < 0) л (Ь < 0)); д) (а=-3) ч(а=3); е) (а>-3) л(а< 3); ж)(а<-3) ч(а>3); з) (а~ О) ч (Ь~ 0); и) (а~О) л (Ь~О); к) (а=О) ч(Ь=О).
8. Истинны высказывания В, С, Е, Н; 1, К; высказывание У может быть любым; остальные — ложны. 9. Истинны высказывания а), б), в), д), е). 10. Истинны высказывания А, О, Е, б, Н, Х 11. Ложны высказывания а), з), и). 12. а) Этот треугольник не равнобедренный и не равносторонний; б) неверно, что треугольник либо равнобедренный, либо равносторонний; д) тогда и только тогда неверно, что треуголь- 257 ник равнобедренный и равносторонний, когда он не равносторонний. 13. а) Если это число целое или положительное, то оно не является простым; з) это число либо целое, либо положительное и одновременно либо простое, либо делящееся на 3.
14. а) (А л -чВ) -+ -зС; е) (А л -тС) -+ -зВ; б) А++ (В ч Сч Р); ж) (В л ~С) -+ тА; в) (А л В) -+ С; з) (А ч Вч С) -+ Р; г) (АлВлС)-+Р; и)(АчВ)-+С; д) (А л В) -+ С; к) (-зАч-зВ)-ь1~Сч-зР). 15.а) А л Вл С; б)АчВчС; в) ~А л ~В л -т С; г) тАч-зВч-зС; д) (А л В л ~С) ч (А л В л С); е) (-~А л ~В л С) ч (-~А л -тВ л-~С); ж) (-зА ч -тВ ч С) л (~А ч ~В ч -~ С); з) (А ч В ч -т С) л (А ч В ч С); и) (А л В л С) ч (зА л тВ л ч С); к) (А ч В ч С) л (-чА ч тВ ч т С). 16. Истинны последние высказывания б), в), г), е), з). 17.
Истинны высказывания б), в), д), з), и); ложны высказывания а), е); могут быть как истинными так и ложными г), ж), к). 18. Ни в одном из случаев трех таких высказываний не существует. 19. Истинны высказывания б), в), г), е), и); можно а). 22. Формулами являются в), е). 23. Число способов: а) 8; б) 12; в) 5; г) 9; д) 10; е) 10; ж) 7; з) 19; и) 14; к) 22. 24. Число подформул, включая данную формулу: а) 11; б) 8; в) 9; г) 7; д) 8; е) 8; ж) 11; з) 11; и) 7; к) 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
