Лекция: Практическое занятие № 3 (продолжение). Технология работы в ОС Windows. Работа с программой Проводник. Совместное использование папок в локальной сети
| … | |||||
| … | |||||
| … | |||||
| … | … | … | … | … | … |
Из этой таблицы видно, что число различных двоичных наборов длины конечно и равно .
Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из строк, то есть принимает значений (каждое 0 или 1). Общее число наборов из 0 и 1 длины равно Это число равно числу различных функций алгебры логики переменных.
Каждой формуле алгебры логики соответствует своя функция. Если формулы и эквивалентны, то соответствующие им функции равны:. Это значит, что при всех значениях переменных значения и совпадают.
Каждая булева функция может быть путем эквивалентных преобразований приведена к двум особым формам, которые называются дизъюнктивной и конъюнктивной нормальными формами. Пусть переменные булевой функции, а — набор этих переменных. Введем обозначение:, где — параметр, равный 0 или 1. Очевидно, что Тогда функцию можно представить в виде:
, (1.13.4)
где дизъюнкция берется по всевозможным наборам значений переменных или
, (1.13.5)
где символ означает, что конъюнкции берутся по тем наборам переменных, которые указаны под ним. Нормальные формы позволяют дать критерий равносильности двух произвольных формул и .
Аппарат булевых функций используется для проектирования цифровых устройств и базовых элементов компьютерных систем.
1.13.2. Элементы теории множеств. Первичным понятием теории множеств является понятие самого множества. Множество – это совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными. Множество обозначается парой скобок, внутри которых либо просто перечисляются элементы, либо описываются их свойства. Например, — множество натуральных чисел, удовлетворяющих условию, очевидно, пусто. сложение, умножение — множество основных арифметических операций. Пустое множество обозначается знаком Æ. Если необходимо указать, что объект является элементом множества, то пишут ( принадлежит ), наоборот запись говорит о том, что не принадлежит .
Если каждый элемент множества является элементом множества, то пишут или и говорят, что множество является подмножеством множества. Если есть подмножество множества, причем, то пишут или. Множества, состоящие из одних и тех же элементов, называются равными, то есть, в противном случае. С помощью скобок и операций над множествами можно построить новые множества, более сложные чем исходные.
Объединение (или сумма). Эта операция над множествами обозначается, определяется как. Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера*- Венна**. Если за некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить (или ) и изобразить его в виде всей плоскости, то любое множество можно изобразить в виде части плоскости, то есть в виде некоторой фигуры, лежащей на плоскости. Множество объединение множеств и, на рис. 1.7 заштриховано. .
Пересечением (или произведением)двух множеств называется такое множество, которое состоит из элементов, принадлежащим одновременно обоим множествам, то есть. Пересечение множеств и заштриховано и изображено на рис. 1.8.
Разностью двух множеств и называется множество, состоящее из тех и только тех элементов, которые входят в и одновременно не входят в, то есть (см. рис 1.9). Если, в частности, подмножество, то разность обозначается и называется дополнением множества (см. рис 1.10).
Симметрической разностью или кольцевой суммой множеств и называется множество (см. рис 1.11). Очевидно, что. Если и, то пару элементов называют упорядоченной парой, причем пары и равны тогда и только тогда, когда
Множество, элементами которого являются все упорядоченные пары,, называется прямым или декартовым произведением множеств и и обозначается Например, а Таким образом, декартово произведение не подчиняется коммутативному закону и справедливо, если Произведение называется декартовым квадратом.
Свойства операций объединения, пересечения и дополнения иногда называются законами алгебры множеств. Эти законы аналогичны правилам для равносильностей в булевой алгебре (1.13.1) –(1.13.3).
Часто элементы разных множеств связаны различными соотношениями, например, соотношениями порядка. -местным отношением или -местным предикатом на множествах называется любое подмножество декартова произведения. Обозначение -местного отношения. При отношение называется унарным и является подмножеством множества. Бинарным (или двуместным при ) отношением называется множество упорядоченных пар. Элементы называются координатами или компонентами отношения .
В теории множеств важную роль играют два вида специальных бинарных отношений: отношения эквивалентности и отношения порядка. Прообразами этих отношений служат интуитивные понятия равенства, предшествования и предпочтения.
Рассмотрим два конечных множества, и бинарное отношение. Введем матрицу бинарного отношения следующим образом: Эта матрица содержит полную информацию о связях между элементами множеств и и позволяет представить эту информацию в графическом виде.
Матрица любого бинарного отношения обладает следующими свойствами:
q если и, то;, причем сложение элементов матрицы осуществляется по правилам 0+0=0, 1+1=1, 1+0=0+1=1, а умножение осуществляется почленно обычным образом, т. е. по правилам ;
q, где — матрица обратного отношения ;
q если, то и .
Пример 1.Бинарное отношение изображено на рис. 1.12. Его матрица имеет вид. Пусть, тогда, .
Пусть — бинарное отношение на множестве,. Отношение на множестве называется рефлексивным, если, т. е., где звездочкой обозначены нули или единицы. Отношение называется иррефлексивным, если. Отношение на множестве называется симметричным, если из условия следует, что. Это значит, что. Отношение называется антисимметричным, если из условий и следует, что, или. Это свойство приводит к тому, что у матрицы все элементы вне главной диагонали будут нулевыми (на главной диагонали тоже могут быть нули). Отношение называется транзитивным, если из и следует, что .
Рефлексивное, транзитивное и симметричное отношение на множестве называется эквивалентностью на. Эквивалентность обозначается символами или ~, например,, .
Пример 2. Докажем, что на множестве отношение является отношением эквивалентности, если .
Если отношение рефлексивно на, то. В нашем случае роль играет множество, а роль элемента играет пара. Тогда отношение рефлексивно на, если. По определению, но, следовательно, рефлексивно.
Аналогично, если, то и, так как из следует, что. Таким образом, симметрично.
Наконец, если,, то, так как и. Тогда, т. е. транзитивно.
Рефлексивное, транзитивное и антисимметричное отношение на множестве называется частичным порядком на. Частичный порядок обозначается символом, а обратное ему отношение символом. Отношение < называется строгим порядком и определяется таким образом. Это отношение не является частичным порядком, так как не удовлетворяет условию рефлексивности .
Если во множестве есть элементы и, о которых нельзя сказать, что или, то такие элементы называются несравнимыми. Частичный порядок называется линейным порядком, если любые два элемента и из множества сравнимы, т. е. или .
Непустое множество, на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством. Элемент частично упорядоченного множества называется максимальным (минимальным), если для из того, что следует. Элемент называется наибольшим (наименьшим), если для всех. Наибольший элемент обозначается, наименьший — . Этих элементов у множества может и не быть, например, линейно упорядоченное множество рациональных чисел не имеет наименьшего элемента, наибольший элемент равен единице.
Верхней (нижней) гранью подмножества частично упорядоченного множества называется всякий элемент и такой, что для всех. Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для. Точная верхняя и точная нижняя грани множества обозначаются через (супремум) и (инфимум) соответственно.
Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.
1.13.3. Элементы теории графов.Граф задается парой множеств. Пусть — непустое множество, — множество всех его двухэлементных подмножеств, Тогда пара называется неориентированным графом.Элементы множества называются вершинами графа, а элементы множества — ребрами. Итак, граф — это конечное множество вершин и множество ребер .
Вершины графа обозначают по-разному: или большими буквами, или малыми с индексами; для ребер наиболее употребительное обозначение — с индексом, например, Взаимное расположение, форма и длина ребер значения не имеют. Важно лишь то, что они соединяют две данные вершины множества .
Если в паре вершин указано направление связи, т. е. какая из вершин является первой, то соединяющий их отрезок называется дугой, а вершины, определяющие дугу, называют концевыми вершинами. Если концевые вершины совпадают, то дугу называют петлей. В графе могут существовать дуги (ребра) с одинаковыми концевыми вершинами. Такие дуги называются параллельными.
Если в графе все элементы множества изображаются дугами, то граф называется ориентированным или орграфом, если ребрами, то неориентированным. Два ребра называются смежными, если они имеют общий конец.
Вершина и ребро называются инцидентными, если является концом ребра и не инцидентными в противном случае. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.
Число вершин графа называется его порядком. Степенью вершины называется число дуг (ребер) графа, инцидентных данной вершине. Вершина степени нуль называется изолированной, а если степень равна единице, то такая вершина называется висячей.
Граф называется простым, если он не содержит петель и параллельных дуг. Простой граф, в котором каждая пара вершин смежна, называется полным. Граф, содержащий хотя бы две параллельные дуги (ребра), называется мультиграфом. Граф, содержащий петли, называется псевдографом.
Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. Два графа и называются изоморфными, если между множеством их вершин существует такое взаимно однозначное соответствие, при котором в одном из графов ребрами соединены вершины в том и только в том случае, если в другом графе ребрами соединены те же вершины. Для орграфов ориентация дуг должна быть также одинаковой.
Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны.
Способов задания графов – великое множество. Самый простой способ – задание множеств и. Граф также может быть задан просто рисунком. В силу изоморфизма один и тот же граф может быть изображен разными рисунками.
Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все пересечения ребер являются его вершинами. Для произвольного графа следующим образом определяется дополнительный граф (дополнение) . В этом графе вершин столько же, сколько в графе, причем любые две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в (см. рис. 1.13).
Чередующая последовательность вершин и ребер графа, такая что, называется маршрутом, соединяющим вершины. Очевидно, что маршрут можно задать последовательностью его вершин или последовательностью ребер. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Гамильтоновой цепью называется простая цепь, содержащая все вершины графа.
Маршрут называется циклическим, если. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется длиной маршрута. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа. Длина всякого цикла не менее трех в графе без петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.
Важным понятием теории графов является связность. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.
В подавляющем большинстве случаев граф задается матрицей. Для расчетов на ЭВМ это единственный способ. Наиболее часто граф задают с помощью матриц смежности и инциденций. Рассмотрим изображенный на рисунке 1.14 граф. Как для орграфов, так и для неориентированных графов можно определить матрицу смежности вершин. Это квадратная матрица
порядка, где — число вершин. Ее строки и столбцы соответствуют вершинам графа. Элементы матрицы смежности вершин равны числу дуг, идущих из — той вершины в
-ю вершину. Если орграф не содержит параллельных дуг, то матрица является бинарной и состоит только из нулей и единиц. В случае неориентированного графа ему вместе с ребром принадлежит и ребро, поэтому матрица смежности вершин будет симметрической. Матрица смежности вершин однозначно определяет структуру графа. Аналогично можно определить и матрицу смежности дуг.
Определим для рассматриваемого графа без ребра матрицу инциденций. Это прямоугольная матрица размерности, где — число вершин, а — число дуг. Элементы этой матрицы равны плюс единице, если дуга исходит из -й вершины (начальная вершина), минус единице, если дуга входит в -ю вершину (конечная вершина), нулю, если дуга не инцидентна -й вершине. В случае неориентированного графа элементами матрицы будут числа единица и нуль, т. е. Строки матрицы инциденций называют векторами инциденций графа Матрица инциденций
* Клод Элвуд Шеннон (1916 – 2001) – американский математик.
* Хартли
* Фэно
* Огастес Морган (де Морган)(1806 – 1875) – шотландский математик и логик.
* Леонард Эйлер (1707 — 1783) — швейцарский математик.
** Джон Венн (1834 — 1923) — английский математик и логик.
Практическое занятие № 3 (продолжение). Технология работы в ОС Windows. Работа с программой Проводник. Совместное использование папок в локальной сети
Операционная система Windows 2000 является высокопроизводительной, универсальной, надёжной, многозадачной и многопотоковой 32-разрядной ОС с расширенными сетевыми возможностями. Она обеспечивает работу пользователя в сети, с электронной почтой, с факсом, со средствами мультимедиа, поддерживает большинство приложений DOS и предыдущих версий Windows.
В системе допускается использование имён, содержащих до 255 символов. Расширение имени файла зависит от приложения, в котором он создавался. В ОС Windows широко используется графический интерфейс: рисунки, специальные значки, цветовое оформление, дизайн экрана и т. п. Графический интерфейс Windows позволяет более оперативно задавать команды операционной системы, запускать программы, выбирать файлы и параметры и т. д. Набор используемых элементов интерфейса стандартен, что позволяет после изучения интерфейса Windows легко осваивать интерфейс приложений Windows.
В комплект поставки операционной системы входят стандартные приложения прикладного и служебного назначения такие, например, как графический редактор Paint, текстовые редакторы Блокнот и WordPad, программы работы с файлами и дисками.
Главным объектом интерфейсной части Windows является окно – прямоугольная часть экрана, которая позволяет просматривать выведенную в ней информацию. Различают три типа окон:
§ окно программы;
§ окно документа (объекта обработки программы);
§ диалоговое окно.
Программа Проводник в своём первоначальном значении определялась как программа-обозреватель локальных и сетевых ресурсов персонального компьютера. Её функции во многом сходны функциям программ-оболочек операционной системы MS DOS, таких, например, как FAR manager.
Программа Проводник управляет файлами и обеспечивает один из наиболее удобных способов просмотра файловой системы. Основное преимущество этой программы по сравнению с окнами папок на Рабочем столе состоит в том, что в Проводнике можно одновременно работать с содержимым правой панели окна и со всей структурой файловой системы компьютера на левой панели.
При работе с программой Проводник необходимо освоить следующие операции:
§ просмотр каталога диска, просмотр содержимого папок;
§ разворачивание и сворачивание папок, копирование, перемещение, удаление файлов и папок;
§ поиск файлов, папок и приложений;
§ сортировку объектов.
Запуск программы можно выполнить несколькими способами:
§ кнопкой <Пуск> и контекстным меню (Пуск – Программы, щелчок правой кнопкой мыши, команда Проводник);
§ каскадным меню Программы (Программы – Стандартные – Проводник);
§ с помощью папки Мой компьютер, командой Проводник.
Любой компьютер можно подключить через локальную сеть к другим компьютерам. Доступ к другим компьютерам сети осуществляется через системную папку Сетевое окружение (см. рис. 3.12), расположенную на Рабочем столе. При открытии папки Сетевое окружение в окне появляются все доступные компьютеры данной рабочей группы. Специальная папка Вся сеть позволяет установить связь с компьютерами других рабочих групп.