Кратко математические основы информатики
Обновлено: 05.07.2024
Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются.
Существуют позиционные и непозиционные системы счисления.
В непозиционных системах счисления вес цифры (т. е. тот вклад, который она вносит в значение числа) не зависит от ее позициив записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.
В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая — 7 единиц, а третья — 7 десятых долей единицы.
Сама же запись числа 757,7 означает сокращенную запись выражения
700 + 50 + 7 + 0,7 = 7 . 10 2 + 5 . 10 1 + 7 . 10 0 + 7 . 10 —1 = 757,7.
Любая позиционная система счисления характеризуется своим основанием.
Основание позиционной системы счисления — количество различных цифр, используемых для изображения чисел в данной системе счисления.
За основание системы можно принять любое натуральное число — два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения
где ai — цифры системы счисления; n и m — число целых и дробных разрядов, соответственно.
Например:
Целые числа в позиционных системах счисления.
В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.
Продвижением цифры называют замену её следующей по величине.
Продвинуть цифру 1 значит заменить её на 2, продвинуть цифру 2 значит заменить её на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену её на 0. В двоичной системе, использующей только две цифры — 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 — замену её на 0.
Целые числа в любой системе счисления порождаются с помощью Правила счета:
Для образования целого числа, следующего за любым данным целым числом, нужно продвинуть самую правую цифру числа; если какая-либо цифра после продвижения стала нулем, то нужно продвинуть цифру, стоящую слева от неё.
Применяя это правило, запишем первые десять целых чисел
в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;
в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;
в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;
в восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.
Какие системы счисления используют специалисты для общения с компьютером?
Кроме десятичной широко используются системы с основанием, являющимся целой степенью числа 2, а именно:
двоичная (используются цифры 0, 1);
восьмеричная (используются цифры 0, 1, . 7);
шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, . 9, а для следующих чисел — от десяти до пятнадцати — в качестве цифр используются символы A, B, C, D, E, F).
Полезно запомнить запись в этих системах счисления первых двух десятков целых чисел:
Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления.
Почему люди пользуются десятичной системой, а компьютеры — двоичной?
Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам, а пальцев у людей по десять на руках и ногах. Не всегда и не везде люди пользуются десятичной системой счисления. В Китае, например, долгое время пользовались пятеричной системой счисления.
А компьютеры используют двоичную систему потому, что она имеет ряд преимуществ перед другими системами:
для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток — нет тока, намагничен — не намагничен и т.п.), а не, например, с десятью, — как в десятичной;
представление информации посредством только двух состояний надежно и помехоустойчиво;
возможно применение аппарата булевой алгебры для выполнения логических преобразований информации;
двоичная арифметика намного проще десятичной.
Недостаток двоичной системы — быстрый рост числа разрядов, необходимых для записи чисел.
Почему в компьютерах используются также восьмеричная и шестнадцатеричная системы счисления?
Двоичная система, удобная для компьютеров, для человека неудобна из-за ее громоздкости и непривычной записи.
Перевод чисел из десятичной системы в двоичную и наоборот выполняет машина. Однако, чтобы профессионально использовать компьютер, следует научиться понимать слово машины. Для этого и разработаны восьмеричная и шестнадцатеричная системы.
Числа в этих системах читаются почти так же легко, как десятичные, требуют соответственно в три (восьмеричная) и в четыре (шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (ведь числа 8 и 16 — соответственно, третья и четвертая степени числа 2.).
Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр).
Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой.
Перевод целых чисел из десятичной системы в любую другую позиционную систему счисления.
Для перевода целого десятичного числа N в систему счисления с основанием q необходимо N разделить с остатком ("нацело") на q , записанное в той же десятичной системе. Затем неполное частное, полученное от такого деления, нужно снова разделить с остатком на q , и т.д., пока последнее полученное неполное частное не станет равным нулю. Представлением числа N в новой системе счисления будет последовательность остатков деления, изображенных одной q-ичной цифрой и записанных в порядке, обратном порядку их получения.
Пример: Переведем число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Ответ: 7510 = 1 001 0112 = 1138 = 4B16.
Пеpевод пpавильную десятичную дpобь в любую другую позиционную систему счисления.
Для перевода правильной десятичной дpоби F в систему счисления с основанием q необходимо F умножить на q , записанное в той же десятичной системе, затем дробную часть полученного произведения снова умножить на q, и т. д., до тех пор, пока дpобная часть очередного пpоизведения не станет pавной нулю, либо не будет достигнута требуемая точность изображения числа F в q-ичной системе. Представлением дробной части числа F в новой системе счисления будет последовательность целых частей полученных произведений, записанных в порядке их получения и изображенных одной q-ичной цифрой. Если требуемая точность перевода числа F составляет k знаков после запятой, то предельная абсолютная погрешность при этом равняется q -(k+1) / 2.
Пример. Переведем число 0,36 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Для чисел, имеющих как целую, так и дробную части, перевод из десятичной системы счисления в другую осуществляется отдельно для целой и дробной частей по правилам, указанным выше.
Пеpевод чисел из двоичной (восьмеpичной, шестнадцатеpичной) системы в десятичную.
Перевод в десятичную систему числа x, записанного в q-ичной cистеме счисления (q = 2, 8 или 16) в виде xq = (anan-1 . a0 , a-1 a-2 . a-m)q сводится к вычислению значения многочлена
средствами десятичной арифметики.
Примеpы:
Сводная таблица переводов целых чисел из одной системы счисления в другую
Рассмотрим только те системы счисления, которые применяются в компьютерах — десятичную, двоичную, восьмеричную и шестнадцатеричную. Для определенности возьмем произвольное десятичное число, например 46, и для него выполним все возможные последовательные переводы из одной системы счисления в другую. Порядок переводов определим в соответствии с рисунком:
На этом рисунке использованы следующие обозначения:
в кружках записаны основания систем счисления;
стрелки указывают направление перевода;
номер рядом со стрелкой означает порядковый номер соответствующего примера в сводной таблице 4.1.
Например: означает перевод из двоичной системы в шестнадцатеричную, имеющий в таблице порядковый номер 6.
Сводная таблица переводов целых чисел
Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются.
Существуют позиционные и непозиционные системы счисления.
В непозиционных системах счисления вес цифры (т. е. тот вклад, который она вносит в значение числа) не зависит от ее позициив записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.
В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая — 7 единиц, а третья — 7 десятых долей единицы.
Сама же запись числа 757,7 означает сокращенную запись выражения
700 + 50 + 7 + 0,7 = 7 . 10 2 + 5 . 10 1 + 7 . 10 0 + 7 . 10 —1 = 757,7.
Любая позиционная система счисления характеризуется своим основанием.
Основание позиционной системы счисления — количество различных цифр, используемых для изображения чисел в данной системе счисления.
За основание системы можно принять любое натуральное число — два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения
где ai — цифры системы счисления; n и m — число целых и дробных разрядов, соответственно.
Например:
Целые числа в позиционных системах счисления.
В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.
Продвижением цифры называют замену её следующей по величине.
Продвинуть цифру 1 значит заменить её на 2, продвинуть цифру 2 значит заменить её на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену её на 0. В двоичной системе, использующей только две цифры — 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 — замену её на 0.
Целые числа в любой системе счисления порождаются с помощью Правила счета:
Для образования целого числа, следующего за любым данным целым числом, нужно продвинуть самую правую цифру числа; если какая-либо цифра после продвижения стала нулем, то нужно продвинуть цифру, стоящую слева от неё.
Применяя это правило, запишем первые десять целых чисел
в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;
в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;
в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;
в восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.
Какие системы счисления используют специалисты для общения с компьютером?
Кроме десятичной широко используются системы с основанием, являющимся целой степенью числа 2, а именно:
двоичная (используются цифры 0, 1);
восьмеричная (используются цифры 0, 1, . 7);
шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, . 9, а для следующих чисел — от десяти до пятнадцати — в качестве цифр используются символы A, B, C, D, E, F).
Полезно запомнить запись в этих системах счисления первых двух десятков целых чисел:
Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления.
Почему люди пользуются десятичной системой, а компьютеры — двоичной?
Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам, а пальцев у людей по десять на руках и ногах. Не всегда и не везде люди пользуются десятичной системой счисления. В Китае, например, долгое время пользовались пятеричной системой счисления.
А компьютеры используют двоичную систему потому, что она имеет ряд преимуществ перед другими системами:
для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток — нет тока, намагничен — не намагничен и т.п.), а не, например, с десятью, — как в десятичной;
представление информации посредством только двух состояний надежно и помехоустойчиво;
возможно применение аппарата булевой алгебры для выполнения логических преобразований информации;
двоичная арифметика намного проще десятичной.
Недостаток двоичной системы — быстрый рост числа разрядов, необходимых для записи чисел.
Почему в компьютерах используются также восьмеричная и шестнадцатеричная системы счисления?
Двоичная система, удобная для компьютеров, для человека неудобна из-за ее громоздкости и непривычной записи.
Перевод чисел из десятичной системы в двоичную и наоборот выполняет машина. Однако, чтобы профессионально использовать компьютер, следует научиться понимать слово машины. Для этого и разработаны восьмеричная и шестнадцатеричная системы.
Числа в этих системах читаются почти так же легко, как десятичные, требуют соответственно в три (восьмеричная) и в четыре (шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (ведь числа 8 и 16 — соответственно, третья и четвертая степени числа 2.).
Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр).
Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой.
Перевод целых чисел из десятичной системы в любую другую позиционную систему счисления.
Для перевода целого десятичного числа N в систему счисления с основанием q необходимо N разделить с остатком ("нацело") на q , записанное в той же десятичной системе. Затем неполное частное, полученное от такого деления, нужно снова разделить с остатком на q , и т.д., пока последнее полученное неполное частное не станет равным нулю. Представлением числа N в новой системе счисления будет последовательность остатков деления, изображенных одной q-ичной цифрой и записанных в порядке, обратном порядку их получения.
Пример: Переведем число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Ответ: 7510 = 1 001 0112 = 1138 = 4B16.
Пеpевод пpавильную десятичную дpобь в любую другую позиционную систему счисления.
Для перевода правильной десятичной дpоби F в систему счисления с основанием q необходимо F умножить на q , записанное в той же десятичной системе, затем дробную часть полученного произведения снова умножить на q, и т. д., до тех пор, пока дpобная часть очередного пpоизведения не станет pавной нулю, либо не будет достигнута требуемая точность изображения числа F в q-ичной системе. Представлением дробной части числа F в новой системе счисления будет последовательность целых частей полученных произведений, записанных в порядке их получения и изображенных одной q-ичной цифрой. Если требуемая точность перевода числа F составляет k знаков после запятой, то предельная абсолютная погрешность при этом равняется q -(k+1) / 2.
Пример. Переведем число 0,36 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Для чисел, имеющих как целую, так и дробную части, перевод из десятичной системы счисления в другую осуществляется отдельно для целой и дробной частей по правилам, указанным выше.
Пеpевод чисел из двоичной (восьмеpичной, шестнадцатеpичной) системы в десятичную.
Перевод в десятичную систему числа x, записанного в q-ичной cистеме счисления (q = 2, 8 или 16) в виде xq = (anan-1 . a0 , a-1 a-2 . a-m)q сводится к вычислению значения многочлена
средствами десятичной арифметики.
Примеpы:
Сводная таблица переводов целых чисел из одной системы счисления в другую
Рассмотрим только те системы счисления, которые применяются в компьютерах — десятичную, двоичную, восьмеричную и шестнадцатеричную. Для определенности возьмем произвольное десятичное число, например 46, и для него выполним все возможные последовательные переводы из одной системы счисления в другую. Порядок переводов определим в соответствии с рисунком:
На этом рисунке использованы следующие обозначения:
в кружках записаны основания систем счисления;
стрелки указывают направление перевода;
номер рядом со стрелкой означает порядковый номер соответствующего примера в сводной таблице 4.1.
Например: означает перевод из двоичной системы в шестнадцатеричную, имеющий в таблице порядковый номер 6.
Инфоpматика — дисциплина, основанная на использовании компьютерной техники, изучающая структуру и общие свойства информации, а также закономерности и методы её создания, хранения, поиска, преобразования, передачи и применения в различных сферах человеческой деятельности. Информатика немыслима без компьютерной техники.
Что такое информация - это до сих пор дискуссионный вопрос.
Американский учёный Клод Шеннон заложил основы теории информации - науки, изучающей процессы, связанные с передачей, приёмом, преобразованием и хранением информации. Он рассматривал информацию как снятую неопределенность наших знаний о чем-то.
Современное научное представление об информации очень точно сформулировал, "отец" кибернетики Норберт Винер. А именно:
Информация — это обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств.
Как измерять информацию ?
Если основание логарифма равно 2, то единицу измерения называют - бит. Она главная в цифровой технике. Если равно 10, называется дит(хартли). Если логарифм натуральный, то ед. изм. называется нат .
После того, как информация представлена в виде данных, т.е. в числовой форме, можно говорить о ее компьютерной обработке.
ТЕМА 1. Математические основы компьютерной обработки информации.
- Двоичная и шестнадцатиричная системы счисления (СС).
Кроме десятичной СС существует бесчисленное множество систем С. СС, в которой для записи числа используется N знаков, называется N-ричной. Например, количество 12 можно представить так. 000000000000 – в одноричной СС,
В общем случае, чтобы записать число Х в N-ричной СС, необходимо представить Х в следующей форме :
или X= a k N k + a k-1 N k-1 + a k-2 N k-2 + …..+a 0 N 0 ,
где k=[log N X] – целая часть числа и все a i
Само же число в N–ричной СС будет - a k a k-1 a k-2 a k-3 ….a 0
Например 10 2 = 1*3 2 +0*3 1 +1*3 0 = 101 3
10 2 = 1*2 3 +0*2 2 +1*2 1 +0*2 0 = 1010 2
10 2 = 2*4 1 +2*4 0 = 22 4
10 2 = 2*5 1 +0*5 0 = 20 5
На дом : представить 100 в 2,3,4,5 СС.
В ЭВМ базовая СС – двоичная, т.е. для представления числа используется два знака – 0 и 1. В качестве дополнительной (для удобства записи исп-ся 16-и ричная). По международному соглашению для нее принято употреблять знаки 0 - 9,A,B,C,D,E,F.
Величина способная принимать только два значения 0 или 1 называется бит. 8 бит – 1 байт.
1Кбайт=1024б, 1Мб=1024Кб, 1Гб=1024Мб, 1Тераб=1024Гб, 1Петаб=1Тб.
1457664 ≈ 1,4 Мб. Объем памяти в ЭВМ(количество информации) измеряется в битах, байтах, Кб, Мб, Гб, Тб.
Алгоритм понятен из следующего примера.
7 6 5 4 3 2 1 0
1 0 1 0 0 1 1 1 2 = (167) 10
1*2 7 +0*2 6 +1*2 5 +0*2 4 +0*2 3 +1*2 2 +1*2 1 +1*2 0 =167
Задание. По коду (ASCII) байтовый код z=01011010. Перевести в дес. СС. (90)
Задание. Перевести число 2011 3 в десятичную СС.
Алгоритм понятен из следующего примера.
Задание. По международному коду ASCII код знака N в 10-ой СС = 72. Определить байт для N ? (01001110)
Задание. Перевести 35 10 в трехричную (1022)
Задание. В ЭВМ знак на клавиатуре кодируется одним байтом. Сколько max количество знаков можно закодировать.? Какого max числовое значение байта?
Математические основы информатики — сочетание слов странное, с какой стороны на него ни посмотри.
Если это про применение математических методов в информатике — а об этом, безусловно, предстоит вести речь, — то почему нет, например, математических основ физики или химии, где математика весьма изощренно используется уже столетия?
Если о том, что информатика как научная теория своим происхождением и развитием обязана математике, то, как повзрослевшее дитя, она давно уже выпорхнула из родового гнездышка, обзавелась пестрым оперением информационных технологий — и стоит ли поминать в этой ситуации старушку-мать, т.е. математику. Современное определение информатики как науки, изучающей информационные процессы в природе, технике и обществе, вообще не содержит и намека на какую-то связь с математикой.
Математические основы информатики
Разберемся по порядку. Основные информационные процессы, как известно, — это получение, хранение, передача и обработка информации. Именно их изучение и представляет собой основную цель информатики. Надо только еще сказать, что акцент делается на автоматизации этих процессов. Не случайно бытует мнение, что сам термин ИНФОРМАТИКА происходит от соединения слов ИНФОРмация и автоМАТИКА. Без указанного акцента информатика неизбежно становится сборищем фрагментов других научных дисциплин: семиотики, изучающей знаковые системы, лингвистики, изучающей закономерности языка как средства передачи информации, психологии, изучающей, в частности, процессы обработки информации человеком, этологии, изучающей поведение животных, архивоведения, формулирующего правила хранения информации, библиологии, занимающейся организацией хранения и поиска информации, и т.д. 1
Образование слова информатика
Получение информации
Пока человек получает информацию непосредственно из окружающего мира с помощью своих органов чувств, никакой автоматизации, а значит, и никакой информатики в этом нет. Но, для того чтобы сохранить эту информацию, чтобы передать ее другим людям (даже если это только его первобытные соплеменники), чтобы осмыслить ее, нужно тем или иным способом зафиксировать информацию. Возникает потребность в знаковой системе и, следовательно, в способах кодирования информации посредством такой системы. Постепенно выкристаллизовывались понятия языка и алфавита. Естественные языки, т.е. языки человеческого общения, не формализованы, а значит, и автоматизация представления информации с помощью таких языков была задачей неразрешимой. Первые существенные продвижения в формализации естественных языков связаны со становлением структурной лингвистики и знаменитыми именами Хомского, Щербы и др. Тем не менее и сегодня проблема формализации естественных языков далека от своего решения. Вполне возможно, что она просто неразрешима.
Какой же язык стал первым в истории человечества формализованным языком? Язык записи натуральных чисел. Четко определенный алфавит, состоящий из 10 цифр, четко фиксированные правила записи чисел с помощью этих цифр — записью натурального числа называется любая упорядоченная последовательность цифр, не начинающаяся с 0. Но, пожалуй, самое главное — однозначно определен смысл каждой такой записи: мы точно знаем, какое натуральное число она обозначает. Эти три свойства и указывают на формальный характер данного языка 2 . Ничего подобного мы не можем сказать о многих словах, скажем, русского языка. Что обозначает слово “лук”, или слово “звезда”, или слово “коса”?
Этот формальный язык впоследствии был расширен для записи обыкновенных, а затем и десятичных дробей, и, наконец, вещественных и даже комплексных чисел.
Итак, первые эффективные средства и методы формального кодирования информации оказались разработанными именно в математике. Информатика естественно восприняла их. Более того, соображения чисто технического характера привели к тому, что в алфавите формального языка, предназначенного для фиксации произвольной информации, осталось всего два символа, которые традиционно обозначают цифрами 0 и 1. Но информатика поставила в вопросах кодирования принципиально новые задачи: разработка кодов, предотвращающих искажение информации во время передачи по каналам связи, создание экономичных кодов (т.е. таких, которые для передачи или сохранения информации требуют минимального числа кодирующих символов), разработка методов кодирования, защищающих информацию от несанкционированного проникновения. Отвечая на эти вызовы, математики начали развивать методы, позволяющие решить эти задачи.
И снова информатика ставит задачи, связанные с существованием алгоритмов, исследованием их свойств, оценкой эффективности, доказательством правильности работы. Математическая подоплека кодирования информации и здесь естественным образом трансформирует эти задачи в математические 3 .
Эти и другие вопросы привели к тому, что в математике образовалось направление, названное дискретной математикой. Сегодня это самостоятельная бурно развивающаяся весьма обширная и разнообразная область математики. Те ее достижения, которые непосредственно связаны с информационными процессами, и образуют так называемые “математические основы информатики”.
А что же школьная математика? Имеется ли в ней место этим вопросам? Конечно, нет. Ведь курс школьной математики сформировался (и это остается краеугольным камнем его сегодняшней идеологии) как курс, обеспечивающий другие школьные предметы — в первую очередь физику — математическим инструментарием. У кого, к примеру, в реальной жизни хоть раз возникла необходимость решать квадратное уравнение или исследовать поведение какой-либо тригонометрической функции? Думаю, что практически ни у кого. Но квадратичная функция и квадратные уравнения нужны для того, чтобы в физике описывать равноускоренное движение, в частности, движение тела у поверхности Земли. А тригонометрические функции нужны для описания колебательных и периодических процессов. Информатика в школу пришла поздно — в середине 80-х годов. И пришла она в заключительное звено школьного образования — 10-е и 11-е классы. Для изложения ее математических основ ни времени, ни места в курсе школьной математики уже нет.
Конечно, если мы говорим о базовом курсе информатики, в котором едва-едва удается представить основные положения этой науки и познакомить с элементами информационных компьютерных технологий, то математические основы информатики вряд ли будут в нем адекватно востребованы. Но если говорить об информатике как профильном курсе, который ориентирован на знание, понимание и умение применять фундаментальные аспекты информатики, то без изучения математических основ этого добиться невозможно.
В наших лекциях речь пойдет именно о таких основах. И начнем мы, естественно, с вопросов, связанных с кодированием информации.
Алгебра логики
Алгеброй логики является раздел математики, который изучает высказывания с точки зрения их логических значений, то есть, истинны они или ложны, и логические операции над ними.
Логическим высказыванием считаются повествовательное предложение, про которое можно точно утверждать, что оно является истинным или ложным.
Истинное высказывание принято обозначать символом единица (1), а ложное высказывание принято обозначать символом ноль (0).
Примеры логических высказываний приведены в таблице ниже:
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Математические и логические основы информатики
Готовые работы на аналогичную тему
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Импликация может быть выражена при помощи дизъюнкции и отрицания:
Логическое тождество может быть выражено при помощи отрицания, дизъюнкции и конъюнкции:
A B = (¬А v B) ^ (¬B v А)
Определение значения логического выражения выполняется слева направо согласно таблице истинности и приоритету осуществления логической операции. Ниже приведена таблица истинности:
Рисунок 3. Таблица истинности. Автор24 — интернет-биржа студенческих работ
Приоритет осуществления логической операции определяется согласно следующей таблице:
Рисунок 4. Таблица. Автор24 — интернет-биржа студенческих работ
Очерёдность осуществления логических операций может быть изменена при помощи круглых скобок.
Основные правила алгебры логики
Базовые правила алгебры логики, которые позволяют выполнять тождественные преобразования логических выражений, приведены в таблице ниже:
Рисунок 5. Таблица. Автор24 — интернет-биржа студенческих работ
Математический аппарат алгебры логики является очень удобным средством для описания работы аппаратного обеспечения компьютерного оборудования, так как там применяется двоичная система счисления, где есть только две цифры нуль и единица аналогично логическим постулатам. На этой основе можно сделать следующие выводы:
- Одни и те же компьютерные модули можно использовать для сохранения и переработки как числовых данных, которые представлены в двоичном формате, так и для переменных алгебры логики.
- При проектировании аппаратного обеспечения компьютеров методы алгебры логики дают возможность существенно упростить логические процедуры, которые описывают работу компьютерных схем. Это позволяет в разы сократить количество элементарных элементов логики, составляющих модули компьютера.
Формирование таблицы истинности
Как отмечалось выше, таблица истинности логического выражения отражает соответствие среди допустимых наборов значений переменных и значениями выражения (формулы). Если формула содержит только две переменные, то возможных наборов величин переменных будет четыре.
Когда в логическую формулу входят три переменные, то количество допустимых наборов значений переменных будет уже равно восьми.
Число наборов для выражений, имеющих четыре переменные, будет равняться шестнадцати и так далее. Для определения значений формулы, очень удобно использовать форму записи в виде таблицы, которая содержит помимо значений переменных и значений формулы ещё и значения промежуточных формул.
Обозначим высказывания следующим образом:
В таком случае исходное высказывание можно выразить так:
Выполнив необходимые преобразования, можно определить, что условию задачи удовлетворяет только имя Антон.
Читайте также: