Например, 150D . A216->2=0001 0101 0000 1101 . 1010 0010
Таблица соответствия систем счисления
-
Десятичная
|
Двоичная
|
Восьмеричная
|
Шестнадцатеричная
|
0
|
0000
|
0
|
0
|
1
|
0001
|
1
|
1
|
2
|
0010
|
2
|
2
|
3
|
0011
|
3
|
3
|
4
|
0100
|
4
|
4
|
5
|
0101
|
5
|
5
|
6
|
0110
|
6
|
6
|
7
|
0111
|
7
|
7
|
8
|
1000
|
10
|
8
|
9
|
1001
|
11
|
9
|
10
|
1010
|
12
|
A
|
11
|
1011
|
13
|
B
|
12
|
1100
|
14
|
C
|
13
|
1101
|
15
|
D
|
14
|
1110
|
16
|
E
|
15
|
1111
|
17
|
F
|
В одном столбце таблицы помещены шестнадцатеричные цифры, напротив, в соседнем столбце — равные им двоичные числа. Причем все двоичные числа записаны в четырехзначном виде (там, где знаков меньше четырех, слева добавлены нули).
ПРИМЕР 4:Перевести число F02E .1C16->2 .(из 16-ричной системы счисления в двоичную).
Для этого проделаем следующее: каждую цифру в шестнадцатеричном числе F02E . 1C16 заменим на соответствующую ей в таблице четверку двоичных знаков. Иначе говоря, перекодируем целое число F02E . 1C по таблице в двоичную форму. Получается: 1111 0000 0010 1110 . 0001 11002.
Если отбросить нули справа (в любой системе счисления они не влияют на значение дробной части числа), то получим искомое двоичное число.
Таким образом: F02E .1C 16->2= 1111 0000 0010 1110 . 0001 112
ПРИМЕР 5:Перевести двоичное число 1101111010111 . 01111 в шестнадцатеричную систему.
Разделим данное число на группы по четыре цифры, начиная от десятичной точки вправо и влево. Если в крайней левой группе окажется меньше четырех цифр, то дополним ее нулями. 0001 1011 1101 0111 . 0111 10002;
А теперь, глядя на таблицу соответствия систем счисления, заменим каждую двоичную группу на соответствующую шестнадцатеричную цифру: 1BD7.7816
Следовательно: 1101111010111 . 011112 = 1BD7 . 7816
ПРИМЕР 6:Перевести двоичное число 1011101 .101112->8 в восьмеричную систему.
Группы по три двоичных знака выделяются от запятой как влево, так и вправо. Затем производится перекодировка по таблице соответствия систем счисления:
1011101 . 101112 = 001 011 101, 101 110= 135. 568.
Правила перевода чисел из любой системы счисления в десятичную систему.
Здесь используется запись числа в позиционной системе счисления в общем виде:
Если основание позиционной системы q > 1, то в качестве цифр используются знаки от 0 до (q-1). Число записывается в виде последовательности цифр anan-1an-2…a1a0 . a-1a-2… , а значение числа равно сумме значений цифр, т.е.
ПРИМЕР 7: Числа 19.816, 31.48, 11001.12 перевести в десятичную систему счисления
19.816 = 1*16 1 + 9*16 0 + 8*16-1= 16 + 9 + 0.5 = 25.510
31.48 = 3*8 1 + 1*8 0 + 4*8-1 = 24 + 1 + 0.5 = 25.510
11001.12 =l*24 + l*23 + 0*22 + 0*21 + l*20 + 1*2-1 = 16 + 8 + l +0.5 = 25.510
Итак, чтобы перевести число из любой системы счисления в десятичную, надо записать его в общем виде, и подсчитать сумму значений его цифр. Результат всегда будет в десятичной системе счисления.
Перевод чисел из десятичной системы счисления в другие.
Перевод целых чисел (или целой части дробного числа).
Основание новой системы счисления выразить в десятичной системе счисления и все последующие действия производить в десятичной системе счисления;
Чтобы перевести целое число из десятичной системы счисления (q=10) в любую другую (q=2, q=8, q=16), надо разделить его на основание новой системы счисления q;
Если полученное частное больше или равно делителю (основанию новой системы счисления), то надо это частное снова разделить на него;
Если полученное частное меньше делителя, то оно является первой цифрой числа в новой системе счисления, последний остаток от деления является второй цифрой нового числа и т. д., первый остаток от деления – это последняя цифра нового числа.
Полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;
ПРИМЕР 8: Перевести число 3710->2 в двоичную систему.
-37 |_2
36 -18 |_2
1 18 -9 |_2
0 8 -4 |_2
1 4 -2 |_2
0 2 1
Отсюда: 37 10 = 100101 2
ПРИМЕР 9: Перевести десятичное число 271 в восьмеричную и в шестнадцатеричную системы: 27110->8, 27110->16:
-271 |_8 -271 |_16
264 -33 |_8 256 -16 |_16
7 32 4 15 16 1
Отсюда следует: 27110 = 4178= 10F16.
Перевод дробной части числа в десятичной системе счисления
Основание новой системы счисления выразить в десятичной системе и все последующие действия производить в десятичной системе счисления;
Чтобы перевести дробную часть десятичного числа в любую другую систему счисления, надо последовательно умножать её на основание новой системы счисления до тех пор, пока дробная часть произведения не станет равной нулю или не будет достигнута требуемая точность представления числа в новой системе счисления;
Полученные целые части произведений, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;
Составить дробную часть числа в новой системе счисления, начиная с целой части первого произведения.
ПРИМЕР 10: Перевести десятичную дробь 0,1875 в двоичную, восьмеричную и шестнадцатеричную системы с точностью до 4 двоичных разрядов.
0. | 1875 0. | 1875 0. |1875
| * 2 | * 8 | * 16
0 | 3750 1 | 5000 3 | 0000
| * 2 | * 8
0 | 7500 4 | 0000
| * 2
1 | 5000
| * 2
1 | 0000
Здесь вертикальная черта отделяет целые части чисел от дробных частей. Отсюда: 0 . 187510 = 0 . 00112 = 0 . 148 = 0 . 316
Перевод смешанных чисел, содержащих целую и дробную части, осуществляется в два этапа. Целая и дробная части исходного числа переводятся отдельно по соответствующим алгоритмам. В итоговой записи числа в новой системе счисления целая часть отделяется от дробной точкой.
1.1.3. Единицы измерения количества информации.
Количество информации – число, адекватно характеризующее разнообразие (структурированность, определенность, выбор состояний и т.д.) в оцениваемой системе. Количество информации часто оценивается в битах, причем такая оценка может выражаться и в долях бит (так как речь идет не об измерении или кодировании сообщений).
Единицы измерения количества информации:
1 бит (binary digit – двоичное число) = 0 или 1,
1 байт=8 бит,
1 килобайт (1Кб) = 1024 байт
1 мегабайт (1Мб) = 1024 килобайт
1 гигабайт (1Гб) = 1024 мегабайт
1 терабайт (1Тб) = 1024 гигабайт
1 петабайт (1Пб) = 1024 терабайт
1 эксабайт (1Эб) = 1024 петабайт
Пример: Учебник содержит 135 страниц, на каждой странице 40 строчек, на каждой строчке 35 символов. Сколько нужно взять дискет, объёмом памяти 3,14 мегабайт?
Решение: Чтобы узнать, какое количество информации содержит эта книга в битах, нужно количество всех страниц умножить на количество всех строчек и на количество всех символов: 135*40*35=189000 бит. (Так как 1 символ соответствует одному биту)
Чтобы узнать количество информации в байтах, нужно получившееся количество бит разделить на 8 (т. к. в одном байте 8 бит): 189000/8=23625 байт.
Чтобы узнать количество информации в килобайтах, нужно разделить получившееся количество байт на 1024 (т. к. в одном килобайте 1024 байта): 23625/1024=23,07 килобайт.
Аналогично переводим в мегабайты: 23,07/1024=0,02 мегабайт.
При переводе из большей единицы измерения количества в меньшую, следует использовать умножение.
Короткие обозначения единиц измерения количества информации:
Килобайт=Кб
Мегабайт=Мб
Гигабайт=Гб
Терабайт=Тб
Петабайт=Пб
Эксабайт=Эб
ВОПРОСЫ ДЛЯ САМОПОДГОТОВКИ
определение системы счисления;
определение тетрады;
определение байта;
определение частного высказывания;
определение триады;
определение бита;
определение высказывания;
определение общего высказывания;
определение единичного высказывания;
знать правило перевода из десятичной системы счисления целой части в двоичную систему счисления;
знать значение дизъюнкции двух переменных;
знать правило перевода из десятичной системы счисления целой части в восьмеричную систему счисления;
знать значение конъюнкции двух переменных;
знать таблицы истинности логических операций.
ТЕМА 1.2.Алгебра логики. Основные логические операции. Построение таблиц истинности сложных высказываний. Решение логических задач.
1.2.1. Алгебра логики. Основные логические операции. Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы речи от ее содержания. Он исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления.
Логика изучает внутреннюю структуру процесса мышления, который реализуется в таких естественно сложившихся формах как понятие, суждение, умозаключение и доказательство.
Понятие. Понятие - это форма мышления, отражающая наиболее существенные свойства предмета, отличающие его от других предметов. В структуре каждого понятия нужно различать две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков предмета. Чтобы раскрыть содержание понятия, следует выделить признаки, необходимые и достаточные для выделения данного предмета по отношению к другим предметам.
Объем понятия определяется совокупностью предметов, на которую оно распространяется, и может быть представлено в форме множества объектов, состоящего из элементов множества. Алгебра множеств, одна из основополагающих современных математических теорий, позволяет исследовать отношения между множествами и, соответственно, объемами понятий.
Между множествами (объемами понятий) могут быть различные виды отношений:
равнозначность, когда объемы понятий полностью совпадают;
пересечение, когда объемы понятий частично совпадают;
подчинения, когда объем одного понятия полностью входит в объем другого и т.д.
Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы Эйлера-Венна. Если имеются какие-либо понятия A, B, C и т.д., то объем каждого понятия (множество) можно представить в виде круга, а отношения между этими объемами (множествами) в виде пересекающихся кругов.
Пример 1. Отобразить с помощью диаграммы Эйлера-Венна соотношение между объемами понятий натуральные числа и четные числа.
Объем понятия натуральные числа включает в себя множество целых положительных чисел А, а объем понятия четные числа включает в себя множество отрицательных и положительных четных чисел В. Эти множества пересекаются, т.к. включают в себя множество положительных четных чисел С.
Совокупность всех существующих множеств образует всеобщее универсальное множество 1, которое позволяет отобразить множество логически противоположное к заданному. Так, если задано множество А, то существует множество НЕ А, которое объединяет все объекты, невходящие во множество А. Множество НЕ А дополняет множествоА до универсального множества 1.
Пример 2. Отобразить с помощью диаграммы Эйлера-Венна множество натуральных чисел А и множество НЕ А.
На диаграммы Эйлера-Венна универсальное множество 1 изображается в виде прямоугольника, множество А в форме круга, а множество НЕ А в форме прямоугольник минус круг.
Высказывание. Высказывание (суждение) - это форма мышления, выраженная с помощью понятий, посредством которой что-либо утверждают или отрицают о предметах, их свойствах и отношениях между ними.
О предметах можно судить верно или неверно, т.е. высказывание может быть истинным или ложным. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Ложным суждение будет в том случае, когда связь понятий искажает объективные отношения, не соответствует реальной действительности.
Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем — в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.
В естественном языке высказывания выражаются повествовательными предложениями. Высказывание не может быть выражено повелительным или вопросительным предложением, оценка истинности или ложности которых невозможна. Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства.
Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным).
Высказывания имеют определенную логическую форму. Понятие о предмете мысли называется субъектом и обозначается буквой S, а понятие о свойствах и отношениях предмета мысли называется предикатом и обозначается буквой P. Оба эти понятия - субъект и предикат называются терминами суждения. Отношения между субъектом и предикатом выражается связкой «есть», «не есть», «является», «состоит» и т.д.
Таким образом, каждое высказывание состоит из трех элементов - субъекта, предиката и связки (двух терминов и связки). Состав суждения можно выразить общей формулой «S есть "» или «S не есть P».
Пример 3. Определить, что в суждении «Компьютер состоит из процессора, памяти и внешних устройств» является субъектом, предикатом и связкой.
«Компьютер» - субъект, «процессора, памяти и внешних устройств» - предикат, «состоит» - связка
Предикат. В современной логике предикат рассматривается как функциональная зависимость. В общем случае предикат от n переменных (от n неопределенных понятий) выражается формулой:
Р (х1,х2,...,хn ), где n * 0
При n = 1, когда один из терминов является неопределенным понятием, мы имеем предикат первого порядка, например, «х - человек».
При n = 2, когда два термина неопределены, мы имеем предикат второго порядка, например, «х любит y».
При n = 3, когда неопределенны три термина, мы имеем предикат третьего порядка, например, «z - сын x и y».
Пример 4. В вышеописанных предикатах заменить неопределенные термины на конкретные понятия.
Преобразуем предикаты в высказывания путем подстановки вместо переменных соответствующих понятий: x = «Сократ», y = «Ксантиппа», z = «Софрониск»:
«Сократ - человек»;
«Ксантиппа любит Сократа»
«Софрониск - сын Сократа и Ксантиппы».
Умозаключение. Умозаключение - это форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, по определенным правилам логического вывода получается новое знание о предметах реального мира (вывод).
Умозаключения бывают дедуктивные, индуктивные и по аналогии. В дедуктивных умозаключениях рассуждения ведутся от общего к частному. Например, из двух суждений: «Все металлы электропроводны» и «Ртуть является металлом» путем умозаключения можно сделать вывод, что: «Ртуть электропроводна».
В индуктивных умозаключениях рассуждения ведутся от частного к общему. Например, установив, что отдельные металлы - железо, медь, цинк, алюминий и т.д. - обладают свойством электропроводности, можно сделать вывод, что все металлы электропроводны.
Умозаключение по аналогии представляет собой движение мысли от общности одних свойств и отношений у сравниваемых предметов или процессов к общности других свойств и отношений. Например, химический состав Солнца и Земли сходен по многим показателям, поэтому, когда на Солнце обнаружили неизвестный еще на Земле химический элемент гелий, то по аналогии заключили: такой элемент есть и на Земле.
Доказательство. Доказательство есть мыслительный процесс, направленный на подтверждение или опровержение какого-либо положения посредством других несомненных, ранее обоснованных доводов. Доказательство по своей логической форме не отличается от умозаключения. Однако, если в умозаключении заранее исходят из истинности посылок и следят только за правильностью логического вывода, в доказательстве подвергается логической проверке истинность самих посылок.
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над различными математическими объектами (алгебра переменных и функций, алгебра векторов, алгебра множеств и т.д.). Объектами алгебры логики являются высказывания.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт — истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = {Аристотель - основоположник логики}
В = {На яблонях растут бананы}.
Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.
Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции. Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.
Логическая операция КОНЪЮНКЦИЯ (логическое умножение):
в естественном языке соответствует союзу и;
в алгебре высказываний обозначение &;
в языках программирования обозначение And.
Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
В алгебре множеств конъюнкции соответствует операция пересечения множеств, т.е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.
Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение):
в естественном языке соответствует союзу или;
обозначение ;
в языках программирования обозначение Or.
Дизъюнкция - это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны и истинным, когда хотя бы одно из двух образующих его высказываний истинно.
В алгебре множеств дизъюнкции соответствует операция объединения множеств, т.е. множеству получившемуся в результате сложения множеств А и В соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В.
Логическая операция ИНВЕРСИЯ (отрицание):
в естественном языке соответствует словам неверно, что... и частице не;
обозначение ;
в языках программирования обозначение Not;
Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества, т.е. множеству получившемуся в результате отрицания множества А соответствует множество , дополняющее его до универсального множества.
Логическая операция ИМПЛИКАЦИЯ (логическое следование):
в естественном языке соответствует обороту если ..., то ...;
обозначение .
Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.
Логическая операция ЭКВИВАЛЕНЦИЯ (равнозначность):
в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;
обозначения , ~ .
Эквиваленция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Логические операции имеют следующий приоритет: действия в скобках, инверсия, &, , , .
Пример. Какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы было ложно логическое выражение ((A В) & В) С.
Импликация ложна на единственном наборе логических значений (1, 0). Значит, ((A В)&В) = 1, С = 0.
Конъюнкция истинна на единственном наборе логических значений (1, 1). Значит, (A В) = 1 и В = 1.
Дизъюнкции истинна при наборах логических значений (0, 1) и (1, 1).
Следовательно, существуют два набора логических значений, удовлетворяющих условию задачи: (А = 0, В = 1, С = 0) и (А= 1, В = 1, С = 0).
Пожалуй, самая интригующая операция – это ИМПЛИКАЦИЯ или "логическое если…, то". Например, «Если Наполеон родился в Кудымкаре, то газ при нагревании сужается». Это, кстати, истинное высказывание! Нет причин считать его ложным. Единственная ситуация, когда импликация ложна, это когда посылка (часть «если») истинна, а следствие (часть «то») ложна.
Еще интереснее с точки зрения здравого смысла то, что импликацию иногда (не совсем корректно по иным причинам!) называют операцией логического следования, хотя наш пример показывает, что высказывания могут логически не следовать одно из другого, более того, могут не иметь между собой никакой логической связи. Напомним, импликация, как и другие операции, берет в расчет только истинность входящих в нее высказываний.
«Если Волга впадает в Каспийское море, то 2 + 2 = 4» истинное высказывание.
«Если Волга впадает в Каспийское море, то 2 + 2 = 5» ложное высказывание.
Хотя оба эти «логические рассуждения» с точки зрения здравого рассуждения одинаково бессмысленны.
Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ или "тогда и только тогда« (кстати, воспользовавшись»американским приемом", можно записать короче – "ттогда"). Результирующее сложное высказывание истинно, если одновременно истинны или ложны оба входящих в него высказывания.
Назовем еще одну операцию, ШТРИХ ШЕФФЕРА или логическое "и-не". Результат этой операции равносилен последовательному применению операций кон'юнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера – это операция замечательная тем, что ее одной (необходимое количество раз примененной) достаточно, чтобы записать любое сложное высказывание.
При использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз'юнкции ("или") соответствует параллельному подключению контактов реле, кон'юнкции ("и") – последовательному. Операция отрицания ("не") моделируется нормально замкнутым контактом реле. То есть контакт размыкается при срабатывании реле. Разумеется, все это реализовывалось в полупроводниковом «модульном» варианте. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему. (А сам процессор был размером со шкаф, но не по вине логики).
1.2.2. Построение таблиц истинности сложных высказываний. Решение логических задач.
Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания.
Составные высказывания в алгебре логики записываются с помощью логических выражений. Для любого логического выражения достаточно просто построить таблицу истинности.
Алгоритм построения таблицы истинности:
1) подсчитать количество переменных n в логическом выражении;
2) определить число строк в таблице, которое равно m = 2n;
3) подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;
4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;
5) заполнить стобцы входных переменных наборами значений;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:
а) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;
б) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц , начиная с группы нулей;
в) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами нулей или единиц до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
ВОПРОСЫ ДЛЯ САМОПОДГОТОВКИ
определение высказывания;
определение общего высказывания;
определение единичного высказывания;
знать правило перевода из десятичной системы счисления целой части в двоичную систему счисления;
знать значение дизъюнкции двух переменных;
знать правило перевода из десятичной системы счисления целой части в восьмеричную систему счисления;
знать значение конъюнкции двух переменных;
знать таблицы истинности логических операций.
Раздел №2 Средства информации и коммутативных технологий
|
