Основы информатики. 7 страница

Разряды

Число

Разряды

Число

Разряды

Число

Разряды

Число

Разряды

Число

Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр).

Например:

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

Например,

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

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

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

Пример: Перевести число 0,35 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:

ВСТАВИТЬ!!!!!!!!!!!!!!!!!!!!!!!!

В двоичную

В восьмеричную

В шестнадцатеричную

Ответ: 0,3510 = 0,010112 = 0,2638 = 0,5916.

Арифметические операции в позиционных системах счисления.

Сложение

Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны — это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем другим позиционным системам счисления.

Сложение в двоичной системе

Сложение в восьмеричной системе

Сложение в шестнадцатеричной системе

При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.

Пример 1. Сложим числа 15 и 6 в различных системах счисления.

Шестнадцатеричная: F16+616

Вычитание

При вычитании цифры вычитаются по разрядам, и если при этом возникает недостаток, то происходит заем в старших разрядах.

Пример. Вычтем единицу из чисел 102, 108 и 1016

Пример. Вычтем число 59,75 из числа 201,25.

Ответ: 201,2510 – 59,7510 = 141,510 = 10001101,12 = 215,48 = 8D,816.

Умножение

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

Умножение в двоичной системе

Умножение в восьмеричной системе

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

Пример. Перемножим числа 5 и 6.

Ответ: 5*6 = 3010 = 111102 = 368.

Проверка. Преобразуем полученные произведения к десятичному виду:

111102 = 24 + 23 + 22 + 21 = 30;

368 = 3•81 + 6•80 = 30.

Деление

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

Пример 1. Разделим число 30 на число 6.

Ответ: 30: 6 = 510 = 1012 = 58.

Пример 2. Разделим число 5865 на число 115.

Восьмеричная: 133518:1638

Ответ: 5865: 115 = 5110 = 1100112 = 638.

Проверка. Преобразуем полученные частные к десятичному виду:

1100112 = 25 + 24 + 21 + 20 = 51; 638 = 6*81 + 3*80 = 51.

Представление чисел в ПК.

Целые числа могут представляться в компьютере со знаком или без знака.

Целые числа без знака обычно занимают в памяти один или два байта и принимают в однобайтовом формате значения от 000000002 до 111111112, а в двухбайтовом формате — от 00000000 000000002 до 11111111 111111112.

Целые числа со знаком обычно занимают в памяти компьютера один, два или четыре байта, при этом самый левый (старший) разряд содержит информацию о знаке числа. Знак “плюс” кодируется нулем, а “минус” — единицей.

В компьютерной технике применяются три формы записи (кодирования) целых чисел со знаком: прямой код, обратный код, дополнительный код.

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

Положительные числа в прямом, обратном и дополнительном кодах изображаются одинаково — двоичными кодами с цифрой 0 в знаковом разряде. Например:

2 ПРИМЕРА

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

Выполнение арифметических действий в компьютере

В большинстве компьютеров операция вычитания не используется. Вместо нее производится сложение уменьшаемого с обратным или дополнительным кодом вычитаемого. Это позволяет существенно упростить конструкцию АЛУ.

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

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

Умножение и деление

Во многих компьютерах умножение производится как последовательность сложений и сдвигов. Для этого в АЛУ имеется регистр, называемый накапливающим сумматором, который до начала выполнения операции содержит число ноль. В процессе выполнения операции в нем поочередно размещаются множимое и результаты промежуточных сложений, а по завершении операции — окончательный результат.

Другой регистр АЛУ, участвующий в выполнении этой операции, вначале содержит множитель. Затем по мере выполнения сложений содержащееся в нем число уменьшается, пока не достигнет нулевого значения.

Для иллюстрации умножим 1100112 на 1011012.

Деление для компьютера является трудной операцией. Обычно оно реализуется путем многократного прибавления к делимому дополнительного кода делителя.

Представление текстовой информации в ПК.

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

Для кодирования одного символа используется количество информации, равное одному байту, т.е. I = 1 байт = 8 бит.

Если рассматривать символы как возможное событие, то можно вычислить, какое количество различных символов можно закодировать:

N = 2I = 28 = 256.

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

Кодирование заключается в том что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код 00000000 до 11111111.Таким образом человек различает символы по их начертанию, а компьютер по их коду.

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

В процессе вывода символа на экран происходит обратный процесс – преобразование кода символа в его изображение.

Существует соглашение которое фиксируется в кодовой таблице (ASCII). Первые 33 кода (0..32) обозначают операции перевод строки, ввод пробела и т.д.

Коды 33..127 – интернациональные и соответствуют символам латинского алфавита, цифрам, знакам арифметических операций и знакам препинания.

Коды 128..255 являются национальными, предназначены для кодировки национальных алфавитов, символов псевдографики и т.д.

Алгебра логики.

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”, “если..., то”, “тогда и только тогда” и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Существуют три основные логические операции: отрицания (операция, выражаемая словом “не”), дизъюнкции (операция, выражаемая связкой “или”) и конъюнкции (операция, выражаемая связкой “и”).

Отрицание (инверсия). Инверсия высказывания истина, когда само высказывание ложно, и ложно, когда высказывание истинно.

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

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

Существуют и другие логические операции.

Операция, выражаемая связками “если..., то”, “из... следует”, “... влечет...”, называется импликацией (лат. implico — тесно связаны) и обозначается знаком.

Высказывание А В ложно тогда и только тогда, когда А истинно, а В — ложно.

Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”, “... равносильно...”, называется эквиваленцией или двойной импликацией и обозначается знаком или ~. Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают.

Импликацию можно выразить через дизъюнкцию и отрицание:

А В = v В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А В = (v В) • (v А).

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (“не”), затем конъюнкция (“и”), после конъюнкции — дизъюнкция (“или”) и в последнюю очередь — импликация.

Логическая формула.

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

Определение логической формулы:

1. Всякая логическая переменная и символы “истина” (“1”) и “ложь” (“0”) — формулы.

2. Если А и В — формулы, то, (А • В), (А v В), (А B), (А В) — формулы.

3. Никаких других формул в алгебре логики нет.

Некоторые формулы принимают значение “истина” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно истинными формулами или тавтологиями.

Некоторые формулы принимают значение “ложно” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно ложными формулами или противоречиями.

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

Связь между алгеброй логики и двоичным кодированием

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Из этого следует два вывода:

1. одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;

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

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

Элементы математической логики. Законы логики. Упрощение логических формул.

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

Наиболее известный базис — это набор функций И, ИЛИ, НЕ. Функция штрих Шеффера является базисной, также как и функция стрелка Пирса. Поэтому, с помощью логических элементов ИЛИ-НЕ или И-НЕ можно собрать любую логическую схему. На таких элементах собран микропроцессор компьютера и другие логические устройства. Логические схемы состоят из логических элементов, осуществляющих логические операции.

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

Математическая логика — современная форма логики, опирающаяся на формальные математические методы.

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

В языках программирования QBasic и Turbo Pascal логические функции И, ИЛИ, НЕ реализуются в виде логических операций OR (ИЛИ), AND (И), NOT (НЕ).

Множество всех логических функций, на котором определены три логические операции И, ИЛИ, НЕ называется булевой алгеброй (по имени основоположника математической логики английского математика Джорджа Буля). Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на следующие основные законы (эквивалентные соотношения):

Кроме того, применяются ещё три соотношения:

Законы 1,2,3,7 показывают, что свойства конъюнкции очень похожи на свойства умножения, поэтому её часто называют логическим умножением. Из законов 6 и 8 следует, что используя отрицание, дизъюнкцию можно выразить через конъюнкцию, и наоборот:

Это означает, что наборы И-НЕ и ИЛИ-НЕ также являются функционально полными или базисными.

Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.

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

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

При упрощении используется закон идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания.

Логические элементы и логические функции.

Логическая функция — это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

Логический элемент — это устройство, реализующее ту или иную логическую функцию. Y=f(X1,X2,X3,...,Xn) — логическая функция, она может быть задана таблицей, которая называется таблицей истинности.

Число строк в таблице — это число возможных наборов значений аргументов. Оно равно 2n, где n — число переменных. Число различных функций n переменных равно 22^n.

Логические функции одной переменной

Таблица истинности функции одной переменной Y=f(X) содержит всего 2 строки, а число функций одной переменной равно 4.

1. Функция константа 0, Y=0. Техническая реализация этой функции — соединение вывода Y с общей шиной с нулевым потенциалом. Таблица истинности функции константа 0 имеет вид:

???

2. Функция Y=f(X)=X — функция повторения. Техническая реализация этой функции — соединение между собой выводов X и Y.

Таблица истинности функции повторения имеет вид:

???

3. Функция Y=f(X)=NOT(X) — отрицание НЕ или инверсия (NOT(X) — это НЕ X). Техническая реализация этой функции - инвертор на любом транзисторе или логическом элементе, или транзисторный ключ.

???

Таблица истинности функции отрицания имеет вид:

????

Логический элемент НЕ обозначается на схемах следующим образом:

????

пишется X c чертой сверху

4.Функция константа 1, Y=1. Техническая реализация этой функции — соединение вывода Y с источником питания.

Таблица истинности функции константа 1 имеет вид:

???

Важнейшей функцией одной переменной является отрицание НЕ, остальные функции являются тривиальными.

Логические функции двух переменных

Таблица истинности функции двух переменных Y=f(X1,Х2) содержит 4 строки, а число функций двух переменных равно 16.

Рассмотрим только несколько основных функций двух переменных.

1. Логическое ИЛИ (логическое сложение, дизъюнкция):

Y= X1 + X2 = X1VX2

Техническая реализация этой функции — два параллельно соединенных ключа:

????

Таблица истинности логического ИЛИ имеет вид:

????

Логический элемент ИЛИ обозначается на схемах следующим образом:

???

2. Логическое И (логическое умножение, конъюнкция, схема совпадений): Y = X1X2 = X1&X2

Техническая реализация этой функции — два последовательно соединенных ключа:

???

Таблица истинности логического И имеет вид:

???

Логический элемент И обозначается на схемах следующим образом:

??

3. Функция стрелка Пирса (ИЛИ-НЕ): Y = NOT(X1+X2)

Таблица истинности функции ИЛИ-НЕ имеет вид:

???

Логический элемент ИЛИ-НЕ обозначается на схемах следующим образом:

????

Функция штрих Шеффера (И-НЕ): Y = X1|X2 = NOT(X1X2)

Таблица истинности функции И-НЕ имеет вид:

???

Логический элемент И-НЕ обозначается на схемах следующим образом:

???

Есть ещё три логические функции двух переменных, имеющие специальные названия: импликация, эквивалентность, неравнозначность (исключающее ИЛИ, сложение по модулю 2). Последние две функции являются взаимно обратными, также как, например, функция И и функция штрих Шеффера.

Элемент памяти триггер. Сумматор.

Триггер — это логическое устройство, способное хранить 1 бит информации. К триггерам относятся устройства, имеющие два устойчивых состояния. Простейший триггер — RS-триггер, образован из двух элементов И-НЕ (или ИЛИ-НЕ). Он позволяет запоминать 1 бит информации, поскольку информация в компьютере представляется в двоичном виде.

Cхема RS-триггера

???

Действие RS-триггера поясняется в приведенной ниже таблице истинности. S-вход установки (Set), R-вход сброса (Reset).

???

В обычном (исходном) состоянии на входы триггера поданы 1. Для записи информации на вход R подан 0. Для сброса информации и подготовки к приёму новой информации на вход S подается 0 и триггер вернётся в исходное состояние.

Поскольку один триггер запоминает 1 бит информации, то для запоминания 1 байта (8 бит) нужно 8 триггеров, для запоминания 1 Кб (1024 байт) надо 8192 триггеров. Современные микросхемы ОЗУ способны запоминать десятки мегабайт информации

Сумматор

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

Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел.

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

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

Условное обозначение одноразрядного сумматора

??

При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами:

1. цифра ai первого слагаемого;

2. цифра bi второго слагаемого;

3. перенос pi–1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра ci для суммы;

2. перенос pi из данного разряда в старший.

Таким образом, одноразрядный двоичный сумматор есть устройство с тремя входами и двумя выходами.

Если требуется складывать двоичные слова длиной два и более бит, то можно использовать последовательное соединение таких сумматоров, причём для двух соседних сумматоров выход переноса одного сумматора является входом для другого.

Функциональные схемы. Таблицы истинности.

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

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

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

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

Задача нахождения среди равносильных схем наиболее простых является очень важной.

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

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

Чтобы составить таблицу истинности для логической формулы надо выполнить следующие шаги:

1. Определить количество входных наборов значений переменных по формуле Q=2n, где n-количество входных переменных, для двух переменных Q=4. для трех Q=8 и т.д.

2. Определить порядок выполнения операций в формуле.

3. Найти значения промежуточных формул и конечного результата.

Таблица истинности для формулы??? (Q=8):

?????

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

Моделирование как метод научного познания. Классификация моделей.

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

Например, открытие кислорода стало возможным благодаря опытам по сгоранию некоторых веществ, а сконструированные модели летательных аппаратов Циолковским привело к созданию космических кораблей и спутников, которые были выведены на орбиту Земли в середине 20 века.

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

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

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

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

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

Модели классифицируются по: области применения (научные, учебные, опытные, деловые игры и т.д.), временному фактору (динамические, статические), способу представления (материальные, информационные).

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

Модели знаковые (информационные) представляют объекты и процессы в форме рисунков, схем, таблиц, текстов и т.д. Информационные модели в свою очередь бывают компьютерные и некомпьютерные.

Модели — представления объектов или процессов реального или вымышленного мира.

Виды моделей: графические представления, натурные, математические, информационно-логические и т.п.

Графические представления — графические изображения объектов и процессов.

Свойства моделей: адекватность, полнота, детальность и т.п.

Адекватность — степень соответствия модели представляемым объектам.

Математические модели — математические описания объектов, выражаемые с помощью математических формул и уравнений.

Математическая модель — это совокупность математических объектов (данных) и отношений между ними, отражающих некоторые свойства моделируемого процесса.

Математическая модель — это система уравнений и неравенств, описывающих поведение объекта с некоторой степенью точности. На основе словесной формулировки задачи, выбираются входные и выходные переменные, записываются ограничения, образующие в совокупности математическую модель решаемой задачи.

Информационно-логические модели — формальные описания объектов, допускающие их представление и обработку на ЭВМ.

Модели движения бывают аналитические, дифференциальные, разностные.

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