- •Информатика Учебное пособие
- •Содержание
- •Предисловие
- •Тема 1. Введение
- •1.1. Цель и задачи курса «Информатика»
- •1.2. Объекты и составные части информатики
- •1.3. Информатика как единство науки и технологии
- •Контрольные вопросы
- •Тема 2. Основные понятия информатики
- •2.1. Место информатики в системе наук
- •2.2. Основные понятия курса «Информатика»
- •Предмет информатики составляют следующие понятия:
- •Информация классифицируется по видам. (рис. 2.4.)
- •Тема 3. Основы дискретной математики.
- •3.2. Основы логики
- •Элементарные булевые функции
- •Из них выделим функцию "отрицание X" (обозначается -X). Эта функция представлена в таблице
- •3.3. Графы и деревья
- •А) граф g; б) остов графа g; в) другой остов графа g
- •Тема 4. Основные понятия архитектуры эвм
- •Для представления числовых данных в эвм используются естественная и нормальная формы записи чисел.
- •4.2. Системы счисления. Правила перевода чисел из одной системы счисления в другую
- •3. Арифметические операции
- •4.3. Логические элементы компьютера
- •В качестве важных последовательностных схем, выполняемых на одной ис, можно отметить счетчики, сдвиговые регистры, элементы памяти и др.
- •Структурная схема базовой модели мп фирмы Intel представлена на рисунке 4.15.
- •4.5. Организация памяти компьютера
- •Используется два основных типа оперативной памяти:
- •Контрольные вопросы
- •Тема 5. Алгоритмическое решение задач, анализ алгоритмической сложности.
- •5.1. Стратегия решения задач.
- •5.2. Алгоритмы (свойства, реализация алгоритмов)
- •5.3. Структуры данных
- •5.4. Основные вычислительные алгоритмы.
- •5.5. Анализ алгоритмов
- •1. Сравнительные оценки алгоритмов
- •2. Система обозначений в анализе алгоритмов
- •3. Классификация алгоритмов по виду функции трудоёмкости
- •4. Асимптотический анализ алгоритмов
- •Контрольные вопросы
- •Тема 6. Знакомство с языками программирования.
- •6.1. Обзор языков программирования
- •6.2. Основные конструкции программирования
- •Внутри программы значение свойств можно изменять как угодно часто.
- •Константы.
- •На практике наибольшее распространение получили язык функционального программирования lisp и два его диалекта: язык Common lisp и язык Scheme.
- •Наиболее распространенным языком логического программирования является язык Prolog (Пролог).
- •Контрольные вопросы
- •Тема 7. Основы операционных систем
- •7.1. Основные концепции операционных систем
- •7.4. Файловые системы
- •7.6. Обзор современного прикладного программного обеспечения
- •Контрольные вопросы
- •Тема 8. Сети и телекоммуникации
- •Компоненты сети
- •По программной совместимости эвм: однородные (гомогенные) и неоднородные (гетерогенные);
- •8.3. Системы телекоммуникаций
- •Типы телекоммуникационных систем
- •Системы телевещания
- •Системы подвижной связи
- •Сети сотовой подвижной связи
- •Сети транкинговой связи
- •Сети персонального радиовызова
- •Сети мобильной спутниковой связи
- •Волоконно-оптические сети
- •Контрольные вопросы:
- •Тема 9. Сеть Internet
- •9.1. Теоретические основы Internet
- •9.2. Основные понятия (сайт, сокет, сервер, клиент). Web как пример архитектуры «клиент-сервер»
- •9.3. Службы Internet
- •Контрольные вопросы:
- •Тема 10. Графическое программное обеспечение
- •10.1. Иерархия графического программного обеспечения. Графические коммуникации. Графические системы.
- •10.2. Системы растровой и векторной графики
- •Описание объекта является простым и занимает мало памяти;
- •10.3. Графические редакторы
- •Контрольные вопросы
- •Тема 11. Основы защиты информации
- •11.1. Информационная безопасность и ее составляющие
- •11.2. Угрозы безопасности информации и их классификация
- •11.3. Сетевая безопасность
- •11.4. Антивирусные программы
- •Контрольные вопросы
3.2. Основы логики
Как было отмечено ранее, информатика — прикладная наука, находящаяся на стыке многих наук. Вместе с тем она опирается на спектр разделов такой фундаментальной науки, как математика. Наиболее важное прикладное значение для информатики имеют булева(я) алгебра, используемая в разработке алгоритмов программ и в синтезе цифровых устройств, теория множеств и теория графов, используемые в описании различных структур.
Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами.
Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозначим 1). Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержательная часть высказываний, а только их истинность. Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.
Аппарат булевой алгебры, как и любая другая формальная математическая система, состоит из трех множеств: элементов, операций над ними и аксиом.
Элементы. Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие. Первые производят обработку информации, представленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться бинарными символами {0,1} или логическими значениями {Истина (True), Ложь (False)}. Поэтому множество элементов булевой алгебры выбирается бинарным В - {0,1}, а сама алгебра называется бинарной, или переключательной. Ее элементы называются константами, или логическими 0 и 1, которым в ряде случаев соответствуют бинарные цифры, в других случаях — логические значения, соответственно ложь (False) и истина (True). В дальнейшем для обозначения булевых переменных будем использовать буквы латинского алфавита — х, у, г... Набор переменных х, у, z... может рассматриваться как n-разрядный двоичный код, разрядами которого являются эти переменные.
Операции. Основными, или базовыми, операциями булевой алгебры служат (табл. 3.1): И (AND), ИЛИ (OR) и НЕ (NOT). Операция И называется логическим умножением, или конъюнкцией, и обозначается знаком умножения {•, }. Операция ИЛИ называется логическим сложением, или дизъюнкцией, и обозначается знаком сложения {+, }. Операция НЕ называется логическим отрицанием, или инверсией (дополнением), и обозначается знаком {—, ¬}.
Таблица 3.1 Базовые логические операции
Операция |
Название операции |
Обозначение операции | |
И (AND) |
Логическое умножение — конъюнкция |
• | |
ИЛИ (OR) |
Логическое сложение — дизъюнкция |
+ | |
ЕСЛИ (TO) |
Импликация, следование |
, | |
НЕ (NOT) |
Логическое отрицание — инверсия |
—, ¬ |
При выполнении операций применяются отношение эквивалентности «=» и скобки «( )», которые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в следующей последовательности: логическое отрицание, логическое умножение и логическое сложение.
Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логических операций. Рассмотрим их подробней.
Операцией отрицания А называют высказывание Ā (или -А, говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «завтра будет снег», то Ā «завтра НЕ будет снега», истинность одного утверждения автоматически означает ложность второго. Отрицание - унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ.
Это правило можно записать в виде следующей таблицы:
А |
Ā |
0 |
1 |
1 |
0 |
Такая таблица называется таблицей истинности.
Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А В или С = А & В (при этом говорят С равно А и В). Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери», т.е. данная операция применяется, если два высказывания связываются союзом И.
Таблица истинности этой операции, как следует из определения, имеет вид
А |
В |
А&В |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A В (при этом говорят: С равно А ИЛИ В). Пример такой операции следующий: пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ.
Таблица истинности такой операции следующая:
А |
В |
AB |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно, записывается С = А В (при этом говорят: из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.
Таблица истинности импликации следующая:
А |
В |
А→В |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
Импликация имеет следующие свойства:
А→В В → А
А→ А= 1
0 →А= 1
1 → А = А
А→ 1 = 1
А→ 0 = А
Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А В (С = А В). Примером такой операции может быть любое высказывание типа: событие А равносильно событию В.
Таблица истинности:
А |
В |
А↔В |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Эквиваленция имеет следующие свойства:
А↔ В = В ↔ А
А ↔ = ↔Ā
А↔ 1 = А
А ↔ 0 = Ā
С помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические выражения, которые также называются булевскими функциями. Например, С = ((A В) → В) А.
Чтобы избежать большого количества скобок в булевских функциях, принято следующее соглашение о старшинстве операций.
Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.
Зависимости между логическими операциями
Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности:
Законы алгебры логики
Закон двойного отрицания
коммутативный закон для конъюнкции
коммутативный закон для дизъюнкции
ассоциативный закон для конъюнкции
ассоциативный закон для дизъюнкции
дистрибутивные законы
законы де Моргана
закон идемпотенции для конъюнкции
закон идемпотенции для дизъюнкции
закон единицы для конъюнкции
закон нуля для конъюнкции
закон единицы для дизъюнкции
закон нуля для дизъюнкции
закон исключения третьего
закон противоречия
законы поглощения
Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований (формул 1-23).
Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид Al A2 ... An, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например:
В = (А1 & А2 & A3) (А4 & А5).
Вторая - конъюнктивная нормальная форма (КНФ), имеет вид А1 А2 ... An, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например:
В = (Al А2 A3) & (А4 А5) & А6.
Аксиомы (постулаты) алгебры логики
1. Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1 и равна 0, если обе переменные равны 0:
0+0=0;
0+1=1;
1+0=1;
1+1=1.
2. Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0 и равна 1, если обе переменные равны 1:
0∙0=0;
0∙1=0;
1∙0=0;
1∙1=1.
3.Инверсия одного значения переменной совпадает с ее другим значением:
1= 0;
0 = 1.