Часть 2 - Логические основы ЭВМ. Основные понятия алгебры логики (Т.В. Лукьянова - Конспект лекций по информатике)

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТМОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТИНСТИТУТ ДИСТАНЦИОННОГО И ДОПОЛНИТЕЛЬНОГООБРАЗОВАНИЯЛукьянова Т.В.КОНСПЕКТ ЛЕКЦИЙпо курсуИНФОРМАТИКАЧасть 2ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ.ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИОГЛАВЛЕНИЕ2. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ ........................................................................ 32.1. Основные понятия алгебры логики ........................................................... 32.1.1. История развития и общие понятия ................................................. 32.1.2. Алгебра логики (алгебра высказываний) ........................................ 62.1.3.

Основные логические операции....................................................... 82.1.4. Дополнительные логические операции ......................................... 102.1.5. Составление таблиц истинности сложных логическихвыражений ....................................................................................................... 132.1.6. Логические формулы ...................................................................... 152.1.7. Упрощение логических выражений ...............................................

162.2. Схемная реализация элементарных логических операций.Типовые логические узлы .................................................................................. 182.2.1. Алгебра логики и двоичное кодирование ...................................... 182.2.2. Схемная реализация логических операций ................................... 192.2.3. Базовые логические элементы........................................................ 212.2.3.1.

Схема И .................................................................................... 212.2.3.2. Схема ИЛИ .............................................................................. 222.2.3.3. Схема НЕ ................................................................................. 232.2.4. Комбинированные логические элементы ...................................... 232.2.4.1.

Схема И–НЕ............................................................................. 232.2.4.2. Схема ИЛИ–НЕ ....................................................................... 242.2.4.3. Схема Исключающее ИЛИ ..................................................... 242.2.5. Примеры применения логических элементовв вычислительной технике ............................................................................. 252.2.5.1. Триггеры ..................................................................................

252.2.5.2. Сумматор ................................................................................. 29ЛИТЕРАТУРА ........................................................................................................ 3222. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ2.1. Основные понятия алгебры логикиВ быту мы часто используем слова «логика», «логично». Логика (др.-греч.λογική – раздел философии, «наука о правильном мышлении», «искусство рассуждения» от λόγος – речь, рассуждение, мысль) – это наука о том, как правильнорассуждать, делать выводы, доказывать утверждения, наука о принципах правильного мышления.Всегда было принято считать, что знание логики обязательно для образованного человека. Сейчас, в условиях коренного изменения характера человеческого труда, ценность такого знания возрастает. Свидетельство тому – растущеезначение компьютерной грамотности, одной из теоретических основ которой является логика.Математическая логика изучает вопросы применения математическихметодов для решения логических задач и построения логических схем.

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

Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) многообщего. Он пытался соединить две эти науки, а именно свести размышление,или, вернее, умозаключение, к вычислению на основании исходных положений.3В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики – теории доказательств.В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646–1716), указавший пути для перевода логики «из словесного царства,полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно».

Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.Следует отметить, что идея использования двух символов для кодированияинформации очень стара. Австралийские аборигены считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования – азбука Морзе, гдебуквы алфавита представлены определенными сочетаниями точек и тире.После Лейбница исследования в этой области вели многие выдающиеся ученые, однако настоящий успех пришел здесь к английскому математику-самоучкеДжорджу Булю (1815–1864), целеустремленность которого не знала границ.

Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, гдесам преподавал. Он много времени уделял самообразованию и вскоре увлексяидеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», ав 1854 году появился главный его труд «Исследование законов мышления, накоторых основаны математические теории логики и вероятностей».4Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений.

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

Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, асам он по праву считается основателем математической логики и тем более важнейших ее разделов – алгебры логики (булевой алгебры) и алгебры высказываний.Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий(1846-1907), И.И. Жегалкин (1869-1947).В XX веке огромную роль в развитии математической логики сыгралД. Гильберт (1862–1943), предложивший программу формализации математики,связанную с разработкой оснований самой математики. Наконец, в последниедесятилетия XX века бурное развитие математической логики было обусловленоразвитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К.

Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).52.1.2.Алгебра логики (алгебра высказываний)Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.Высказывание (суждение) – это любое повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно. Так,например, предложение «8 – четное число» следует считать высказыванием, таккак оно истинно.

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

Логические константы (логические утверждения) – конкретные частные утверждения, которые могут принимать два значения (булевых значения)«ложь» и «истина».Примеры:«Аристотель – основоположник логики»«На яблонях растут бананы»2. Логические переменные (предикаты) – логические высказывания, значения которых меняются в зависимости от входящих в них переменных, обозначаются заглавными латинскими буквами А, В, С, D, F, …Примеры: А = «Аристотель – основоположник логики».В = «На яблонях растут бананы».Истинному высказыванию ставится в соответствие 1, ложному – 0. Такимобразом, А = 1, В = 0.63.

Логические функции (логические формулы) – сложные логические выражения, образованные из простых и связанные логическими операциям И, ИЛИ,НЕ и др.)Высказывание «Все мышки и кошки с хвостами» является сложным и состоит из двух простых высказываний: А = «Все мышки с хвостами» и В = «Всекошки с хвостами». Его можно записать в виде логической функции, значениекоторой истинно: F(A, B) =A И B.В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно.