Методичка. Учебное пособие В. М. Лопатин издание второе, стереотипное 1 17
 Скачать 4.33 Mb.
|
|
– число растровых точек на единице длины (обычно на одном дюйме). Чем выше число растровых точек, тем меньше заметна дискретность изображения, обусловленная его растровой структурой. 3. Уголнаклонарастра– это угол поворота растровых точек разного цвета относительно друг друга и относительно общей оси изображения. Этот параметр имеет особое значение при цветной печати, так как печать каждой краски осу- ществляется с использованием разных углов наклона. Значения углов наклона растра стандартизированы, и менять их не рекомендуется. При нарушении по- рядка расположения углов наклона может возникать муар – паразитный, раздра- жающий глаз визуальный эффект. Выбор параметров растрирования определяет качество печатной продукции и соответствующую стоимость печатного тиража. Операции с логическими данными Компьютер предназначен не только для обработки числовых, текстовых и графических данных. К числу сохраняемых и обрабатываемых данных относятся также логические данные. Для обработки логических данных используется арифметико-логическое устройство (АЛУ), которое входит в состав микропро- цессора и отвечает за выполнение логических операций. Математической осно- вой всех логических операций в АЛУ является алгебра логики. 6 / 17 41 Основные понятия алгебры логики Основоположником алгебры логики является английский математик и логик Джорж Буль, в честь которого математические основы логики называют булевой алгеброй. В XIX в. он написал более 50 статей и монографий, в которых изложил основные понятия современной алгебры логики. Алгебра логики – это раздел математики, в основе которого лежат опера- ции с логическими высказываниями. Логическое высказывание – это утверждение в языковой форме, которое может иметь только одно из двух возможных значений: ИСТИНА(логическая 1) илиЛОЖЬ(логический 0). Примеры логических высказываний: Луна – спутник планеты Земля – истинное высказывание; Волга впадает в Черное море – ложное высказывание; Завтра ожидается хорошая погода – фраза не относится к логическому выска- зыванию. В алгебре логики не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Для обозначения истинности и ложности логических высказываний используют разные варианты: ИСТИНА И True T 1 ЛОЖЬ Л False F 0 Простые высказывания могут объединяться в составные или сложные вы- сказывания. Объединение высказываний выполняется с помощью логических операций и записывается в виде логических формул или логических выражений. Логическое выражение – это запись высказывания в математической форме, которая состоит из логических величин, связанных между собой логиче- скими операциями. Логические операции выступают в роли связок между логическими вели- чинами. Рассмотрим пример преобразования логического высказывания в логическое выражение и перевод полученного выражения в математическую форму (табл. 17). Таблица 17 Формирование логического выражения Полное высказывание F диаметр Земли больше диаметра Венеры и меньше диа- метра Юпитера Высказывание А диаметр Земли больше диаметра Венеры Высказывание В диаметр Земли меньше диаметра Юпитера 7 / 17 42 Продолжение табл. 17 Полное высказывание F диаметр Земли больше диаметра Венеры и меньше диа- метра Юпитера Союз «и» логическая операция между двумя высказываниями Логическое выражение F = А и В Значение выра- жения F = (1 и 1) = 1 Пример, приведенный в табл. 17, показывает, что полное высказывание F с помощью союза «и» связывается из двух исходных высказываний и является ис- тинным, поскольку истинны исходные высказывания А и В. Базовые логические операции В записи выражения логические высказывания принято обозначать латин- скими буквами А, В, С, а логические операции – словами естественного языка или специальными символами. Названия и способы обозначения основных или базовых логических операций показаны в табл. 18. Каждая логическая операция имеет свое наименование, определение и форму записи. В естественном языке, в алгебре логики и в языках программирования приняты разные формы записи од- них и тех же операций. Таблица 18 Обозначения базовых логических операций Наименование Формы записи в естественном языке в алгебре выска- зывания в языках программирования КОНЪЮНКЦИЯ И ∧ или & and ДИЗЪЮНКЦИЯ ИЛИ ∨ или + or ИНВЕРСИЯ НЕ, НЕВЕРНО, ЧТО… ¬ или − not Описание базовых логических операций и соответствующих определений этих операций представлено в табл. 19. 8 / 17 43 Таблица 19 Логические операции Наименование операции Форма записи Определение КОНЪЮНКЦИЯ (логическое умножение) A ∧ B Новое выражение, которое будет ис- тинным только тогда, когда истинны оба исходных простых выражения. Определяет соединение логических выражений с помощью союза И ДИЗЪЮНКЦИЯ (логическое сложение) A ∨ B Новое выражение, которое будет ис- тинным только тогда, когда истинно хотя бы одно из исходных выражений. Определяет различие двух логических выражений с помощью союза ИЛИ ИНВЕРСИЯ (логическое отрицание) ¬A К исходному выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО ИМПЛИКАЦИЯ (логическое следование) A→B Связывает два логических выражения, из которых первое является условием (А), а второе (В) – следствием. Резуль- татом является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Выражается словами ЕСЛИ, ТО ЭКВИВАЛЕНТНОСТЬ (логическая равнознач- ность или тождество) A↔B Результатом является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исход- ных выражения одновременно ис- тинны или ложны В табл. 19 показано пять логических операций: конъюнкция, дизъюнкция, ин- версия, импликация и эквиваленция. Эти функции связаны между собой опреде- ленными соотношениями. В частности, верны следующие выражения. 1. Импликацию можно выразить через дизъюнкцию и отрицание: A B A B → = ∨ 2. Эквивалентность можно выразить через отрицание, дизъюнкцию и конъ- юнкцию: 9 / 17 44 ( ) ( ) A B A B B A ↔ = ∨ ∧ ∨ Таким образом, для описания и обработки всех логических выражений доста- точно иметь три основные операции: инверсию, дизъюнкцию и конъюнкцию. Если в выражении использована не одна, а несколько логических операций, то действия выполняются в определенном порядке: 1 – инверсия, 2 – конъюнкция, 3 – дизъюнкция, 4 – импликация, 5 – эквивалентность. Для изменения указанного порядка действий используют скобки. Все возможные значения любой логической операции представляются в таб- лице истинности(см. табл. 20). Таблица истинности показывает, каким образом связаны комбинации входных логических величин с соответствующими значе- ниями на выходе логической операции. Таблица 20 Таблицы истинности логических операций Наименование операции Таблица истинности КОНЪЮНКЦИЯ A B A∧B 1 1 1 1 0 0 0 1 0 0 0 0 ДИЗЪЮНКЦИЯ A B A∨B 1 1 1 1 0 1 0 1 1 0 0 0 ИНВЕРСИЯ A ¬A 1 0 0 1 ИМПЛИКАЦИЯ A B A→B 1 1 1 1 0 0 0 1 1 0 0 1 ЭКВИВАЛЕНТНОСТЬ A B A↔B 1 1 1 1 0 0 0 1 0 0 0 1 10 / 17 45 В качестве примера составим таблицу истинности и рассчитаем значение ло- гического выражения (X˄Y)→ Y. В левых столбцах табл. 21 представим возмож- ные комбинации значений X и Y, а в правых – результат применения логических операций. Полученный в табл. 21 результат показывает, что выражение принимает зна- чение «ИСТИНА» при любых значениях истинности входящих переменных. Та- кое выражение называется тождественно истинным, или логическойтавтоло- гией. Логические тавтологии называют также логически истинными высказыва- ниями. Если выражение принимает значение «ЛОЖЬ» при любых значениях истин- ности входящих в них переменных, то оно называется тождественно ложным вы- ражением, или противоречием. Противоречие называют также логически ложным высказыванием. Таблица 21 Пример расчета таблицы истинности X Y X ˄ Y (X ˄ Y) →Y 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 Логические элементы и схемы Математический аппарат логики используется для описания процесса функ- ционирования вычислительной техники. Вычислительная техника основана на двоичной системе счисления, в которой используются цифры 0 и 1 и две логиче- ские переменные, которые также равны 0 и 1. Отсюда следует, что базовые ло- гические операции можно представить в форме технических элементов, которые реализуют логические функции. Логические элементы – простые конструкции, предназначенные для реа- лизации базовых логических операций и обработки данных в цифровой форме. Наглядное описание логических элементов может быть представлено в графиче- ской форме (табл. 22). Логические элементы имеют один или несколько входов и, как правило, один выход. Как входные, так и выходные сигналы имеют дискретную форму. Значе- ние сигнала на выходе логического элемента определяется комбинацией вход- ных сигналов и видом логической функции элемента. 11 / 17 46 Таблица 22 Графическое представление логических элементов Логические функции Обозначения логических элементов ИНВЕРСИЯ (НЕ) КОНЪЮНКЦИЯ (И) ДИЗЪЮНКЦИЯ (ИЛИ) ИНВЕРСИЯ КОНЪЮНКЦИИ (И – НЕ) ИНВЕРСИЯ ДИЗЪЮНКЦИИ (ИЛИ – НЕ) Из нескольких логических элементов можно построить простую или сложную логическую схему. Пример простой схемы показан на рис. 13, где представлена система безопасности механического пресса, предназначенная для ис- ключения травмирования конечностей работ- ника. В этой схеме сигнал от оператора к сило- вому узлу проходит через элемент «И» (&), ко- торый пропускает его тогда, когда включены оба пускателя, расположенные под его правой и левой рукой. Рис. 13. Система безопасно- сти механического пресса 12 / 17 47 Другой пример простой схемы – логический триггер (рис. 14). Логическая схема триггера строится из двух элементов «ИЛИ-НЕ», соеди- ненных таким образом, что при подаче внешнего сигнала элементы переключаются из одного со- стояния в другое и устойчиво хранят это состоя- ние до следующего переключения. Способность к сохранению одного из двух возможных состоя- ний позволяет использовать триггер в качестве ячейки памяти, в которой хранится 1 бит данных. Пример. Составим логическую схему для вы- ражения F = ¬(AVB) & ¬C и заполним таблицу истинности. В схеме должно быть 3 входа: A, B, C. Собираем логическую схему устрой- ства из трех элементов: инверсия дизъюнкции, инверсия и конъюнкция (рис. 15). Заполняем таблицу истинности для всех возможных комбинаций на входе схемы (табл. 23). Таблица 23 Таблица истинности выражения F = ¬(AVB) & ¬C Исходные данные Промежуточные данные Резуль- тат A B C AVB ¬(AVB) ¬C F 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 Рис. 14. Логическая схема триггера Рис. 15. Логическая схема 13 / 17 48 Получаем, что функция F на выходе будет равна 1 только тогда, когда все три входных сигнала равны нулю. Из основных логических элементов складываются и более сложные логиче- ские узлы, в частности: – регистры – устройства для хранения n-разрядных двоичных чисел и вы- полнения преобразований над ними; – комбинационные преобразователи кодов (шифратор, дешифратор, мультиплексор – устройство, в котором имеется один выход, зависящий от ком- бинации нескольких входных сигналов); – счетчики – устройства для подсчета количества поступающих импульсов и вывода результатов в двоичном коде; – арифметико-логические узлы (сумматор, узел сравнения). Из логических узлов строятся интегральные микросхемы более высокого уровня интеграции, например микропроцессоры, модули ОЗУ, контроллеры внешних устройств. Логические операции с множествами Множество можно представить как совокупность элементов, обладающих некоторым общим свойством. Объекты любой природы, составляющие множе- ство, называют его элементами. Например, автомобиль с конкретным номером является элементом множества автомобилей и т. п. Общее количество множеств не ограничено. Множества между собой могут пересекаться, объединяться или содержать подмножества. Для наглядного представления множеств и отношений между подмножествами используются диаграммы, которые называют кругами Эйлера, или кругами Эйлера – Венна. При построении кругов Эйлера предполагается, что они выделяют подмно- жества из одного и того же большого множества, которое называют универсаль- ным множеством. Предполагается, что универсальное множество содержит все используемые нами множества (обозначают символом U). Универсальное множество изображают в виде прямоугольника, а множества, входящие в универ- сальное множество, – в виде кругов внутри прямо- угольника; при этом элементу множества соответ- ствует точка внутри круга. Например, множество А в универсальном множестве U изображается с помо- щью затемненного круга, расположенного внутри прямоугольника (рис. 16). С помощью нескольких кругов Эйлера, располо- женных в универсальном множестве, удобно иллю- стрировать отношения между множествами и опре- делять характер этих отношений на основе базовых логических операций. Каждый вид отношений между множествами соответ- ствует определенной логической операции. Объединение множеств связано с Рис. 16. Множество А в универсальном множестве U 14 / 17 49 операцией дизъюнкции, пересечение множеств характеризуется операцией конъ- юнкции, а дополнение – инверсией. Примеры простых логических отношений между двумя множествами показаны в табл. 24. Операции с множествами могут использоваться для решения практических за- дач, в частности, для обработки данных, полученных из поисковых систем. При поиске по ключевому слову система сообщает, какое количество результатов было найдено. Полученное количество результатов можно представить некото- рым множеством web-страниц, на которых найдено ключевое слово. Таким об- разом, каждому ключевому слову соответствует множество, наполненное конеч- ным значением элементов, а разным ключевым словам соответствуют разные множества. Соотношение и количественную связь между множествами можно найти, используя данные поисковых систем и графическое представление мно- жеств. Таблица 24 Графическое и логическое представление множеств Отношения между множе- ствами Обозна- чение Круги Эйлера Логическое выражение Объединение двух мно- жеств – новое множество, состоящее из элементов, принадлежащих хотя бы од- ному из этих множеств АUВ Дизъюнкция A˅B Пересечениедвухмно- жеств – новое множество, состоящее из элементов, принадлежащих одновре- менно обоим множествам А∩В Конъюнкция A˄B Дополнениемножества А до множества U есть множе- ство, состоящее из тех и только тех элементов U, ко- торые не принадлежат А не А Инверсия ¬A Пример. Рассчитайте, сколько результатов (в млн шт.) будет найдено поиско- вой системой по запросу электрон или протон, если известны результаты запро- сов, представленные в табл. 25. 15 / 17 50 Таблица 25 Результаты поиска по ключевым словам Запросы Найдено результатов (млн шт.) электрон 155 протон 56 протон и электрон 21 Используем графическое представление множеств в виде кругов Эйлера. По- лучим два пересекающихся множества, одно из которых относится к слову «электрон», другое – к слову «протон». Вводим обозначения n 1 , n 2 , n 3 для под- множеств пересекающихся множеств. Соотношения между подмножествами определяем из табл. 25 и составляем исходные уравнения, из которых требуется найти объединение множеств, т. е. сумму 1 2 3 n n n + + . Решаем систему уравнений и получаем, что объединение двух множеств 1 2 3 190 млн шт. n n n + + = История развития вычислительной техники Создание вычислительных средств началось задолго до появления компью- теров. В истории вычислительной техники принято выделять три основных этапа: домеханический, механический и электронно-вычислительный. В этих эта- пах укладывается многовековой процесс развития человечества, который начи- нается со счета на пальцах и завершается созданием суперкомпьютеров. Вычислительные средства домеханического и механического этапов История создания счетных инструментов насчитывает более 30 тыс. лет. К числу древних счетных инструментов относятся следующие простые устрой- ства. 1. Абак. Изготовленная из камня или других материалов плита с линиями или желобками, в которые помещались и использовались для счета камешки или шарики (рис. 17). Инструмент появился в Древнем Вавилоне в III тысячелетии до новой эры. Египет узнал об абаке в V в. до н. э., в страны Средиземноморья он пришел в V–VI вв. н. э. и получил распространение в Древней Греции и Древ- нем Риме. Электрон Протон n 1 n 3 n 2 1 2 155 n n + = 2 3 56 n n + = 16 / 17 51 Рис. 17. Абак – древнейший счетный инструмент 2. Суаньпань. Китайская разновидность абака, представляющая собой пря- моугольную раму, в которой протянуты параллельные проволоки или веревки с нанизанными на них шариками. Перпендикулярно натянутым проволокам суань- пань разделен перегородкой на два неравных отделения. В большом отделении на каждой проволоке нанизано пять шариков, а в меньшем – два. Время появле- ния этого счетного устройства датируется VI в. Система счисления, используе- мая в суаньпане, – пятеричная (по числу пальцев на одной руке). 3. Соробан. Появился в Японии в Средние века. Его устройство выполнено по аналогии с китайским суаньпанем. Инструмент известен в настоящее время как японские счеты. Основное отличие соробана от китайского прототипа со- стоит в количестве спиц (веревок). В Японии соробан и по сей день используется в педагогике для начального обучения арифметическому счету. 4. Русские счеты – простое механическое устройство для выполнения арифметических расчетов. Представляет собой раму, имеющую некоторое количе- ство спиц, на которые нанизаны костяшки. Количество костяшек – 10. Система счисления – десятичная. Мнения историков относительно появления этого устрой- ства на Руси разделились. Одни считают, что счеты – это разновидность китай- ского суаньпаня, пришедшего к нам с золотоордынскими татарами в XIV в. Другие полагают, что счеты произошли от прибора «дощаный щот», возникшего в Мос- ковском государстве в XVI в. 5. Логарифмическаялинейка. Была сконструирована для выполнения расчетов в XVI–XVIII в. и использовалась в инженерных работах вплоть до 1980 г. Линейка явилась переходным инструментом на пути к механическим счетным устройствам. Логарифмической линейкой можно выполнять деление и умножение чисел, возводить их в квадрат и куб, извлекать корень, решать урав- нения и др. Точность вычисления – 3 значащих цифры. Несмотря на кажущуюся простоту, все инструменты домеханического этапа не только дожили до наших дней, но кое-где используются до настоящего времени. На следующем механическом этапе развития появились первые счетные меха- низмы, создание и совершенствование которых продолжалось с XV до XIX в. К наиболее значимым достижениям механического этапа относятся следующие устройства. 1. Первым механическим счетным устройством принято считать тринадцати- разрядное суммирующее устройство на основе зубчатых колес, созданное 17 / 17 52 Леонардо да Винчи в виде рисунка в начале XV в. При жизни изобретателя это устройство, скорее всего, не создавалось. Уже в XX в. на основе найденного эскиза при участии фирмы IBM была создана действующая модель суммирую- щего устройства. 2. Первая действующая механическая счетная машина была изготовлена в 1623 г. профессором математики Вильгельмом Шиккардом. Машина суще- ствовала в единственном экземпляре. В машине Шиккарда впервые была исполь- зована принципиальная схема, которая послужила основой для последующих моделей счетных машин. 3. Счетное устройство, на котором можно было выполнять четыре ариф- метических действия, была создана немецким математиком и физиком Готфри- дом Лейбницем в 1673 г. Доработанное устройство, имеющее двенадцать раз- рядов, было завершено в 1710 г. 4. Универсальная цифровая вычислительная машина,которая послу- жила прообразом ЭВМ, была разработана британским математиком и изобрета- телем Чарльзом Бэббиджем в 1833 г. Машина в автоматическом режиме вы- полняла сложные вычисления с высокой степенью точности. 5. Арифмометр с зубчаткой и переменным количеством зубцов раз- работал российский механик шведского происхождения Вильгодт Однер. В 1873 г. он изготовил первый прототип, а в 1890 г. наладил промышленное про- изводство арифмометров в Санкт-Петербурге. Позже его арифмометры выпуска- лись в Германии и Швеции. 6. Арифмометр «Феликс», конструкция которого была разработана Одне- ром, с 1925 г. до середины XX в. производился в Москве под торговой маркой «Феликс» и был широко распространенным механическим счетным устрой- ством. Все вычислительные устройства механического этапа были ручными и не могли функционировать без участия человека в процессе вычислений. Для вы- полнения каждой операции необходимо было набирать исходные данные, при- водить в движение счетный механизм, результаты всех операций записывать. Высокая трудоемкость механических расчетов не позволяла решать вычисли- тельные задачи большого объема. |