Г. М. Нурмухамедов, Л. Ф. Соловьева

Санкт-Петербург

«БХВ-Петербург»

2012

УДК  681.3.06(075.3)

ББК  32.973.я729

          Н90

Нурмухамедов, Г. М.

 Н90  Информатика.Теоретические основы. Учебное пособие для   подготовки к ЕГЭ / Г. М. Нурмухамедов, Л. Ф. Соловьева. —   СПб.: БХВ-Петербург, 2012. — 208 с.: ил. + CD-ROM —

                       (ИиИКТ)

                           ISBN 978-5-9775-0871-1

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

Для образовательных учреждений

УДК  681.3.06(075.3)

ББК  32.973.я729 Группа подготовки издания:

                      Главный редактор                                         Екатерина Кондукова

                       Зав. редакцией                                               Елена Васильева

                      Редактор                                                         Анна Кузьмина

                      Компьютерная верстка                                 Натальи Караваевой

                      Корректор                                                       Наталия Першакова

                       Дизайн серии                                                 Инны Тачиной

                      Цветовое решение обложки и коллаж         Людмилы Соловьевой

                

Подписано в печать 30.07.12.

Формат 60х90¹/₁₆. Печать офсетная. Усл. печ. л. 13.

Тираж 1000 экз. Заказ №       

«БХВ-Петербург», 191036, Санкт-Петербург, Гончарная ул., 20.

Первая Академическая типография «Наука»

199034, Санкт-Петербург, 9 линия, 12/28

	ISBN 978-5-9775-0871-1	© Нурмухамедов Г. М., гл. 1–6, 2012
		© Соловьева Л. Ф., гл. 7, 8, 2012
		© Оформление, издательство «БХВ-Петербург», 2012
Содержание                                                                                                                 3

Оглавление

Введение ................................................................................................................5

Глава 1. Информатика и информация ............................................................9

Что такое информатика .........................................................................................9

Структура информатики .....................................................................................12

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

Искусственный интеллект ..................................................................................14

Программирование .............................................................................................15

Прикладная информатика ..................................................................................16

Вычислительная техника ....................................................................................18

Кибернетика.........................................................................................................18

Информация и ее свойства .................................................................................19

Понятие «информация» ......................................................................................19

Свойства информации ........................................................................................23

Вопросы и задания ..............................................................................................27

Глава 2. Устройство ЭВМ ................................................................................29

Современный персональный компьютер ..........................................................29

Структура ЭВМ ...................................................................................................29

Принципы работы ЭВМ .....................................................................................30

Эволюция ЭВМ ...................................................................................................34

Появление первых ЭВМ .....................................................................................34

Первое поколение ЭВМ (1955–1960) ................................................................34

Второе поколение ЭВМ (1960–1965) ................................................................35

Третье поколение ЭВМ (1965–1970) .................................................................35

Четвертое поколение ЭВМ (1970–1990) ...........................................................36

Пятое поколение ЭВМ (с 1990 г. и по настоящее время) ................................36

Сравнительные характеристики ЭВМ различных поколений ........................37

Перспективы дальнейшего развития ЭВМ .......................................................37

Программное обеспечение ЭВМ .......................................................................39 Элементная база ЭВМ ........................................................................................43

Понятие об элементной базе ЭВМ. Типы транзисторов. 

Полупроводниковые интегральные схемы .......................................................43

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

Структура и принцип работы базовых электронных элементов ....................47

Инвертор ........................................................................................................47

Вентиль ..........................................................................................................48

Триггер ...........................................................................................................50

Регистры .........................................................................................................51

Вопросы и задания ..............................................................................................52

Ответы и решения ...............................................................................................54

Глава 3. Двоичная арифметика ......................................................................57

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

Преобразование чисел в различных системах счисления ...............................61

Представление информации в ЭВМ ..................................................................64

Арифметические операции с двоичными числами .........................................67

Сложение и вычитание .......................................................................................67

4                                                                                                                 Оглавление

Умножение и деление .........................................................................................68 Вопросы и задания ..............................................................................................70 Ответы и решения ...............................................................................................72

Глава 4. Бинарная логика ...............................................................................79 Алгебра логики ....................................................................................................79 Законы алгебры логики ......................................................................................83 Однотактные и многотактные автоматы ...........................................................85 Вопросы и задания ..............................................................................................97 Ответы и решения ...............................................................................................99

Глава 5. Информационные системы ...........................................................105 Понятие «система»............................................................................................105 Понятие «информационная система» .............................................................111 Классификация информационных систем ......................................................114 Классификация по используемой технической базе ......................................114 Классификация по степени автоматизации ....................................................115 Классификация по структурированности задач .............................................117 Классификация по функциональному назначению .......................................118

Вопросы и задания ............................................................................................119

Глава 6. Информационные модели ..............................................................121 Понятие «модель» .............................................................................................121 Понятие «информационная модель» ...............................................................124 Классификация информационных моделей ...................................................126 Вопросы и задания ............................................................................................132

Глава 7. Основы теории алгоритмов ...........................................................133

Понятие алгоритма. Исполнители алгоритмов. Система команд

исполнителя .......................................................................................................133 Свойства алгоритмов и способы их записи ....................................................135 Базовые алгоритмические структуры .............................................................139 Построение алгоритмов и представление их в виде блок-схем ...................145

Исполнители алгоритмов .................................................................................148 Вопросы и задания ............................................................................................153 Ответы и решения .............................................................................................158

Глава 8. Программный способ записи алгоритмов ..................................163 Языки и среды программирования ..................................................................163 Основные элементы языка Object Pascal ........................................................165 Операторы присваивания и ввода/вывода ......................................................172

Условные операторы.Простые и составные условия.Логические

операции в условиях .........................................................................................174

Операторы цикла с параметром, предусловием и постусловием .................178

Сортировка и поиск данных в массиве ...........................................................185

Подпрограммы. Процедуры и функции. Принципы структурного

программирования ............................................................................................189

Символьные и строковые переменные. Операторы, процедуры

и функции обработки строковых переменных ...............................................194 Вопросы и задания ............................................................................................197 Ответы и решения .............................................................................................203

Заключение .......................................................................................................207 Приложение. Описание компакт-диска .........................................................208

Двоичная арифметика                                                                                                5

ВВедение

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

Книга и соответствующий курс включает 8 разделов: «Информатика и информация», «Устройство ЭВМ», «Двоичная арифметика», «Бинарная логика», «Информационные системы», «Информационные модели», «Основы теории алгоритмов», «Программный способ записи алгоритмов» и рассчитан на 70 часов учебного времени. Материал изложен компактно, в виде конспекта лекций, по- этому им удобно будет пользоваться и на уроках,  и при подготовке к экзамену по информатике.

Книга сопровождается авторским компакт-диском, содержащим электронную версию изучаемого материала.

Учебно-тематический план курса

«Информатика. Теоретические основы»

№ п/п	Тема	Количество часов
		тео- рия	прак- тика	все- го
1	Информатика и информация	2,5	1,5	4
1.1	Что такое информатика	0,5		0,5
1.2	Структура информатики	1	0,5	1,5
1.3	Информация и ее свойства	1	1	2
2	Устройство ЭВМ	5,5	3,5	9
2.1	Современный персональный  компьютер	0,5		0,5

6                                                                                                                      Введение

Продолжение

№ п/п	Тема	Количество часов
		тео- рия	прак- тика	все- го
2.3	Программное обеспечение ЭВМ	1,5	0,5	2
2.4	Эволюция ЭВМ	0,5	0,5	1
2.5	Элементная база ЭВМ	1	1	2
2.6	Технология изготовления полупроводниковых интегральных схем	0,5	0,5	1
2.7	Структура и принципы работы  базовых электронных элементов	1	1	2
3	Двоичная арифметика	3	3	6
3.1	Системы счисления	0,5	0,5	1
3.2	Представление информации  в ЭВМ	1	1	2
3.3	Преобразование чисел в различных системах счисления	1,5	1,5	3
4	Бинарная логика	6	5	11
4.1	Алгебра логики	1	1	2
4.2	Законы алгебры логики	2	2	4
4.3	Однотактные и многотактные  автоматы	3	2	5
5	Информационные системы	4		4
5.1	Понятие «система»	2		2
5.2	Понятие «информационная система»	1		1
5.3	Классификация информационных систем	1		1
6	Информационные модели	4		4
6.1	Понятие «модель»	1		1
6.2	Понятие «информационная  модель»	1		1
6.3	Классификация информационных моделей	2		2

Введение                                                                                                                       7

Окончание

№ п/п	Тема	Количество часов
		тео- рия	прак- тика	все- го
7	Основы теории алгоритмов	6	6	12
7.1	Понятие алгоритма. Исполнители алгоритмов. Система команд исполнителя	0,5	0,5	1
7.2	Свойства алгоритмов и способы  их записи	1	0,5	1,5
7.3	Базовые алгоритмические  структуры	1,5	1,5	3
7.4	Построение алгоритмов и представление их в виде блок-схем	1,5	1,5	3
7.5	Исполнители алгоритмов	1,5	2	3,5
8	Программный способ записи  алгоритмов	8	10	18
8.1	Языки и среды программирования	0,5		0,5
8.2	Основные элементы языка Object Pascal	1	1	2
8.3	Операторы присваивания и ввода/ вывода	0,5	0,5	1
8.4	Условные операторы. Простые и составные условия, логические операции в условиях	1,5	1,5	3
8.5	Операторы цикла с параметром, предусловием и постусловием	1,5	2	3,5
8.6	Сортировка и поиск данных в массиве	1	2	3
8.7	Подпрограммы. Процедуры и функции. Принципы структурного программирования	1	1,5	2,5
8.8	Символьные и строковые переменные. Операторы, процедуры и функции обработки строковых переменных	1	1,5	2,5
	Резерв	2		2
	ИТОГО	41	29	70

 

Глава 1

ИнформатИка И ИнформацИя

Информатика и информация                                                                                    9

Что такое информатика

Слово «информатика» (informatique) возникло в 1960-х гг. во Франции как объединение двух терминов — «информация» (infor mation) и «автоматика» (automatique) и первоначально означало «информационная автоматика» или «автоматизированная переработка информации». Этот термин вошел в обиход и в других странах, в том числе в СССР, а затем и в России. Однако в англо- язычных странах используется другой термин — computer science (вычислительная наука).

Информатика в современном ее представлении родилась с появлением ЭВМ, развивается вместе с развитием компьютерной техники и не может без нее существовать. За прошедшие полвека содержание понятия «информатика» трансформировалось так, что теперь информатика представляет собой единство разнообразных отраслей науки, техники и производства, связанных с переработкой информации во всех сферах человеческой деятельности.

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

Определение

Информатика — комплексная научная и инженерная дисциплина, изучающая все аспекты разработки, проектирования, создания, оценки, функционирования, основанных на ЭВМ систем переработки информации, их применения и воздействия на различные области социальной практики. (Принято на сессии годичного собрания Академии наук СССР в 1983 г.)

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

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

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

 Рекомендуемая литература

1.   Информатика: Учебник / Под ред. Н. В. Макаровой. — М.: Финансы и статистика, 1999.

2.   Информатика: Энциклопедический словарь для начинающих / Сост. Д. А. Поспелов. — М.: Педагогика-Пресс, 1994.

3.   Фридланд А. Я. Информатика: процессы, системы, ресурсы. — М.: БИНОМ. Лаборатория знаний, 2003.

Структура информатики

На рис. 1.1 представлена структура информатики как научной и прикладной дисциплины, в которой выделены шесть основных научно-технических направлений:

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

2.    Искусственный интеллект.

3.    Программирование.

4.    Прикладная информатика.

5.    Вычислительная техника.

6.    Кибернетика.

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

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

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

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

Подраздел «Теория информации» (а также «Теория кодирования и передачи информации») изучает информацию в виде абстрактного объекта, лишенного конкретного содержания. Здесь исследуются

Рис. 1.1. Структура дисциплины «Информатика»

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

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

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

Искусственный интеллект

Это направление информатики — одно из самых молодых, оно возникло в середине 1970-х гг. Однако именно искусственный интеллект определяет стратегические направления развития информатики.

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

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

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

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

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

1.    Она адаптирована для любого пользователя.

2.    Она позволяет получать не только новые знания, но и профессиональные умения и навыки, связанные с данными знаниями, т. е. обеспечивает ответ не только на вопрос «что знать?», но и «как знать?».

3.    Она передает не только знания, но и пояснения и разъяснения,

т. е. обладает обучающей функцией.

Программирование

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

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

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

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

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

Прикладная информатика

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

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

Структурно ИС состоит из технического, математического, программного, информационного и организационного обеспечения.

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

Математическое и программное обеспечение — это совокупность используемых математических методов, моделей, алгоритмов и программ.

Информационное обеспечение — это банк данных, блок расшифровки запросов и блок поиска.

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

Различные типы информационных систем перечислены ранее в этой главе.

Вычислительная техника

Материал, посвященный вычислительной технике, будет рассмотрен в главе 2 «Устройство ЭВМ».

Кибернетика

Термин «кибернетика» (от греч. κυβερνητης — кормчий) появился летом 1947 г. как результат обсуждения новой терминологии группой ученых во главе с Норбертом Винером, в течение целого ряда лет проводивших исследования в различных областях научных знаний (математической статистики, электросвязи, нейрофизиологии и др.), связанных с вопросами управления системами и объектами с помощью различного рода информационных сигналов. В 1948 г. Н. Винер опубликовал свою монографию под названием «Кибернетика, или управление и связь в животном и машине». Идея «общей теории управления» получила новое развитие с появлением компьютеров, способных решать самые разные задачи.

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

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

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

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

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

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

Информация и ее свойства

Понятие «информация»

Слово «информация» относится к основополагающим терминам информатики и в переводе с латинского означает «сообщение», «разъяснение». До появления компьютерной техники это слово использовалось редко — в основном в специальной и технической литературе.

Впервые термин «информация» приводится в книге Н. Винера «Кибернетика», однако лишь в узком смысле — в составе понятия «количество информации».

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

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

В книге В. Шнейдерова «Занимательная информатика» [8] отмечено, что в настоящее время известно более четырехсот определений термина «информация». Для примера приведем некоторые из них.

Определение

Информация: первоначально — сведения, передаваемые людьми, устным, письменным или другим способом (с помощью условных сигналов, технических средств и т. д.); с середины  в. — общенаучное понятие, включающее обмен сведениями между людьми, человеком и автоматом, автоматом и автоматом; обмен сигналами в животном и растительном мире; передачу признаков от клетки к клетке, от организма к организму [1].

Определение

Информация — содержание сообщения или сигнала, сведения, рассматриваемые в процессе их передачи или восприятия; одна из исходных общенаучных категорий, отражающая структуру материи и способы ее познания, несводимая к другим, более простым понятиям [5].

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

Подробно и обстоятельно понятие «информация» исследовано в книге [6]. Здесь же мы приведем лишь выводы из этого исследования.

1.    Предлагается считать понятие «информация» субъективным понятием в том смысле, что понимание происходит только в аппарате мышления человека.

2.    Человек не может получать информацию непосредственно. Он лишь может на основании каких-либо данных, представленных в виде сигналов, документов и т. д., сформировать у себя в аппарате мышления информацию о чем-либо.

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

4.    Предложена модель процесса получения информации человеком:

внешние сигналы

↓ данные

↓

неформальный смысл, выраженный в ощущениях

↓

полуформальный смысл, выраженный в словах

↓

формальный смысл, выраженный в терминах логики

5.    Предложена модель передачи информации от человека:

неформальный смысл

↓

полуформальный смысл, выраженный в тексте

↓

формальный смысл, выраженный в алгоритме

↓ данные

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

Свойства информации

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

1.    Синтаксическая адекватность — отображает формально- структурные характеристики информации и не затрагивает ее смыслового содержания.

2.    Семантическая (смысловая) адекватность — определяет степень соответствия информации об объекте самому этому объекту.

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

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

Что же можно измерить в ней?

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

Существует и другой количественный подход — кибернетиче ский, который учитывает ценность информации (ее прагматиче скую адекватность). Впервые он был предложен в работах К. Шеннона [7] и Н. Винера [2]. Изучая системы передачи информации, К. Шеннон пришел к выводу, что каждое элементарное сообщение на выходе системы уменьшает неопределенность исходного множества сообщений, причем собственно смысловой аспект сообщения в этом случае не имеет никакого значения. За единицу количества ин формации им было предложено принять «количество информации, передаваемое при одном выборе между двумя равновероятными альтернативами». Эта наименьшая единица информации называется битом. Информация в один бит уменьшает неопределенность информационной системы в два раза. Для вычисления среднего количества информации, связанного с положительным исходом некоторого события x из множества m событий, К. Шеннон предложил формулу:

H_x =−∑ p_i log p_i,

где p_i — вероятность i-го события.

Эта формула (получившая название «формулы Шеннона») характеризует энтропию (меру неопределенности) системы. Изначально это понятие появилось в физике и характеризует степень неупорядоченности (неопределенности) микросостояния, в котором система (например, термодинамическая) может находиться в данный момент времени.

Значение H_x достигает максимума для равновероятных событий, т. е. при p_i =1/ m формула Шеннона упрощается:

H_max =−log p_i = logm (формула Р. Хартли).

П р и м е р. Рассмотрим систему с 256 возможными состояниями, например расширенную кодовую таблицу символов. Тогда H_max будет равно 8 битам. Другими словами, восьми битов достаточно, чтобы точно описать исход любого события, связанного с кодовой таблицей (например, выборку определенного символа из этой таблицы).

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

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

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

Репрезентативность информации связана с правильностью ее отбора и формирования для адекватного отражения свойств объекта.

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

 Рекомендуемая литература

1.   Большой энциклопедический словарь. — М.: Большая Российская Энциклопедия, 1998.

2.   Винер Н. Кибернетика, или управление и связь в животном и машине: Пер. с англ. — М.: Советское радио, 1958.

3.   Информатика: Учебник / Под ред. Н. В. Макаровой. — М.: Финансы и статистика, 1999.

4.   Информатика: Энциклопедический словарь для начинающих / Сост. Д. А. Поспелов. — М.: Педагогика-Пресс, 1994.

5.   Математический энциклопедический словарь. — М.: Советская Энциклопедия, 1988.

6.   Фридланд А. Я. Информатика: процессы, системы, ресурсы. —

М.: БИНОМ. Лаборатория знаний, 2003.

7.   Шеннон К. Работы по теории информации и кибернетике: Пер. с англ. — М.: Иностранная литература, 1963.

8.   Шнейдеров В. С. Занимательная информатика. — СПб.: Политехника, 1994.

Вопросы и задания

1.        В этой главе было приведено несколько различных определений понятия «информатика». Какое из них, на ваш взгляд, наиболее точно и полно отражает сущность этого понятия?

2.        Используя древовидную структуру направлений развития современной информатики (см. рис. 1.1), укажите в ней разделы научной информатики. Обоснуйте свой выбор.

3.        В чем состоит принципиальное различие между кибернетикой и информатикой?

4.        В чем заключается различие между направлениями «Искусственный интеллект» и «Кибернетика»?

5.        В этой главе приведено несколько разных определений и толкований понятия «информация». Какое из них вам представляется наиболее полно отражающим сущность этого понятия?

6.        Охарактеризуйте основные свойства информации.

7.        Какие подходы можно использовать для измерения количества информации?

8.        С чем связано появление такой единицы измерения количества информации как бит?

 

Глава 2

Устройство ЭвМ

Современный персональный компьютер

Вопрос для обсуждения

1.   Каким        стал       бы          компьютер,          если       бы           вместо  двоичной             элементной         базы      для   него       была      использована     многозначная?

Устройство ЭВМ                                                                                                        29

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

Структура ЭВМ

Структура ЭВМ (рис. 2.1) не зависит от ее технических характеристик, размеров и назначения — она едина для любой ЭВМ!

Рис. 2.1.          Структура              ЭВМ        (общий   вид)

Процессор является «сердцем» ЭВМ. Он исполняет программы и управляет работой остальных узлов машины.

Память подразделяется на внутреннюю (оперативную и постоянную) и долговременную.

Устройства ввода/вывода обеспечивают взаимодействие ЭВМ с человеком и с различными внешними информационными объектами.

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

Принципы работы ЭВМ

Принципы работы ЭВМ мы рассмотрим на примере персонального компьютера (ПЭВМ, ПК).

На рис. 2.2 представлена структура ПК. Его основу составляет системный блок, в котором размещены микропроцессор (МП), блоки оперативного запоминающего устройства (ОЗУ) и постоянного запоминающего устройства (ПЗУ), устройство долговременной памяти на жестком магнитном диске (винчестер), устройства для чтения/записи компакт-дисков (compact disk, CD) и дискет (накопители на гибких магнитных дисках, НГМД). В последние годы на смену дискетам пришли флеш-накопители (флешки), имеющие емкость от 4 до 256 Гбайт и подключаемые к компьютеру через разъем USB.

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

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

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

Упрощенная схема микропроцессора представлена на рис. 2.3^[1] (выделена штриховой линией с надписью «ЦП»). В его состав входят:

r арифметико-логическое устройство (АЛУ), выполняющее арифметические и логические операции над двоичными числами;

r блок регистров общего назначения (РОН), используемых для временного хранения обрабатываемой информации (R0–R5), указателя стека (R6) и счетчика команд (R7);

r устройство управления (УУ), определяющее порядок работы всех узлов микропроцессора.

Одной из важнейших характеристик микропроцессора является его разрядность, определяемая количеством разрядов АЛУ и РОН. Современные микропроцессоры могут иметь разрядность 16, 32 и 64 бит, а также поддерживать до 200 и более различных внутренних команд.

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

Программы и данные размещаются в 8-битовых ячейках ОЗУ, адресация которых организована по байтам. Таким образом, 16-разрядный процессор за один такт извлекает информацию из двух таких ячеек, а 32-разрядный процессор — из четырех ячеек ОЗУ.

Команды микропроцессора бывают безадресными, одноадресными и двухадресными. Например, двухадресная команда сложения выглядит так:

ADD

Адрес источника

Адрес приемника

Выполнение микропроцессором любой команды состоит из двух этапов: фазы выборки и фазы исполнения.

Фаза выборки начинается по сигналу начала цикла команды. При этом содержимое счетчика команд указывает на ее адрес в ОЗУ (например, 1000). Как только сигнал по шине адресов поступает в ОЗУ, содержимое счетчика команд увеличивается на 2 (для 16-разрядного процессора) и указывает на адрес следующей команды. Из ОЗУ по шине данных команда поступает в регистр команд микропроцессора. В данном случае это команда ADD(R0), R1.

Фаза исполнения начинается с расшифровки полученной команды. В нашем примере код операции ADD предписывает АЛУ сложить содержимое, которое находится в ОЗУ по адресу, содержащемуся в регистре источника, хранимому в регистре R0, с содержимым, размещенным в регистре R1, а результат поместить в регистр приемника R1.

На этом фаза исполнения данной команды завершается, а микропроцессор готов к выполнению следующей команды, указанной в счетчике команд (СК + 2) и т. д.

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

Итак, компьютер функционирует лишь благодаря программному обеспечению, без которого он бесполезен.

Эволюция ЭВМ

Эволюцию ЭВМ рассмотрим на примере больших универсальных ЭВМ фирмы IBM.

Появление первых ЭВМ

Становление вычислительной техники началось с появления в 1946 г. первой ЭВМ «ЭНИАК» и продолжалось до 1955 г., когда сформировалась архитектура вычислительных машин и был принят принцип модульности, согласно которому ЭВМ конструировались в виде набора отдельных функционально завершенных блоков.

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

Обобщенным параметром любого компьютера является его вычислительная мощность, определяемая быстродействием и объемом внутренней памяти ЭВМ. Первые ЭВМ:

r ЭНИАК (1946);

r МЭСМ (конструктор — академик С. А. Лебедев, 1951).

Первое поколение ЭВМ (1955–1960)

Первое поколение ЭВМ строилось на электровакуумных лампах (радиолампах) и дискретных радиодеталях. В качестве внутренней памяти использовались магнитные барабаны. Внешняя память была построена на магнитных лентах. Информация в машину вносилась с бумажных перфолент и перфокарт. Выходная информация распечатывалась на бумажном но- сителе.

29 апреля 1952 г. появилась первая ЭВМ фирмы IBM — IBM 701. В качестве устройства оперативной памяти в ней использовался магнитный барабан. Емкость ОЗУ составляла 20 480 байт, а производительность — 8000 оп./с.

Второе поколение ЭВМ (1960–1965)

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

IBM 360/40 была изготовлена в 1964 г. Для разных моделей она комбинировалась из 19 блоков центрального процессора и 40 типов периферии. Емкость ОЗУ — 256 Кбайт, производительность — 246 тыс. оп./с.

Третье поколение ЭВМ (1965–1970)

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

IBM 370/145 была изготовлена в 1970 г. В ней впервые применены интегральные схемы с 1400 элементами на одном кристалле. Емкость ОЗУ — 512 Кбайт, производительность — 1,23 млн оп./с.

Четвертое поколение ЭВМ (1970–1990)

В ЭВМ этого поколения, построенного на базе кремниевой технологии, применяются большие (БИС) и сверхбольшие (СБИС) интегральные схемы. В машинах этого поколения стали впервые использоваться микропроцессоры. Степень их интеграции росла лавинообразно, например, динамика изменения величины памяти на однокристальных БИС выглядит так:

1970 г. — 128 бит;

1978 г. — 64 Кбит;

1982 г. — 228 Кбит; 1984 г. — 1 Мбит.

IBM 370/168 была изготовлена в 1972 г. и являлась одной из самых распространенных моделей. Емкость ОЗУ — 8,2 Мбайт, производительность — 7,7 млн оп./с.

Пятое поколение ЭВМ (с 1990 г. и по настоящее время)

В ЭВМ пятого поколения используются как универсальные, так и специализированные сверхбольшие (СБИС) и ультрабольшие (УБИС) интегральные схемы широкой номенклатуры. Монтаж УБИС ведется на многослойных печатных платах, в свою очередь, спрессованных в виде «сэндвича» толщиной до 100 слоев.

EServer z990 изготовлен в 2003 г. Имеет вес 2000 кг и потребляемую мощность 21 кВт, занимает площадь 2,5 кв. м и имеет высоту 1,94 м. Емкость ОЗУ — 256 Гбайт, производительность — 9 млрд оп./с.

Сравнительные характеристики ЭВМ  различных поколений

В табл. 2.1 приведены характеристики разных поколений ЭВМ.

Таблица 2.1. Сравнительные характеристики ЭВМ

Поколение ЭВМ	Тип ЭВМ	Год выпуска	Объем ОЗУ	Быстро- действие (оп./с)
1	IBM-701	1952	20,5 Кбайт	8 тыс.
2	IBM-360/140	1964	256 Кбайт	246 тыс.
3	IBM-360/145	1970	512 Кбайт	1,23 млн
4	IBM-370/168	1972	8,2 Мбайт	7,7 млн
5	eServer z990, модель D32	2003	256 Гбайт	9 млрд

Перспективы дальнейшего  развития ЭВМ

В настоящее время достигнуты очень высокие характеристики ЭВМ по быстродействию и объему памяти. Линейные размеры микроэлементов достигли 0,09 мкм (физический предел формирования линий рисунка схемы на кристалле — примерно 0,03 мкм). Рост параметров ЭВМ возможен также за счет улучшения схемотехнических решений и методов размещения микросхем на платах. По мнению некоторых специалистов, кремниевая технология исчерпает себя к 2015 г.

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

Программное обеспечение ЭВМ

На рис. 2.4 представлена классификация программного обеспечения (ПО) для современных персональных компьютеров.

Программное обеспечение условно можно разделить на три больших класса:

r системное ПО; r прикладное ПО;

r инструментальное ПО.

Системное программное обеспечение, в свою очередь, состоит из базового ПО и сервисного ПО.

Базовое ПО поставляется вместе с компьютером и обеспечивает его работоспособность. В состав базового ПО входят операционная система (ОС), операционная оболочка и сетевые программные средства.

Операционная система предназначена:

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

r для обеспечения функционирования других программ на компьютере;

r для диагностики и контроля работоспособности блоков и узлов компьютера;

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

В настоящее время разработано большое количество ОС, различающихся по возможностям их функционирования: одно- и многопользовательские, одно- и многозадачные, поддерживающие сетевые режимы работы и др. Широкое применение нашли ОС семейств: Windows, Linux, Mac OS, NetWare, OS/2, Solaris, QNX, MS-DOS и др.

Операционная оболочка предназначена для обеспечения более комфортного общения пользователя с ЭВМ. Она снимает проблему управления компьютером путем ввода текстовых команд в командной строке и их запуска на исполнение. В оболочке может быть реализован текстовый или/и графический интерфейс. Например, в ОС MS-DOS в качестве такой оболочки выступает программа Norton Commander, реализующая текстовый интерфейс в виде двух таблиц с каталогами файловой системы, а в ОС Windows и M S интерфейс встроенной операционной оболочки — графический (хотя имеется и оболочка с текстовым интерфейсом, реализуемая программой Windows Commander).

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

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

В настоящее время такие известные операционные системы как Windows XP, Windows Vista, Windows 7, Mac OS и некоторые другие включают в себя все вышеперечисленные компоненты системного ПО, являясь по существу комплексным системным ПО.

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

ПО общего назначения обычно комплектуется в пакеты. Например, для ОС Windows выпущен пакет прикладных программ Mirosoft ffie, включающий в себя программные средства для создания текстовых документов (Word), электронных таблиц (Excel), презентаций (PowerPoint), публикаций (Publisher), базы данных (Access), а также для подготовки и редактирования Webдокументов (rote). В этот пакет еще входит ряд дополнительных программных средств: Picture Mer — для просмотра, систематизации и редактирования графики; Document Imi — для просмотра, чтения и распознавания текста в графических документах и факсах; Domet Si — для сканирования многостраничных документов и распознавания текста в графических документах; файлы библиотеки картинок и др.

ПО мультимедиа предназначено для создания и использования (отображения, воспроизведения) двух- и трехмерной графики, анимации, аудио- и видеофайлов. Примерами такого ПО являются широко известные программные комплексы oe Photoshop — для создания и редактирования двухмерной графики, 3D Stio M — для трехмерного моделирования и проектирования, Mromei s — для создания анимаций и мультипликаций. Для обработки и редактирования звука используются такие программы как Nero, Audio Editor Gold, для воспроизведения звука и видео — программы Windows Media Player, QuickTime Player и др.

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

Значительное количество прикладных программ разработано в качестве информационных систем (см. главу 1 «Информатика и информация»), к которым относятся также информационнопоисковые, издательские и прочие системы.

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

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

В процессе становления и развития вычислительной техники возникали и развивались также языки программирования. Некоторые из них затем изменялись, трансформировались, интегрировались с другими, а некоторые — исчезали. Сегодня у программистов имеется богатый арсенал языков программирования на все случаи программистской жизни: ассемблер, Бейсик, C++, Delphi, ortr, Java, Pascal и др. Каждый из этих языков программирования имеет целый ряд модификаций (например, для Бейсика — GW-Basic, QBasic, Visual Basic и др.), которые по возможностям и свойствам существенно отличаются друг от друга.

Языки программирования можно разделить на машинно-зависимые (низкого уровня) и машинно-независимые (высокого уровня). К языкам низкого уровня относятся:

r машинные языки — запись команд в двоичных кодах в виде нулей и единиц;

r машинно-ориентированные языки (ассемблеры), реализующие запись команд в так называемых мнемокодах, соответствующих системе команд конкретного процессора (например, мнемокод «сложить» записан как ADD, мнемокод «очистить» — как DEL и т. д.).

К языкам высокого уровня относятся:

r алгоритмические языки — перевод алгоритмов с языка математики на язык программных кодов;

r процедурно-ориентированные языки — запись программ в виде набора процедур;

r проблемно-ориентированные языки — языки, предназначенные для решения определенного класса задач.

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

Такой процесс осуществляется, например, при написании программы на языке ortr и называется компилированием. В других языках высокого уровня (например, в Бейсике) трансляция исходного кода в исполняемый происходит последовательно для каждой команды (оператора). Такой способ трансляции называется интерпретацией.

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

Система программирования обычно состоит из:

r языковых средств разработчика программ;

r текстового редактора для написания текста программ;

r компилятора;

r редактора связей;

r отладчика;

r оптимизатора кода программ;

r набора библиотек;

r справочной системы и др.

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

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

Элементная база ЭВМ

Понятие об элементной базе ЭВМ. Типы транзисторов. Полупроводниковые

интегральные схемы

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

Основой большинства элементов современных ЭВМ является транзистор — полупроводниковый прибор, способный преобразовывать электрические сигналы. Существуют два типа транзисторов: биполярный, с двумя взаимодействующими электроннодырочными переходами (рис. 2.5), и униполярный, или полевой

(рис. 2.6).

В полевом транзисторе управляющий электрод (затвор) изолирован от тела полупроводника слоем диэлектрика (обычно двуокиси кремния), поэтому такой транзистор также называют МОП- или МДП-транзистором, подчеркивая его структуру: «металл — окисел (диэлектрик) — полупроводник». Из сравнения рис. 2.5 и 2.6 видно, что изготовить МДП-транзистор проще, чем биполярный, т. к. в этом случае на поверхности подложки (полупроводника n-типа) достаточно лишь сформировать две небольшие области полупроводника р-типа и покрыть всю поверхность слоем окисной пленки, в то время как для изготовления биполярного транзистора нужно провести два процесса формирования микрообластей с разной проводимостью.

Интегральная схема (ИС) содержит логический, запоминающий или какой-либо другой элемент цифрового устройства. Конструктивно ИС выполняется на монокристаллической пластинке кремния размером в несколько квадратных миллиметров путем формирования с помощью специальной технологии отдельных микрокомпонентов. Количество элементов в ИС характеризует ее степень интеграции. В соответствии с ним все ИС условно делят на малые (МИС — до 10² элементов на кристалле), средние (СИС — до 10³ элементов), большие (БИС — до 10⁴ элементов), сверхбольшие (СБИС — до 10⁶ элементов), ультрабольшие (УБИС — до 10⁹ элементов) и гигабольшие (ГБИС — свыше 10⁹ элементов на кристалле). В настоящее время по МДП-технологии разработаны сверхбольшие и ультрабольшие интегральные схемы (СБИС и УБИС).

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

Однако МДП ИС имеют и недостатки. Главный из них — сравнительно низкое быстродействие. По этому параметру биполярные ИС превосходят МДП в 10 и более раз, однако потребляемая ими энергия существенно больше, чем для МДП ИС.

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

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

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

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

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

Наряду с фотолитографией используется электронолитография, позволяющая получать элементы рисунка толщиной до 0,1 мкм, и рентгенолитография с длиной волны излучения 0,003– 0,005 мкм, дающая возможность получать размеры элементов менее 0,1 мкм.

Линейные размеры микроэлементов последних СБИС и УБИС достигли величины порядка 0,09 мкм. По оценкам специалистов верхний предел ширины линий рисунка составит около 0,03– 0,05 мкм. Фактически это физический предел малости рисунка ИС. Столь малые размеры деталей полупроводниковых приборов позволяют на одном кристалле размером 1 см² разместить сотни миллионов отдельных компонентов электронной схемы.

По планарной технологии ИС обычно изготовляют целыми группами, когда на одной пластине кремния диаметром 150–200 мм одновременно формируются десятки и сотни отдельных ИС. Для размещения схемных деталей ИС средней степени интеграции при этом отводится площадь 2,5×2,5 мм², для БИС — площадь 6×6 мм², для СБИС — до 10×10 мм², а для УБИС свыше 1 см². После завершения процесса формирования ИС пластина кремния разрезается на отдельные кристаллы, которые затем монтируются в пластмассовые корпуса и проходят тщательный контроль на пригодность схемы к работе.

Структура и принцип работы базовых электронных элементов

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

Инвертор

На рис. 2.7, а представлена схема электронного ключа на биполярном транзисторе, реализующая логическую функцию «НЕ» (отрицание), а на рис. 2.7, б приведено его условное обозначение.

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

                                  а                                                                   б

Рис. 2.7.          Инвертор

за счет падения напряжения на сопротивлении нагрузки R_н устано вится напряжение низкого уровня (логический 0).Таким образом, данная схема преобразует (инвертирует) сигналы одного уровня в другой, тем самым выполняя логическую функцию «НЕ».

Вентиль

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

                                   а                                                                   б

Рис. 2.8.          Вентиль «И»

Функция «И» — это логическое умножение: ее результат С равен единице, когда оба аргумента (и А, и В) равны единице.

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

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

                                   а                                                                   б

Рис. 2.9.          Вентиль «ИЛИ»

Функция «ИЛИ» — это логическое сложение, ее результат С равен единице, если хотя бы один из аргументов (A или B) равен единице.

Здесь транзисторы включены параллельно друг другу. Если оба они закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический 0). Но достаточно подать сигнал высокого уровня (логическую 1) на один из транзисторов (любой), и схема начнет пропускать ток, а на сопротивлении нагрузки R_н установится сигнал высокого уровня (логическая 1).

В разделе, посвященном законам алгебры логики (см. гла- ву 4) показано, что любая сложная логическая функция может быть представлена как комбинация функций «НЕ», «И» и «ИЛИ», так что из инвертора и соответствующих вентилей можно построить электронную логическую схему, выполняющую любое заплани рованное действие. В этом же разделе показано, что вместо трех перечисленных логических функций можно использовать всего одну комбинированную функцию «И-НЕ» или «ИЛИ-НЕ». Для получения вентилей «И-НЕ» и «ИЛИ-НЕ» из «И» и «ИЛИ» достаточно перенести сопротивление нагрузки R_н из эмиттерной цепи в коллекторную (как в схеме инвертора).

Триггер

Триггером называется электронное устройство с двумя устойчивыми состояниями, одно из которых характеризуется высоким (логическая 1), а второе — низким (логический 0) уровнем выходного сигнала.

Триггер состоит из двух вентилей. На рис. 2.10, а показан триггер, составленный из двух вентилей «ИЛИ-НЕ» (аналогично для этой цели можно использовать и вентили «И-НЕ»), а на рис. 2.10, б — его условное обозначение.

                                   а                                                                   б

Рис. 2.10.               Триггер

Рассмотрим работу этой схемы (соответствующая анимация имеется на диске, прилагаемом к книге). Пусть в начальный момент времени входы R, S и выход Q имеют низкий логический уровень.

Для переключения триггера в состояние Q = 1 необходимо на вход S подать логическую 1. На входе соответствующего вентиля будут действовать входные логические сигналы: 0 (с выхода Q)

и 1 (со входа S). На его выходе возникает инвертированная 1, т. е. 0. Следовательно, через некоторое время ∆τ, в течение которого входной сигнал S = 1 достигнет выхода вентиля, состояние

выхода Q изменится с 1 на 0.

Теперь на входы второго вентиля будет действовать новая пара

сигналов: 0 на вход R и 0 с выхода Q . Следовательно, еще через время ∆τ на выходе этого вентиля возникнет инвертированный сигнал 0, т. е. 1.

Таким образом, через время 2∆τ после подачи входного сигнала S = 1 на выходе Q триггера логический 0 изменится на логическую 1.

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

Триггер может работать бесперебойно лишь с периодом, не меньшим 4∆τ. В современных транзисторных вентилях ∆τ составляет единицы наносекунд (10^–9 с), поэтому быстродействие электронных элементов вычислительных устройств очень велико и достигает сотен миллионов переключений в секунду.

Регистры

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

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

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

Вопросы и задания

1.       Из каких основных узлов состоит ЭВМ?

2.       Компьютер и мобильный телефон содержат одинаковые узлы: микропроцессор, память, устройства ввода/вывода. Есть ли между ними принципиальные отличия? Если есть, то в чем?

3.       В чем разница между внутренней и внешней памятью ЭВМ? На какие виды разделяется внутренняя память? Назовите внешние виды памяти?

4.       Какие функции в компьютере выполняет микропроцессор?

5.       Как осуществляется программный принцип работы компьютера?

6.       На какие классы и подклассы разделяется программное обеспечение ЭВМ?

7.       Каково назначение и структура системного программного обес- печения?

8.       Каково назначение и структура прикладного программного обеспечения?

9.       В чем разница между языком и системой программирования?

10.   По каким признакам история развития вычислительной техники ассоциируется с поколениями ЭВМ?

11.   Почему вычислительная мощность является основным параметром ЭВМ?

12.   Каковы ближайшие перспективы развития вычислительной техники?

13.   Из каких элементов («кирпичиков») строится компьютер?

14.   Чем отличается технология производства элементов вычислительной техники от технологии производства деталей автомобиля?

15.   В чем общность и различие базовых электронных элементов?

16.   Как устроен триггер и где он используется?

17.   Используя табл. 2.1, содержащую сравнительные характеристики ЭВМ, с помощью программы Ee постройте график зависимости вычислительной мощности компьютера от номера поколения ЭВМ.

18.   Используя табл. 2.1, с помощью программы Ee постройте зависимость «Изменение основных параметров ЭВМ пяти поколений».

19.   В современном процессоре серии etim на площади кристалла в 3,6 см² размещается примерно 5 млн транзисторов (n). Считая, что размеры транзистора по каждой оси равны 15 линиям технологического разрешения (0,09 мкм). Рассчитайте коэффициент заполнения поверхности кристалла ( K = n / N_max).

Ответы и решения

Задание 17

Изменение вычислительной мощности в зависимости от поколения ЭВМ

Объем памяти, lgQ, Кбайт	Быстродействие, lgV, тыс. оп./с	Вычислительная мощность, lgQ × lgV	Поколения ЭВМ
1,301029996	0,903089987	1,174947162	1
2,408239965	2,390935107	5,757945479	2
2,709269961	3,089905111	8,371387101	3
3,913813852	3,886490725	15,21100124	4
8,408239965	6,954242509	58,4729398	5

Рис. 2.11. График         зависимости         вычислительной   мощности              компьютеров от    номера  поколения             ЭВМ

Задание 18

Изменение основных параметров ЭВМ пяти поколений

Объем памяти, lgQ, Кбайт	Быстродействие, lgV, тыс. оп./с
1,301029996	0,903089987
2,408239965	2,390935107
2,709269961	3,089905111
3,913813852	3,886490725
8,408239965	6,954242509

Рис. 2.12.               Изменение            основных              параметров           ЭВМ        пяти       поколений

Задание 19

1.    Переведем площадь кристалла из сантиметров в микроны:

3,6 см² = 360 мм² = 360 ⋅ 1000 ⋅ 1000 мкм² = 3,6 ⋅ 10⁸ мкм².

2.    Определим площадь, занимаемую одним транзистором:

3,6 ⋅ 10⁸ : 5 ⋅ 10⁶ = 72 мкм².

3.    Определим размер теоретически возможного транзистора по заданной технологии (0,09 мкм):

(15 ⋅ 0,09)² = 1,35² = 1,8 мкм².

Количество таких транзисторов на кристалле будет равно:

3,6 ⋅ 10⁸ : 1,8 = 2 ⋅ 10⁸ штук.

4.    Коэффициент заполнения поверхности кристалла равен:

5 ⋅ 10⁶ : 2 ⋅ 10⁸ = 0,025.

Глава 3

Двоичная арифметика

Без знания правил двоичной арифметики нельзя разобраться в особенностях работы ЭВМ.

Двоичная арифметика                                                                                              57

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

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

Текстовая информация осмысленно воспринимается только в том случае, если человек умеет читать и знает язык, на котором написан текст, т. е. знает буквенный и числовой алфавит. В русском языке используются кириллица (33 буквы) и арабские цифры от 0 до 9. В английском языке используются буквы латинского алфавита (26 букв). В японском или китайском языке вместо привычных нам букв используются иероглифы, каждый из которых обозначает целое понятие, и т. д.

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

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

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

Кроме двоичной, в вычислительной технике применяются и другие системы счисления, являющиеся в каком-то смысле «производными» от двоичной, — восьмеричная, шестнадцатеричная и др. В восьмеричной системе счисления используются восемь цифр: 0, 1, 2, 3, 4, 5, 6 и 7. Шестнадцатеричная система счисления состоит из десяти арабских цифр (от 0 до 9) и первых 6 букв латинского алфавита: A, B, C, D, E, F, которые обозначают числа 10, 11, 12, 13, 14 и 15 соответственно.

Системы счисления бывают позиционными и непозиционными.

В непозиционной системе счисления цифры не меняют своего количественного значения при изменении места их расположения в числе. Например, в римской непозиционной системе счисления для каждого числа используется некоторый набор базовых символов (I, V, X, L, C, D и M), соответствующих числам 1, 5, 10, 50, 100, 500 и 1000. Остальные значения чисел получаются из базовых путем их сложения (например, XVII = 17) или вычитания (например, IX = 9).

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

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

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

XP = A(N – 1) ⋅ P(N – 1) + A(N – 2) ⋅ P(N – 2) + ∙∙∙

... + A₁ ⋅ P¹ + A₀ ⋅ P⁰ + A_–1 ⋅ P^–1 + A_–2 ⋅ P^–2 + ∙∙∙ + A^–S ⋅ P^–S, а краткая запись имеет вид:

XP = A(N – 1)A(N – 2) ∙∙∙ A1A0A–1A–2 ∙∙∙ A–S.

Здесь P — основание системы счисления; N — количество разрядов целочисленной части числа; S — количество разрядов дробной части числа; A — цифры, входящие в основание системы счисления.

Например, в наиболее привычной нам десятичной системе счисления краткая и развернутая записи шестиразрядного числа (N = 6) выглядят так:

X₁₀ = 123325,8 =

= 1 ⋅ 10⁵ + 2 ⋅ 10⁴ + 3 ⋅ 10³ + 3 ⋅ 10² + 2 ⋅ 10¹ + 5 ⋅ 10⁰ + 8 ⋅ 10^–1.

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

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

r возможность использования наиболее простой элементной базы микроэлектроники — всего с двумя устойчивыми состояниями;

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

r возможность использования простейших правил арифметики.

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

В табл. 3.1 приведена запись чисел от 0 до 20 в разных системах счисления.

Таблица 3.1. Примеры чисел в разных системах счисления

Основание системы счисления
10	2	8	16
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	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
17	10001	21	11
18	10010	22	12
19	10011	23	13
20	10100	24	14

Преобразование чисел в различных системах счисления

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

XP = A(N – 1) ⋅ P(N – 1) + ... + A1 ⋅ P1 + A0 ⋅ P0  + A–1 ⋅ P–1 + ... + A–SP–S или

XP = AN – 1 ... A1A0A–1 ... A–S.

При этом справедливо равенство:

XP(A1) = YQ(B1)

или

AN – 1 ... A1A0A–1 ... A–S = BN – 1 ... B1B0B–1 ... B–S,

где A₁, B₁ — цифры в системах P и Q соответственно.

В частности для перевода числа X из десятичной системы в P-ичную, можно воспользоваться выражением:

X10  = XP = AN – 1 ... A2A1A0A–1A–2 ... A–S.

Вычисления при этом производятся отдельно для целой и дробной частей числа.

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

X₁₀ = A₀ + P ⋅ (A₁ + P ⋅ (A₂ + ... + P ⋅ (A_{(N – 1)}) ...)).

Если теперь нацело разделить число X₁₀ на P, то получится частное и остаток. Остаток будет равен A₀, а частное — первому множителю числа P, т. е. A₁ + P ⋅ (A₂ + ... + P ⋅ (A_{(N – 1)})...). Снова разделив частное на P, получим в остатке A₁, а в частном — (A₂ + ... + P ⋅ (A_{(N – 1)})...) и т. д. Этот процесс продолжается, пока очередное частное не станет меньше P. Это частное будет старшей цифрой в записи числа: A_{(N – 1)}.

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

Определение

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

Теперь рассмотрим перевод правильной десятичной дроби. Пусть X₁₀ = A_–1 ⋅ P^–1 + A_–2 ⋅ P^–2 + ... + A_–SP^–S. Если умножить это число на P, то получим: ^X₁₀ ⋅ P = ^A_–1 + ^A_–2 ⋅ P^–1 + ... + ^A_–SP^–S + 1. Это смешанное число, у которого целая часть равна A_–1. Это первая искомая цифра. Дробная часть произведения равна: (A_–2 ⋅ P^–1 + ... + A_–SP^–S + 1). Последовательное умножение повторяется до тех пор, пока в дробной части очередного произведения не получится ноль, не будет обнаружена периодичность повторяющихся цифр или не будет исчерпано отведенное для хранения числа количество разрядов.

Определение

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

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

1. 2710 = X2:				2. 0,7510 = X2:
					0 75 1 1 50 0
		Ответ: 2710 = 110112.		Ответ: 0,7510 = 0,112.

      Ответ: 316₁₀ = 474₈.                        Ответ: 4798₁₀ = 12BE₁₆.

Для смешанного числа необходимо отдельно преобразовать целую и дробную части числа и соединить их через запятую.

П р и м е р: 27,7510 = 11011,112.

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

110100101,101₂ = (1 ⋅ 2⁸ + 1 ⋅ 2⁷ + 0 ⋅ 2⁶ + 1 ⋅ 2⁵ + 0 ⋅ 2⁴ + + 0 ⋅ 2³ + 1 ⋅ 2² + 0 ⋅ 2¹ + 1 ⋅ 2⁰ + 1 ⋅ 2^–1 + 0 ⋅ 2^–2 + 1 ⋅ 2^–3)₁₀ = = (256 + 128 + 32 + 4 + 1 + 1/2 + 1/8)₁₀ = 421,625₁₀.

Шестнадцатеричное число преобразуется аналогично:

AF0₁₆ = 10 ⋅ 16^{2 +} 15 ⋅ 16^{1 +} 0 ⋅ 16⁰ = 2560 + 240 + 0 = 2800₁₀.

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

П р и м е р: 11011100011 = 011 011 100 011.

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

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

П р и м е р: (1011 1010 1101)2 = (11 10 13)10 = BAD16.

Представление информации в ЭВМ

Любая информация (тексты, изображения, числа, звуки и т. д.), поступающая в ЭВМ, преобразуется в двоичный код.

Например, каждая клавиша на клавиатуре компьютера имеет собственный 8-разрядный двоичный код, так что любая буква латинского и русского алфавита (как прописная, так и строчная), цифра десятичной системы счисления, знак препинания или другой служебный символ имеют свой индивидуальный двоичный код. А поскольку двоичное 8-разрядное число (байт) может обозначать 2⁸ = 256 различных комбинаций, этого вполне достаточно для кодирования сразу двух текстовых алфавитов, цифр и других знаков.

Изображение на экране компьютера представляется в виде растрового расположения точек (пикселов). При этом для монохромных изображений информация о цвете каждой точки хранится в одном 8-разрядном двоичном коде, что позволяет отображать чернобелые изображения с 256 градациями яркости. Для цветных изображений каждый из трех основных цветов также кодируется одним байтом; следовательно, на каждую цветную точку выделяется 3 байта информации (256 × 256 × 256 = 16 777 216 цветовых оттенков).

На кодирование единичного звукового элемента — ноты требуется от нескольких единиц до десятков байтов и т. д.

С учетом сказанного, одна страница текста имеет информационный объем около 3 Кбайт, один цветной экранный кадр содержит уже примерно 3 Мбайт, а 1,5-часовой цветной телевизионный фильм займет объем почти в 300 Гбайт (без учета сжатия видеоинформации).

Рассмотрим теперь более подробно процесс кодирования чисел в компьютере.

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

В вычислительных машинах применяются две формы представления чисел:

r естественная форма, или форма с фиксированной запятой (точкой);

r нормализованная форма, или форма с плавающей запятой (точкой).

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

П р и м е р ы: 32,54; 0,0036; –108,2.

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

В форме с плавающей запятой числа изображаются в виде:

X = ±M ×  P^±r,

где M — мантисса числа (правильная дробь в пределах от 0,1 до 1), r — порядок числа (целое значение), а P — основание системы счисления. Например, приведенные в предыдущем примере числа с фиксированной запятой можно записать в форме с плавающей запятой как  0,3254 × 10²,  0,36 × 10^–2,  –0,1082 × 10³. Нормализованная форма представления чисел обеспечивает огромный диапазон их записи и является основной в современных ЭВМ.

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

X10 → X2 → M2 ×10 .2r

После этого осуществляются еще две важные процедуры:

r  мантисса вместе с ее знаком заменяется кодом мантиссы с ее знаком;

r  порядок числа вместе с его знаком заменяется кодом порядка с его знаком.

Указанные коды двоичных чисел — это образы чисел, с которыми и работают вычислительные устройства.

Каждому двоичному числу можно поставить в соответствие несколько видов кодов.

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

1.      Определить данное двоичное число — оно может быть целым (порядок) или правильной дробью (мантисса).

2.      Если это дробь, то цифры после запятой можно тоже рассматривать как отдельное целое число.

3.      Если это целое положительное двоичное число, то путем добавления нуля в старший разряд это число превращается в его код. Для отрицательного двоичного числа в его старшем разряде ставится единица.

П р и м е р ы:

r  число X₂ = –0,101101₂ ⇒ код числа X_пр = 1101101;

r  число Y₂ = +0,1101101₂ ⇒ код числа Y_пр = 01101101.

(Жирным шрифтом выделены знаковые разряды; кроме того, в записи кодов отсутствует индекс системы счисления — «2».)

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

П р и м е р ы:

r  число X₂ = –0,10101₂ ⇒ X_пр = 110101 ⇒ X_обр = 101010; r число Y₂ = + 0,1101₂ ⇒ Y_пр = 01101 = Y_обр.

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

П р и м е р ы:

r  число X₂ = –0,10010₂ ⇒ X_пр = 110010 ⇒ X_обр = 101101 ⇒ X_доп = 101110;

r  число Y₂ = + 0,1011 ⇒ Y_пр = 01011 = Y_обр = Y_доп.

Арифметические операции с двоичными числами

Сложение и вычитание

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

П р и м е р: сложение чисел +18 и –7.

	В обратном коде		В дополнительном коде
Десятичная форма	+18	–7	+18	–7
Двоичная форма	+10010	–111	+10010	–111
Прямой код	00010010	10000111	00010010	10000111
Обратный код	00010010	11111000
Дополнительный код			00010010	11111001
Сложение	00010010 + 11111000			00010010 + 11111001
прибавить → (1)00001010+1                        игнорировать → (1)00001011

Как видим, и в обратном, и в дополнительном коде результаты сложения совпали и равны 1011₂ = 11₁₀.

Умножение и деление

Умножение и деление двоичных чисел в ЭВМ производится в прямом коде, а их знаки используются лишь для определения знака результата. Так же, как и в математике, умножение и деление сводится здесь к операциям сдвига и сложения (с учетом знаков чисел). Полученные коды мантиссы и порядка для каждого числа помещаются в соответствующие ячейки памяти ЭВМ. Для каждой цифры, входящей в код, в ячейке памяти отводится отдельное место. Одна ячейка памяти состоит из 8 бит (1 байта). В современных компьютерах для одного машинного слова выделяются 2 байта, а в самых последних моделях ПК обработка информации ведется двойными словами, содержащими 4 байта. Числа с фиксированной запятой имеют формат одного слова, а числа с плавающей запятой — формат двойного слова.

П р и м е р. Дано число с плавающей запятой –0,625×10⁸. Нужно преобразовать его в машинный код и заполнить 32-разрядную ячейку памяти.

Мантисса числа равна 0,625₁₀ = 0,101₂. Поскольку порядок таких чисел может быть как положительным, так и отрицательным, то машинный порядок смещается относительно естественного так, чтобы весь диапазон машинных порядков изменялся от 0 до максимума, определяемого количеством разрядов, выделяемых для размещения кода порядка. Обычно в 32-разрядной ячейке памяти цифры порядка занимают семь разрядов старшего байта, а восьмой разряд используется для фиксации знака числа. Семь двоичных разрядов позволяют разместить диапазон десятичных разрядов от –64 до +63. Если обозначить машинный порядок через R, а естественный — через r, то связь между ними будет такой:

R10 = r10 + 6410.

Для двоичной системы счисления

R₂ = r₂ + 1000000₂.

В нашем примере порядок r равен 8₁₀ = 1000₂, следовательно, R₂ = 1001000.

В двоичной системе исходное число имеет вид:

 –0,101 × 10¹⁰⁰⁰.

Запись этого числа в 32-разрядной ячейке памяти будет следующей:

	Знак числа	Порядок							Мантисса
Номер  разряда	31	30	29	28	27	26	25	24	23	22	21	20	19	18	...	1	0
Значение разряда	1	1	0	0	1	0	0	0	1	0	1	0	0	0	0	0	0

Вопросы и задания

1.       Что понимается под системой счисления?

2.       В чем заключается разница между непозиционной и позиционной системами счисления?

3.       Чем отличается развернутая запись многоразрядного числа от краткой записи?

4.       В чем состоят преимущества и недостатки двоичной системы счисления?

5.       Как преобразовать целое число, записанное в одной системе счисления, в число в другой системе счисления?

6.       Как преобразуется дробная часть числа при переходе из одной системы счисления в другую?

7.       Какие существуют формы представления чисел в компьютере?

8.       Каково представление двоичных чисел в прямом, обратном и дополнительном кодах?

9.       Как производится сложение, вычитание, умножение и деление двоичных чисел?

10.   В каком формате представляются в памяти ЭВМ действительные числа?

11.   Запишите десятичное число 25 в двоичной, восьмеричной и шестнадцатеричной системах счисления.

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

10110₂ ⇒ Х₁₀

2910 ⇒ Х2

4910 ⇒ Х8

1268 ⇒ Х10

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

110101001₂ ⇒ Х₁₆

1111000111₂ ⇒ Х₈

37₈ ⇒ Х₃

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

7765₈ ⇒ Х₁₆

D4F₁₆ ⇒ Х₂

231₅ ⇒ Х₈

2102₃ ⇒ Х₈

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

1101,11₂ ⇒ Х₁₀

45,7₈ ⇒ Х₁₀

3D,A16 ⇒ Х10

Ответы и решения

Задание 11

О т в е т:  25₁₀ = 11001₂;   25₁₀ = 31₈;   25₁₀ = 19₁₆.

Р е ш е н и е.

1.      Делим число 25 на 2:

25  : 2 = 12 (остаток 1).

Снова делим число 12 на 2:

12 : 2 = 6 (0).

Снова делим число 6 на 2:

6 : 2 = 3 (0).

Наконец, делим число 3 на 2:

3 : 2 = 1 (1).

Двоичное число составится из остатков, записанных от конца к началу, т. е. 1(1)(0)(0)(1) ⇒ 11001.

Ответ: 11001₂.

2.      Делим число 25 на 8:

25  : 8 = 3 (остаток 1).

Восьмеричное число составится так: 3(1) ⇒ 31.

Ответ: 31₈.

3.      Делим число 25 на 16:

25  : 16 = 1 (остаток 9).

Шестнадцатеричное число составится так: 1(9) ⇒ 19.

Ответ: 19₁₆.

Задание 12

О т в е т: 10110₂ ⇒ Х₁₀ = 22

29₁₀ ⇒ Х₂ = 11101

49₁₀ ⇒ Х₈ = 61  126₈ ⇒ Х₁₀ = 86

Р е ш е н и е.

1.      Запишем двоичное число в развернутой форме и вычислим его сумму:

10110₂ = 1 ⋅ 2⁴ + 0 ⋅ 2³ + 1 ⋅ 2² + 1 ⋅ 2¹ + 0 ⋅ 2⁰ = 16 + 4 + 2 = 22.

Ответ: Х₁₀ = 22.

2.      Делим число 29 на 2:

29 : 2 = 14 (остаток 1).

Снова делим число 14 на 2:

14 : 2 = 7 (0).

Снова делим число 7 на 2:

7 : 2 = 3 (1).

Наконец, делим число 3 на 2:

3 : 2 = 1 (1).

Двоичное число составится из остатков, записанных с конца до начала, т. е. 1(1)(1)(0)(1) ⇒ 11101.

Ответ: Х₂ = 11101.

3.      Делим число 49 на 8:

49 : 8 = 6 (остаток 1).

Восьмеричное число составится так: 6(1) ⇒ 61.

Ответ: Х₈ = 61.

4.      Запишем восьмеричное число в развернутой форме и вычислим его сумму:

126₈ = 1 ⋅ 8² + 2 ⋅ 8¹ + 6 ⋅ 8⁰ = 64 + 16 + 6 = 86.

Ответ: Х₁₀ = 86.

Задание 13

О т в е т: 110101001₂ ⇒ Х₁₆ = 1A9

1111000111₂ ⇒ Х₈ = 1707

37₈ ⇒ Х₃ = 1101

Р е ш е н и е.

1.      При переводе двоичного числа в шестнадцатеричное это двоичное число сгруппируем по 4 разряда справа налево. Если в самой левой группе остается менее четырех разрядов, то слева дополним ее недостающими нулями. Затем каждую группу заменим одним шестнадцатеричным числом:

110101001 ⇒ 0001 1010 1001 ⇒ 1А9.

Ответ: Х₁₆ = 1A9.

2.      При переводе двоичного числа в восьмеричное это двоичное число сгруппируем по 3 разряда справа налево. Если в самой левой группе остается менее трех разрядов, то слева дополним ее недостающими нулями. Затем каждую группу заменим одним восьмеричным числом:

1111000111 ⇒ 001 111 000 111 ⇒ 1707.

Ответ: Х₈ = 1707.

3.      Делим число 37 на 3:

37 : 3 = 12 (остаток 1).

Снова делим число 12 на 3:

12 : 3 = 4 (0).

Наконец, делим число 4 на 3:

4 : 3 = 1(1).

Троичное число составится из остатков, записанных с конца до начала, т. е. 1(1)(0)(1) ⇒ 1101.

Ответ: Х₃ = 1101.

Задание 14

О т в е т: 7765₈ ⇒ Х₁₆ = FF5

D4F₁₆ ⇒ Х₂ = 110101001111

231₅ ⇒ Х₈ = 102

                         2102₃ ⇒ Х₈ = 101

Р е ш е н и е.

1.      Запишем исходное восьмеричное число в двоичном коде, присвоив каждой цифре ее 3-разрядный двоичный аналог:

7765 ⇒ 111 111 110 101.

Преобразуем 3-разрядные группы в 4-разрядные и затем каждую группу запишем в шестнадцатеричном коде:

111 111 110 101 ⇒ 1111 1111 0101 ⇒ FF5.

Ответ: Х₁₆ = FF5.

2.      Запишем исходное шестнадцатеричное число в двоичном коде, присвоив каждой цифре ее 4-разрядный двоичный аналог:

D4F ⇒ 1101 0100 1111 ⇒ 110101001111₂.

Ответ: Х₂ = 110101001111.

3.      Запишем пятеричное число в развернутой форме и вычислим его сумму:

231₅ = 2 ⋅ 5² + 3 ⋅ 5¹ + 1 ⋅ 5⁰ = 50 + 15 + 1 = 66₁₀.

Теперь преобразуем полученное десятичное число в искомое восьмеричное по правилу последовательного деления. Делим число 66 на 8:

66 : 8 = 8 (остаток 2).

Снова делим число 8 на 8:

8 : 8 = 1 (0).

Восьмеричное число составится из остатков, записанных с конца до начала, т. е. 1(0)(2) ⇒ 102.

Ответ: Х₈ = 102.

4.      Запишем троичное число в развернутой форме и вычислим его сумму:

2102₃ = 2 ⋅ 3³ + 1 ⋅ 3² + 0 ⋅ 3¹ + 2 ⋅ 3⁰ = 54 + 9 + 2 = 65₁₀.

Теперь преобразуем полученное десятичное число в искомое восьмеричное по правилу последовательного деления. Делим число 65 на 8:

65 : 8 = 8 (остаток 1).

Снова делим число 8 на 8:

8 : 8 = 1 (0).

Восьмеричное число составится из остатков, записанных с конца до начала, т. е. 1(0)(1) ⇒ 101.

Ответ: Х₈ = 101.

Задание 15

О т в е т: 1101,11₂ ⇒ Х₁₀ = 13,75

       45,7₈ ⇒ Х₁₀ = 37,875    3D,A₁₆ ⇒ Х₁₀ = 61,625

Р е ш е н и е.

1.  Вычисления будем проводить отдельно для целой и дробной частей смешанного числа.

Запишем двоичное число в развернутой форме и вычислим его сумму:

1101₂ = 1 ⋅ 2³ + 1 ⋅ 2² + 0 ⋅ 2¹ + 1 ⋅ 2⁰  = 8 + 4 + 1 = 13.

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

0,11 ⋅ 1010 = 111,10 0,10 ⋅ 1010 = 101,0.

Дробная часть стала нулевой, а целые числа 111₂ и 101₂ в десятичной записи равны соответственно числам 7 и 5. Таким образом, 0,11₂ ⇒ 0,75₁₀.

Ответ: смешанное число Х₁₀ = 13,75₁₀.

2.  Вычисления будем проводить отдельно для целой и дробной частей смешанного числа.

Запишем восьмеричное число в развернутой форме и вычислим его сумму:

45₈ = 4 ⋅ 8¹ + 5 ⋅  8⁰ = 32 + 5 = 37.

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

0,7₈ ⋅ 12 = 8,6₈

(потому, что в восьмеричной системе 2 ⋅ 7 равно не 14, а 16 — одна восьмерка плюс одна шестерка). Получившуюся дробную часть снова умножаем на 12:

0,6₈ ⋅ 12 = 7,4₈

(по той же причине, т. к. 2 ⋅ 6 равно не 12, а 14 в восьмеричной системе). Оставшуюся дробную часть снова умножаем на 12:

0,4₈ ⋅ 12 = 5,0₈.

Дробная часть стала нулевой, а целые числа имеют значения

8, 7, 5. Итак,

0,7₈ = 0,875₁₀.

Рассмотренное преобразование можно осуществить проще. Величина 0,7₈ в развернутой форме будет иметь вид:

7 ⋅ 8^–1 = 7 : 8 = 0,875₁₀.

Таким образом,

0,7₈ = 0,875₁₀.

Ответ: смешанное число X₁₀ = 37,875₁₀.

3. Вычисления будем проводить отдельно для целой и дробной части смешанного числа.

Запишем шестнадцатеричное число в развернутой форме и вычислим его сумму:

3D = 3 ⋅ 16¹ + D ⋅ 16⁰ = 48 + 13 = 61.

Теперь преобразуем дробную часть: величина A₁₆ равна 10 единицам в этой системе счисления, следовательно, в десятичной системе счисления величина А равна частному от деления:

10 : 16 = 0,625₁₀.

Таким образом,

0,А₁₆ = 0,625.

Ответ: смешанное число X₁₀ = 61,625₁₀.

Глава 4

Бинарная лоГика

Двоичная арифметика                                                                                              79

Алгебра  логики

Основы логики как науки были заложены великим древнегреческим ученым Аристотелем (IV в. до н. э.), а со средины XIX в. благодаря трудам англичанина Джорджа Буля (1815–1864), шотландца Огастеса (Августа) де Моргана (1806–1871), немца Готлоба Фреге (1848–1925), итальянца Джузеппе Пеано (1858–1932) и других возникла математическая логика, которая перевела на точный язык математики все прежние достижения логики, дала мощный толчок ее дальнейшему развитию и существенно повысила уровень строгости и доказательности математики в целом.

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

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

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

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

Любую логическую функцию f (x₁, ..., x_n) можно задать в виде таблицы, в левой части которой записаны все возможные наборы значений ее аргументов х₁, ..., х_n, а правая часть содержит столбец значений функции, соответствующих этим наборам. Количество строк в такой таблице равно 2ⁿ — числу возможных наборов значений аргументов, т. е. количеству различных комбинаций длины n из нулей и единиц.

n

Количество различных функций от n переменных равно 2² — числу возможных расстановок нулей и единиц в столбце с 2ⁿ строками.

Таблица функции f (х) от одной переменной содержит всего две строки, а самих функций одной переменной — четыре:

x	f (x)		x	f (x)		x	f (x)		x	f (x)
0	0		0	0		0	1		0	1
1	0		1	1		1	0		1	1

Генератор 0                    f (x) = x                    f (x) = ¬x                 Генератор 1

                                     (повторение)            (отрицание)

Таблица функции f (х₁, х₂) от двух переменных содержит четыре строки, а самих функций от двух переменных — шестнадцать

n

(2² = 2⁴ =16). Наиболее важные из них — следующие:

x1 x2 x1 ∨ x2 0 0 0 0 1 1 1 0 1 1 1 1

x1 x2 x1 ∧ x2 0 0 0 0 1 0 1 0 0 1 1 1

                       Дизъюнкция                                            Конъюнкция

                             (ИЛИ)                                                           (И)

x1 x2 x1 → x2 0 0 1 0 1 1 1 0 0 1 1 1

x1 x2 x1 ∼ x2 0 0 1 0 1 0 1 0 0 1 1 1

                       Импликация                                        Эквивалентность

x1	x2	x1 ⊕ x2
0	0	0
0	1	1
1	0	1
1	1	0

Сложение по модулю 2

(исключающее ИЛИ)

Указанные пять функций соответствуют логическим связкам ИЛИ (дизъюнкция, логическое сложение), И (конъюнкция, логическое умножение), ЕСЛИ ... ТО (импликация), ЕСЛИ И ТОЛЬКО ЕСЛИ (эквивалентность, равнозначность) и ЛИБО, ... ЛИБО (исключающее ИЛИ, неравнозначность, сложение по модулю 2). Кроме этого, часто употребляются еще две функции двух переменных — ИЛИ-НЕ (стрелка Пирса) и И-НЕ (штрих Шеффера):

x1	x2	x1 ↓ x2		x1	x2	x1 | x2
0	0	1		0	0	1
0	1	0		0	1	1
1	0	0		1	0	1
1	1	0		1	1	0

                     Стрелка Пирса                                      Штрих Шеффера

                          (ИЛИ-НЕ)                                                    (И-НЕ)

Приведенные 11 таблиц логических функций называются таблицами истинности этих функций. Значение любой логической формулы, содержащей знаки этих функций, на заданном наборе значений переменных можно вычислить, используя эти таблицы. Пусть, например, функция f (х₁, х₂, х₃) задана формулой:

(¬х₁ ∨ х₂) → х₁ ∧ х₃.

Вычислим эту функцию на наборе х₁ = 1, х₂ = 1, х₃ = 0. (С точки зрения логики нужно определить значение истинности сложного высказывания при условии, что составляющие его простые высказывания х₁ и х₂ истинны, а х₃ — ложно.) Подстановка значений в формулу дает запись:

(¬1 ∨ 1) → 1 ∧ 0 = 1 → 0 = 0.

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

Законы алгебры логики

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

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

r для каждого набора значений переменных х₁, ..., х_n из таблицы истинности, на котором функция f (х₁, ..., х_n) равна 1, выписывается конъюнкция всех переменных (знак ∧ , & или ⋅);

r над теми переменными, которые в этом наборе равны 0, ставятся отрицания (знак ¬ либо надчеркивание);

r все такие конъюнкции соединяются знаками дизъюнкции (∨ или +).

В дальнейшем мы будем пользоваться следующими обозначениями: отрицание (¬), дизъюнкция (+) и конъюнкция (⋅).

Полученная формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции f (х₁, ..., х_n). СДНФ для каждой функции единственна. Это означает, что две различные СДНФ одной функции могут отличаться только порядком конъюнкций и расстановкой переменных в конъюнкциях. Для примера СДНФ функции импликации (см. таблицу истинности в разд. «Алгебра логики» ранее в этой главе) имеет вид:

(¬х₁ ⋅ ¬х₂) + (¬х₁ ⋅ х₂) + (х₁ ⋅ х₂).

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

В булевой алгебре эти законы — следующие:

1.    Ассоциативность конъюнкции и дизъюнкции:

х₁ ⋅ (х₂ ⋅ х₃) = (х₁ ⋅ х₂) ⋅ х₃ = х₁ ⋅ х₂ ⋅ х₃; х₁ + (х₂ + х₃) = (х₁ + х₂) + х₃ = х₁ + х₂ + х_3.

2.    Коммутативность конъюнкции и дизъюнкции:

x1 ⋅ x2 = x2 ⋅ x1; x₁ + x₂ = x₂ + x₁.

3.    Дистрибутивность конъюнкции относительно дизъюнкции: х₁ ⋅ (х₂ + х₃) = (х₁ ⋅ х₂) + (х₁ ⋅ х₃).

4.    Дистрибутивность дизъюнкции относительно конъюнкции: х₁ + (х₂ ⋅ х₃) = (х₁ + х₂) ⋅ (х₁ + х₃).

5.    Идемпотентность (отсутствие степеней и коэффициентов): х ⋅ х = х; х + х = х.

6.    Закон двойного отрицания:

¬ ¬х = х.

7.    Свойства констант 0 и 1: х ⋅ 1 = х; х ⋅ 0 = 0; х + 1 = 1; х + 0 = х;

¬0 = 1; ¬1 = 0.

8.    Правила де Моргана:

¬(х₁ ⋅ х₂) = ¬х₁ + ¬х₂;

¬(х₁ + х₂) = (¬х₁ ⋅ ¬х₂).

9.    Закон противоречия:

х ⋅ ¬х = 0.

10. Закон исключенного третьего:

х + ¬х = 1.

Два последних закона указывают, что при любых аргументах высказывание х ⋅ ¬х всегда ложно, а высказывание х + ¬х всегда истинно.

Законы 1, 2, 3, 7 показывают, что свойства конъюнкции очень похожи на свойства умножения, поэтому ее часто называют логическим умножением.

Из законов 6 и 8 следует, что, используя отрицание, можно выразить дизъюнкцию через конъюнкцию и наоборот:

х₁ + х₂ = ¬ ¬(х₁ + х₂) = ¬(¬х₁ ⋅ ¬х₂);

х₁ ⋅ х₂ = ¬ ¬(х₁ ⋅ х₂) = ¬(¬х₁ + ¬х₂).

Это означает, что наборы ИЛИ-НЕ и И-НЕ также явля- ются функционально полными. Отсюда следует, что базисом может служить одиночная функция «стрелка Пирса» или «штрих Шеффера».

С помощью основных законов можно вывести соотношения, часто используемые в булевой алгебре. Например, соотношение х + х ⋅ у = х (поглощение) выводится путем последовательного применения законов 7, 3, 7, 7:

х + х ⋅ у = х ⋅ 1 + х ⋅ у = х ⋅ (1 + у) = х ⋅ 1 = х.

Аналогично выводятся формулы

х ⋅ у + х ⋅ ¬у = х (склеивание по у)

и

                                        х + ¬х ⋅ у = х + у                                  (*).

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

r   импликация:	x1 → x2 = ¬x1 + x2;
r   эквивалентность:	x1 ∼ x2 = x1 ⋅ x2 + ¬x1 ⋅ ¬x2;
r   сложение по модулю 2:	x1 ⊕ x2 = x1 ⋅ ¬x2 + ¬x1 ⋅ x2;
r   штрих Шеффера:	x1 | x2 = ¬(x1 ⋅ x2) = ¬x1 + ¬x2;
r   стрелка Пирса:	x1 ↓ x2 = ¬(x1 + x2) = ¬x1 ⋅ ¬x2.

Эквивалентные соотношения, приведенные выше, можно получить с помощью СДНФ. Например, для формулы импликации СДНФ будет иметь вид:

¬х₁ ⋅ ¬х₂ + ¬х₁ ⋅ х₂ + х₁ ⋅ х₂.

Применяя законы 3, 10 и формулу (*), получим:

¬х₁ ⋅ ¬х₂ + ¬х₁ ⋅ х₂ + х₁ ⋅ х₂ = ¬х₁(¬х₂ + х₂) + х₁ ⋅ х₂ =

= ¬х₁ + х₁ ⋅ х₂ = ¬х₁ + х₂.

Однотактные и многотактные автоматы

Для формирования цифровых выходных сигналов используются ЦУ двух классов.

1.    ЦУ, выходные сигналы Y которых в некоторый момент времени зависят только от совокупности (комбинации) сигналов Х, присутствующих на их входах в тот же момент времени, и не зависят от входных сигналов, поступивших в предшествующие моменты времени. ЦУ этого класса «не помнят» предыстории поступления сигналов на их входы. Такие ЦУ принято называть комбинационными цифровыми устройствами (КЦУ), или однотактными автоматами.

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

Правила функционирования КЦУ могут быть заданы различными способами: словесно, таблицами истинности, булевыми выражениями. Реализация КЦУ предполагает выбор определенных логических элементов из заданного набора и их соединение таким образом, чтобы обеспечивалась зависимость цифровых выходных сигналов от входных в соответствии с заданными правилами функционирования.

Ранее было указано, что в базисный набор элементарных логических элементов входят три логические функции — И, ИЛИ, НЕ. В качестве базиса также могут выступать одиночные функции: ИЛИ-НЕ (стрелка Пирса) и И-НЕ (штрих Шеффера). Графическое обозначение вышеперечисленных логических элементов приведено на рис. 4.1.

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

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

A

&	A B	1

                                                                               X            A

B

                               И                                ИЛИ                              НЕ

A

B

                                           ИЛИ-НЕ                        И-НЕ

Рис. 4.1. Графические обозначения базисных логических элементов

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

1.    Задать словесное описание автомата.

2.    Рассмотреть работу автомата на уровне «черного ящика», т. е. определить количество его входов и выходов.

3.    Составить таблицу его работы.

4.    Записать структурную формулу автомата.

5.    Начертить структурную (функциональную) схему.

П р и м е р.

1.    Словесное описание автомата.

Для оповещения зрителей на соревнованиях по тяжелой атлетике (штанга) используется периодически загорающийся транспарант «Вес взят правильно». Транспарант освещается, получив сигнал от автомата, который обрабатывает сигналы, поступившие к нему от судей. Судей трое, один из них — старший. Вес считается взятым правильно при единодушном мнении всех трех судей или двух из них, но при условии, что один из судей — старший. Пометим его буквой А. Если по мнению судьи вес взят правильно, то он нажимает кнопку, расположенную на его столе, тем самым на один из входов автомата подается сигнал 1.

2.    Располагая словесным описанием автомата, можно представить его в виде «черного ящика»: автомат имеет три входа, по которым поступают сигналы от судей, и один выход, по которому автомат выдает сигнал освещения транспаранта (рис. 4.2).

Рис. 4.2. Представление автомата в виде «черного ящика»

3.    Составим таблицу работы автомата. Полученная таблица задает автомат табличным способом.

A	B	C	Х
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	0
0	0	1	0
0	0	0	0

Из таблицы видно, в каких случаях Х = 1 (тогда транспарант будет освещен).

4.    Структурная формула автомата имеет вид:

                X = ABC + ABC + ABC = AB + AC = A B( + C).

5.    Соответствующая структурная (функциональная) схема представлена на рис. 4.3.

Рис. 4.3. Функциональная схема автомата

Возможная структура ПЦУ представлена на рис. 4.4.

Рис. 4.4. Возможная структура ПЦУ

ПЦУ состоит из комбинационного цифрового устройства (КЦУ) и запоминающего устройства (ЗУ). Последнее представляет собой совокупность простейших элементов памяти (триггеров) Т₁, Т₂, ..., Т_k, на которые воздействуют сигналы U = {u₁, u₂, ..., u_k} (структура и принцип действия триггера приведены в разд. «Триггер» главы 2 «Устройство ЭВМ»).

Под воздействием сигнала u_i элемент T_i может перейти в одно из двух состояний: 0 или 1. Состояние элемента T_i отображается сигналом Z_i. Совокупность сигналов Z = {z₁, z₂, ..., z_k} отображает состояние ПЦУ.

Комбинационное цифровое устройство, входящее в состав ПЦУ, представляет собой устройство, схема которого описывается булевыми функциями Y = F (X, Z), U = H (X, Z). ПЦУ работает под воздействием входных сигналов Х, которые поступают в моменты времени t = 0, 1, 2, ... В момент времени t = 0 ПЦУ находится в начальном состоянии. При этом Z (t) принимает некоторое начальное значение Z (0) = {z₁(0), z₂(0), ..., z_k(0)}.

При поступлении в последующие моменты времени сигналов X (t) в ПЦУ формируются выходные сигналы Y (t) и сигналы U (t), воздействующие на запоминающие элементы. В результате ПЦУ переходит в некоторое состояние Z (t), и тем самым фиксируется воздействие входных сигналов X (t) в момент времени t. Темп работы ПЦУ определяется темпом поступления входных сигналов.

Итак, в ПЦУ каждому набору входных сигналов соответствует однозначный набор выходных сигналов, т. е. реализуется некоторое отображение. Это отображение однозначно определяется заданием функции переходов δ и функции выходов λ автомата.

Функция переходов определяет состояние автомата z(t) по входному сигналу x(t) и состоянию в предыдущий момент времени z(t – 1):

   z(t) = δ (z(t – 1), x(t)).

Функция выходов λ устанавливает зависимость выходного сигнала y(t) от тех же переменных:

   y(t) = λ (z(t – 1), x(t)).

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

П р и м е р задания автомата в форме таблиц переходов и выходов:

                 Таблица переходов                     Таблица выходов

Входной  сигнал	Состояние			Входной  сигнал	Состояние
	z0	z1			z0	z1
x1	z1	z1		x1	y1	y2
x2	z0	z0		x2	y2	y2

Новые состояния автомата определяются на пересечении строк (входные сигналы) и столбцов (предшествующие состояния). В таблице выходов на пересечении строк и столбцов находятся выходные сигналы.

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

Рис. 4.5. Граф конечного автомата

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

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

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

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

Автомат, запоминая что-то, приобретает соответствующее состояние. Состояния конструируемого автомата будем обозначать так:

r а₀ — исходное состояние или состояние перед началом комплектации следующей тройки;

r а₁ — состояние после регистрации первой детали А;

r а₂ — состояние автомата, который укомплектовал пару АВ.

Как только будет укомплектована тройка АВА, автомат из состояния а₂ перейдет в состояние а₀ и т. д.

На основе словесного описания автомата-сортировщика построим его граф-схему (рис. 4.6) и таблицу:

	Входы автомата		Выходы из памяти		Входы в память		S	Примечание
	A	B	X1	X2	Y1	Y2
a0	1	0	0	0	0	1	0	Смена состояния а0 на а1
	0	1	0	0	0	0	1	Сброс детали В
a1	1	0	0	1	0	0	1	Сброс детали А
	0	1	0	1	1	1	0	Смена состояния а1 на а2
a2	1	0	1	0	1	0	0	Смена состояния а2 на а0
	0	1	1	0	0	0	1	Сброс детали В

Рис. 4.6. Граф-схема автомата (к примеру)

Из схемы (см. рис. 4.6) видно, что начальное состояние а₀ сменяется состоянием а₁ под воздействием сигнала А; состояние а₁ — состоянием а₂ под воздействием сигнала В и, наконец, состояние а₂ — начальным состоянием под воздействием сигнала А. Если в состоянии а₀ автомат получит сигнал В, то состояние автомата не изменится и он выработает сигнал S — сигнал сброса детали В на вспомогательный конвейер. Эти же действия осуществит автомат, если «увидит» деталь А в состоянии а₁ и деталь В — в состоянии а₂.

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

Двоичные коды этих состояний: а₀ — 00, а₁ — 01, а₂ — 10.

Основное назначение нашего автомата — комплектовать упорядоченные тройки, своевременно сбрасывая на вспомогательный конвейер ненужные детали. Сбрасывает он их по сигналу S = 1, формирующемуся под влиянием сигналов A, B, X₁, X₂, т. е. S = F

(A, B, X₁, X₂).

С помощью таблицы можно составить структурные формулы:

                                  S = ABX X_{1 2} + ABX X_{1 2} + ABX X_{1 2};

                                            Y₁ = ABX X_{1 2} + ABX X_{1 2};

                                            Y₂ = ABX X_{1 2} + ABX X_{1 2}.

Рис. 4.7. Функциональная схема автомата

Упростим выражение для S, группируя первый и третий члены функции:

                 S = ABX X_{1 2} + ABX X_{1 2} + ABX X_{1 2} =

                      = ABX₂(X₁ + X₂) + ABX X_{1   2} = ABX₂ + ABX X_{1  2}.

Используя полученные структурные формулы:

                                                S = ABX₂ + ABX X_{1 2},

                                            Y₁ = ABX X_{1 2} + ABX X_{1 2},

                                            Y₂ = ABX X_{1 2} + ABX X_{1 2},

построим функциональную схему автомата в базисе «И», «ИЛИ», «НЕ»  (рис. 4.7).

На компакт-диске для этой темы есть анимация, в которой демонстрируется порядок построения функциональной схемы автомата. Вначале рисуются логические элементы «И» для выше- указанных структурных формул, далее элементы суммирования «ИЛИ», затем изображаются ячейки памяти «Т» и вспомогательные элементы «НЕ». Наконец, рисуются соединительные линии между элементами схемы и вписываются соответствующие надпи- си. (Примечание: для S логические входы расположены сверху вниз, для Y₁, Y₂ — снизу вверх.)

Вопросы и задания

1.        Что представляет собой логика как наука? Какие проблемы она рассматривает?

2.        В чем состоит отличие алгебры логики от алгебры арифметики? Что такое логические переменные и логические функции?

3.        Назовите логические функции одной переменной и представьте их табличное значение.

4.        Назовите основные логические функции двух переменных и представьте их табличное значение.

5.        Что такое таблицы истинности?

6.        Приведите примеры функционально полного набора логических функций. Как составить формулу логической функции в виде совершенной дизъюнктивной нормальной формы (СДНФ)?

7.        Назовите основные законы (эквивалентные соотношения) булевой алгебры.

8.        Как с помощью СДНФ можно преобразовать логические формулы из табличной формы в аналитическую?

9.        Дайте определение цифрового автомата. Каковы различия между однотактными и многотактными (конечными) цифровыми автоматами?

10.    Как осуществляется разработка однотактного автомата?

11.    Опишите структуру и принцип действия многотактного автомата.

12.    Какое из трех выражений эквивалентно сложному высказыва-

нию (A+ B) (⋅ A + B + C) : а) (A+ C)⋅B;

б) (A+ C)⋅B;

в) AC + B ?

13.. Какие два из четырех высказываний эквивалентны:

         а) A B⋅ + C;

б) (A + B)⋅C;

в) (A + B)⋅C;

          г) A B⋅ +C ?

14.    Структурная формула автомата имеет вид: X = A+ B . Начерти- те его функциональную схему в базисе «стрелка Пирса», а также в базисе «И», «НЕ».

15.    Структурная формула автомата имеет вид: X = AB + AB . Начертите его функциональную схему в базисе «штрих Шеффера».

16.    Структурная формула логической функции «эквивалентность»

имеет вид: X₁ : X₂ = X₁ ⋅ X₂ + X₁ ⋅ X₂ . Начертите функциональную схему в базисе «ИЛИ», «НЕ».

17.    Структурная формула автомата имеет вид: X A B= + . Начертите его функциональную схему в базисе «штрих Шеффера».

18.    На рис. 4.8 приведена функциональная схема. Составьте структурную формулу устройства.

Рис. 4.8. Функциональная схема (к заданию 18)

Ответы и решения

Задание 12

Р е ш е н и е.

Упростим сложное высказывание:

(A+ B) (⋅ A + B + C) =

                            = A A⋅ + A B⋅ + A C⋅ + A B⋅ + B B⋅ + B C⋅ .

       В соответствии с законами булевой алгебры, A A⋅ всегда равно

0, а B B⋅ всегда равно B . Группируя теперь второй и пятый члены развернутого выражения, получим:

                                       B ⋅(A+1) + A C⋅ + A B⋅ + B C⋅ .

А + 1 всегда равно 1, поэтому объединим теперь первый и третий члены полученного выражения:

                                             B ⋅(1+ A) + A C⋅ + B C⋅ .

Далее сгруппируем снова первый и третий члены выражения:

                                         B ⋅(1+ C) + A C⋅ = B + A C⋅         .

Что и требовалось доказать.

Можно решить задачу проще, воспользовавшись законом поглощения:

                                                        B + X B⋅ = B,

где Х — любая логическая переменная. Перепишем развернутое выражение с учетом того, что A A⋅ = 0 , а B B B⋅ = :

                                        A B⋅ + A C⋅ + A B⋅ + B + B C⋅        .

Переменная B последовательно поглощает первый, третий и

пятый члены выражения, в результате остается A C⋅ + B .

Ответ: выражение (в) эквивалентно сложному высказыванию

(A+ B) (⋅ A + B + C) .

 Задание 13

Р е ш е н и е.

Будем сравнивать первое высказывание ( A B⋅ + C ) с другими высказываниями.

Сравнение начнем между первым и вторым высказываниями. Применим правило де Моргана ко второму высказыванию:

      (A + B)⋅C = (A + B)⋅C = (A + B) +C = (A B⋅ ) +C = (A B⋅ ) + C.

Очевидно, они не эквивалентны (второе высказывание отрицает первое).

Далее сравним первое и третье высказывания. Дважды применим к третьему высказыванию правило де Моргана:

                      (A + B)⋅C = (A + B) +C = A B⋅ +C = A B⋅ +C.

Видим, что эти высказывания эквивалентны.

Сравним теперь первое и четвертое высказывания. Дважды применим к четвертому высказыванию правило де Моргана:

                         A B⋅ + C = A B C⋅                    ⋅   = (A + B)⋅C = (A + B)⋅C .

Видим, что они не эквивалентны.

Ответ: эквивалентны высказывания (а) и (в).

Задание 14

Р е ш е н и е.

В базисе «стрелка Пирса» (логическое значение «ИЛИ-НЕ») функциональная схема показана на рис. 4.9, а, в базисе «И», «НЕ» — на рис. 4.9, б.

                                   а                                                                      б

Рис. 4.9. Функциональная схема к заданию 14

Задание 15

Р е ш е н и е.

В базисе «штрих Шеффера» (логическое значение «И-НЕ») функциональная схема показана на рис. 4.10. При этом исходная структурная формула была преобразована с помощью правила де Моргана:

A

B

A

B

Рис. 4.10. Функциональная схема к заданию 15

Задание 16

Р е ш е н и е.

В базисе «ИЛИ», «НЕ» функциональная схема показана на рис. 4.11. При этом исходная структурная формула была преобразована с помощью правила де Моргана:

                    X1 : X2      X1 X2     X1 X2     X1 X2     X1 X2

Рис. 4.11. Функциональная схема к заданию 16

Задание 17

Р е ш е н и е.

В базисе «штрих Шеффера» (логическое значение «И-НЕ») функциональная схема показана на рис. 4.12. При этом исходная структурная формула была преобразована с помощью правила де Моргана:

                                            X = A+ B = A+ B = A B⋅ .

Рис. 4.12. Функциональная схема к заданию 17

Задание 18

Р е ш е н и е.

Структурная формула составляется последовательно слева направо, затем к ее предварительной записи применяется правило де Моргана:

                                    X = A B B⋅      ⋅        = A B⋅ + B = A B⋅         + B.