Количество информации. Аддитивность количества информации. Оценки измерения информации

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

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

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

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

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

1 килобайт (Кбайт) = 210 байт = 1024 байт;

1 мегабайт (Мбайт) = 210 Кбайт = 1024 Кбайт;

1 гигабайт (Гбайт) = 210 Мбайт = 1024 Мбайт

Закон аддитивной информации: Количество информации H(x1, x2), необходимое для установления пары (x1, x2), равно сумме количеств информации H(x1) и H(x2), необходимых для независимого установления элементов x1, x2:

 

H(x1, x2) = H(x1) + H(x2).

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

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

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

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

ü Аддитивная. Эта мера предложена в 1928 году американским ученым Хартли, поэтому имеет второе название – мера Хартли. Мера Хартли связывает факт получения информации с уменьшением неопределенности в знаниях о некотором объекте. Пусть в каждый момент времени источник может случайным образом принять одно из конечного множества возможных состояний. Каждому состоянию источника соответствует некоторое значение.

· Статистический подход (мера Шеннона). Учитывает вероятность появления сообщений: более информативным считается то сообщение, которое менее вероятно, т.е. менее всего ожидалось. Применяется при оценке ценности (значимости) получаемой информации. Статистический подход впервые был использован К. Шенноном, который в 1948 году ввел понятие энтропии дискретного источника информации. Недостатком меры Хартли является тот факт, что никак не учитывается априорная информация о вероятностях состояния источника, которая может быть известна получателю.

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

Элементы математической логики. Логичные операции. Определения основных логичных операций

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

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

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

 

«Земля — планета солнечной системы.»	Истина
«2+8<5»	Ложь
«Всякий квадрат есть параллелограмм.»	Истина
«Каждый параллелограмм есть квадрат.»	Ложь

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

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

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

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И),дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

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

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

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

6. Булева алгебра. Булевы переменные. Основные особенности булевых операций. Булевы функции. Понятие совершенной ддизъюнктивной нормальной формы

Булева алгебра это созданная Джорджем Булем и усовершенствованная рядом других математиков система записи логических выражений. Впоследствии она выросла в важное направление науки - математическую логику. Широко применяется в программировании.

Итак, булева алгебра предполагает наличие:

высказываний;

логических операций;

функций и законов.

Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».

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

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

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

Отрицание НЕ

Отрицание — операция, применяемая к одному операнду, т.е. унарная операция.

 

. Операции отрицания задается следующей таблицей истинности:

А А’

0 1

1 0

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

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

Логическое И

Логическое И (конъюнкция) — операция, применяемая к двум операндам, т.е. бинарная операция.

А В А*В

0 0 0

0 1 0

1 0 0

1 1 1

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

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

Логическое ИЛИ

Логическое ИЛИ (дизъюнкция) — еще одна бинарная операция.

А В А,В

0 0 0

0 1 1

1 0 1

1 1 1

Производные логические операции

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

Исключающее ИЛИ

Операция исключающего ИЛИ похожа на обычную дизъюнкцию.

A B A/B

0 0 0

0 1 1

1 0 1

1 1 0

 

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

Операция импликации

Бинарная операция импликации выражается связками если…, то, из … следует, влечет.

A B A-B

0 0 1

0 1 1

1 0 0

1 1 1

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

Операция эквивалентности