Способы кодирования информации лекция

Электронные облака

Лекции

Рабочие материалы

Тесты по темам

Template tips

Задачи

Логика вычислительной техники и программирования

Лекция «Кодирование информации»

Формы представления информации

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

Текстовая информация основана на использовании цифр, знаков и т.д. Информация заложена не только в этих символах, но и в их сочетании. Так, слова «кот» и «ток» состоят из одинаковых букв, но содержат различную информацию. Благодаря взаимосвязи символов и письменному отображению речи человека, текстовая информация чрезвычайно удобна и широко используется.

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

Числовая информация представляется в виде чисел, определяющих количество чего-либо.

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

Знаки, наборы знаков и алфавиты

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

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

Знак – это элемент некоторого конечного множества отличимых друг от друга объектов – набора знаков.

Набор знаков, в котором определен линейный порядок знаков, называется алфавитом.

Примеры:

алфавит десятичных цифр: <0,1,2,3,4,5,6,7,8,9>,
алфавит заглавных латинских букв (А, В, С, D. );
алфавит заглавных букв кириллицы;
нотная запись в музыке также представляет собой своеобразный алфавит и может быть представлена латинскими буквами: <С-до, D-pe, Е-ми, F-фа, G-соль, А-ля, В-си>.

Вот некоторые наборы знаков, в которых нет какого-либо общепринятого порядка:

набор знаков клавиатуры пишущей машинки;
набор знаков мастей игральных карт;
набор знаков генетического кода, состоящий из четырех букв А,Ц,Г и Т, которые обозначают соответственно химические соединения (адеин, цитозин, гуанин и тимин).

С появлением электрического телеграфа, а позднее – технологии обработки данных возникли важные технические коды:

набор знаков азбуки Морзе;
набор знаков международного телеграфного кодаCCIT-2;
набор знаков кода IBM для пробивки перфокарт;
набор знаков 7-разрядного международного кода ISO (International Standards Organization), содержащий 128 различных символов.

Особое значение имеют наборы, состоящие из двух знаков. Такие наборы называются двоичными наборами, а сами знаки – двоичными знаками. Вместо термина «двоичный знак» часто употребляют сокращение БИТ (от английского BInary digiT – двоичная цифра).

Коды и кодирование дискретных сообщений

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

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

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

Таким образом, можно констатировать:

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

Сформулируем ряд определений.

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

Решение задач по кодированию

Разберём в качестве примеров несколько задач:

Используя шифр «Цезаря» зашифруйте слово МИР

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

Букву М заменяем на П (т.к. 3-я буква после М – П)
Букву И заменяем на М (т. к. 3-я буква после И – М)
Букву Р заменяем на У (т. к. 3-я буква после Р – У)

Ответ: код слова МИР – ПМУ

Расшифруйте слово ПМУ, закодированное с помощью шифра Цезаря

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

Букву П заменяем на М (т.к. 3-я буква перед П – М)
Букву М заменяем на И (т. к. 3-я буква перед М – И)
Букву У заменяем на Р (т. к. 3-я буква перед У – Р)

Ответ: декодируем ПМУ и получаем МИР

Закодируйте слова шифром «Винжера» (ключевое слово ВАЗА) слово МИР

Это шифр представляет шифр «Цезаря» с переменной величиной сдвига. Величину сдвига задают ключевым словом. Например, слово ВАЗА означает следующую последовательность сдвигов букв исходного текста: 3 1 9 1 3 1 9 1 и т.д.

Т.к.
В – 3-я буква алфавита
А – 1-я буква алфавита
З – 9-ая буква алфавита
А – 1-я буква алфавита

Итак, кодируем слово МИР:

первую букву М сдвигаем на 3 и получаем П
вторую букву И сдвигаем на 1 и получаем К
третью букву Р сдвигаем на 9 и получаем Щ

Источник

Лекция на тему «Кодирование информации. Измерение информации»

Кодирование информации. Измерение информации.

Кодирование информации – переход от одной формы представления информации к другой.

Способ кодирования зависит от цели, ради которой оно осуществляется: сокращение записи, шифровка. Существуют три основных способа кодирования:

Графический – с помощью рисунков или значков.

Числовой – с помощью чисел.

Символьный – с помощью символов того же алфавита, что и исходный текст.

Самое простое кодирование – перевод с одного языка на другой.

Английский писатель Конан Дойль придумал пляшущих человечков, Леонардо да Винчи писал свои записки в зеркальном отражении, американский художник Морзе придумал свою азбуку, существует флажковая азбука, штрих-код.

Компьютерное кодирование. Всю получаемую информацию компьютер превращает в свой код – всего две цифры – 1 и 0. Человечеству удалось придумать надежные технические устройства, которые распознают и сохраняют два различных состояния (цифры):

— магнитная лента. Намагничено/не намагничено. И т.д.

Все виды информации в ПК кодируются на машинном языке в виде последовательностей нулей и единиц.

Единицы измерения информации

Самая маленькая единица измерения информации – 1 бит (0 или 1).

BIT – это аббревиатура от BI nary digi T ( двоичная цифра ).

Следующая единица – байт.

BYTE – B inar Y Te rm (двоичный элемент) – это последовательность из восьми бит. Именно одним байтом кодируется один символ.

1 байт = 8 битам.

В информатике система образования кратных единиц измерения количества информации отличается от принятых в большинстве наук. Международная система единиц СИ в качестве множителей кратных единиц использует коэффициент 10 n , где n =3, 6, 9. Для компьютера кратной единицей измерения информации является коэффициент 2 n . Значит 1 байт=8 битам, будет равен 2 3 .

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

Килобайт=2 10 =1024 байт

Мегабайт=2 10 Кбайт=2 20 байт=1 048 576байт

Гигабайт=2 10 Мбайт=2 30 байт=1 073 741 824байт

Терабайт=2 10 Гбайт=2 40 байт=1 099 511 627 776байт

Петабайт; Экзабайт; Зеттабайт; Йоттабайт.

1 страница печатного текста (60 строк и 80 символов в строке)- (60*80=4800/1024=4,7 Кбайт).

ПРИМЕР: перевести 5Мбайт в байты;

Перевести 345байт в Кбайты;

Количество возможных событий и количество информации

Существует формула, которая связывает между собой количество возможных событий N и количество информации I .

ПРИМЕРЫ: 1. Вы подошли к светофору, когда горел желтый цвет. После этого загорелся зеленый. Какое количество информации вы при этом получили?

N =2; 2=2 I > I =1 бит

2. Вы подошли к светофору, когда горел красный цвет. После этого загорелся желтый. Какое количество информации вы при этом получили?

N=1; 1=2 I > 2 0 =2 I > I=0 бит

3. Группа школьников пришла в бассейн, в котором 4 дорожки для плавания. Тренер сообщил, что группа будет плавать по дорожке № 3. Сколько информации получили школьники из этого сообщения?

N =4; 4=2 I > 2 2 =2 I > I =2 бит

4. В корзине лежат 8 шаров. Все шары разного цвета .Сколько информации несет сообщение о том, что из корзины достали красный шар?

N =8; 8=2 I > 2 3 =2 I > I =3 бит

5. В школьной библиотеке 16 стеллажей с книгами. На каждом стеллаже по 8 полок. Библиотекарь сообщил Пете, что нужная ему книга находится на пятом стеллаже на третьей сверху полке. Какое количество информации библиотекарь передал Пете?

N =16*8=128; 128=2 I > 2 7 =2 I > I =7 бит

6. Сообщение о том, что ваш друг живет на 10 этаже, несет 4 бита информации. Сколько этажей в доме?

N =2 4 ; > N =16 этажей (событий)

7. Сообщение о том, что Петя живет во втором подъезде, несет 3 бита информации. Сколько подъездов в доме?

N =2 3 =8 подъездов (событий)

8. В коробке лежат 7 разноцветных карандашей. Какое количество информации содержит сообщение, что из коробки достали красный карандаш?

N=2 I ; > 7=2 I > 2 2,8 =2 I > I=2,8 бита

9. Какое количество информации несет сообщение «Встреча назначена на сентябрь»?

N=2 I ; > 12=2 I > 2 3,58 =2 I > I=3,58 бит

Источник

Лекция 2 Кодирование информации

Лекция 2

Кодирование информации

Кодирование информации — это процесс формирования определенного представления информации.

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

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

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

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

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

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

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

Например, VI = 5 + 1 = 6, а IX = 10 — 1 = 9.

В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от ее позиции. Количество используемых цифр называется основанием системы счисления. Место каждой цифры в числе называется позицией. Первая известная нам система, основанная на позиционном принципе — шестидесятeричная вавилонская. Цифры в ней были двух видов, одним из которых обозначались единицы, другим — десятки. Следы вавилонской системы сохранились до наших дней в способах измерения и записи величин углов и промежутков времени.

Однако наибольшую ценность для нас имеет индо-арабская десятичная система. В этой системе впервые использовался ноль для указания позиционной значимости величины в строке цифр. Эта система получила название десятичной, так как в ней десять цифр.

Основание системы счисления, в которой записано число, обычно обозначается нижним индексом. Например, 5557 — число, записанное в семеричной системе счисления. Если число записано в десятичной системе, то основание, как правило, не указывается. Основание системы — это тоже число, и его мы будем указывать в обычной десятичной системе. Вообще, число x может быть представлено в системе с основанием p, как x=an*pn+an-1*pn-1+ a1*p1+a0*p0, где an. a0 — цифры в представлении данного числа. Так, например,

103510=1*103+0*102+3*101+5*100;
10102 = 1*23+0*22+1*21+0*20 = 10.

Наибольший интерес при работе на ЭВМ представляют системы счисления с основаниями 2, 8 и 16. Вообще говоря, этих систем счисления обычно хватает для полноценной работы как человека, так и вычислительной машины. Однако иногда в силу различных обстоятельств все-таки приходится обращаться к другим системам счисления, например к троичной, семеричной или системе счисления по основанию 32.

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

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

Часто в информатике используют шестнадцатеричную систему, так как запись чисел в ней значительно короче записи чисел в двоичной системе. Может возникнуть вопрос: почему бы не использовать для записи очень больших чисел систему счисления, например по основанию 50? Для такой системы счисления необходимы 10 обычных цифр плюс 40 знаков, которые соответствовали бы числам от 10 до 49 и вряд ли кому-нибудь понравится работать с этими сорока знаками. Поэтому в реальной жизни системы счисления по основанию, большему 16, практически не используются.

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

Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам. Но, не всегда и не везде люди пользовались десятичной системой счисления. В Китае, например, долгое время применялась пятеричная система счисления. В ЭВМ используют двоичную систему потому, что она имеет ряд преимуществ перед другими:

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

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

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

1 + 1 = 0 (перенос в старший разряд)

Таблица умножения для двоичных чисел еще проще:

Рассмотрим подробнее, как происходит процесс умножения двоичных чисел. Пусть надо умножить число 1101 на 101 (оба числа в двоичной системе счисления). Машина делает это следующим образом: она берет число 1101 и, если первый элемент второго множителя равен 1, то она заносит его в сумму. Затем сдвигает число 1101 влево на одну позицию, получая тем самым 11010, и если, второй элемент второго множителя равен единице, то тоже заносит его в сумму. Если элемент второго множителя равен нулю, то сумма не изменяется.

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

Следует отметить, что большинство калькуляторов, реализованных на ЭВМ (в том числе и KCalc) позволяют осуществлять работу в системах счисления с основаниями 2, 8, 16 и, конечно, 10.

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

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

Пусть требуется перевести число 567 из десятичной в двоичную систему. Сначала определим максимальную степень двойки, такую, чтобы два в этой степени было меньше или равно исходному числу. В нашем случае это 9, т. к. 29=512, а 210=1024, что больше начального числа. Таким образом, мы получим число разрядов результата. Оно равно 9+1=10. Поэтому результат будет иметь вид 1ххххххххх, где вместо х могут стоять любые двоичные цифры. Найдем вторую цифру результата. Возведем двойку в степень 9 и вычтем из исходного числа: 567-29=55. Остаток сравним с числом 28=256. Так как 55 меньше 256, то девятый разряд будет нулем, т. е. результат примет вид 10хххххххх. Рассмотрим восьмой разряд. Так как 27=128>55, то и он будет нулевым.

Седьмой разряд также оказывается нулевым. Искомая двоичная запись числа принимает вид 1000хххххх. 25=32 Программы > Стандартные > Калькулятор.

Рис. 1.6. Пример, поясняющий принцип действия метода дихотомии

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

Его суть понятна из примера, представленного на рис. 1.6. В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.

Упорядочение структур данных

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

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

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

Основы логики высказываний

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

Слово логика означает систематический метод рассуждений. Мы познакомимся с одним из разделов этой науки — исчислением высказываний. Исчисление высказываний — совокупность правил, используемых для определения истинности или ложности логических предложений. Логике высказываний можно «научить» вычислительную машину, которая таким образом получает возможность «рассуждать», хотя и на весьма примитивном уровне.

Математик Джордж Буль () описал алгебру, основанную на операторах И, ИЛИ и НЕ и булевых переменных, которые принимают только два значения, например, 0 или 1.

Буль (Boole) Джордж (2 ноября 1815, Линкольн, Великобритания — 8 декабря 1864, Баллинтемпль, Ирландия), английский математик и логик, один из основоположников математической логики. Разработал алгебру логики (булеву алгебру) («Исследование законов мышления», 1854), основу функционирования цифровых компьютеров.

Джордж Буль родился в бедной рабочей семье. Первые уроки математики получил у отца и, хотя посещал местную школу, в общем его можно считать самоучкой. В 12 лет он уже знал латынь, затем овладел греческим, французским, немецким и итальянским языками. В 16 лет уже преподавал в деревенской школе, а в 20 открыл собственную школу в Линкольне. В редкие часы досуга зачитывался математическими журналами Механического института, интересовался работами математиков прошлого — Ньютона, Лапласа, Лагранжа, проблемами современной алгебры.

Начиная с 1839 года, Буль стал посылать свои работы в новый Кембриджский математический журнал. Его первая работа «Исследования по теории аналитических преобразований» касалась дифференциальных уравнений, алгебраических проблем линейной трансформации и концепции инвариантности. В своем исследовании 1844 года, опубликованном в «Философских трудах Королевского общества», он коснулся проблемы взаимодействия алгебры и исчисления. В том же году молодой ученый был награжден медалью Королевского общества за вклад в математический анализ.

Вскоре после того, как Буль убедился, что его алгебра вполне применима к логике, в 1847 году он опубликовал памфлет «Математический анализ логики», в котором высказал идею, что логика более близка к математике, чем к философии. Эта работа была чрезвычайно высоко оценена английским математиком Августом де Морганом. Благодаря этой работе Буль в 1849 году получил пост профессора математики Куинз-колледжа в графстве Корк, несмотря на то что он даже не имел университетского образования.

В 1854 году он опубликовал работу «Исследование законов мышления, базирующихся на математической логике и теории вероятностей». Работы 1847 и 1854 годов дали рождение алгебре логики, или булевой алгебре. Буль первым показал, что существует аналогия между алгебраическими и логическими действиями, так как и те, и другие предполагают лишь два варианта ответов — истина или ложь, нуль или единица. Он придумал систему обозначений и правил, пользуясь которыми можно было закодировать любые высказывания, а затем манипулировать ими как обычными числами. Булева алгебра располагала тремя основными операциями — И, ИЛИ, НЕ, которые позволяли производить сложение, вычитание, умножение, деление и сравнение символов и чисел. Таким образом, Булю удалось подробно описать двоичную систему счисления. В своей работе «Законы мышления» (1854) Буль окончательно сформулировал основы математической логики. Он также попытался сформулировать общий метод вероятностей, с помощью которого из заданной системы вероятных событий можно было бы определить вероятность последующего события, логически связанного с ними.

В 1857 году Буль был избран членом Королевского общества. Его работы «Трактат о дифференциальных уравнениях» (1859) и «Трактат о вычислении предельных разностей» (1860) оказали колоссальное влияние на развитие математики. В них нашли свое отражение наиболее важные открытия Буля. Идеи Буля нашли применение в использующих двоичный код цифровых компьютерах.

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

Высказывание или предложение — это просто утверждение, которое может быть истинно или ложно. Примерами могут служить следующие утверждения: «Сидорову 20 лет», «Сидоров — студент». Такие высказывания называются атомарными. Примером составного предложения может служить высказывание «Сидорову 20 лет и он студент», которое содержит два отдельных атомарных предложения (атома), каждое из которых может быть истинно или ложно. Если, например, Сидорову 19 лет, то высказывание «Сидорову 20 лет» ложно. Составные и атомарные предложения называются в логике формулами.

В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от «истинно» и «ложно». Используется двузначная логика: ответ, отличный от «Да», есть «Нет». Древние философы назвали этот принцип «законом исключенного третьего». Существуют другие логики, правила которых отличаются от правил исчисления высказываний, например, трехзначная логика со значениями «Да», «Нет», «Не знаю» или так называемая нечеткая логика, где можно оперировать утверждениями типа «С вероятностью 90% величина А больше 3».

В таблице приводятся обозначения, используемые для логических связок в различной литературе. Мы в дальнейшем изложении будем использовать обозначения, принятые в большинстве языков программирования. Истинное значение далее будем обозначать символом T (от True — истина), а ложное — F (от False — ложь).

Источник