Применение алгебры высказываний в информатике

Всероссийский заочный финансово-экономический  институт

 

 

 

 

Курсовая  работа

по  дисциплине: «Информатика»

на  тему:  «Применение алгебры высказываний в информатике»

 

 

 

Исполнитель:

ФНО, день

Факультет: учетно-статистический.

Специализация: «Бухгалтерский учет, анализ и аудит»

Руководитель:

 

 

 

 

Содержание.

Введение………………………………………………………………..3

Глава 1: Теоретическая  часть

1. Двоичная система счисления……………………………………………….4
2. Понятие алгебры логики………………………………8
3. Логические операции…………………………………11

1.4.   Логическая формула…………………………………..14

Заключение……………………………………………………………16

Глава 2:  Практическая часть.

2.1.  Общая характеристика задачи ……………………….18

2.2.   Описание алгоритма решения задачи………………..20

 

Список литературы…………………………………………………...24

 

 

 

 

 

Введение.

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

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

Отцом алгебры  логики по праву считается английский математик ХIХ столетия Джордж Буль.

Большой вклад  в становление и развитие алгебры  логики внесли Августус де Морган  (1806-1871), Уильям Стенли Джевонс (1835-1882), Платон Сергеевич  Порецкий (1846-1907), Чарлз Сандерс Пирс (1839-1914), Андрей Андреевич Марков (1903-1979), Андрей Николаевич Колмогоров (1903-1987) и др.

Долгое время  алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 году выдающийся американский математик и инженер Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.

Глава 1: Теоретическая часть

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

Двоичная система  счисления была придумана математиками и философами ещё до появления  компьютеров (XVII — XIX вв.). Мысль о  двоичной системе принадлежит Лейбницу, который полагал, что при трудных исследованиях в теории чисел она может иметь большие преимущества перед десятичной системой. Кроме того, при всяких арифметических операциях действия над числами, написанными в бинарной системе, облегчаются в высшей степени.

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

В двоичной системе не существует "таблицы сложения", которую нужно бы было запоминать, так как "перенос в старший разряд" начинается с 1 + 1 = 10. При сложении больших чисел необходимо лишь складывать по столбцам или разрядам, как в десятичной системе, памятуя лишь о том, что как только сумма в столбце достигает числа 2, двойка переносится в следующий столбец (влево) в виде единицы старшего разряда.

Вычитание производится так же, как в десятичной системе, не задумываясь о том, что теперь в случае необходимости нужно "занимать" из столбца слева 2, а не 10.

В двоичной таблице  умножения единственный результат, отличный от нуля, соответствует 1?1 = 1. Каких-нибудь других "табличных" произведений, требующих запоминания, не существует, так как любое целое  число больше единицы в двоичной системе по крайней мере "двузначно".

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

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

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

 Числа, записанные  в двоичной системе, требуют  большего числа знаков, чем их  аналоги в десятичной системе,  но при проектировании компьютеров,  предназначенных для работы с  числами, не превышающими 10 миллионов, оказалось, что легче оперировать с 24-разрядными двоичными числами, чем с семизначными десятичными числами. И в двоичной, и в десятичной системе суть состоит в позиционном принципе записи чисел, поэтому ясно, что современные суперкомпьютеры стали возможны благодаря тому, что четыре тысячи лет назад в Месопотамии было совершено важнейшее открытие в области обозначения чисел.

Выдающийся математик  Лейбниц говорил: "Вычисление с  помощью двоек... является для науки  основным и порождает новые открытия... При сведении чисел к простейшим началам, каковы 0 и 1, везде появляется чудесный порядок". Позже двоичная система была забыта, и только в 1936 — 1938 годах американский инженер и математик Клод Шеннон нашёл замечательные применения двоичной системы при конструировании электронных схем. Рассмотрим пример представления числа в двоичной системе счисления:

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

1. Делим 2000 на  основание новой системы счисления  — 2:

2000:2=1000(0 - остаток),

1000:2=500(0),

500:2=250(0),

250:2=125(0),

125:2=62(1),

62:2=31(0),

31:2=15(1),

15:2=7(1),

7:2=3(1),

3:2=1(1)

2. Собираем  последнее частное от деления  (всегда равно 1) и остатки от  деления и записываем их по  порядку, начиная снизу :

2000₁₀==11111010000₂

Для проверки переведём полученное число в десятичную систему счисления, для этого:

1. Выделим  двоичные разряды числа, то  есть, степени числа 2, начиная  с 0-й:

1	1	1	1	1	0	1	0	0	0	0
210	29	28	27	26	25	24	23	22	2'	2°

2. Запишем  сумму произведений 0 и 1 на соответствующую степень числа 2 (см. представление числа в р-ричной системе счисления):

0*2⁰+0*2¹+0*2²+0*2³+l*2⁴+0*2⁵+l*2⁶+l*2⁷+l*2⁸+l*2⁹+l*210= 16+64+128+256+512+1024=2000

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

Из этого  следует два вывода:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Понятие алгебры логики.

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

Алгебра логики возникла в середине ХIХ века в  трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Логическое  высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Так, например, предложение "6 — четное число" следует считать высказыванием, так как оно истинное. Предложение "Рим — столица Франции" тоже высказывание, так как оно ложное.

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

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

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения —  является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн. кв. км" в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы".

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

Истинность или ложность получаемых таким образом составных  высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание   "Тимур летом побывает и на море,  и в горах"   можно кратко записать как     А и В.  Здесь   "и"  — логическая связка,   А,   В   — логические переменные, которые мoгут принимать только два значения —   "истина"   или   "ложь",  обозначаемые, соответственно,   "1"  и   "0".