Математические основы информатики

Математические основы информатики

8 класс

Тихонова Вера Константиновна, учитель информатики

Содержание:

• Системы счисления
• Представление чисел в компьютере
• Введение в алгебру логики

Системы счисления

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

А.П.Стахов

Какие системы счисления рассматриваются математиками и инженерами в качестве «компьютерных»? Какими свойствами должна обладать система счисления, при помощи которой будет кодироваться информация в компьютерных системах? Наша задача – рассмотреть принципы построения позиционных систем счисления, используемыми в компьютерах .

Позиционные системы счисления

Система счисления или нумерация – это способ записи чисел.

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

Система счисления называется позиционной , если количественный эквивалент цифры зависит от ее положения (позиции)в записи числа. Например, 5555=5*1000+5*100+5*10+5*1

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

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

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

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

Система счисления

Основание

Десятичная

10

Размерность алфавита

Двоичная

Цифры

10

2

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

8

0,1,2,3,4,5,6,7,8,9

Шестнадцатеричная

2

8

0, 1

16

0,1,2,3,4,5,6,7

16

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

Основанием P-ичной системы счисления может быть любое натуральное число, большее единицы. Минимальной системой счисления является двоичная, в которой все числа записываются с помощью 0 и 1.

Представление произвольных чисел в позиционных системах счисления

• Любое число может быть записано в виде суммы степеней числа P, где P – натуральное число, больше 1. Вместе с тем, если мы в качестве базиса позиционной системы счисления возьмем возрастающую последовательность степеней числа P и тем самым определим P–ичную систему счисления, то это разложение по степеням числа P будет являться представлением данного числа в P-ичной системе счисления .

Развернутая и свернутая формы записи.

• Развернутая форма запись числа используется при решении задач. При использовании развернутой формы для записи числа в P –ичной системе счисления основание P и его степени обычно записывают в десятичной системе, а цифры – в P-ичной. При использовании свернутой формы цифры также записывают в P-ичной системе, а основание P записанное в десятичной системе, приписывают к числу в качестве его нижнего индекса.
• В позиционной системе счисления с основанием qлюбое число может быть представлено в виде: A q =(a n-1 *q n-1 +a n-2 *q n-2 +…. a 0 *q 0 +a -1 *q -1 +…a -m *q -m ) – это развернутая запись числа.
• Свернутой формой записи числа называется его представление в виде:

+a n-1 a n-2 …a 1 a 0 ,a -1 …a -m

Двоичная система счисления

• Двоичной системой счисления называется позиционная система счисления с основанием 2, где для записи чисел используются только 0 и 1.
• Например: 100111 2 =1*2 5 +0*2 4 +0*2 3 +1*2 2 +1*2 1 +1*2 0 =32+4+2+1=39 10
• Отсюда следует правило перевода натуральных двоичных чисел в десятичную систему счисления: необходимо вычислить сумму степеней двойки, соответствующих единицам в свернутой форме записи двоичного числа.
• Для перевода десятичного числа в двоичную систему счисления нужно делить данное число на 2 до тех пор, пока не получим частное, меньше 2, остатки от деления записываем в обратном порядке.
• Например:11 10 =1011 2

Восьмеричная система счисления

• Восьмеричной системой счисления называется позиционная система счисления с основанием 8. Для записи чисел в восьмеричной системе счисления используются цифры: 0,1, 2, 3, 4, 5, 6, 7.
• Например: 1063 8 =1*8 3 +0*8 2 +6*8 1 +3*8 0 =512+48+3=563 10
• Таким образом, для перевода восьмеричного числа в десятичную систему счисления , надо записать его в развернутом виде.
• Для перевода целого десятичного числа в восьмеричную систему счисления следует последовательно делить его на 8 до тех пор, пока не получим частное, меньшее 8, а остатки от деления записываем в обратном порядке.
• Например: 103 10 = 147 8

Шестнадцатеричная система счисления

• Шестнадцатеричной системой счисления называется позиционная система счисления с основанием 16. Для записи чисел в восьмеричной системе счисления используются цифры: 0,1, 2, 3, 4, 5, 6, 7, 8, 9, A (10), B (11), C (12), D (13), E (14), F (15).
• Например: 3AF 16 =3*16 2 +10*16 1 +15*16 0 = 768+160+16=943 10
• Для перевода целого десятичного числа в шестнадцатеричную систему счисления следует последовательно делить его на 16 до тех пор, пока не получим частное, меньшее 16, а остатки от деления записываем в обратном порядке.
• Например: 154 10 =9А 16

Правило перевода целых десятичных чисел в систему счисления с основанием q

• 1. Последовательно выполняем деление данного числа и получаемых целых частных до тех пор, пока не получим частное меньшее, чем основание системы счисления.
• 2. Полученные остатки, являющиеся цифрами числа в новой системе счисления, приводим в соответствие с алфавитом новой системы счисления.
• 3. Составляем число в новой системе счисления, записывая его, начиная с последнего полученного остатка.

Таблица соответствия десятичных, двоичных, восьмеричных и шестнадцатеричных чисел

10-я

2-я

0

0

8-я

1

2

16-я

0

1

10

3

1

0

1

4

2

11

100

3

2

5

3

4

101

6

4

7

5

110

8

111

5

6

6

7

10001

9

10

7

10

1001

11

1010

11

8

9

12

12

1011

13

1100

13

A (10)

B (11)

14

1101

14

C (12)

15

1110

15

D (13)

16

1111

E (14)

17

F (15)

«Компьютерные» системы счисления

• В компьютерной технике используется двоичная система счисления, обеспечивающая ряд преимуществ по сравнению с другими системами счисления:
• двоичные числа представляются в компьютере с помощью простых технических элементов с двумя устойчивыми состояниями;
• представление информации посредством двух состояний надежно и помехоустойчиво;
• двоичная арифметика наиболее проста;
• существует математический аппарат, обеспечивающий логическое преобразование двоичных данных.
• Обмен информацией между компьютерными устройствами осуществляется путем передачи двоичных кодов. Двоичный код удобен для компьютера.
• Человеку неудобно пользоваться длинными и однородными кодами. Специалисты заменяют двоичные коды на величины в восьмеричной или шестнадцатеричной системах счисления. В результате длина исходного кода сокращается в три, четыре раза соответственно. Это делает информацию более удобной для рассмотрения и анализа

Представление чисел в компьютере

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

( n -1)-й разряд

0 –й разряд

ячейка из n разрядов

Представление чисел в компьютере

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

Под целые отводится 8 разрядов, 16 разрядов, 32 разряда или 64 разряда.:

Беззнаковые целые n-разрядные числа. Минимальное значение: во всех разрядах ячейки хранятся нули. Максимальное значение: во всех разрядах ячейки хранятся единицы (2 n –1).

Количество битов

8

Минимальное значение

16

Максимальное значение

0

255 (2 8 – 1)

32

0

64

65 535 (2 16 – 1)

0

4 294 967 295 (2 32 – 1)

0

18 446 744 073 709 551 615 (2 64 – 1)

Представление чисел в компьютере

• Для получение компьютерного представления беззнакового целого числа достаточно перевести число в двоичную систему счисления и дополнить полученный результат слева нулями до стандартной разрядности.
• Например: число 53 10 = 110101 2 в восьмиразрядном представление иметт следующий вид:

• При представлении со знаком самый старший (левый) разряд отводиться под знак числа, остальные разряды – под само число. Если число положительное, то в знаковый разряд помещается 0, если число отрицательное – 1. Такое представление чисел называется прямым кодом. В компьютере прямые коды используются для хранения положительных чисел в запоминающихся устройствах, для выполнения операций с положительными числами. Для выполнения операций с отрицательными числами используется дополнительный код, позволяющий заменить операцию вычитания сложением.

0

0

1

1

0

1

0

1

Представление вещественных чисел

• Любое вещественное число А может быть записано в нормальной (научной, экспоненциальной) форме:
• А =± m  q p , где:
• m - м антисса числа;
• q - основание системы счисления;
• p - порядок числа.

• Например: 472 000 000 может быть представлено так: 47,2*10 7
• Экспоненциальная запись этого числа выглядит так: 4.72Е+8. Знак Е обозначает основание десятичной системы счисления и читается как «умножить на десять в степени». Для единообразия мантиссу обычно записывают как правильную дробь, имеющую после запятой цифру, отличную от нуля, например, как 0,472* 10 9 .
• Широкий диапазон представления вещественных чисел важен для решения научных и инженерных задач. Следует понимать, что алгоритмы обработки таких чисел более трудоемкий по сравнению с алгоритмами обработки целых чисел.

Введение в алгебру логики

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

Понятие высказывания

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

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

Земля вращается вокруг Солнца.

Москва - столица.

Но не всякое повествовательное предложение является высказыванием:

Это высказывание ложное.

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

Без стука не входить!

Откройте учебники.

Ты выучил стихотворение?

Простые и сложные высказывания

Высказывания бывают простые и сложные.

Высказывание называется простым , если никакая его часть сама не является высказыванием.

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

Название логической операции

Конъюнкция

Логическая связка

Дизъюнкция

«и»; «а»; «но»; «хотя»

«или»

Инверсия

«не»; «неверно, что»

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

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

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

Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей ( А = 1 ), а если ложно - нулём ( В = 0 ).

0 и 1 называются логическими значениями .

Логические операции

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

Конъюнкция (логическое умножение)

• Конъюнкция – логическая операция, ставящая в соответствие двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
• Для записи конъюнкции используются следующие знаки:  ,  , & , И.
• Таблица истинности Графическое представление

А

0

В

А&В

0

0

0

1

1

1

0

0

0

1

1

А&В

А

В

Дизъюнкция (логическое сложение)

• Дизъюнкция - логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.
• Обозначения: V, |, ИЛИ, +.
• Таблица истинности Графическое представление

А

0

В

АVВ

0

0

1

0

1

1

0

0

0

1

1

АVВ

Инверсия (логическое отрицание)

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

Другое название: логическое отрицание.

Обозначения: НЕ, ¬ , ¯ .

• Таблица истинности Графическое представление

Ā

А

0

Ā

1

1

0

А

Логические операции имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция .

Построение таблиц истинности

• подсчитать n - число переменных в выражении
• подсчитать общее число логических операций в выражении
• установить последовательность выполнения логических операций
• определить число столбцов в таблице
• заполнить шапку таблицы, включив в неё переменные и операции
• определить число строк в таблице без шапки: m =2 n
• выписать наборы входных переменных

• провести заполнение таблицы по столбцам, выполняя логические

операции в соответствии с установленной последовательностью

Пример заполнения таблицы истинности

А V A & B

n = 2, m = 2 2 = 4 .

Приоритет операций: &, V

A

B

0

A&B

0

0

A V A&B

1

0

1

1

0

0

0

0

0

1

1

1

1

Свойства логических операций (законы алгебры логики)

• Переместительный (коммутативный)закон :

для логического умножения: А&В=В&А

для логического сложения: АVВ=ВVА

• Сочетательный (ассоциативный) закон :

для логического умножения: ( А&В)&С= А&(В&С)

для логического сложения: ( АVВ)VС=АV(ВVС)

• Распределительный (дистрибутивный) закон :

для логического умножения: А&(ВVС)=(А&В)V(А&С)

для логического сложения: АV(В&С) =(АVВ)&(АVС)

• Закон двойного отрицания: ¬¬А=А
• Закон исключенного третьего:

для логического умножения: А&¬А=0

для логического сложения: ( АV¬А=1

Свойства логических операций (законы алгебры логики)

• Закон повторения:

для логического умножения: А&А=А

для логического сложения: АVА=А

• Законы операций с 0 и 1:

для логического умножения: А&0=0; А&1=А

для логического сложения: АV0=А; АV1=1

• Законы общей инверсии:

для логического умножения: ¬ ( А&В)= ¬АV¬В

для логического сложения: ¬ ( АVВ)=¬А&¬В

Законы алгебры логики могут доказаны с помощью таблиц истинности .

Методы решения логических задач

• Формальный способ решения логических задач

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

Логические элементы (схемы)

• Логический элемент – устройство, которое после обработки двоичных сигналов выдаёт значение одной из логических операций.

А

А

&

1

А

В

В

НЕ (инвертор)

И (конъюнктор)

ИЛИ (дизъюнктор)

Источники:

• http://school-collection.edu.ru/catalog/res/9e997f40-f285-4369-aa7d-88b892beca45/?interface=catalog&class=51&subject=19 – Элементарные логические операции
• Математические основы информатики. Учебное пособие., Е.В. Андреева, Л.Л. Босова, И.Н. Фалина
• Информатика, 8 класс, Л.Л. Босова, А.Ю. Босова
• Рабочая тетрадь по информатике, 8 класс, Л.Л. Босова