Теоретическая информатика

Главная | Разделы | В начало страницы | Другие темы раздела: 1 | 2 | 3 | 4

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

§3. Кодирование графической и видеоинформации.

§5. Единицы измерения количества информации. Скорость информационного обмена.

Подходы к измерению информации.

Вопрос «как измерить информацию?» очень непростой. Понятие "информация" является контекстным, а значит и способы её измерения могут быть различны .

Информация - мера уменьшения неопределенности знаний.

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

Вероятностный подход к измерению информации.

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

Пример 1. Предположим, что мы подбрасываем монету. Есть два равновероятных исхода – выпадет орел или решка. Узнав результат бросания монеты, Вы получаете 1 бит информации.

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

Можно обозначить (закодировать) возможные варианты:

Равновероятные события	Их обозначение (код)
Решка	0
Орёл	1

Преобразование информации из одной формы представления в другую называют кодированием. Для кодирования используют определенную систему знаков – алфавит. Количество знаков в алфавите может быть различным. Самый короткий алфавит состоит из двух знаков. Если для кодирования информации используется только два знака - 0 и 1, то кодирование называют двоичным. Таблица, представленная выше, называется таблицей двоичной кодировки, а один бит информации, таким образом, представляет собой один двоичный знак.

Заметим теперь, что записать результаты многократного бросания монет можно по-разному:

Орёл, решка, решка, орёл, решка, орёл, орёл ......
1, 0, 0, 1, 0, 1, 1, ........

Пример 2. На уроке информатики проводится тестовая работа, состоящая из трёх заданий. Составим таблицу двоичной кодировки возможных результатов выполнения работы одним из учеников:

События	Двоичные коды
выполнено 0 заданий	00
выполнено 1 задание	01
выполнено 2 задания	10
выполнено 3 задания	11

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

Пример 3. Если увеличить количество заданий до семи, то таблица примет вид:

События	Двоичные коды
выполнено 0 заданий	000
выполнено 1 задание	001
выполнено 2 задания	010
выполнено 3 задания	011
выполнено 4 задания	100
выполнено 5 заданий	101
выполнено 6 заданий	110
выполнено 7 заданий	111

С увеличением количества событий в два раза увеличивается на 1 бит длина кода:

Количество событий (N)	Длина кода (i)
N = 2	i = 1
N = 4	i = 2
N = 8	i = 3

Нетрудно заметить, что величины N и i связаны формулой 2ⁱ= N, если N выбирать из ряда 2,4,8,16,32,64…….. Для других значений N формула выглядит так: 2ⁱ ≥ N. По ней мы можем рассчитать длину двоичного кода для любого количества событий. Неравенство можно решить подбором наименьшего значения i из ряда натуральных чисел.

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

Для записи текстовой (знаковой) информации всегда используется какой-либо язык (естественный или формальный). Всё множество используемых в языке символов называется алфавитом. Полное число символов алфавита называют его мощностью. При записи текста в каждой очередной позиции может появиться любой из N символов алфавита, т.е. может произойти N событий. Следовательно, каждый символ алфавита содержит i бит информации, где i определяется из неравенства: 2ⁱ ≥ N. Тогда общее количество информации в тексте определяется формулой:

V = k * i , где V – количество информации в тексте; k – число знаков в тексте (включая знаки препинания и даже пробелы), i - количество бит, выделенных на кодирование одного знака.

Так как каждый бит – это 0 или 1, то любой текст может быть представлен последовательностью нулей и единиц. Именно так текстовая информация хранится в памяти компьютера. Присвоение символу алфавита конкретного двоичного кода - это вопрос соглашения, зафиксированного в кодовой таблице. В настоящее время широкое распространение получили кодовые таблицы ASCII и Unicode.

ASCII (American Standart Code for Informational Interchange - Американский стандартный код информационного обмена) используется достаточно давно. Для хранения кода одного символа выделено 8 бит, следовательно, кодовая таблица поддерживает до 2⁸= 256 символов. Первая половина таблицы (128 символов) - управляющие символы, цифры и буквы латинского алфавита. Вторая половина отводится под символы национальных алфавитов. К сожалению, в настоящее время существует целых пять вариантов кодовых таблиц для русских букв, поэтому тексты созданные в одной кодировке неверно отображаются в другой. (Наверное, Вы встречали русскоязычные сайты, тексты которых выглядят как бессмысленный набор знаков? Приходилось менять кодировку?).

Unicode - получил распространение в последние годы. Для хранения кода одного символа выделено 16 бит, следовательно, кодовая таблица поддерживает до 2¹⁶= 65536 символов. Такого пространства достаточно, чтобы в одном стандарте объединить все "живые" официальные (государственные) письменности. Кстати, стандарт ASCII вошел в состав Unicode.

Кодирование графической информации.

Растровая графика.

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

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

V = k * i , где V – количество информации в изображении; k – количество пикселей, а i – глубина цвета (т.е. количество бит, выделенных на кодирование цвета), определяемая по формуле: 2ⁱ≥ N, где N – количество цветов в палитре. Так как каждый бит – это 0 или 1, то изображение может быть представлено последовательностью нулей и единиц. Количество пикселей на экране дисплея (растр) указывают соотношением количества пикселей в строке по горизонтали к их количеству в столбце по вертикали (800*600, 1024*768 и т.д.). Максимально возможное количество пикселей на экране называют разрешающей способностью дисплея. Качество растровых изображений может быть очень высоким, но размер файла также весьма велик (изучите свойства нескольких Точечных рисунков *.BMP, созданных с помощью Paint). При уменьшении размера изображения (например, с целью экономии места на диске) качество безвозвратно ухудшается. Для уменьшения размера файлов часто используют другие форматы файлов такие как *.JPG,*.GIF и др.

Векторная графика.

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

Видеоинформация.

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

Кодирование звука.

Из курса физики Вам должно быть известно, что звук представляет собой волну с непрерывно меняющейся амплитудой и частотой:

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

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

V = k * i , где V – количество информации в звуке; k – количество временных интервалов, а

i – глубина звука (т.е. количество бит, выделенных на кодирование уровня громкости на одном интервале), определяемая по формуле: 2ⁱ ≥ N, где N – количество уровней громкости. Так как каждый бит – это 0 или 1, то любой звук может быть представлен последовательностью нулей и единиц. Качество звука тем выше, чем больше глубина звука и частота дискретизации (т.е. количество «ступеней» в секунду). Исходная формула может быть преобразована следующим образом:

V = t * ν * I , где V – количество информации в звуке; t – время звучания, ν – частота дискретизации, а i – глубина звука.

Единицы измерения информации. Скорость информационного обмена.

При работе с компьютером используется алфавит мощностью 256 символов. В него входят русские и латинские буквы, цифры, знаки препинания, специальные символы. Для кодирования одного символа такого алфавита потребуется 8 бит (2 ⁸= 256). Этой величине присвоили своё название – байт. Бит и байт – «мелкие» единицы измерения количества информации. Для измерения больших объемов используют производные от байта единицы. При этом знакомая приставка кило- обозначает не точно 10³, а 2¹⁰, т.е. 1024. То же правило действует и на другие приставки (мега-, гига- и т.д.).

Таблица единиц измерения количества информации. Передача информации.

Единица измерения	Обозначение	Связь с другими единицами измерения количества информации
1 бит	бит	Минимальное количество информации
1 Байт	байт	8 бит
1 Килобайт	Кб	2¹⁰ байт = 1024 Байт
1 Мегабайт	Мб	2¹⁰ Килобайт = 1024 КБ
1 Гигабайт	Гб	2¹⁰ Мегабайт = 1024 МБ

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

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

В начало темы

Главная | Разделы | В начало раздела | Другие темы раздела: 1 | 2 | 3 | 4

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

§1. Непозиционные и позиционные системы счисления. Развёрнутая форма записи числа.

§2. Десятичная, двоичная, восьмеричная и шестнадцатеричная системы счисления.

§3. Перевод чисел из одной системы счисления в другую.

§4. Представление чисел в компьютере. Арифметические операции в позиционных системах счисления.

Непозиционные и позиционные системы счисления. Развёрнутая форма записи числа.

Система счисления – это способ изображения чисел и соответствующие ему правила действий над числами.

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

Все системы счисления делятся на две группы: непозиционные и позиционные. В непозиционной системе счисления значения цифры в числе не зависит от позиции. Из непозиционных систем самая известная – римская. Римское число ХХХ состоит из трёх цифр Х, каждая из которых обозначает одну и ту же величину – число 10. Три числа по 10 в сумме дают 30. В позиционных системах значение цифры зависит от позиции в числе. В такой системе счисления основание системы равно количеству цифр и определяет, во сколько раз отличаются значения одинаковых цифр, стоящих в соседних позициях. Например, число 535,75₁₀ записано в привычной для нас свернутой форме. В развернутой форме его можно записать так:

535,75₁₀ = 500 + 30 + 5 + 0,7 + 0,05 = 5*10 ²+ 3*10 ¹+ 5*10 ⁰+ 7*10 ^-1+ 5*10 ^-2

Итак, развернутая форма записи числа представляет собой сумму числового ряда степеней основания, коэффициентами которых выступают цифры данного числа. Теоретически возможно использование множества позиционных систем счисления с основанием q ≥ 2. В общем виде число А_q можно записать так:

Аq = a _n-1*q ^n-1+ a _n-2*q ^n-2+…. a ₀*q ⁰+ a _-1*q ^-1+…+ a _-m*q ^–m

^{Десятичная,
двоичная, восьмеричная и шестнадцатеричная системы
счисления.}

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

Десятичная (Dec)	Двоичная (Bin)	Восьмеричная (Oct)	Шестнадцатеричная (Hex)
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
16	10000	20	10

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

Перевод чисел из одной системы счисления в другую.

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

1. Перевод чисел в десятичную систему счисления.

Для перевода в десятичную систему счисления число записывают в развернутой форме и вычисляют его значение. Например:

1). 110,11₂ = 1*2²+ 1*2¹ + 0*2⁰ + 1*2^-1 + 1*2^-2 =

= 1*4 + 1*2 + 0*1 + 1*0,5 + 1*0,25 = 6,75₁₀

2). 67,5₈ = 6*8¹ + 7*8⁰ + 5*8^-1 = 6*8 + 7*1 + 5*0,125 = 55,625₁₀

3). 19F₁₆ = 1*16²+ 9*16¹ + F*16⁰ = 1*256 + 9*16 +15*1 = 415₁₀

2. Перевод чисел из десятичной в другие системы счисления.

Рассмотрим пример перевода десятичного числа 19,75 в двоичную систему счисления. Перевод целой части числа и дробной части выполним отдельно. Сначала переведём целую часть. Для этого будем делить нацело исходное целое число и получаемые целые частные на основание системы (на 2) до тех пор, пока не получится частное, меньшее основания системы (т.е. меньшее 2).

Десятичное число/целое частное	Основание системы счисления (делитель)	Остаток
19	2	1
9	2	1
4	2	0
2	2	0
1	2	1

Запишем полученные остатки в обратной последовательности (снизу вверх):

19₁₀ = 10011₂

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

Десятичная дробь/дробная часть произведения	Основание системы счисления (множитель)	Произведение	Целая часть произведения
0,75	2	1,5	1
0,5	2	1	1
0	2	0

Запишем целые части произведений в прямой последовательности (сверху вниз).

0,75₁₀ = 0,11₂

Соединим целую и дробную часть:

19,75₁₀ = 10011,11₂

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

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

Перевод чисел между двоичной и восьмеричной, а также между двоичной и шестнадцатеричной системой можно выполнить проще.

Переведем двоичное число 1101001,1101011₂ в восьмеричную систему:

§ разобьём целую часть числа на группы по три цифры (двоичные триады) справа налево, а дробную часть слева направо: 1 101 001 , 110 101 1;

§ дополним крайнюю левую и крайнюю правую группы незначащими нулями до трёх цифр: 001 101 001 , 110 101 100;

§ воспользуемся таблицей соответствия чисел: 001 101 001,110 101 100₂ = 151,654₈

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

§ каждой восьмеричной цифре по таблице ставится в соответствие двоичная триада;

§ убираются (если нужно) незначащие нули слева от целой части и справа от дробной;

§ получаем двоичную форму записи восьмеричного числа.

Переведем двоичное число 1101001,1101011₂ в шестнадцатеричную систему:

§ разобьём целую часть числа на группы по четыре цифры (двоичные тетрады) справа налево, а дробную часть слева направо: 110 1001,1101 011;

§ дополним крайнюю левую и крайнюю правую группы незначащими нулями до четырёх цифр: 0110 1001 , 1101 0110;

§ воспользуемся таблицей соответствия чисел: 0110 1001,1101 0110₂ = 69,D6₁₆

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

§ каждой шестнадцатеричной цифре по таблице ставится в соответствие двоичная тетрада;

§ убираются (если нужно) незначащие нули слева от целой части и справа от дробной;

§ получаем двоичную форму записи шестнадцатеричного числа.

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

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

Рассмотрим сложение в двоичной системе счисления. В его основе лежит таблица сложения двоичных чисел:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10

1 + 1 + 1 = 11

При сложении двух или трёх единиц производится перенос единицы в старший разряд. Приведём пример сложения двух больших двоичных чисел:

Переведите числа в десятичную систему и выполните проверку. Правильно? Интересно, что в любой позиционной системе счисления все арифметические действия могут быть заменены сложением! Например, в десятичной системе:

вычитание: 3-2 = 3+(-2)
умножение: 2*3 = 2+2+2
деление: 3/2 = 3*0,5 = 0,5+0,5+0,5
возведение в степень: 3² = 3*3= 3+3+3

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

Например, формат для хранения целого числа со знаком отводит 16 бит, причём старший разряд отводится под хранение знака числа (0 это плюс, 1 это минус). Сложение двух положительных чисел выполняется без проблем, если не возникает переполнение (т.е. сумма не помещается в отведенное под число 15 бит) Если прибавляется отрицательное число (т.е. в сущности выполняется вычитание), то это число представляется в дополнительном коде. Предположим, нужно вычислить:

1 0 1 1 0 1 1 1 0 1 ₂ - 1 1 1 0 1 0 1 1 0 ₂(Переведите и вычислите в десятичной системе!)

Заменим вычитание сложением:

1 0 1 1 0 1 1 1 0 1 ₂+ (- 1 1 1 0 1 0 1 1 0 ₂)

Запишем эти два числа в шестнадцатиразрядную сетку:

Переведём отрицательное число в дополнительный код. Для этого:

§ получим модуль этого числа (т.е. в старший разряд запишем нуль) - 0 000000111010110;

§ заменим нули единицами, а единицы нулями (обратный код) - 1 111111000101001;

§ прибавим 1 - 1 111111000101001 + 1 = 1 111111000101010.

Полученное число – дополнительный код исходного отрицательного числа. Сложим исходное положительное число и дополнительный код отрицательного числа:

Появился лишний 17–й разряд. Отбросим его. Получим число 100000111₂ . Переведите его в десятичную систему и сравните с числом, полученным в результате вычитания. Результаты одинаковы! Если результат сложения - отрицательное число, то он представлен в дополнительном коде и для получения прямого кода необходимо выполнить его обратное преобразование!

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

В начало темы

Главная | Разделы | В начало раздела | Другие темы раздела: 1 | 2 | 3 | 4

Элементы формальной логики

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

§2. Базовые логические операции.

§3. Логические выражения, логические схемы, таблицы истинности.

§4. Логические законы и правила преобразования логических выражений.

§5. Логические основы устройства компьютера.

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

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

Истинность и ложность простых высказываний (суждений) устанавливается на основании здравого смысла:

Высказывание (суждение)	Его логическое значение
Солнце – планета солнечной системы.	Ложь
*5₁₀ 5₁₀ = 25₁₀**	Истина
Каждый параллелограмм является квадратом.	Ложь
Каждый квадрат является параллелограммом.	Истина

Уходя, гаси свет!	Не может рассматриваться в логике

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

В алгебре логики рассматривается только истинность или ложность высказывания, а не его смысл. Высказывания обозначаются именами логических переменных (а, b, c, x1, x2 и т.д.), которые могут принимать лишь два значения логических констант: «истина» ( 1 ) и «ложь» ( 0 ). Связки НЕ, И, ИЛИ заменены логическими операциями. На их основе можно записать любую логическую функцию.

Базовые логические операции.

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

Любое сложное высказывание можно рассмотреть как логическую функцию, аргументами которой являются логические переменные (простые высказывания). На входах устройства есть некоторый набор логических сигналов - логических переменных, а на выходах – набор сигналов - значений логических функций, полученных путём выполнения логических операций с входными логическими переменными. Устройство (комбинационную схему, состоящую из логических элементов) преобразователя мы пока не будем рассматривать, поэтому назовём её чёрным ящиком. Несмотря на то, что устройство преобразователя нам не известно, его работу можно описать с помощью таблицы истинности. Она показывает зависимость значений выходов от состояния входов (т.е. зависимость значений логических функций от значений логических переменных). Поясним это на примерах логических схем, реализующих базовые логические операции инверсию (НЕ), конъюнкцию (И) и дизъюнкцию (ИЛИ).

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

Инверсия.

Инвертор – логический элемент, реализующий операцию отрицания (инверсию), которая соответствует связке НЕ. Инверсию в алгебре логики обозначают знаком ¬ или надчеркиванием. Обозначение ¬Х читается НЕ Х .

В схемах и технической документации этот элемент выглядит так:

или

Его работу объясняет следующая таблица истинности:

Х	НЕ Х
0	1
1	0

Действительно, с точки зрения формальной логики не ложь – это истина, а не истина – ложь.

Конъюнкция.

Конъюнкция (логическое умножение) соответствует логической связке И. Обозначают эту операцию знаком & (иногда _^). В технической документации элемент, реализующий логическое умножение обозначают так:

или

Работу этого элемента поясняет следующая таблица истинности:

Х1	Х2	Х1 & Х2
0	0	0
0	1	0
1	0	0
1	1	1

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

Дизъюнкция.

Дизъюнкция (логическое сложение) соответствует логической связке ИЛИ. Обозначают эту операцию знаком V. В технической документации этот элемент обозначают так:

или

Работу этого элемента поясняет такая таблица истинности:

Х1	Х2	Х1 V Х2
0	0	0
0	1	1
1	0	1
1	1	1

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

Логические выражения, логические схемы, таблицы истинности.

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

Анализ логического выражения.

Рассмотрим пример задачи первого типа. Пусть задана логическая функция:

F (X1, X2, X3) = (X1 V X2) & ¬X3

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

действия в скобках;
инверсия (НЕ);
конъюнкция (И);
дизъюнкция (ИЛИ).

Для построения таблицы истинности выполним следующие действия:

во-первых, определим количество возможных комбинаций значений входных переменных по формуле: 2ⁱ = N, где N – количество возможных комбинаций (количество записей в таблице), а i – количество входных переменных (в нашем случае 2³ = 8);
во-вторых, определим количество столбцов в таблице, сложив количество входных переменных и количество логических операций (в нашем случае 3+3 = 6);
в-третьих, постоим таблицу, обозначив столбцы в соответствии с принятым порядком действий, и внесём в неё все возможные наборы входных переменных:

Х1	Х2	Х3	(Х1 V Х2)	¬Х3	(Х1 V Х2) & ¬Х3
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

в четвёртых, заполним пустые столбцы в соответствии с таблицами истинности базовых операций:

Х1	Х2	Х3	(Х1 V Х2)	¬Х3	(Х1 V Х2) & ¬Х3
0	0	0	0	1	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	1	0	0
1	0	0	1	1	1
1	0	1	1	0	0
1	1	0	1	1	1
1	1	1	1	0	0

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

Х1	Х2	Х3	(Х1 V Х2) & ¬Х3
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Преобразование логической функции в логическую схему.

Пусть задана логическая функция:

F (x1, x2, x3) = ¬((x1 & x2) v (x1 & x3))

требуется составить логическую схему. Для этого:

определим порядок выполнения операций с учетом скобок: сначала операции логического умножения во внутренних скобках, потом операция логического сложения (внешние скобки) и, в последнюю очередь, операция отрицания всего выражения;
нарисуем, входы (х1, х2, х3) и выход (F) логической схемы;
соединим входы с выходом логическими элементами в порядке, указанном в пункте 1, получим:

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

Пусть задана таблица истинности (мы вычислили её раньше):

Х1	Х2	Х3	F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

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

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

третья строка - ¬Х1 & X2 & ¬X3

пятая строка - Х1 & ¬X2 & ¬X3

седьмая строка - Х1 & X2 & ¬X3

соединим полученные выражения операцией ИЛИ:

F = (¬Х1 & X2 & ¬X3) v (X1 & ¬X2 & ¬X3) v (X1 & X2 & ¬X3)

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

Логические законы и правила преобразования логических выражений.

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

	Закон непротиворечия:		А & ¬А = 0
	Закон исключения третьего:		А V ¬А = 1
	Закон двойного отрицания:		А = ¬(¬А)
	Законы де Моргана:		¬(A v B) =¬ A &¬ B ¬(A & B) =¬ A v¬ B
	Переместительные законы:		A & B = B & A A v B = B v A
	Сочетательные законы:		(A & B) & C = A & (B & C) (A v B) v C = A v (B v C)
	Распределительные законы:		(A & B) v (A & C) = A & (B v C) (A v B) & (A v C) = A v (B & C)

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

Логические основы устройства компьютера.

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

Сумматор двоичных чисел.

В целях упрощения устройства процессора, все математические операции сводятся к сложению двоичных чисел (см. "Представления чисел в компьютере. Арифметические операции в позиционных системах счисления"). При сложении двоичных чисел в каждом разряде образуется сумма (S) и возможен перенос (P) единицы в старший разряд и перенос единицы из младшего разряда (P0). Рассмотрим таблицу:

Слагаемые		Перенос из младшего разряда	Перенос в старший разряд	Сумма
А	В	Р0	Р	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

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

Триггеры и регистры.

Элементы памяти компьютера могут быть построены на основе триггеров. Это устройство позволяет записывать, хранить, считывать и удалять 1 бит информации. В простейшем триггере два входа: S - set (установка) и R - reset (сброс) и один выход Q. Рассмотрим его схему:

В исходном состоянии, когда на оба входа схемы подан сигнал 0, триггер хранит 0. Для записи в триггер единицы нужно подать на вход S соответствующий сигнал. Рассмотрев прохождение сигнала по схеме, можно понять, что на выходе триггера Q единица сохранится и после того, как единица на входе S исчезнет, то есть триггер запомнил единицу. Для сброса информации и обнуления триггера подаётся сигнал 1 на вход R. Из нескольких триггеров можно собрать регистр - устройство для хранения нескольких бит информации.

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

В начало темы