Разработка алгоритма вычисления квадратного корня

Вычисление квадратного корня производится путем деления исходного числа на переменный делитель [14]. Первое значение переменного делителя равно 0,01, следующие значения формируются путем приписывания пары цифр 01 к уже найденному числу.

Для нахождения результата нужно выполнить (n-2) цикла, каждый из которых может содержать три такта:

1) из значения на сумматоре вычитается содержимое переменного делителя (РгД) и определяется очередная цифра результата, которая равна инверсии знака сумматора;

2) если после выполнения вычитания сумматор меньше нуля, то нужно выполнить восстановление сумматора путем сложения его с содержимым переменного делителя;

3) производится сдвиг содержимого сумматора на один разряд влево и формируется новый переменный делитель.

Нужно помнить, что из отрицательных чисел корень не вычисляется.

Схема алгоритма извлечения квадратного корня в соответствии с описанным алгоритмом изображена на рис. 4.7.

с анализом двух разрядов делителя

Рис. 4.6. Схема алгоритма ускоренного деления с анализом двух разрядов делителя (окончание)

Рис. 4.7. Схема алгоритма вычисления квадратного корня

Буквами y_i обозначены разряды регистра результата (РгР). Начальное значение счетчика во всех алгоритмах принимается равным (n-2), где n – число разрядов исходных чисел, так как используются модифицированные коды.

Рассмотрим пример для операции вычисления квадратного корня для числа с фиксированной запятой. Извлечем квадратный корень из числа А = 0,101111 по разработанному алгоритму.

См = 0,101111 РгР = 0 (регистр результата)

⁺ 1,110000 РгД = 0,01 (переменный делитель)

I 1) См= См-РгД = 0,011111 РгР = 0,1 (так как См>0)

3) См = См← = 0,111110 РгД = 0,101

⁺ 1,011000

II 1) См= См-РгД = 0,010110 РгР = 0,11 (См>0)

3) См = См← = 0,101100 РгД = 0,1101

⁺ 1,001100

III 1) См= См-РгД = 1,111000 РгР = 0,110 (так как См<0)

⁺ 0,110100

2) См=См+РгД = 0,101100

3) См = См← = 1,011000 РгД = 0,11001

⁺ 1,001110

IV 1) См= См-РгД = 0,100110 РгР = 0,1101 (так как См>0)

3) См = См← = 1,001100 РгД = 0,110101

⁺ 1,001011

V 1) См= См-РгД = 0,010111 РгР = 0,11011 (так как См>0)

3) См = См← = 0,101110 РгД = 0,1101101

⁺ 1,0010011

VI 1) См= См-РгД = 0,010111 РгР = 0,110110 (так как См<0)

В циклах I, II, IV и V пропущен второй такт, потому что сумматор положителен и восстановление остатка не требуется.

Ответ: В = = 0,110110, что соответствует результату, полученному при извлечении корня из числа А программой «Операции».

В настоящей главе проанализирована часть алгоритмов реализации программных моделей операций, изучаемых в курсе «Дискретная математика». Приведены схемы алгоритмов перевода чисел из одной позиционной системы счисления в другую, а также для выполнения арифметических операций сложения (вычитания), умножения, деления и вычисления квадратного корня для двоичных чисел, в том числе и ускоренные методы умножения и деления. Таким же образом можно проектировать любые алгоритмы выполнения операций, описанных в теоретических главах 2 и 3.

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ

Соответствия и предикаты

Соответствия

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

Определение 1. Пусть и произвольные множества.Соответствием называется тройка множеств

y d

d

c c

a Ob x a O b x

Рис. 5.1. Функция Рис. 5.2. Инъекция

y

d

c

a O b x

Рис. 5.3. Общий случай соответствия

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

Итак, любое соответствие имеет обратное. Однако не любая функция будет иметь обратную функцию. Функция будет иметь обратную только тогда, когда она одновременно и инъекция. При возведении закона в степень –1 свойства инъективности и однозначности взаимно заменяются. Поэтому для любой функции обратным соответствием будет инъекция и, обратно, обратным соответствием для любой инъекции будет функция.

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

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

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

, (5.2)

где

- знак операции композиции;

- знак операции умножения двух двоичных матриц;

- закон соответствия , заданный двоичной матрицей*;

- закон соответствия , заданный двоичной матрицей.

Это новое соответствие будет устанавливать связь уже между множествами и . Например, если - соответствие, определяющее распределение водителей по автобусам , а - соответствие, определяющее распределение автобусов по маршрутам , то соответствие определит распределение водителей по маршрутам .

Пример 5.2. Рассмотрим соответствие p между временем года и характеристикой погоды, качественно выражающей температуру в умеренных широтах.

Y={зима, весна, лето, осень}; W={тепло, холодно, неопределенно}; P={(зима, холодно), (весна, неопределенно), (лето, тепло), (осень, неопределенно)}.

Очевидно, что соответствие из примера 5.1 совместно с данным соответствием образует композицию, позволяющую определить характеристику месяца.

Вопросы для самоконтроля

1. Определите свойства и тип соответствия, которое задается списком дат знаменательных событий.

2. Будет ли соответствие, которое задает шахматная позиция (между - шахматными фигурами и - полями шахматной доски), функцией?

3. Определите области определения и значений для функции

.

5.1.2. Логические функции

Понятие функции в самом широком смысле уже дано в п. 5.1.1. Рассматриваемые в школьном курсе алгебры, а затем и в высшей математике действительные функции действительных переменных, суть частные случаи функциональных соответствий. Называются они так потому, что их областью отправления всегда является множество ( здесь – число переменных, от которых зависит функция; =1, 2, …), а областью прибытия – множество действительных чисел.

Ниже рассмотрим случаи, когда множества, между которыми установлены функциональные соответствия, состоят из элементов, в общем случае не связанных с какими-нибудь числами. Такие соответствия получили название логических функций.

При изучении логических функций будем полагать, что их области отправления и прибытия суть абстрактные множества. При этом нас не будет интересовать конкретное содержание этих множеств – физическая природа их элементов. Чтобы различать такие элементы между собой, припишем каждому из них свой символ (или номер). Тогда область отправления логической функции будет представлена алфавитом, содержащим все эти символы, а некоторый иной символ, не принадлежащий данному алфавиту, будет называться логической переменной, если его можно заменять некоторыми из символов области отправления. Каждому из таких символов однозначным образом по заданному закону поставлен в соответствие единственный символ из области прибытия, а вся их совокупность образует область определения логической функции.

В самом общем случае алфавиты логических переменных, от которых зависит логическая функция, могут не совпадать. Тогда областью отправления будет являться прямое произведение этих алфавитов, а областью прибытия – какой-либо свой алфавит, который, в частности, может и совпасть с областью изменения одной из переменных. Когда алфавиты функций и переменных совпадают, над логическими функциями становится возможной операция композиции (операция «функция от функции»), с помощью которой из ограниченного набора простейших (базовых) логических функций можно получить все остальные логические функции.

Определение 2. Логическая функция от переменных ( =0, 1, 2, …) называется -местным предикатом, а ее переменные называются вхождениями. Нульместный предикат ( =0) называют высказыванием; одноместный предикат

( = 1) называют признаком или свойством; - местный предикат, имеющий не менее двух вхождений ( ), называют отношением.

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

Вопросы для самоконтроля

1. Назовите основные отличия логических функций от основных элементарных функций, изучаемых в школе.

2. Приведите примеры логических переменных.

5.1.3. Признаки

Признак (свойство) - это функциональное соответствие вида

, где . (5.3)

Рассмотренный пример 5.1 как раз определяет свойства, принадлежность какого-либо месяца к определенному времени года может рассматриваться как его (месяца) свойство.

Заданная таким образом тройка множеств , где , определяет некоторое соответствие между названиями месяцев и названиями времени года. Данное соответствие будет функцией, поскольку каждый из месяцев относится только к одному времени года. Тем самым задана логическая функция одной переменной (или свойство) вида у = SEASON(x), определяющая время года, соответствующее месяцу. Например, с учетом закона соответствия

SEASON(январь)= SEASON(февраль)= SEASON(декабрь)=зима;

SEASON(март)= SEASON(апрель)= SEASON(май)=весна;

SEASON(июнь)= SEASON(июль)= SEASON(август)=лето;

SEASON(сентябрь)= SEASON(октябрь)= SEASON(ноябрь)=осень.

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

Данная логическая функция разбивает множество месяцев на четыре множества. Множества {январь, февраль, декабрь} зимних, {март, апрель, май} весенних, {июнь, июль, август} летних и {сентябрь, октябрь, ноябрь} осенних месяцев попарно не пересекаются, а их объединение равно - области определения этой логической функции, т.е.

{январь, февраль, декабрь} {март, апрель, май} {январь, февраль, декабрь} {июнь, июль, август} {январь, февраль, декабрь} {сентябрь, октябрь, ноябрь} {март, апрель, май} {июнь, июль, август}, {март, апрель, май} {сентябрь, октябрь, ноябрь}, {июнь, июль, август} {сентябрь, октябрь, ноябрь} и {январь, февраль, декабрь} {март, апрель, май} {июнь, июль, август} {сентябрь, октябрь, ноябрь} .

Следовательно, данная функция - это разбиение. И для любой другой логической функции это также справедливо.

Замечание 1. Всякая логическая функция задает разбиение своей области определения на попарно непересекающиеся подмножества, где - число элементов в ее области значений. Это следует из того, что, во-первых, объединение всех прообразов всегда будет являться областью значений в любом соответствии, а, во-вторых, условие того, что прообразы функционального соответствия попарно не пересекаются, вытекает из свойства однозначности.

Замечание 2. Справедливо и обратное. Если задано разбиение некоторого множества на попарно непересекающиеся классы, то это разбиение задает закон соответствия между множествами и , где - множество номеров классов разбиения, который является логической функцией с областями отправления и прибытия.

Замечание 3. Если логическая функция всюду определена, то замечание 1 справедливо и для ее области отправления , т.к. последняя в этом случае совпадает с ее областью определения . В противном случае ( ) область отправления разобьется функцией на частей, т.е. область будет включать в себя дополнительно еще одно подмножество , которое называют областью неопределенности. Например, если в законе соответствия исключить хотя бы одну пару, допустим пару (июнь, лето), то информация о том, к какому времени года относится июнь, будет утрачена и элемент июнь попадет в область неопределенности, т.е. при значении x=июнь полученная функция будет не определена.

Замечание 4. При замене вхождения в свойстве (одноместном предикате) конкретным значением получается нульместный предикат. Иначе говоря, свойство (признак) при конкретном значении переменной превращается в высказывание. Под высказыванием обычно понимают повествовательное предложение, которое может быть либо истинным, либо ложным. Например, SEASON(июнь)=лето, т.е. июнь - летний месяц есть истинное высказывание.

Замечание 5. В примере 5.1 была рассмотрена четырехзначная логическая функция – ее область прибытия (а также и область значений) состояла из четырех элементов. Однако многозначную логическую функцию всегда можно заменить двузначными. В частности, функцию из примера 5.1 можно заменить четырьмя такими , которые могут принимать только два значения ДА или НЕТ (истинно или ложно).

Замечание 6.Всюду определенные логические функции двузначной логики разбивают свою область отправления на две части – область истинности и область ложности. Например, признак для названий месяцев разделит всё множество месяцев на два подмножества {январь, февраль, декабрь} - область истинности и {март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь} - область ложности. Однако для не всюду определенной логической функции к этим областям еще добавится область неопределенности (см. замечание 3).

Вопросы для самоконтроля

1. Определите область истинности функций , , , которые определены на множестве названий месяцев.

2. Составьте соответствие, определяющее цвет граней некоторого заданного

куба. Будет ли функция COLOR(g) , задающая цвет грани куба, свойством?

5.1.4. Бинарные отношения

Бинарные отношения и способы их задания

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

Иначе говоря, бинарное отношение – это однозначное соответствие вида

, (5.4)

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

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

, (5.5)

а область ложности – соответственно выражением

. (5.6)

Из (5.5) и (5.6) следует, что и , а когда бинарное отношение всюду определено ( ), то . Иначе говоря, всюду (не всюду) определенное бинарное отношение задано тогда, когда задан алфавит для независимых переменных и (а также область ложности или область определения , или область неопределенности ) и область истинности .

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

, , (5.7)

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

(5.8)

Задать область можно, кроме простого перечисления ее элементов, квадратной двузначной матрицей размерностью , т.е. таблицей вида

Каждый элемент данной матрицы равен либо нулю, либо единице. При этом если элемент , то пара , и (т.е. ), если .

Пример 5.3. Пусть на множестве задано отношение с областью истинности . Тогда данное отношение можно задать следующей матрицей:

. (5.9)

Каков смысл данного отношения? Его область истинности составляют все те, и только те пары, в которых первая компонента меньше второй. Следовательно, матрица (5.9) задает на числах 1, 2, 3 и 4 отношение «меньше».

Замечание 1.В данном примере область истинности отношения и двоичная матрица, которая эту область определяет, обозначены одним и тем же символом. С целью упрощения наших обозначений условимся еще и знак самого отношения обозначать тем же символом . Ранее имя отношения у нас обозначалось буквой . Теперь мы и его станем обозначать буквой . При этом совершенно равнозначными будут следующие условия:

, , , .

Здесь во втором условии под символом подразумевается множество пар (область истинности), в четвертом этот символ означает знак отношения между двумя элементами (аналогично тому, когда пишут ), а третье условие указывает на то, что в -й строке -го столбца матрицы стоит единица. Также равнозначными являются и такие условия:

, , , , или .

В третьем условии обозначение определяет область ложности (5.6), т.е. множество пар , а в пятом – знак отношения, у которого областью истинности является область ложности отношения . Шестое условие – это отрицание условия (в математическом языке знак отрицания условия может совпадать со знаком дополнения множества).

Не нашли, что искали? Воспользуйтесь поиском по сайту: