Архив рубрики: Блог

Компания Prost посетила iForum 2013

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

  • ИНТЕРНЕТ БИЗНЕС
  • РЕКЛАМА/АНАЛИТИКА/ПРОДВИЖЕНИЕ
  • СТАРТАПЫ E-COMMERCE
  • MOBILE/ИГРЫ/ЮЗАБИЛИТИ
  • ИНТЕРНЕТ ТЕХНОЛОГИИ
  • МАСТЕР-КЛАССЫ, СЕМИНАРЫ

На iForum 2013 докладчиками были рассмотрены различные темы и актуальные проблемы IT-сферы, были озвучены новые тенденции интернет-рекламы.

Относительно Яндекса (голландской компании), который сейчас переживает не лучшие времена,  Антон Носик озвучил мнение, что все неприятности Яндекса связаны с тревогами в Евросоюзе, в частности в Греции, а отнюдь не из-за финансовых показателей, с которыми все ок.

Что касается новых тенденций в интернет-рекламе, то будущее за видео-рекламой! Максим Макаренко (Google Украина) представил новый формат True View. То есть за такую видео-рекламу клиент платит только когда пользователь вовлечен. То есть когда досматривает видео-ролик до конца. В случае же если пользователь делает клик на 10 секунде просмотра и переходит на сайт клиента, то клик бесплатный, а влияние все равно ощутимое. Видео оставляет больший след в подсознании человека чем текст.

 

 
  

 

Относительно рекомендаций в продвижении сайтов интернет-магазинов по-прежнему высоко ценится поисковыми системами контент:

  • видеообзоры
  • характеристики товаров
  • отзывы потребителей

Для ПС важна так же доступность сайта — удобность контента, юзабилити.

Здесь заметим, что важно грамотно структурировать каталог продукции/услуг — разбивать по брендам, подвидам и т.д.

Антон Воронюк представил довольно интересную статистику. После запуска в 2012 г. 19 апреля — Panda 3.5, 24 апреля — Penguin 1.0, 27 апреля — Panda  3.6 пострадало в google.ru 37% сайтов, из них к сентябрю 2012 года свои позиции вернуло только 1,1 % сайтов.

Кейсы спасения:

1. Жесткие требования к доступности сайта, к уникальности текста

Заметим, что после запуска обновленного google translate теперь гугл больше разбирается в славянских языках ( в частности русский и украинский)

2. Большое количество запросов — сейчас уже не продвинешь сайт по 10-20 запросам

3. Требования к ссылочным факторам:

  • Анкорный текст
  • Возраст ссылки
  • Количество ссылок
  • Качество ссылок

Поисковики в ссылках хотят видеть БРЕНД, название компании, название сайта.

   

 

 

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

— уход от позиций

— SEO-аналитика рулит!

— долгосрочные цели стают передовыми

— link building

—  приоритет юзабилити

— мобильный поиск

— локальные запросы

In-content filter — Google плохо реагирует на ссылки внутри статей

голосовой поиск

— персонализация выдачи (результаты Google+)

— продвижение с оплатой за позиции (разными методами: трафиковое СЕО, оплата за звонки…)

— факторы ранжирования — уровень авторитетности сайта

— покупать ссылки нужно с разных бирж

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

 

 

 

Как избежать 12 распространенных ошибок в разработке коммерческого сайта

Герман Дрост

 

На Ваш сайт регулярно заходит большое
количество посетителей, которые ничего не покупают? Что ж, возможно,
пришло время переработать дизайн Вашего ресурса. Зачастую Ваше детище
настолько Вам дорого, что Вы относитесь к нему слишком необъективно, не
замечая очевидных ошибок в его оформлении. Это случается со всеми, в
том числе и со мной, когда я пишу очередную статью. Закончив и
перечитав ее, я радуюсь тому, как замечательно все написал, но когда
возвращаюсь к статье на следующий день, то бываю буквально потрясен
количеством сделанных в ней ошибок.В настоящей статье я собираюсь рассмотреть 12 наиболее часто совершаемых ошибок при разработке коммерческого сайта.

1. Небрежно
сработанный заголовок. Зачастую предприниматели не уделяют должного
внимания разработке заголовков, что влечет за собой рассеивание
внимания посетителей и не оставляет шансов на то, что они выполнят те
действия, которых Вы от них ждете. Заголовок и следующее за ним
предложение должны четко и ясно объяснять пользователю назначение
Вашего сайта. Помните общеизвестную формулу о том, что король Всемирной
Паутины – это контент? Так вот, переведите контент на Вашем сайте в
русло фокусировки на посетителе. Контент должен брать посетителя за
руку и вести его туда, куда он должен идти, подробно объясняя, что
должен делать посетитель, куда смотреть, куда нажимать и т.п. На каждой
странице размещайте свою контактную информацию, чтобы в случае чего
посетитель смог легко связаться с Вами, если у него появятся какие-либо
вопросы.

2. Плохо
подобранная цветовая гамма. Не вздумайте использовать темный цвет для
текста на темном фоне. Следует использовать темный текст на светлом
фоне, лучше всего текст должен быть черным, а фон — белым. Таким
образом он будет лучше всего читаться посетителями. Гамму цветов,
которую Вы используете на своем сайте, нужно подбирать так, чтобы цвета
хорошо между собой сочетались. Цветов в гамме должно быть немного.
Лучше всего позаимствовать хорошую цветовую гамму у природы, но для
этого нужно быть, по меньшей мере, натуралистом-любителем и обладать
хорошей наблюдательностью.

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

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

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

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

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

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

9. Плохой дизайн. Для того, чтобы посетителям было приятно заходить на Ваш
ресурс и оставаться на нем, он должен иметь эстетичный и приятный для
глаза дизайн (имеется в виду взаимное расположение элементов на
страницах). Используйте поля, выдерживайте промежутки между текстом и
графическими изображениями. Разделяйте абзацы пустыми строками. Ибо
наличие единого текстового блока создает у посетителей такое
впечатление, что Вы попросту вываливаете контент им на голову. Для
отображения текста используйте традиционные шрифты, такие, как Arial,
Verdana и им подобные, чтобы сделать текст максимально легким для
прочтения с экрана монитора.

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

11. Несовместимость страниц с различными браузерами и экранными
параметрами. Если Вы не разрабатываете свой сайт таким образом, чтобы
он точно также хорошо смотрелся в других браузерах и при настройках
экрана, отличных от Ваших, Вы теряете большое количество посетителей.
Ибо далеко не все используют тот же браузер, что и Вы, и имеют экранные
настройки аналогичные Вашим. И несмотря на то, что абсолютное
большинство пользователей Сети использует в своей работе Internet
Explorer различных версий и экранное разрешение 800 х 600 с глубиной
цвета 16 бит, необходимо удостовериться, что созданный Вами сайт будет
одинаково хорошо смотреться и в других браузерах, а также с другими
разрешениями экрана.

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

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

 

Источник: www.insiderreports.com

Перевод на русский язык: Павел Берестнев

www.berestneff.com

 

Семь трендов современной интернет-торговли

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

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

Тренд 1. Региональный Интернет остается свободным

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

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

Тренд 2. Некоторые товары остаются неизменными. Меняется подход

Доля интернет-магазинов, торгующих «традиционными» для Сети товарами
(теми, с которых «всё начиналось» — книгами, DVD и CD) практически не
снижается. Многие сайты закрываются из-за возросшей конкуренции, на
смену им приходят новички. Чтобы достичь успеха, владельцам новых
онлайн-магазинов приходится фокусироваться на «узкой» тематике и
аудитории: например, открывать магазины культовой литературы, этнической
музыки или фильмов-концертов. Возможно, в дальнейшем подобных
«узкотематических» интернет-магазинов станет больше.

Тренд 3. Продавцы из регионов могут выиграть за счет доставки

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

Тренд 4. Даже в освоенных тематиках остаются незанятые ниши

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

Тренд 5. Покупатели по-прежнему предпочитают наличные

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

Тренд 6. Некоторые платежные системы уйдут с рынка

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

Тренд 7. Растет популярность SMS-платежей

Когда некоторые крупные игроки, предоставлявшие услуги смс-биллинга,
прекратили свое существование, их место сразу же заняли новые. Это и
понятно — предоставление такого рода услуг в нашей стране только-только
набирает обороты и является весьма перспективным делом. Кроме того,
подобный вид оплаты понравился и покупателям. Так, по данным
интернет-магазина Allsoft.ru, платные SMS вошли в пятерку наиболее
популярных способов оплаты, наряду с пластиковыми картами, платежами
через Сбербанк, системами «Яндекс.Деньги» и WebMoney.

Вместо заключения

Как ни крути, а финансовый кризис повлияет на онлайн-торговлю. Изменятся как покупатели, так и интернет-магазины.

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

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

Электронную торговлю все же «зацепит» кризис кредитования (особенно
тяжело придется крупным игрокам), обострятся проблемы с неполучением или
задержкой платежей.

Нас ждет тотальное «перетасовывание» рынка. Появятся новые ниши. Станет
больше проигравших, а их место займут новые, более жизнеспособные,
победители.

Алексей Леонов, исполнительный директор сервиса аренды интернет-магазинов Shop-Rent.ru

О дизайне

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

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

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

Дроздовский Михаил
www.woweb.ru/publ/26-1-0-685

Что влияет на дизайн сайтов?

Прежде всего на дизайн сайтов оказывает огромное влияние аппаратное обеспечение Всемирной Сети.

В
настоящее время по данным некоторых независимых исследований (в
частности, проводимых агентством  ROMIR Monitoring) в крупных городах
России и Украины число пользователей, использующих широкополосные
каналы доступа в Интернет или ставших клиентами локальных сетей доходит
до 60-80%.  Учитывая тот факт, что переход клиентов на
высокоскоростной  ADSL — доступ в Днепропетровске, Киеве, Харькове,
Запорожье и других городах Украины в последние годы стал массовым
явлением , можно спрогнозировать что в ближайшее время, число клиентов,
использующих коммутируемый доступ в Интернет будет не более 10-12 % в
городах и не более 30 % в среднем по Украине.

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

Можно ещё упомянуть  о некоторых
ограничениях, которые стремительно уходят в прошлое. Например, следует
ли оптимизировать дизайн web-сайта под устаревшие мониторы с
разрешением экрана 640Х480 и 800Х600, или под браузер Nescape Navigator
1.0 ?    Пользователей, которые в настоящее время используют мониторы с
таким разрешением для просмотра web-страниц или пользующихся таким
«доисторическим» браузером  уже практически не осталось, во всяком
случае их просто невозможно найти среди потенциальных клиентов,
например,  бизнес- авиации, или потенциальных посетителей ресторанного
комплекса, или в отделах снабжения предприятий.   А ограничения,
которые приходится накладывать на дизайн страниц в таком случае,
значительно снижают привлекательность web-сайта.

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

www.promsistema.dp.ua/statyi_web.html

 

Дискретная математика

Лекция № 1. Множества, операции над ними. Соответствия

и функции.

1. Основные понятия теории множеств.

Определение. Множеством М называется объединение в единое целое

определенных различимых однотипных объектов а, которые называются элементами

множества.

Множество можно описать, указав какое-то свойство, присущее всем элементам

этого множества.

Замечание. Вообще говоря, понятие множества считается первичным (исходным)

понятием, и, как таковое, не определяется. Приведённое выше определение следует,

скорее, считать уточнением понятия множества.

Множество, все элементы которого являются числами, называется числовым. В

дальнейшем мы будем, прежде всего, рассматривать именно такие множества.

Множество, элементами которого являются другие множества, называется классом или

семейством.

Множество, содержащее конечное число элементов, называется конечным. При

подсчёте количества элементов учитываются только различные (неповторяющиеся)

элементы.

Множество, не содержащее элементов, называется пустым и обозначается

символом .

Множество может быть задано перечислением (списком) своих элементов,

порождающей процедурой или описанием характеристических свойств (предикатом),

которым должны обладать его элементы. Причём в последнем случае необходимо

формулировать описание характеристических свойств элементов множества достаточно

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

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

(например, множество чётных однозначных чисел).

Пример 1. Некоторые примеры множеств, заданных различными способами.

а) 4;3;2;11M.

б) 94,2xZxxM

Nnnxx,12

в) 3M

Мощностью конечного множества М называется количество его элементов.

Обозначается M

Определение. Если все элементы множества А являются также элементами

множества В, то говорят, что множество А включается (содержится) в множестве В.

а  М

. Если BA

.

.

, то множества А и В называются равномощными.

А

В

А  В

Определение. Если А  В, то множество А называется подмножеством множества

В (также говорят, что В покрывает А). Если при этом А  В, то множество А называется

собственным подмножеством множества В и обозначается А  В.

Замечание. Не следует считать равносильными отношения принадлежности )(и

вхождения одного множества в другое )(. Можно привести следующий пример. Пусть А

– множество всех студентов данной группы, а В – множество всех учебных групп данного

института. Здесь BA, но BA, поскольку элементы этих множеств разнородны. Этот

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

может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих

себя в качестве элемента: XXXY

ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если

YY, то YY. С другой стороны, если YY, то YY! Это противоречие можно

разрешить различными способами, в целом сводящимся к тому, что Y не является

множеством.

Для трех множеств А, В, С справедливы следующие соотношения:

Парадокс Рассела. Задание множеств характеристическим предикатом

. Если такое множество существует, то можно

;;AAAA

;CACBBA

;CACBBA

Связь между включением и равенством множеств устанавливается следующим

соотношением:

Здесь знак  обозначает конъюнкцию (логическое “и”).

В заключение добавим, что Г. Кантор предложил использовать понятие

“универсального множества” (универсум), как бы противоположного понятию пустого

множества . По мысли Кантора, универсальное множество U содержит все мыслимые

множества, и при этом оно само содержится во множестве своих подмножеств в качестве

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

раскрыты более подробно.

.ABBABA

2. Операции над множествами и их свойства.

Определение. Объединением множеств А и В называется множество С, элементы

которого принадлежат хотя бы одному из множеств А и В.

Обозначается С = А  В.

А

В

Геометрическое изображение множеств в виде области на плоскости называется

диаграммой Эйлера – Вэйна.

Определение. Пересечением множеств А и В называется множество С, элементы

которого принадлежат каждому из множеств А и В.

Обозначение С = А  В.

2

А С В

Для множеств А, В и С справедливы следующие свойства:

А  А = А  А = А; A  B = B  A; A  B = B  A;

(A  B)  C = A  (B  C); (A  B)  C = A  (B  C);

A  (B  C) = (A  B)  (A  C); A  (B  C) = (A  B)  (A  C);

A  (A  B) = A; A  (A  B) = A;

A = А; A   = ;

Определение. Разностью множеств А и В называется множество, состоящее из

элементов множества А, не принадлежащих множеству В.

Обозначается: С = А \ В.

А В

Определение. Симметрической разностью множеств А и В называется

множество С, элементы которого принадлежат в точности одному из множеств А или В.

Обозначается: А  В.

А  В = (A \ B)  (B \ A)

A B

Определение. СЕ называется дополнением множества А относительно множества

Е, если А  Е и CЕ = Е \ A.

3

A E

Для множеств А, В и С справедливы следующие соотношения:

A \ B  A; A \ A = ; A \ (A \ B) = A  B;

A  B = B  A; A  B = (A  B) \ (A  B);

A \ (B  C) = (A \ B)  (A \ C); A \ (B  C) = (A \ B)  (A \ C);

(A  B) \ C = (A \ C)  (B \ C); (A  B) \ C = (A \ C)  (B \ C);

A \ (B \ C) = (A \ B)  (A  C); (A \ B) \ C = A \ (B  C);

(A  B)  C = A  (B  C); A  (B  C) = (A  B)  (A  C);

A  CEA = E; A  CEA = ; CEE = ; CE = E; CECEA = A;

CE(A  B) = CEA  CEB; CE(A  B) = CEA  CEB;

Пример 2. Исходя из определения равенства множеств и операций над

множествами, доказать тождество и проверить его с помощью диаграммы Эйлера — Вэйна.

)(\\BAABA

Из записанных выше соотношений видно, что

)\()\()(\BAAABAA)\(BA= A \ В

Что и требовалось доказать.

Для иллюстрации полученного результата построим диаграммы Эйлера – Вэйна:

А В А В

AB

Пример 3. Исходя из определения равенства множеств и операций над

множествами, доказать тождество.

A \ (B  C) = (A \ B)  (A \ C)

4

Если некоторый элемент х  А \ (В  С), то это означает, что этот элемент

принадлежит множеству А, но не принадлежит множествам В и С.

Множество А \ В представляет собой множество элементов множества А, не

принадлежащих множеству В.

Множество А \ С представляет собой множество элементов множества А, не

принадлежащих множеству С.

Множество (A \ B)  (A \ C) представляет собой множество элементов, которые

принадлежат множеству А, но не принадлежат ни множеству В, ни множеству С.

Таким образом, тождество можно считать доказанным.

3. Векторы и прямые произведения.

Вектором (кортежем) в линейной алгебре и дискретной математике называют

упорядоченный набор элементов. Это не есть определение вектора, поскольку

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

Элементы, определяющие вектор, называются координатами или компонентами.

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

вектора. В отличие от элементов множества, координаты вектора могут совпадать.

Координаты вектора заключаются в круглые скобки, например )…,,,(21пааа

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

парами, длины 3 – тройками и т. д.

Определение. Два вектора равны, если они имеют равную длину и их

соответствующие координаты равны. Иначе говоря, векторы )…,,(1паа

равны, если тп

Определение. Прямым произведением множеств А и В (обозначение ВА)

называется множество всех упорядоченных пар );(ва, таких, что ВвАа,. В

частности, если А=В, то обе координаты принадлежат множеству А, такое произведение

обозначается А2. Аналогично, прямым произведением множеств пААА…,,,21

множество всех векторов )…,,,(21пааа

Пример 4. Множество 2RRR — это множество всех упорядоченных пар

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

координатная плоскость.

Координатное представление точек плоскости было впервые предложено Р.

Декартом и исторически является первым примером прямого произведения. Поэтому

часто прямое произведение множеств называют декартовым произведением.

Пример 5. Даны множества hgfedcbaA,,,,,,, и 8;7;6;5;4;3;2;1B. Тогда

BA есть множество обозначений клеток шахматной доски.

Вообще конечное множество, элементами которого являются какие-либо символы

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

элементы множества пА в этом случае являются словами длины п в алфавите А.

Например, десятичное целое число – это слово в алфавите цифр.

Определение. Проекцией вектора )…,,,(21naaaa

компонента (координата) с соответствующим порядковым номером (обозначается прia).

Например, проекция точки плоскости на 1-ю ось есть её абсцисса (первая координата).

Теорема 1.1. Мощность произведения конечных множеств пААА…,,,21

произведению мощностей этих множеств: ппАААААА……

Следствие.

и тпвава…,,

11.

длины п, таких, что ппАаАаАа…,,,

2121.

п

АА

п

.

5

Эта простая теорема и её следствие впоследствии широко используются в комбинаторике.

4. Соответствия.

Определение. Соответствием между множествами А и В называется некоторое

подмножество G их декартова произведения: BAG.

Если Gba;, то говорят, что bсоответствует a при соответствии G. При этом

множество всех таких a

множество соответствующих значений b называются областью значений соответствия

)(GE.

В принятых обозначениях, каждый элемент Bb, соответствующий данному

элементу Aa называется образом a при соответствии G, наоборот, элемент Aa

называется прообразом элемента Bb при данном соответствии.

Соответствие называется полностью определённым, если AGD)(, то есть

каждый элемент множества A имеет хотя бы один образ во множестве B; в противном

случае соответствие называется частичным.

Соответствие G называется сюръективным, если BGE)(, то есть если каждому

элементу множества В соответствует хотя бы один прообраз во множестве A.

Соответствие G называется функциональным (однозначным), если любому

элементу множества A соответствует единственный элемент множества B.

Соответствие называется инъективным, если оно является функциональным, и при

этом каждый элемент множества B имеет не более одного прообраза.

Соответствие G называется взаимнооднозначным (биективным), если

любому элементу множества A соответствует единственный элемент множества B, и

наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если

оно является полностью определённым, сюръективным, функциональным, и при этом

каждый элемент множества В имеет единственный прообраз.

Пример 1.

а) Англо-русский словарь устанавливает соответствие между множествами слов

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

русскому слову соответствует несколько английских переводов; оно, также, не является,

как правило, полностью определённым соответствием, так как всегда существуют

английские слова, не включённые в данный словарь. Таким образом, это частичное

соответствие.

б) Соответствие между аргументами функции 2xу и значениями этой функции

является функциональным. Однако оно не является взаимнооднозначным, так как

каждому значению функции 00y

в) Соответствие между расположенными на шахматной доске фигурами и

занимаемыми ими полями является взаимно однозначным.

г) Соответствие между телефонами города Вязьмы и их пятизначными номерами

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

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

соответствующие никаким телефонам.

называют областью определения соответствия )(GD, а

соответствуют два прообраза 01yx

5. Взаимнооднозначные соответствия и мощности множеств.

Если между двумя конечными множествами А и В существует

взаимнооднозначное соответствие, то эти множества равномощны. Этот очевидный факт

позволяет, во-первых, установить равенство мощности этих множеств, не вычисляя их.

6

Во-вторых, часто можно вычислить мощность множества, установив его однозначное

соответствие с множеством, мощность которого известна, либо легко вычисляется.

Теорема 2.1. Если мощность конечного множества А равна n, то число всех

подмножеств А равно n2, то есть nA

Множество всех подмножеств множества М называется булеаном и обозначается

2

М

. Для конечных множеств выполняется:

Определение. Множества А и В называются равномощными, если между их

элементами можно установить взаимнооднозначное соответствие.

Заметим, что для конечных множеств это утверждение легко доказать. Для

бесконечных множеств оно определят само понятие равномощности.

Определение. Множество А называется счётным, если оно равномощно множеству

натуральных чисел N

Очень упрощённо можно сказать, что данное бесконечное множество является

счётным, если для его элементов можно установить нумерацию с помощью натуральных

чисел.

Без доказательства примем ряд важных фактов:

1. Любое бесконечное подмножество множества натуральных чисел является

2. Множество NkNk, является счётным.

3. Множество рациональных чисел R является счётным (является следствием из

4. Объединение конечного числа счётных множеств является счётным.

5. Объединение счётного числа конечных множеств является счётным.

6. Объединение счётного числа счётных множеств является счётным.

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

факт, что данное множество является счётным. Однако сейчас будет показано, что не

всякое бесконечное множества является счётным; существует множества большей

мощности.

Теорема 2.2 (теорема Кантора). Множество всех действительных чисел из отрезка

]1;0[ не является счётным.

Доказательство. Допустим, что множество RxxxM,1;0

и существует его нумерация. Поскольку любое действительное число можно представить

в виде бесконечной десятичной дроби (периодической или непериодической), то

проделаем это с числами данного множества. Расположим их в порядке этой нумерации:

22.

22

ММ

: NA

.

счётным.

предыдущего утверждения).

…,0

…,0

…,0

…………,0

…000,1

aaa

131211

aaa

232221

aaa

333231

Теперь рассмотрим любую бесконечную десятичную дробь вида …,0131211bbb

организованную таким образом, что 331322121111,,ababab

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

числа она отличается первой цифрой после запятой, от второго – второй цифрой и так

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

пронумеровано и, таким образом, множество M не является счётным. Его мощность

называется континуум, а множества такой мощности называются континуальными.

Приведённый метод доказательства называется диагональным методом Кантора.

Следствие 1. Множество действительных чисел R континуально.

7

Следствие 2. Множество всех подмножеств счётного множества континуально.

Как показывается в теории множеств (с помощью метода, аналогичного приведённому

выше), для множества любой мощности множество всех его подмножеств (булеан) имеет

более высокую мощность. Поэтому не существует множества максимальной мощности.

Например, множество-универсум U, описанное Кантором должно содержать все

мыслимые множества, однако оно само содержится в множестве своих подмножеств в

качестве элемента (парадокс Кантора). Получается, что множество U не является

множеством максимальной мощности.

6. Отображения и функции.

Функцией называется любое функциональное соответствие между двумя

множествами. Если функция f устанавливает соответствие между множествами А и В, то

говорят, что функция f имеет вид ВА (обозначение BAf:). Каждому элементу а

из своей области определения функция ставит в соответствие единственный элемент b из

области значений. Это записывается в традиционной форме baf)(. Элемент a

называется аргументом функции, элемент b- её значением.

Полностью определённая функция BAf: называется отображением А в В;

образ множества А при отображении обозначается )(Af. Если при этом BAf)(, то есть

соответствие сюръективно, говорят, что имеет отображение А на В.

Если )(Af состоит из единственного элемента, то f называется функцией-

константой.

Отображение типа AA называется преобразованием множества А.

Пример 2.

а) Функция Nxxfx,2)( является отображением множества натуральных чисел в себя

(инъективная функция). Эта же функция при всех Zx является отображением

множества целых чисел в множество рациональных чисел.

б) Функция 0\,)(Zxxxf

числа 0) на множество натуральных чисел. Причём в данном случае соответствие не

является взаимно однозначным.

в) Функция Rxxxf,)(3является взаимнооднозначным отображением множества

действительных чисел на себя.

г) Функция xxf)( не полностью определена, если её тип NN

определена, если её тип RN

Определение. Функция типа BAAAn…

функцией. В этом случае принято считать, что функция имеет n аргументов:

21, где BbAaAaAann,…,,,

baaafn)…,,,(

Например, сложение, умножение, вычитание и деление являются двухместными

функциями на R, то есть функциями типа RR2.

Определение. Пусть дано соответствие BAG. Если соответствие ABH

таково, что Hab),( тогда и только тогда, когда Gba),(, то соответствие H называют

обратным к G и обозначают 1G.

Определение. Если соответствие, обратное к функции BAf: является

функциональным, то оно называется функцией, обратной к f.

Очевидно, что в обратном соответствии образы и прообразы меняются местами, поэтому

для существования обратной функции 1f

значения f имел бы единственный прообраз. Это означает, что для функции BAf:

является отображением множества целых чисел (кроме

или RR

.

21 называется n

2211.

требуется, чтобы каждый элемент из области

8

обратная функция 1f

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

Пример 3. Функция

отображает на отрезок ]1;1[. Поэтому для неё на отрезке ]1;1[ существует обратная

функция. Как известно, это xarcsin.

Определение. Пусть даны функции BAf: и CBg:. Функция CAh:

называется композицией функций f и g

равенство: ))(()(xfgxh, где Ax.

существует тогда и только тогда, когда f

xsin

имеет тип

RR

. Отрезок 

(обозначается gf), если имеет место

Композиция функций f и g

этих функций; g

подстановкой f в g

Для многоместных функций CBgBAfnm:,: возможны различные

варианты подстановок f в g

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

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

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

mff…,,1

некоторой подстановкой их друг в друга и переименованием аргументов,

называется их суперпозицией.

Например, в математическом анализе вводится понятие элементарной функции,

являющейся суперпозицией фиксированного (не зависящего от значения аргумента) числа

арифметических операций, а также элементарных функций (xnexx,sin,

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

n переменных представима в виде суперпозиции непрерывных функций двух

переменных.

Замечание. Понятие функции широко используется в математическом анализе,

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

“функция” в матанализе несколько уже, чем в дискретной математике. Как правило, в нём

рассматриваются так называемые вычислимые функции. Функция называется

вычислимой, если задана процедура, позволяющая по любому заданному значению

аргумента найти значение функции.

представляет собой последовательное применение

применяется к результату f.Часто говорят, что функция h получена

.

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

1.

Лекция № 2. Отношения и их свойства. Основные виды

отношений.

1. Основные понятия и определения.

Определение. Подмножество nAR называется n

отношением на множестве А. Говорят, что элементы naa…,,1

если Raan)…,,(

1.

Одноместное (одномерное) отношение – это просто некоторое подмножество А.

Такие отношения называют признаками. Говорят, что а обладает признаком R, если

Ra и AR. Свойства одноместных отношений – это свойства подмножеств А,

поэтому для случая 1n термин “отношения” употребляется редко.

находятся в отношении R

9

Наиболее часто встречающимися и хорошо изученными являются двухместные или

бинарные отношения. Если a

виде aRb.

Пример 1. Бинарные отношения на множестве N.

а) Отношение “

б) Отношение “иметь общий делитель, не равный единице” выполняется для пар

)10;4(),6;3( и не выполняется для пар )3;11(),5;6(.

в) Отношение “быть делителем” выполняется для пар )5;5(),6;2( и не выполняется для

пар )1;6(),2;4(.

Пример 2. Бинарные отношения на множестве точек координатной плоскости.

а) Отношение “быть равноудалёнными от начала координат” выполнятся для пар точек

)4;1( и )1;4(, но не выполнятся для пары точек )0;3( и )6;2(.

б) Отношение “принадлежать окружности, центр которой находится в начале координат”,

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

второй пары.

в) Отношение “быть удалёнными на разное расстояние от начала координат” выполняется

для всех точек, для которых не выполняется отношение, описанное в пункте “б”.

Пусть дано отношение R

определяется отношение 1R, называемое сужением R

отношения R

11ARR.

говоря, 2

Строго говоря, само отношение R

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

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

отношении “быть делителем”, не уточняя, задано оно на множестве N или на каком-

нибудь его подмножестве.

Для задания бинарных отношений можно использовать любые способы задания

множеств (например, список пар, для которых данное отношение выполняется).

Отношения на конечных множествах обычно задаются списком или матрицей. Матрица

бинарного отношения на конечном множестве naaaM…,,,21 — это квадратная матрица

порядка n

и b находятся в отношении R, это обычно записывается в

” выполняется для пар )7;7(),9;7( и не выполняется для пары )7;9(.

на множестве А. Для любого подмножества AA

на 1A, которое получается из

удалением всех пар, содержащих элементы, не принадлежащие 1A. Иначе

и его сужение 1R — это разные отношения, с

, в которой каждый элемент ijc



,,1

явыполняетсесоотношенипарыющейсоответсвудляесли

сij

.,0

случаепротивномв

определяется следующим образом:

Пример 3. Для конечного множества 6,5,4,3,2,1M матрицы отношений из

примера 1 (а – в) приведены в следующих таблицах.

а)

1 2 3 4 5 6

1 1 1 1 1 1 1

2 0 1 1 1 1 1

3 0 0 1 1 1 1

4 0 0 0 1 1 1

5 0 0 0 0 1 1

6 0 0 0 0 0 1

1 2 3 4 5 6

1 0 0 0 0 0 0

2 0 1 0 1 0 1

3 0 0 1 0 0 1

10

4 0 1 0 1 0 1

5 0 0 0 0 1 0

6 0 1 1 1 0 1

1 2 3 4 5 6

1 1 1 1 1 1 1

2 0 1 0 1 0 1

3 0 0 1 0 0 1

4 0 0 0 1 0 0

5 0 0 0 0 1 0

6 0 0 0 0 0 1

Поскольку отношения на множестве А задаются подмножествами А2, для

отношений можно определить те же операции, что и для множеств. Например, отношение

“” является объединением отношений “<” и “=”.

Определение. Отношение 1R называется обратным к отношению R, если abR1

тогда и только тогда, когда aRb.

Непосредственно из определения следует, что RR11. Например, для

отношения “” обратным является отношение “”.

2. Свойства отношений.

Определение. Отношение R называется рефлексивным, если для любого элемента

Аa имеет место aRa.

Главная диагональ матрицы рефлексивного отношения содержит только единицы.

Определение. Отношение R называется антирефлексивным, если ни для какого

элемента Аa не выполняется aRa.

Главная диагональ матрицы рефлексивного отношения содержит только нули.

Например, отношения “” и “иметь общий делитель” являются рефлексивными.

Отношения “

симметричным относительно оси абсцисс” не является ни рефлексивным, ни

антирефлексивным: точка плоскости симметрична сама себе, если лежит на этой оси, и не

симметрична себе, если не лежит на ней.

Определение. Отношение R называется симметричным, если для любой пары

),(Mba из отношения aRb

симметричным тогда и только тогда, когда для любой пары 2),(Mba оно выполняется в

обе стороны (или вовсе не выполняется).

Матрица симметричного отношения симметрична относительно главной

диагонали: jiijcс

Определение. Отношение R называется антисимметричным, если из отношений

aRb и bRa следует, что ba.

Отношение “быть симметричным относительно оси абсцисс” является

симметричным: если первая точка симметрична второй относительно этой оси, то и

вторая точка симметрична первой. Отношение “” является антисимметричным.

Действительно, если ba и ab, это означает, что ba.

Нетрудно убедиться в том, что отношение R симметрично тогда и только тогда,

когда 1RR.

Определение. Отношение R называется транзитивным, если для любых cba,, из

отношений aRb и bRc следует aRc.

” и “иметь сына” являются антирефлексивными. Отношение “быть

2

следует bRa

. Иными словами, отношение R

для любых ji,

.

11

Отношения “быть равным”, “жить в одном городе”, “быть параллельным” являются

транзитивными. Отношения “пересекаться”, “быть сыном” не являются транзитивными.

Замечание. В отличие от отношений рефлексивности и симметричности, для

отношения транзитивности не формулируется противоположного понятия

(антитранзитивности).

Определение. Транзитивным замыканием R

определяемое следующим образом: если в множестве M существует цепочка из n

элементов baaaan…,,,

выполняется отношение R

транзитивное замыкание bRa

Замечание. Замыкание является весьма общим математическим понятием.

Упрощённо говоря, замкнутость означает, что многократное повторение допустимых

шагов не выводит за определённые границы. Например, множество натуральных чисел

замкнуто относительно операции сложения, однако открыто (то есть незамкнуто)

относительно операции деления.

Если отношение Rтранзитивно, то, очевидно, RR

отношение “быть делителем” транзитивно для любой цепочки элементов и само является

транзитивным замыканием этого отношения.

Если отношение R

Например, транзитивным замыканием отношения “быть сыном” является

отношение “быть прямым потомком”, включающее в себя понятия “быть сыном”, “быть

внуком”, “быть правнуком” и так далее.

отношения R называется отношение,

21, в которой между каждыми двумя соседними элементами

()…,,,1322RbaRaaaRan

.

, то говорят, что существует

не транзитивно, то RR

.

3. Отношения эквивалентности.

Определение. Отношение называется отношением эквивалентности (или просто

эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Пример 1.

а) Отношение равенства (часто обозначается Е) на любом множестве является

отношением эквивалентности. Равенство – это минимальное отношение эквивалентности

в том смысле, что при удалении любой пары из этого отношения (то есть любой единицы

на главной диагонали матрицы Е) оно перестаёт быть рефлексивным и, следовательно,

уже не является эквивалентностью.

б) Утверждения вида 22))((bababa или 1cossin22xx, состоящие из

формул, соединённых знаком равенства, задают бинарное отношение на множестве

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

называется отношением равносильности и определяется следующим образом: две

формулы равносильны, если они задают одну и ту же функцию. Равносильность в данном

случае, хотя и обозначена знаком “=”, означает не то же самое, что отношение равенства,

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

равенства в таких отношениях относится не к самим формулам, а к функциям, которые

ими описываются. Для формул же отношение равенства – это совпадение формул по

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

ситуациях избежать разночтений, часто для обозначения отношения равносильности

используют знак “

в) Рассмотрим множество треугольников на координатной плоскости, считая, что

треугольник задан, если даны координаты его вершин. Два треугольника будем считать

равными (конгруэнтными), если при наложении они совпадают, то есть, переведены друг

в друга с помощью некоторого перемещения. Равенство является отношением

эквивалентности на множестве треугольников.

”.

12

г) Отношение “иметь один и тот же остаток отделения на натуральное число b” на

множестве натуральных чисел является отношением эквивалентности.

е) Отношение “быть делителем” не является на множестве N отношением

эквивалентности. Оно обладает свойствами рефлексивности и транзитивности, но

является антисимметричным (см. ниже).

Пусть на множестве М задано отношение эквивалентности R. Осуществим

следующее построение. Выберем элемент Ma

), состоящий из элемента 1a и всех элементов, эквивалентных ему в рамках данного

отношения. Затем выберем элемент 122,CaMa и образуем класс

и эквивалентных ему элементов. Продолжая эти действия, получим систему классов

…,,21СС (возможно, бесконечную) такую, что любой элемент из множества М

хотя бы в один класс, то есть 

Эта система обладает следующими свойствами:

1) она образует разбиение множества М, то есть классы попарно не пересекаются;

2) любые два элемента из одного класса эквивалентны;

3) любые два элемента из разных классов не эквивалентны.

Все эти свойства прямо следуют из определения отношения эквивалентности.

Действительно, если бы, например, классы 1С и 2С пресекались, то они имели бы хотя бы

один общий элемент. Этот элемент был бы, очевидно, эквивалентен 1a и 2a. Тогда, в силу

транзитивности отношения R

классов, это не возможно. Аналогично можно доказать другие два свойства.

Построенное разбиение, то есть система классов – подмножеств множества М,

называется системой классов эквивалентности по отношению R. Мощность этой

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

М на классы само определяет некоторое отношение эквивалентности, а именно

отношение “входить в один класс данного разбиения”.

Пример 2.

а) Все классы эквивалентности по отношению равенства Е состоят из одного элемента.

б) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном

классе эквивалентности по отношению равносильности. В данном случае счётными

являются само множество формул, множество классов эквивалентности (то есть индекс

разбиения) и каждый класс эквивалентности.

в) Разбиение множества треугольников по отношению равенства имеет континуальный

индекс, причём каждый класс имеет также мощность континуум.

г) Разбиение множества натуральных чисел по отношению “иметь общий остаток при

делении на 7” имеет конечный индекс 7 и состоит из семи счётных классов.

1 и образуем класс 1C (подмножество M

iMC

1

i

.

выполнялось бы 21Raa. Однако, по способу построения

4. Отношения порядка.

Определение 1. Отношение R называется отношением нестрогого порядка, если оно

является рефлексивным, антисимметричным и транзитивным.

Определение 2. Отношение R называется отношением строгого порядка, если оно

является антирефлексивным, антисимметричным и транзитивным.

Оба типа отношений вместе называются отношениями порядка. Элементы ba,

сравнимы по отношению порядка R, если выполняется одно из двух отношений aRb или

bRa. Множество M, на котором задано отношение порядка, называется полностью

упорядоченным, если любые два его элемента сравнимы. В противном случае, множество

называется частично упорядоченным.

Пример 3.

13

а) Отношения “” и “” являются отношениями нестрогого порядка, отношения “<” и

“>” – отношениями строгого порядка (на всех основных числовых множествах). Оба

отношения полностью упорядочивают множества N и R.

б) Определим отношения “” и “<” на множестве n

1) )…,,()…,,(11nnbbaa

2) )…,,()…,,(11nnbbaa

координаты выполняется iiba

Тогда, например, )4,2,1()3,2,1(, но )3,2,1( и )4,2,1( несравнимы. Таким образом,

эти отношения частично упорядочивают nR.,

в) На системе подмножеств множества М отношение включения “

частичный порядок, а отношение строгого включения “

порядок. Например, 3,2,12,1, а 2,1 и 4,3,1 не сравнимы.

г) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок.

В нём, например, несравнимыми являются сотрудники различных структурных

подразделений (отделов и т. п.).

д) В алфавите русского языка порядок букв зафиксирован, то есть всегда один и тот же.

Тогда этот список определяет полное упорядочение букв, которое называется отношением

предшествования. Обозначается jiaa

предшествования букв построено отношение предшествования слов, определяемое

примерно, таким образом, как производится сравнение двух десятичных дробей. Это

отношение задаёт полное упорядочение слов в русском алфавите, которое называется

лексикографическим упорядочением.

Пример 4.

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

упорядочение слов в словарях. Например, летолес (так как тс), поэтому слово лес

расположено в словаре раньше слова лето.

б) Если рассматривать числа в позиционных системах счисления (например, в десятичной

системе) как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с

обычным, если все сравниваемые числа имеют одинаковое количество разрядов. В общем

же случае эти два вида могут не совпадать. Например, 107310 и 107320, но 107310

, а 107320. Для того, чтобы они совпадали, нужно уравнять число разрядов у всех

сравниваемых чисел, приписывая слева нули. В данном примере при этом получим

10730020. Такое выравнивание происходит автоматически при записи целых чисел в

в) Лексикографическое упорядочивание цифровых представлений дат вида 19.07.2004

(девятнадцатое июля две тысячи четвёртого года) не совпадает с естественным

упорядочением дат от более ранних к более поздним. Например, дата 19.07.2004

“лексикографически” старше восемнадцатого числа любого года. Чтобы возрастание дат

совпадало с лексикографическим упорядочением, обычное представление надо

“перевернуть”, то есть записать в виде 2004.07.19. так обычно делают при представлении

дат в памяти ЭВМ.

, если nnbaba…,,

11;

, если )…,,()…,,(11nnbbaa

.

R следующим образом:

и при этом ходя бы для одной ойi

” задаёт строгий частичный

(ia

предшествует ja

). На основании отношения

Лекция № 3. Элементы математической логики.

Математическая логика – разновидность формальной логики, т.е. науки, которая

изучает умозаключения с точки зрения их формального строения.

Определение. Высказыванием называется предложение, к которому возможно

применить понятия истинно или ложно.

14

В математической логике не рассматривается сам смысл высказываний,

определяется только его истинность или ложность, что принято обозначать

соответственно И или Л.

Понятно, что истинные и ложные высказывания образуют соответствующие

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

соединяя простые высказывания союзами “и”, “или”.

Таким образом, операции с высказываниями можно описывать с помощью

некоторого математического аппарата.

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

1) Отрицание. Отрицанием (логическим “не”) высказывания Р называется

Обозначается 

Соответствие между высказываниями определяется таблицами истинности. В

нашем случае эта таблица имеет вид:

высказывание, которое истинно только тогда, когда высказывание Р ложно.

Р или P.

P 

И Л

Л И

Р

2) Конъюнкция. Конъюнкцией (логическим “и”) двух высказываний P и Q

называется высказывание, истинное тогда и только тогда, когда истинны оба

высказывания.

Обозначается P&Q или РQ.

P Q P&Q

И И И

И Л Л

Л И Л

Л Л Л

3) Дизъюнкция. Дизъюнкцией (логическим “или”) двух высказываний P и Q

называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

Обозначается PQ.

P Q PQ

И И И

И Л И

Л И И

Л Л Л

4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q

называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно,

а Q – ложно.

Обозначается PQ (или РQ). Высказывание Р называется посылкой импликации,

а высказывание Q – следствием.

15

P Q PQ

И И И

И Л Л

Л И И

Л Л И

5) Эквиваленция. Эквиваленцией (логической равносильностью) двух

высказываний P и Q называется высказывание, истинное тогда и только тогда, когда

истинности высказываний совпадают.

Обозначается РQ или РQ.

P Q PQ

И И И

И Л Л

Л И Л

Л Л И

С помощью этих основных таблиц истинности можно составлять таблицы

истинности сложных формул.

Замечание. В дальнейшем мы познакомимся с принципиально иной, более

широкой трактовкой тех понятий, которые мы определили в данной лекции. Мы будем их

рассматривать уже не как операции над высказываниями, но как некоторые функции.

Поясним на следующем примере. Запись ху

бинарной операции умножения переменных х и у, а, с другой стороны, так же

обозначается функция двух переменных xyyxf),(.

можно рассматривать как обозначение

Пример 1. С помощью таблиц истинности проверить, являются ли

эквивалентными формулы  и .



rpp

)(



rpp

)(

Составим таблицы истинности для каждой формулы:

p r p (pr) )(rpp

И И Л И И

И Л Л Л И

Л И И Л Л

Л Л И Л Л

p r p r )(rp )(rpp

И И Л Л Л И

И Л Л И И И

Л И И Л И И

Л Л И И И И

Данные формулы не являются эквивалентными.

16

Пример 2. С помощью таблиц истинности проверить, являются ли

эквивалентными формулы  и .





)(

rqp

)()(

rpqqp

Составим таблицы истинности для заданных формул.

p q r pq (pq)r

И И И И И

И И Л И И

И Л И Л И

И Л Л Л Л

Л И И Л И

Л И Л Л Л

Л Л И И И

Л Л Л И И

p q r pq qp (pq)(qp) (pq)(qp)r

И И И И И И И

И И Л И И И И

И Л И Л И И И

И Л Л Л И И И

Л И И И Л И И

Л И Л И Л И И

Л Л И И И И И

Л Л Л И И И И

Из составленных таблиц видно, что данные формулы не равносильны.

Основные равносильности.

Для любых формул А, В и С справедливы следующие равносильности:

A & B  B & A; A & A  A; A & (B & C)  (A & B) & C;

A  B  B  A; A  A  A; A  (B  C)  (A  B)  C;

A  (B & C)  (A  B) & (A  C); A & (B  C)  (A & B)  (A & C);

A & (A  B)  A; A  (A & B)  A; A  A; (A & B)  A  B;

A  (A & B)  (A & B); A  (A  B) & (A  B);

Булевы функции.

Определение. Булевой функцией f(X1, X2, …, Xn) называется произвольная n –

местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

17

Вообще говоря, между логическими высказываниями, логическими связками и

булевыми функциями просматривается явная аналогия (подробнее она рассматривается в

следующей лекции). Если логические функции могут принимать значения истинно или

ложно, то для булевой функции аналогами этих значений будут значения 0 или 1.

Для булевых функций также можно составить таблицы значений,

соответствующим основным логическим операциям.

X1 X2 X1 X1&X2 X1X2 X1X2 X1X2

1 1 0 1 1 1 1

1 0 0 0 1 0 0

0 1 1 0 1 1 0

0 0 1 0 0 1 1

Лекция № 4. Логические функции.

Ниже будет подробно рассматриваться двухэлементное множество B и двоичные

переменные, принимающие значения из этого множества. Его элементы часто обозначают

0 и 1, однако они, вообще говоря, не являются числами в обычном смысле (хотя и похожи

на них по некоторым свойствам). Наиболее распространённая интерпретация двоичных

переменных – логическая: “да” – “нет”, “истинно” – “ложно”. В контексте, содержащем

одновременно двоичные и арифметические величины, а также функции, эта

интерпретация обычно фиксируется явно. Например, в языках программирования (Pascal

и др.) вводится специальный тип переменной – логическая переменная, значения которой

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

переменных не везде является обязательной, поэтому будем считать, что 1;0B,

рассматривая 0 и 1 как формальные символы, не имеющие арифметического смысла.

1. Функции алгебры логики.

Определение. Алгебра, образованная множеством B вместе со всеми возможными

операциями на нём, называется алгеброй логики.

Определение. Функцией алгебры логики (логической функцией) называется п

операция на множестве В.

Первый термин является более точным, однако второй более распространён, особенно

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

)…,,(1nxxf

функций будем обозначать 2P, множество всех логических функций n

)(2nP.

Определение. Алгебра, образованная kэлементным множеством вместе со всеми

операциями на нём, называется алгеброй kзначной логики, а п

элементном множестве называется kзначной логической функцией.

Множество всех k

будем рассматривать логические функции только из 2Р.

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

которой перечислены все наборы значений переменных (которых всего п2), а в правой

части – значение функции на этих наборах значений. Ниже приведена таблица, задающая

некоторую функцию трёх переменных.

— это функция, принимающая значения 0 или 1. Множество всех логических

значных логических функций обозначается kP

18

Наборы, на которых значение функции равно 1, часто называют единичными

наборами функции f, а множество единичных наборов называют единичным

множеством функции f. Аналогично, наборы, на которых значение функции равно 0,

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

и пять нулевых наборов.

1х 2x 3x f

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 0

Таблица 1.

Заметим, что наборы в таблице расположены в определённом порядке –

лексикографическом, который совпадает с возрастанием наборов, если рассматривать их

как двоичные числа. Этим упорядочением будем пользоваться в дальнейшем. При любом

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

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

функций п

Определение. Переменная ix

несущественной (фиктивной), если 

любых значениях остальных переменных.

Иначе говоря, переменная считается несущественной, если изменение её значения в

любом наборе не изменяет значения функции. В этом случае функция )…,,(1nxxf

существу зависит от 1n переменной, то есть представляет собой некоторую функцию g

от 1n переменной. Говорят, что функция g

фиктивной переменной или, наоборот, что функция f получена из функции g

добавлением фиктивной переменной. Например, запись ),(),,(21321xxgxxxf

что при любых значениях 21,xx

Практический смысл удаления фиктивных переменных очевиден, поскольку они не

влияют на значение функции и являются с этой точки зрения лишними. Однако иногда

бывает полезно вводить фиктивные переменные. Благодаря такому введению можно

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

Поэтому любую конечную совокупность функций можно считать зависящей от одного и

того же множества переменных (которое является объединением множеств переменных

всех взятых функций).

переменных равно числу различных двоичных векторов длины п2.

в функции )…,,,,…,,(111niiixxxxxf

)…,,,0,…,,(111niixxxxf)…,,,1,…,,(111niixxxxf

получена из функции f удалением

выполняется gf

независимо от значения 3x

2. Примеры логических функций.

Логических функций одной переменной четыре; они приведены в таблице 2.

x

1

0 0 0 1 1

1 0 1 0 1

2

3

4

Таблица 2.

19

Здесь функции 1 и

зависят от значения переменной, и, следовательно, переменная х для них несущественна.

Значения функции 2совпадают со значениями переменной х

значения которой противоположны значениям переменной, есть ни что иное, как

отрицание х

Логических функций двух переменных – шестнадцать; они приведены в таблице 3.

21хх 1

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Функции 1

функциями с двумя несущественными переменными. Отметим, что формально эти

функции отличаются от функций 1 и

бинарными операциями на множестве В. Однако ранее было принято функции,

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

Среди представленных в таблице 3 функций отметим те, которые уже знакомы нам в

качестве логических операций, изученных в ходе предыдущей лекции.

Функция ),(212хх является конъюнкцией переменных

равна 1 тогда и только тогда, когда обе переменные равны 1. Обозначается: 2121,хххх,

2121;&xxxх. Её также называют логическим умножением, поскольку таблица её

действительно совпадает с таблицей обычного умножения для чисел 0 и 1. Поэтому,

кстати, по аналогии с обычным умножением, знак операции между переменными часто

опускают: 21хх.

Операцию  будем называть умножением по модулю 2 (см. ниже). Она реализует произведение

остатков от деления чисел 0 и 1 на число 2.

Функция ),(218хх

Она равна 1, если значения 1х или 2х равны 1. Союз “или” понимается здесь в

неразделительном смысле “хотя бы один из двух”. Обозначается: 2121,хххх.

Функция ),(217хх

когда значения аргументов различны, и равна 0, когда значения аргументов одинаковы.

Обозначается: 2121,хххх.

Привести пример такой функции более сложно. Для этого введём следующее понятие, широко

используемое в теории чисел.

Два целых числа a

число они дают одинаковые остатки.

Обозначается: )(modpba

можно рассматривать, как сложение по модулю 2. Действительно, сумма остатков от деления чисел 0 и 1 на

число 2 равна 1, а сумма остатков от деления чисел 0 и 0, либо 1 и 1 на 2 равна 0.

Функция ),(2114хх называется импликацией или логическим следованием.

Обозначается: 212121,,хххххх.

Функция ),(2110хх

1, если значения переменных одинаковы и 0, если они различны. Обозначается:

212121~,,xххххх.

Есть ещё две функции двух переменных, имеющие специальные названия. Функция

),(219хх

4 — константы 0 и 1 соответственно, значения которых не

(функция НЕ). Различные способы обозначения этой функции: ххх,,

2

3

4

5

6

7

8

9

10

11

Таблица 3.

и 16

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

4 из предыдущего примера, поскольку являются

1х и 2х (функцией И). Она

называется дизъюнкцией переменных 1х

называется неравнозначностью переменных 1х

и bназываются сравнимыми по модулюNpp,

. Например, )3(mod107

, )6(mod511

называется эквивалентностью или равнозначностью. Она равна

называется стрелкой Пирса и обозначается 21хх. Функция ),(2115хх

20

называется штрихом Шеффера и обозначается 21хх

названий не имеют и, как можно показать, легко выражаются через перечисленные выше

функции.

В функциях 4

1214),(ххх

фиктивна: 2216),(ххх

Доказано, что с ростом числа переменных п доля функций, имеющих фиктивные

переменные, убывает и стремится к нулю.

. Остальные функции специальных

и 13

, а 12111),(ххх

переменная 2х

, а 22111),(ххх

фиктивна. Из таблицы 3 видно, что

. Аналогично, в функциях 6

.

3. Суперпозиции и формулы.

Ранее было введено определение суперпозиции функций, согласно которому

суперпозицией нескольких функций называлась новая функция, полученная с помощью

подстановок данных функцией друг в друга и переименования переменных. Выражение,

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

является очень важным в алгебре логики, рассмотрим его более подробно.

Пусть дано множество (конечное или бесконечное) исходных функций mff…,,1.

Символы переменных тхх…,,1

формулами глубины 0.

Определение. Говорят, что формула F имеет глубину 1k, если она имеет вид

)…,,(1niFFf

При этом nFF…,,1

главной операцией формулы F.

Соответственно, формулы nFF…,,1

являются в этом случае и подформулами формулы F

в наших обозначениях – это формула глубины 1. Выражение )),(,(),,((321122113xxfxfxxff

является формулой глубины 3, содержащей одну подформулу глубины 2 и две

подформулы глубины 1.

В дальнейшем конкретные формулы будем записывать в более привычном виде, при

котором условные знаки функций стоят между аргументами (такую запись называют

инфиксной). Например, если 1f

импликацией, то приведённая выше формула примет вид (*)))((32121xxxxx

Все формулы, построенные подобным образом, то есть содержащие только символы

переменных, скобки и знаки функций из множества , называются формулами над

множеством .

Возможны и другие интерпретации понятия глубины. Например, считается, что

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

когда множество 

что применение этой операции к формулам с той же внешней операцией f не

увеличивает глубины формулы. Например, формулы ))((4321xxxx

)))(((43212xxxxx

Всякая формула, выражающая данную функцию, как суперпозицию других функций,

задаёт способ её вычисления (при условии, что известно, как вычислять исходные

функции). Этот способ определяется следующим очевидным правилом: формулу можно

вычислить, только если уже вычислены значения всех её подформул. Применим,

например формулу (*)

Далее получим 1)(321xxx

, содержащихся в данных функциях, будем считать

, где 

if

называются подформулами формулы F

, а 

nFF…,,1

формулы, максимальная из глубин которых равна k

, а if

также могут иметь подформулы, которые

. Например, выражение ),,(3211xxxf

является конъюнкцией, 

содержит некоторую ассоциативную операцию f, можно считать,

имеют одну и ту же глубину 3.

к набору 0,1,1321xxx

. Наконец, 1))((32121xxxxx

. Получим: 0;13221xxxx

21

Таким образом, формула ставит в соответствие каждому набору значений аргументов

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

вычисления функции. В частности, по формуле, вычисляя её на всех п2 наборах, можно

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

представляет или реализует функцию.

В отличие от табличного задания представление данной функции формулой не

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

функции 382,, из предыдущего пункта (то есть функции И, ИЛИ, НЕ), то функцию

— штрих Шеффера – можно представить формулами 21xx

стрелка Пирса – можно представить формулами 21xx

Определение. Формулы, представляющие одну и ту же функцию называются

эквивалентными или равносильными.

Эквивалентность формул принято обозначать знаком равенства, поэтому можно

записать: 2112115),(xxxxxx

Существует стандартный метод для выяснения эквивалентности двух формул. По

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

сравниваются. Таким способом в предыдущеё лекции мы устанавливали равносильность

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

обе формулы зависят от п переменных. Более простыми методами, позволяющими

устанавливать эквивалентность данных формул, а также получать новые формулы,

эквивалентные исходной, являются эквивалентные преобразования, которые будут

рассмотрены в дальнейшем.

и 21xx.

.

Лекция № 5. Булевы алгебры и теория множеств..

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

виде суперпозиций функций И, ИЛИ, НЕ.

1. Разложение функций по переменным. Совершенная дизъюнктивная нормальная

Введём обозначения: xxxx01,. Пусть 

, если x

Теорема 8.1. Всякая логическая функция )…,,(1nxxf

следующем виде:



1111nmmnmmxxfxxxxxxf

)1(),,,,,(),,,,,(

где nm

Равенство (1) называется разложением по переменным mxx,,1

достаточно громоздка на вид, однако её несложно использовать при небольших значениях

и n

. Например, при значениях 4n, 2m разложение (1) имеет вид:

&),,0,1(),,1,0(),,0,0(),,,(4321432143214321xxfxxxxfxxxxfxxxxxxf

),,1,1(&4321xxfxx

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

функцию нескольких переменных суперпозицией конечного числа функций с меньшим

количеством переменных. Особенно важен частный случай nm

производится по всем переменным. При этом все переменные в правой части равенства (1)

форма.

параметр, равный 0 или 1. Тогда 1x

, и 0x, если x

.

может быть представлена в



, а дизъюнкция берётся по всем m2



,

1

m

1

m

наборам значений переменных mxx,,1

m

1

.

22

получают фиксированные значения, и функции в конъюнкциях правой части становятся

равными 0 или 1, что даёт:

nxxxxf



)2(),,(1

1





1),,(

f

1

n

a

1

,

, на которых 1f

n

n

где дизъюнкция берётся по всем наборам ),,(1n

называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f. СДНФ

содержит ровно только конъюнкций, сколько единиц в таблице функции f; каждому

единичному набору ),,(1n

взято с отрицанием, если 01

взаимно однозначное соответствие между таблицей функции f и её СДНФ.

Следовательно, для каждой логической функции СДНФ является единственной (с

точностью до порядка переменных и конъюнкций).

Пример 1. Составить СДНФ для функции, заданной таблицей:

соответствует дизъюнкция всех переменных, в которых ix

и без отрицания, если 1

i

. Таким образом, существует

1х 2x 3x f

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 0

Поскольку данная таблица (уже встречавшаяся ранее) содержит три единичных

набора, СДНФ будет конъюнкцией трёх дизъюнкций. В свою очередь, каждая

дизъюнкция включает три переменных – по числу их в функции f.

Получим: 321321321321),,(xxxxxxxxxxxxf

Напомним, что, подобно знаку умножения, знак дизъюнкции 

формулах часто опускают. Тогда полученное выражение примет более компактный вид:

Единственная функция, которая не имеет СДНФ – это константа 0f.

Формулы, содержащие кроме переменных и скобок, только знаки дизъюнкции,

конъюнкции и отрицания, будем называть булевыми формулами.

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

то есть как суперпозиция дизъюнкции, конъюнкции и отрицания.

321321321321),,(xxxxxxxxxxxxf

2. Булева алгебра функций.

Выше мы обозначили множество всех логических операций на двухэлементном

множестве 1,0, как 2Р.

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

),,;(2Р, основным множеством которой является всё множество логических функций,

а операциями – дизъюнкция, конъюнкция и отрицание.

Замечание. На практике мы имеем дело не самими функциями, а с представляющими

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

функцию представляет бесконечное множество формул. Чтобы “синхронизировать” их

алгебре формул придаётся следующий вид. Элементами алгебры формул объявляются не

сами формулы, а классы эквивалентности формул, то есть классы формул,

23

представляющих одну и ту же функцию. Определённая таким образом, алгебра формул

называется алгеброй Линденбаума — Тарского. Она изоморфна булевой алгебре функций.

Теперь рассмотрим основные свойства булевых операций (частично уже знакомые по

теме “Элементы математической логики”).

1. Ассоциативность: а) 321321)()(xxxxxx

2. Коммутативность: а) 1221xxxx; б)

3. Дистрибутивность конъюнкции относительно дизъюнкции: 3121321)(xxxxxxx

4. Дистрибутивность дизъюнкции относительно конъюнкции:

5. Идемпотентность: а) xxx

6. Двойное отрицание: xx.

7. Свойства констант: а) 11x; б) xx0; в) xx1; г) 00x; д) 10; е)

01.

8. Правила де Моргана: а) 2121xxxx; б)

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

соотношения 6) дизъюнкция заменяется конъюнкцией и наоборот.

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

10. Закон “исключённого третьего”: 1xx.

Все соотношения 1 – 10 можно проверить указанным ранее стандартным методом –

вычислением обеих частей равенств на всех наборах значений переменных. Эти

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

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

Важно лишь соблюдать следующее правило подстановки формулы вместо переменной.

При подстановке формулы F вместо переменной x все вхождения данной

переменной в исходное соотношение должны быть одновременно заменены формулой F.

Правило подстановки позволяет получать из соотношений 1 – 10 новые эквивалентные

соотношения. Заметим, что равенство 21FF означает в данном контексте, что формулы

1F и 2F описывают одну и ту же логическую функцию. Следовательно, если какая-то

формула F

формулы F. Это утверждение представляет собой правило замены подформул, которое

позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные

данной. Практическое применение описанных правил будет рассмотрено ниже.

Замечание. Есть существенная разница между подстановкой и заменой. При

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

лишь бы производилась одновременная замена ею всех вхождений переменной. При

замене подформул может быть заменена любая подформула, однако, не на любую другую,

а только на подформулу, эквивалентную ей. При этом замена всех вхождений исходной

подформулы не обязательна.

; б) )()(321321xxxxxx

1221xxxx.

))(()(3121321xxxxxxx

; б) xxx

.

.

2121xxxx. Очень важные соотношения,

содержит 1F в качестве подформулы, то замена её на 2F не изменит значения

3. Эквивалентные преобразования.

Пример 2. Возьмём соотношение 8а и подставим вместо переменной 1x выражение

. Получим: 231231xxxxxx

исходным формулам, но эквивалентные между собой. Если же в правой части нового

соотношения формулу 31xx

соотношения 8а и затем заменить 1x на 1x

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

. Здесь в обеих частях стоят формулы, неэквивалентные

заменить формулой 31xx

, эквивалентной ей в силу

(согласно 6), то получим 231xxx

24

231231xxxxxxxxxxxx

231231

Такие преобразования, использующие эквивалентные соотношения и правило замены,

называют эквивалентными преобразованиями. Эквивалентные преобразования являются

мощным средством доказательства эквивалентности формул, как правило, более

эффективным, чем их вычисление на наборах значений переменных.

В булевой алгебре принято опускать скобки в следующих двух случаях: а) при

последовательном выполнении нескольких конъюнкций или дизъюнкций; б) если они

являются внешними скобками у конъюнкции. Оба соглашения совершенно аналогичны

общепринятому опусканию скобок для операции умножения в арифметических

выражениях.

Рассмотрим несколько способов упрощения формул с помощью эквивалентных

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

символов.

а) Поглощение: 1)xxyx

используя для доказательства соотношения 3, 7а и 7в.

Далее будем опускать доказательства приводимых равенств, которые при желании можно

получить из соотношений 1 – 10 и уже доказанных равенств.

б) Склеивание: xyxxy.

в) Обобщённое склеивание: zyxzxyzyxz.

г) yxyxx.

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

дизъюнктивной нормальной форме (ДНФ).

Определение. Элементарными конъюнкциями называются конъюнкции

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

раза. Дизъюнктивной нормальной формой называется формула, имеющая вид дизъюнкции

элементарных конъюнкций.

Заметим, что СДНФ является частным случаем ДНФ.

Приведение формулы к ДНФ выполняется так. Сначала с помощью соотношений 6

и 8 все отрицания “спускаются” до переменных. Затем раскрываются скобки. После этого

с помощью соотношений 5, 9 и 10 удаляются лишние конъюнкции и повторения

переменных в конъюнкциях. Наконец, с помощью соотношений 7а – 7е удаляются

лишние константы. При этом необходимо помнить, что ДНФ данной формулы может

быть не единственной.

Пример 3. Привести к ДНФ формулу ))(()(yzzyxxzyxxy.

Решение:

))()(0()(()())(()(zyzyxzyxxyyzzyxxzxyxxyyzzyxxzyxxy

)())(())()(0(zzyzyyzxyxyxxyzyzyxyxxyzyzyxyxxy

zyyxzyxxyyxxxyzyzxyxyxxyzyzzxyxyxxy)()0(

zyxxyzyxzyxxxy0. В итоге получили дизъюнкцию элементарных

конъюнкций, то есть ДНФ.

Доказано, что если из формулы 1F можно с помощью эквивалентных

преобразований получить формулу 2F, то можно из формулы 2F (с помощью тех же

соотношений) получить формулу 1F. Иначе говоря, всякое эквивалентное преобразование

обратимо. Это позволяет сформулировать следующую теорему.

Теорема 8.3. Для любых двух эквивалентных формул 1F и 2F существует

эквивалентное преобразование 1F в 2F и наоборот с помощью соотношений 1 – 10.

и 2) xyxx)(. Докажем данное равенство подробно,

xxyxxyxxyx1)1(1.

25

Аналогично понятию ДНФ определяется понятие конъюнктивной нормальной

формы (КНФ), то есть КНФ есть конъюнкция элементарных дизъюнкций. Переход от

КНФ к ДНФ и обратно всегда осуществим (обычно, с помощью формул Де Моргана).

Пример 4. Привести формулу zxyxyx к КНФ.

Заменим исходную формулу её двойным отрицанием, а затем применим соотношения 8.

))()(())()((zxyxyxzxyxyxzxyxyxzxyxyxzxyxyx

xyzzyxyxxyzyxxzyxyxxzxxyyxzxyyxyyxxx))(())((

))(()1(zyxyxxyzyxxyzyxxyzzyx.

Определение. Функция ),,(11nxxf

, если ),,(),,(1211nnxxfxxf

Если взять отрицание обеих частей равенства и подставить nxx,,1

переменных nxx,,1

означает, что функция 2f двойственна к функции 1f, и, таким образом, отношение

двойственности является симметричным. Из определения двойственности ясно, что для

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

оказаться, что функция двойственна самой себе. В этом случае она называется

самодвойственной.

Пример 1. Если рассматривать логические функции, то, очевидно, дизъюнкция

двойственна конъюнкции и наоборот (непосредственно следует из правил Де Моргана).

Отрицание является самодвойственной функцией. Функция-константа 11f двойственна

функции 02f. Ещё один традиционный пример самодвойственной функции – функция

xzyzxy

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

называемое принципом двойственности.

Теорема 10.1. Если в формуле F, представляющей функцию f, все знаки функций

заменить соответственно на знаки двойственных им функций, то полученная формула *F

будет представлять функцию *f

В булевой алгебре принцип двойственности имеет более конкретный вид, вытекающий

из ранее приведённых примеров: если в формуле F, представляющей функцию f, все

конъюнкции заменить дизъюнкциями и наоборот, все единицы заменить нулями и

наоборот, то получим формулу *F

функции f.

Если функции равны, то двойственные им функции также равны. Это позволяет с

помощью принципа двойственности получать новые эквивалентные соотношения,

переходя от равенства 21FF с помощью указанных замен к равенству 2*1*FF.

Примером могут служить соотношения xyxx)( и xyxx)(, которые могут быть

получены друг из друга по указанному принципу.

4. Двойственность.

называется двойственной к функции ),,(12nxxf

.

, то получится ),,(),,(),,(2121211xxfxxfxxfnn

.

, двойственную функции f

.

, представляющую функцию *f

5. Булева алгебра и теория множеств.

Ранее были описаны булевы алгебры множеств, то есть алгебры вида

),,);((UB, где )(U

подмножеств. Общий термин “булева алгебра” для алгебр множеств и логических

функций не является случайным.

— булеан множества U

, то есть множество всех его

26

Определение. Всякая алгебра типа )1,2,2( называется булевой алгеброй, если её

операции удовлетворяют соотношениям 1 – 10 (см. предыдущую лекцию).

В алгебре множеств элементами являются подмножества фиксированного

универсального множества U. В этой алгебре операция пересечения соответствует

конъюнкции, операция объединения соответствует дизъюнкции, а операция дополнения

соответствует отрицанию. Само множество U является единицей, а пустое множество –

нулём. Справедливость соотношений 1 – 10 для этой алгебры можно доказать

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

функций – как соответствующие операции над множествами.

В одной из предыдущих лекций отмечалось взаимно однозначное соответствие между

множеством )(U

Каждому подмножеству UM

где 1

i

алгебре ),,;(

nBB

Пусть даны два вектора ),,(1n

, где naaU,,1 и множеством nB двоичных векторов длины n.

, если Mai

соответствует двоичный вектор ),,()(1nMГ

, и 0

i

определяются следующим образом.

),,(11nn

),,(11nn

, если Mai

и ),,(1n

. Операции над векторами в булевой

из множества nB

,

,

),,(1n

.

Поскольку компоненты (координаты) векторов принимают значения 0 или 1, то

указанные операции – это просто логические операции над двоичными переменными,

поэтому операции над векторами естественно назвать покомпонентными логическими

операциями над двоичными векторами.

Пример 2. Даны векторы 01011a и 11010b. Найти ababa,,.

Решение:

00100,01010,11011ababa.

Заметим, что подобные операции (наряду с логическими операциями над

переменными) входят в систему команд любой современной ЭВМ.

Теорема 10.2. Если мощность множества U

),,);((U

Эта простая по содержанию теорема имеет огромное значение в математике. Она

позволяет заменить теоретико-множественные операции над системой подмножеств

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

Похожая по формулировке, но значительно отличающаяся по смыслу теорема

существует для множества всех логических функций n

Обозначим это множество )(2nP

следовательно, образует конечную булеву алгебру ),,);((2nP, которая является

подалгеброй булевой алгебры логических функций.

Теорема 10.3. Если мощность множества U

),,);((U изоморфна булевой алгебре функций ),,);((

Теорема 10.3 указывает на тесную связь между множествами и логическими

функциями и позволяет переходить от операций над множествами к операциям над

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

операции над функциями, заданными не формулами, а таблицами. Пример приведён в

следующей таблице, содержащей две функции трёх переменных f и g

операций над ними:

)(nU

изоморфна булевой алгебре ),,;(

nB

равна n

.

переменных ),,(1nxxf

. Оно замкнуто относительно операций ,, и,

равна n2

2nP.

)2(nU

1x 2x 3x f g gf gf

27

0 0 0 0 0 0 0 1

0 0 1 1 1 1 1 0

0 1 0 0 1 1 0 1

0 1 1 0 0 0 0 1

1 0 0 1 0 1 0 0

1 0 1 1 1 1 1 0

1 1 0 0 0 0 0 1

1 1 1 0 1 1 0 1

6. ДНФ, интервалы и покрытия.

Теоретико-множественная интерпретация булевой алгебры предлагает очень удобный

язык для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их

упрощения. Рассмотрим кратко основные понятия, связанные с ДНФ.

Введём следующее обозначение: обозначим через fM

наборов функции f

только тогда, когда 1)(f

функции f

Легко показать, что соответствие между функциями и их единичными множествами

является изоморфизмом.

Если функция ),,(1nxxf

переменных, то множество fM

функция – элементарная конъюнкция k

двоичных наборов. Это объясняется тем, что в таком случае kn переменных, не

входящих в эту конъюнкцию несущественны для функции f. Тогда они принимают kn2

значений, не изменяя значения f

интервалом.

Пример 3. Рассмотрим функцию 424321),,,(xxxxxxf

Прежде всего, заметим, что две переменных 

Это позволяет сразу определить количество единичных наборов, содержащихся в

множестве fM

получим 4224

Далее, очевидно, что 1f

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

данной функции: 1110,1100,0110,0100

В рассматриваемом случае говорят, что конъюнкция 42xx

) покрывает множество fM

Представление некоторой функции в виде ДНФ соответствует представлению её

единичного множества в виде объединения интервалов; в совокупности все конъюнкции

ДНФ покрывают всё единичное множество функции f. Обратное также верно: если все

элементы некоторого интервала kM

функции, содержащая конъюнкцию k.

множество всех единичных

. Тогда набор (вектор) 

. Множество fM

из множества nB

называется единичным множеством

, а функция f

называется характеристической функцией множества fM

представляется элементарной конъюнкцией всех n

содержит ровно один элемент множества nB

переменных )(nk

. Множество fM

такой функции называется

и найдём её интервал.

31,xx

являются несущественными.

(иначе говоря, его мощность). Поскольку в данном случае 2,2kn

fM

.

только при значениях 0,142xx. При этом переменные

. Итак, 1110,1100,0110,0100fM

(или, точнее, интервал 42xxM

и все его подмножества.

принадлежат fM

, то существует ДНФ данной

28

Лекция № 6. Полнота и замкнутость.

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

помощью формул. Таблица задаёт функцию непосредственно как соответствие между

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

то есть, пригоден для любых функций, однако слишком громоздок. Формула – гораздо

более компактный способ задания функции, но она задаёт функцию через другие

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

ли логическая функция представима формулой в этой системе. В позапрошлой лекции

был получен положительный ответ для системы ,,0 (теорема 8.2). В данной

лекции будет показано, как решать этот вопрос для произвольной системы .

1. Функционально полные системы.

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

любая логическая функция может быть представлена формулой над системой  (является

суперпозицией функций этой системы).

Из теоремы 8.2 следует, что система ,,0 является функционально полной.

Равным образом, функционально полна любая система , через функции которой можно

выразить конъюнкцию, дизъюнкцию и отрицание. Действительно, для любой логической

функции f из такой системы следует составить булеву формулу (а она обязательно

существует согласно теореме 8.2) и потом выразить в ней конъюнкцию, дизъюнкцию и

отрицание через функции системы . Аналогично обосновывается более общее

утверждение.

Теорема 11.1. Если все функции функционально полной системы * представимы

формулами над системой , то система  также функционально полна.

Пример 1.

а) Системы ,1 и ,2 функционально полны. Действительно, с помощью

законов Де Моргана и двойного отрицания можно выразить в каждой из этих систем

функцию, недостающую до 0

С точки зрения функциональной полноты систему 0

она сохраняет свойство полноты и при удалении из неё конъюнкции или дизъюнкции.

Однако легко видеть из приведённого примера, что, хотя системы 1 и

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

на другую вносит в формулу сразу три лишних отрицания.

б) Системы 3

функционально полными.

)()();()(;212121212121xxxxxxxxxxxxxxxxx

Таким образом, система 3

в) Система 1,,5 (умножение по модулю 2, сложение по модулю 2 –

см. пункт 1 лекции № 8)) является функционально полной. Поскольку 1xx, данная

система сводится к 0

На свойствах этой системы остановимся подробнее.

через остальные две:

21212121,xxxxxxxx.

следует считать избыточной:

(штрих Шеффера) и 4

(стрелка Пирса) являются

сводится к системе 1

, а система 4

.

2. Алгебра Жегалкина и линейные функции.

29

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

операциями , называется алгеброй Жегалкина.

Замечание. Операция  вполне аналогична операции конъюнкции (логического

умножения). Однако операция  имеет совершенно другой математический смысл, чем

дизъюнкция (соответствующая функция ранее была названа неравнозначностью).

Поэтому никак нельзя считать алгебру Жегалкина иной формой записи булевой алгебры.

В алгебре Жегалкина выполняются следующие соотношения (знак умножения 

опущен):

2.1. xyyx,

2.2. xzxyzyx)(,

2.3 0xx,

2.4 xx0.

Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры,

относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:

2.5 1xx,

2.6 yxxyyx.

Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все

упрощения по вышеуказанным соотношениям, то получится формула, имеющая вид

Суммы произведений, то есть полином (многочлен) по модулю 2. Такая формула

называется полиномом Жегалкина для данной функции.

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

равенства 2.5 и 2.6, а также прямое следствие из равенства 2.6: если 021xx, то

2121xxxx. Оно, в частности, позволяет заменять знак дизъюнкции знаком 

случаях, когда исходная формула представляет собой СДНФ.

Пример 2. Составить полиномы Жегалкина для данных функций:

а) 31331121312131213121)()()1()1(xxxxxxxxxxxxxxxxxxxx

б) 1)1()1)(1(2121212121212121xxxxxxxxxxxxxxxx.

Заметим, что если в полученных полиномах Жегалкина произвести обратную замену

функций, то получим упрощённые формулы булевой алгебры.

Теорема 11.2. Для всякой логической функции существует полином Жегалкина и

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

Существование такого полинома, по сути, уже доказано, а для доказательства его

единственности достаточно показать существование взаимно однозначного соответствия

между множеством всех функций п переменных и множеством всех полиномов

Жегалкина.

Определение. Функция, у которой полином Жегалкина имеет вид 

параметры ,

Все функции от одной переменной линейны. Также линейными являются функции

эквивалентность и сумма по модулю 2.

i равны нулю или единице, называется линейной.

3. Замкнутые классы. Монотонные функции.

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

классом, если любая суперпозиция функций из множества М снова принадлежит М.

Всякая система  логических функций порождает некоторый замкнутый класс, а

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

Такой класс называется замыканием 

функционально полная система, то 2PM.

Пример 3.

и обозначается . Если множество М —

30

а) Множество всех дизъюнкций, то есть функций вида nxxx

замкнутым классом.

б) Множество всех линейных функций является замкнутым классом, так как

подстановка формул вида 

вида.

Важнейшим примером замкнутого класса является класс монотонных функций,

который будет рассмотрен далее.

Ранее рассматривалось отношение частичного порядка  на множестве векторов

одинаковой длины. Напомним, что для векторов ),,(1naaa

выполняется ba

воспользуемся этим отношением для двоичных векторов.

Определение. Функция ),,(1nxxf

двоичных наборов длины n

Пример 4.

а) Функция xxf)( монотонна.

б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными

функциями.

в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.

iix

после преобразований даёт формулу такого же

, если для любого ni,,1

выполняется iiba

называется монотонной, если для любых двух

из того, что ba следует )()(bfaf.

1x 2x 3x 1f 2f

0 0 0 0 0

0 0 1 1 0

0 1 0 0 1

0 1 1 1 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 0 1

Функция 1f, очевидно, не является монотонной, так как, например 101001

0)101(1)001(11ff. Монотонность функции

непосредственной проверкой.

Проверка монотонности функции непосредственно по определению требует

анализа таблицы функции и может оказаться достаточно трудоёмкой. Поэтому весьма

полезной для установления монотонности является следующая теорема. Всякая булева

формула, не содержащая отрицаний, представляет собой монотонную функцию

отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1,

найдётся представляющая её булева формула без отрицаний.

Теорема 11.3. Всякая булева формула, не содержащая отрицаний, представляет

собой монотонную функцию отличную от константы; наоборот, для любой

монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула

без отрицаний.

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

без отрицаний в формулу без отрицаний снова даёт формулу без отрицаний, вытекает

следующая теорема.

Теорема 11.4. Множество всех монотонных функций является замкнутым классом.

Но поскольку всякая булева формула без отрицаний является суперпозицией

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

Следствие. Класс монотонных функций является замыканием системы функций

1,0,,.

2f легко установить

4. Теоремы о функциональной полноте.

31

Теперь перейдём к рассмотрению основного вопроса, поставленного в рамках

данной лекции: каковы необходимые и достаточные условия функциональной

полноты для произвольной системы функций ? Вначале было сказано, что система

 полна, если конъюнкция, дизъюнкция и отрицание являются суперпозициями

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

выразить через них булевы операции. Сначала сформулируем две леммы,

позволяющие вывести соответствующие теоремы.

Лемма 1 (о немонотонных функциях). Если функция ),,(1nxxf

то подстановкой констант из неё можно получить отрицание.

Практически данная лемма является утверждением, противоположным теореме,

обратной к теореме 11.3. Смысл её заключается в том, что для функции ),,(1nxxf

существует такая подстановка 1n константы, что функция оставшейся одной

переменной является отрицанием.

Лемма 2 (о нелинейных функциях). Если функция ),,(1nxxf

помощью подстановки констант и использования отрицаний из неё можно получить

дизъюнкцию или конъюнкцию.

Иначе говоря, существует представление дизъюнкции и конъюнкции в виде

суперпозиции констант, отрицаний и нелинейной функции f.

Замечание. При традиционных обозначениях переменных в выражениях вида

),,(1nxxf

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

функции. Эти роли следует различать.

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

немонотонных функций, нелинейных функций и констант. Это ещё не полнота в

точном смысле слова, так как константы с самого начала предполагались данными.

Однако такое предположение часто бывает оправданным в различных приложениях

(прежде всего в синтезе логических схем). Поэтому есть смысл ввести ослабленное

определение полноты.

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

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

системой 1,0, то есть является суперпозицией констант и функций из системы .

Очевидно, что из обычной полноты системы следует её слабая полнота.

Теорема 11.5 (первая теорема о функциональной полноте). Для того, чтобы

система функций  была функционально полной в слабом смысле, необходимо и

достаточно, чтобы она содержала хот бы одну немонотонную функцию и хотя бы одну

нелинейную функцию.

Доказательство:

1) Необходимость. Классы монотонных и линейных функций замкнуты и содержат 0 и

1. Поэтому если  не содержит немонотонных или нелинейных функций, то их нельзя

получить с помощью суперпозиций функций из системы  и констант.

2) Достаточность. Пусть  содержит немонотонную и нелинейную функцию. Тогда

по лемме 1 подстановкой констант из монотонной функции получаем отрицание, а

затем по лемме 2 из нелинейной функции с помощью отрицаний и констант получаем

дизъюнкцию и конъюнкцию.

Пример 5.

а) Система ,6 функционально полна в слабом смысле, так как операция 

нелинейна (как и конъюнкция), а операция  (сложение по 2mod) немонотонна.

б) В функционально полной системе 3

Шеффера – нелинейна и немонотонна.

, где переменные расположены в естественном порядке индексов, эти

единственная функция – штрих

32

Для формулировки необходимых и достаточных условий “cильной” полноты (в

отличие от слабой) нужно ввести ряд определений, описывающих ещё три замкнутых

класса функций.

Определение. Функция ),,(1nxxf

выполняется 0)0,,0(f и сохраняющей единицу, если выполняется 1)1,,1(f.

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

констант в суперпозиции. Равным образом замкнутый класс образуют

самодвойственные функции (такие, что ),,(),,(11nnxxfxxf

Теорема 11.6 (вторая – основная – теорема о функциональной полноте). Для

того чтобы система функций  была функционально полной (в сильном смысле),

необходимо и достаточно, чтобы она содержала: 1) нелинейную функцию, 2)

немонотонную функцию, 3) функцию, не являющуюся самодвойственной, 4)

функцию, не сохраняющую ноль, 5) функцию, не сохраняющую единицу.

называется сохраняющей ноль, если

Лекция № 7. Язык логики предикатов.

Определение. Предикатом ),,(1nxxP

произвольное множество, а B

Иначе говоря, n

двузначная функция от n аргументов из произвольного множества M. Множество M

называется предметной областью предиката, переменные nxx,,1

переменными. В принципе, можно определить предикат как функцию BMMPn

то есть допустить, что переменные принимают значения из различных множеств – в

некоторых случаях это оказывается удобным.

Для любых Mи n существует взаимно однозначное соответствие между n

местными отношениями и n

следующим образом. Каждому n

такой, что 1),,(1

определяет отношение R

1),,(1

nxxP

Всякой функции MMfn: можно поставить в соответствие )1(n

предикат P

Поскольку функция должна быть однозначной, то это соответствие требует, чтобы для

любого 11

nnxx

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

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

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

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

будем пользоваться обозначениями вида 21Pxx, которые употреблялись ранее для

бинарных отношений.

Пример 1.

а) Предикат 21xx является двухместным предикатом, предметной областью

которого могут служить любые множества действительных чисел. Высказывание 56

истинно, а высказывание 103 ложно. Если вместо одной из переменных подставить

число, то получится одноместный предикат: 215,3xx и так далее.

1. Предикаты.

определённое ранее двоичное множество 1;0.

называется функция BMPn:, где M

местным предикатом, определённым на множестве M называется

местными предикатами на множестве M, определяемое

местному отношению R соответствует предикат P

nxxP

. При этом R

такой, что 1),,,(11

выполнялось 0),,,(11

тогда и только тогда, когда Rxxn),,(

такое, что Rxxn),,(

задаёт область истинности предиката.

nnxxxP

1

1

тогда и только тогда, когда

тогда и только тогда, когда 11),,(

nnxxxP

. Поэтому обратное соответствие (от

33

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

натурального числа 2n не существует натуральных чисел zyx,,, которые

удовлетворяли бы равенству nnnzyx. Этому равенству можно поставить в

соответствие предикат ),,,(nzyxP, истинный тогда и только тогда, когда оно

выполняется.

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

часто встречаются указания типа “повторять цикл до тех пор, пока переменные x и y не

станут равными или прекратить вычисление цикла после ста повторений”. Если

обозначить через i счётчик повторений, то описанное здесь условие примет вид

)100()(iyx, а само указание в целом описывается выражением: “повторять, если

)100()(iyx”.

2. Кванторы.

Пусть )(xP предикат, определённый на множестве M. Высказывание “для всех

)(xP

входит в обозначение, но когда оно ясно из контекста пишут просто )(xPx. Знак 

называется квантором общности.

Высказывание “существует такое значение Mx, что )(xP истинно” обозначается

)(xPMx

предиката )(xP к выражениям вида )(xPx или )(xPx называется связыванием

переменной x

). Переменная, на которую навешен квантор, называется связанной, несвязанная

переменная называется свободной.

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

Свободная переменная – это обычная переменная, которая может принимать различные

значения из множества M; выражение )(xP — переменное высказывание, зависящее от

значения x

определённое значение. Это, в частности, означает, что переименование связанной

переменной, то есть переход от выражения )(xPx к выражению )(xxP и наоборот не

меняет истинности выражения. Переменные, являющиеся, по существу, связанными,

встречаются не только в логике. Например, в выражениях

переменная x

определенному числу, а второе становится функцией от пределов интегрирования.

Навешивать кванторы можно и на многоместные предикаты и вообще на любые

логические выражения, которые при этом заключаются в скобки. Выражение, на которое

навешивается квантор  или  называется областью действия квантора. Все вхождения

переменной в это выражение являются связанными. Навешивание квантора на

многоместный предикат уменьшает в нём количество свободных переменных и

превращает его в предикат от меньшего числа переменных.

истинно” обозначается )(xPMx

или )(xPMx

или )(xPx

, а также навешиванием квантора на переменную x

. Знак 

называется квантором существования. Переход от

. Выражение )(xxP не зависит от переменной x

связана: при фиксированной функции f первое выражение равно

определенному числу, а второе становится функцией от пределов интегрирования.

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

Пример 2.

а) Пусть предикат “ чётное число”. Тогда высказывание истинно на любом множестве чётных чисел и ложно, если множество содержит хотя бы одно нечётное число. Высказывание истинно на любом множестве, содержащем хотя бы одно чётное число и ложно на любом множестве нечётных чисел.

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

3. Истинные формулы и эквивалентные соотношения.

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

  1. Если в области для формулы существует такая подстановка констант вместо всех переменных, что становится истинным высказыванием, то эта формула называется выполнимой в области . Если существует область , в которой формула выполнима, то формула называется просто выполнимой. Пример выполнимой формулы — .

  2. Если формула выполнима в области при любых подстановках констант, то она называется тождественно истинной в области . Формула, тождественно истинная в любых множествах называется просто тождественно истинной, или общезначимой, или тавтологией. Например, формула тождественна для всех множеств, состоящих из одного элемента, а формула является тавтологией.

  3. Если формула невыполнима в области при любых подстановках констант, то она называется тождественно ложной в области . Формула, тождественно ложная в любых множествах называется просто тождественно ложной или противоречивой. Формула является противоречивой.

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

Отметим, что если формулы и эквивалентны в соответствии с этим определением, то формула является тождественно истинной.

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

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

Аналогично доказывается истинность соотношения

Большое значение имеют следующие свойства, которые могут быть доказаны способом, рассмотренным в примере 3.

    1. Дистрибутивность квантора относительно конъюнкции:

.

    1. Дистрибутивность квантора относительно дизъюнкции:

.

Если же кванторы и поменять местами, то получатся соотношения, верные только в одну сторону:

3) ,

4) .

В таких случаях говорят, что левая часть является более сильным утверждением, чем правая, поскольку она требует для своего выполнения более жёстких условий. Так, например, в соотношении 3 в левой части требуется, чтобы оба предиката были истинны для одного и того же значения , тогда как в правой части они могут быть истинны при различных значениях переменной. Пример случая, когда соотношения 3 и 4 в обратную сторону неверны: чётное число”, нечётное число”.

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

5) .

6) .

7) .

8) .

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

  1. Доказательства в логике предикатов.

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

, .

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

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

Лекция № 8. Комбинаторика.

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

  1. Правила суммы и произведения.

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

Теорема 13.1. Пусть даны непересекающиеся конечные множества . Тогда мощность объединения этих множеств равна сумме мощностей данных множеств:

.

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

Если некоторый элемент можно выбрать способами, а элемент способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “ или ” можно сделать способами. Это правило называется правилом суммы.

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

Теорема 13.2. Число элементов в декартовом произведении множеств равно произведению мощностей этих множеств:

.

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

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

Пример 1.

а) В некоторой средней школе имеется три пятых класса, в которых обучаются соответственно 28, 31 и 26 учащихся. Требуется одного из них выбрать для участия в совете школы. Сколькими способами можно сделать выбор?

По правилу суммы получаем .

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

По правилу произведения получаем .

  1. Размещения.

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

Пример 2. Куплено различных 12 книг. На полке можно поставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?

Будем считать различными не только те случаи, когда берутся разные книги, но и когда они по-разному расставлены на полке (в различном порядке). Тогда речь идёт о перестановках по 6 из 12. Получаем: .

Рассмотрим существенно другой случай, а именно когда элементы множества в векторах могут повторяться.

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

Пример 3. Сколько различных комбинаций может получиться при одновременном бросании трёх игральных костей?

Каждая игральная кость представляет собой кубик, на гранях которого нанесено от одного до 6 очков. При каждом бросании мы будем получать наборы вида , где — количество очков, выпавших на соответствующей кости. Речь идёт о перестановках с повторениями по 3 элемента из 6. Получаем: .

Замечание. Очевидно, что размещения без повторений являются частным случаем размещений с повторениями.

  1. Перестановки.

Определение. Любой вектор длины , составленный из элементов элементного множества , в котором все элементы различны, называется перестановкой без повторений из элементов. Число всех перестановок без повторений из элементов обозначается и равно .

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

Пример 4. Сколькими различными способами можно расставить на полке 10 различных книг?

Здесь, в отличие от примера 2, значение имеет только порядок расставляемых книг. Поэтому речь идёт о перестановках из 10 элементов. Получаем: .

Рассмотрим случай, когда элементы множества повторяются по нескольку раз. Для определённости пусть 1-й элемент повторяется раз, 2-й элемент — раз и так далее. Тогда векторы длины , образованные из элементов данного множества называются перестановками из элементов с повторениями. Число таких перестановок обозначается и равно .

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

Пример 5. Сколько различных шестизначных чисел могут быть записано с помощью цифр 1, 2, 2, 2, 3, 3?

Имеется набор из шести цифр, в котором цифра 2 повторяется трижды и цифра 3 – дважды. Полученные числа будут представлять собой перестановки с повторениями из 6 элементов. Получаем: .

  1. Сочетания. Бином Ньютона.

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

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

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

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

Замечание 2. Для сочетаний без повторений обязательно требование , причём в случае равенства получим естественный результат . Но для сочетаний с повторениями это требование необязательно, как будет видно из приведённого ниже примера.

Пример 6.

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

Поскольку имеет значение только то, какие именно сотрудники отобраны, то речь идёт о сочетаниях без повторений по 3 элемента из 10. Получаем:

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

Будем считать различными те букеты, которые отличаются друг от друга по подбору цветов. Поскольку цветы в букете могут повторяться, то речь идёт о сочетаниях с повторениями по 7 элементов из 5. Тогда получим .

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

.

С частными случаями применения этой формулы ( для случаев и ) сталкиваются ещё в школе при изучении формул сокращённого умножения:

.

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

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

…………………..

Лекция № 9. Графы: основные понятия и операции. Маршруты. Цепи. Циклы.

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

  1. Графы, их вершины, рёбра и дуги. Изображение графов.

Определение. Если на плоскости задать конечное множество V точек и конечный набор линий E, соединяющих некоторые пары из точек V, то полученная совокупность точек и линий будет называться графом G = (V, E).

При этом элементы множества V называются вершинами графа, а элементы множества Eребрами.

Определение. Если вершина v является концом ребра , то говорят, что v и инцидентны.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями (на рисунке 1.4 при вершине 5 имеется петля). Одинаковые пары в множестве E называются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в E называется кратностью ребра (v, w). Например, на рисунке 1.1 все рёбра имеют кратность 1, а на рисунке 1.2 есть два ребра, соединяющих одни и те же вершины 1 и 4, следовательно, их кратность равна двум.

Множество V и набор E определяют граф с кратными ребрами – псевдограф.

Псевдограф без петель называется мультиграфом.

Если в наборе E ни одна пара не встречается более одного раза, то мультиграф называется графом.

Ниже, на рисунке 1.1 изображен граф, на рисунке 1.2 мультиграф, на рисунке 1.4 – псевдограф.

Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины. На рисунке 1 изображены некоторые неориентированные графы.

Рисунок 1.

1.1 1.2 1.3

1.4 1.5

Замечание 1. Слово “линия”, которое мы используем, подразумевает несущественность того, какая конкретно линия используется для соединения двух вершин графа, то есть её геометрические характеристики не имеют значения.

Замечание 2. Граф можно определить, также как совокупность двух множеств и , между элементами которых установлено отношение инцидентности, при котором каждый элемент инцидентен ровно двум элементам .

Определение. Если х = {v, w} – ребро графа, то вершины v, w называются концами ребра х.

Определение. Если пары в наборе E являются упорядоченными, то граф называется ориентированным или орграфом.

Если пишут = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.

Определение. Вершины v, w графа G = (V, E) называются смежными, если {v,w}Е. Два ребра называются смежными, если они имеют общую вершину.

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

На рисунке 1.5 все вершины, кроме вершины 1, являются висячими. На рисунке 1.3 вершина 4 является изолированной. Если граф состоит только из таких вершин, его называют пустым. В некоторых случаях пустым называют граф, не имеющей ни одной вершины.

Рисунок 2.

2.1 2.2 2.3

    1. 2.5

На рисунке 2 представлены различные типы ориентированных графов.

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

  1. Матрица инцидентности и список рёбер. Матрица смежности графа.

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

Задать граф – значит, описать множества его вершин и рёбер и задать между ними отношение инцидентности. Когда граф конечный, для описания его вершин и рёбер достаточно их занумеровать. Пусть — вершины графа, а — его рёбра. Отношение инцидентности можно определить матрицей размерности . Столбцы этой матрицы будут соответствовать вершинам графа, а строки – его рёбрам. Если ребро инцидентно вершине , то , в противном случае — . Такая матрица называется матрицей инцидентности неориентированного графа, поскольку по способу её задания невозможно различить начало и конец каждого ребра.

Пример 1. Составить матрицу инцидентности неориентированного графа, изображённого на рисунке 3.

Рисунок 3.

Строим матрицу инцидентности в виде таблицы:

 

1

2

3

4

5

6

7

a

1

1

0

0

0

0

0

b

1

0

1

0

0

0

0

c

0

1

0

1

0

0

0

d

1

0

0

0

1

0

0

e

0

1

0

0

0

1

0

f

0

0

1

1

0

0

0

g

0

0

1

0

1

0

0

h

0

0

0

1

0

1

0

i

0

0

0

0

1

0

1

j

0

0

0

0

0

1

1

 

Для ориентированного графа матрица инцидентности составляется иначе. Это матрица размерности .

Если вершина — начало ребра , то . Если вершина — конец ребра , то . Если вершине инцидентна петля , то , где любое число, кроме чисел (обычно берут 2). В любом противном случае — .

Пример 2. Построить матрицу инцидентности для графа, изображённого на рисунке 4.

Строим матрицу инцидентности в виде таблицы:

 

1

2

3

4

5

6

7

a

1

1

0

0

0

0

0

b

1

0

1

0

0

0

0

c

0

1

0

1

0

0

0

d

0

0

1

0

1

0

0

e

0

0

1

0

0

1

0

f

0

0

1

0

0

0

1

g

0

0

0

0

0

0

2

 

Ещё проще задавать граф с помощью таблицы рёбер. Она состоит из двух столбцов; в левых содержатся названия рёбер, а в правых – инцидентные им вершины (для ориентированных графов обязательно сначала указывается начало ребра, потом конец). Ниже приведены таблицы рёбер для графов из примеров 1 и 2.

Для примера 1:

 

Рёбра

Вершины

a

1, 2

b

1, 3

c

2, 4

d

1, 5

e

2, 6

f

3, 4

g

3, 5

g

4, 6

i

5, 7

j

6, 8

 

Для примера 2:

 

Рёбра

Вершины

a

1, 2

b

1, 3

c

2, 4

d

3, 5

e

3, 6

f

3, 7

g

7, 7

 

Очевидно, по списку рёбер можно построить его таблицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером; аналогично можно выполнить обратную процедуру.

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

 

1

2

3

4

5

6

7

1

0

1

1

0

1

0

0

2

1

0

0

1

0

1

0

3

1

0

0

1

1

0

0

4

0

1

1

0

0

1

0

5

1

0

1

0

0

0

1

6

0

1

0

1

0

0

1

7

0

0

0

0

1

1

0

 

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

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

 

1

2

3

4

5

6

7

1

0

1

1

0

0

0

0

2

0

0

0

1

0

0

0

3

0

0

0

0

1

1

1

4

0

0

0

0

0

0

0

5

0

0

0

0

0

0

0

6

0

0

0

0

0

0

0

7

0

0

0

0

0

0

1

 

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

Ориентированный граф с симметричной матрицей смежности канонически соответствует неориентированному графу, имеющему ту же таблицу смежности (но не наоборот).

  1. Идентификация графов, заданных своими представлениями.

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

Рисунок 5.

а) б)

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

Определение. Графы G1(V1, E1) и G2(V2, E2) называются изоморфными, если существует взаимно однозначное отображение : V1 V2, сохраняющее смежность.

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

  1. Основные определения.

Пусть G(V, Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

Определение . Маршрутом (путем) для графа G(V, Е) называется последовательность v1e1v2e2v3ekvk+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).

Любой отрезок конечного или бесконечного маршрута вида , где также является маршрутом и называется участком маршрута .

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

Рисунок 1.

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

Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

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

Определение. Замкнутый маршрут (путь) называется циклическим маршрутом или циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

Иначе говоря, простой цикл – это циклический маршрут, в котором любые два соседние ребра имеют одну инцидентную вершину. Последовательности , и представляют один и тот же цикл (рисунок 2). Часто считается, что можно менять порядок рёбер цикла на противоположный, то есть, например, последовательность представляет тот же цикл.

Рисунок 2.

Участок цепи или цикла является цепью; соответственно, участок простой цепи или простого цикла является простой цепью.

  1. Связные компоненты графов.

Определение. Вершины и называются связанными, если существует маршрут с началом и концом . Наоборот, маршрут с началом и концом называется связывающим эти вершины.

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

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

Определение. Граф называется связным, если все его вершины связаны между собой.

Поэтому все подграфы связного графа связны и называются связными компонентами графа .

  1. Расстояния. Диаметр, радиус и центр графа. Протяжённости.

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

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

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

Определение. Минимальная длина простой цепи с началом в вершине и концом в вершине называется расстоянием между этими вершинами. Обозначается: .

Расстояние между любой вершиной и ею самой равно 0. Ему соответствует нулевой маршрут, не содержащий рёбер. Для любой пары различных вершин и выполняется , так как связывающая их цепь состоит хотя бы из одного ребра. Вообще, расстояние удовлетворяет аксиомам метрики:

1) , причём тогда и только тогда, когда ;

2) .

Также для расстояния выполняется неравенство треугольника: для любых трёх вершин выполняется неравенство: .

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

Определение. Диаметром конечного графа называется наибольшее из расстояний между парой его вершин: .

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

Пусть — рассматриваемая вершина данного графа, а произвольная вершина графа. Максимальным удалением в графе от фиксированной вершины называется величина .

Определение. Вершина называется центром графа , если максимальное удаление от неё до остальных вершин графа принимает минимальное значение: .

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

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

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

Определение. Протяжённостью называется максимальная из длин связывающих эти вершины простых цепей.

  1. Эйлеровы графы.

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

Теорема 15.1. Для того, чтобы связный граф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.

Рисунок 3

а) б)

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кенигсбергских мостах. Расположение семи мостов в городе Кенигсберге в начале XVIII века приведено на рисунке 3а. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.

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

Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.

Теорема 15.2. Для того, чтобы связный граф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.

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

Определение. Цикл (цепь) в графе G называется Гамильтоновым, если он проходит через каждую вершину графа G ровно один раз.

Пример 1.

а)

— в графе есть и Эйлеров и Гамильтонов циклы

б)

— в графе есть Эйлеров цикл, но нет Гамильтонова

в)

— в графе есть гамильтонов, но нет Эйлерова цикла

г)

— в графе нет ни Эйлерова, ни Гамильтонова цикла

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

Также необходимым условием существования гамильтонова цикла является связность графа.

Лекция № 10. Некоторые классы графов и их частей. Алгоритмы на графах

  1. Деревья.

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

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

Определение. Несвязный неориентированный граф без циклов называется лесом; связные компоненты леса являются деревьями.

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

Теорема 16.1. Любые две вершины дерева связаны одной и только одной цепью. Обратно, если две любые вершины графа можно связать только одной цепью, то он является деревом.

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

Если конечное дерево состоит более чем из одной вершины, оно имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

Пусть в дереве отмечена некоторая вершина . Эту вершину называют корнем дерева , а само дерево – деревом с корнем. В таком дереве можно естественным образом ориентировать рёбра. Любую вершину ребра можно соединить с корнем единственной простой цепью. Если эта цепь не содержит ребра , то вводится ориентация от к ; если цепь содержит данное ребро, то вводится ориентация от к . Ориентированное таким образом дерево называется ориентированным деревом с корнем.

В нём все рёбра имеют направление от корня (см. рисунок 1).

Рисунок 1.

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

Замечание. Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.

Пусть дано конечное дерево . Назовём его концевые вершины вершинами типа 1. Отметим, что если дерево имеет более двух вершин, то среди них есть неконцевые.

Далее удалим из дерева все вершины типа 1 и инцидентные им рёбра. Останется связный граф , также являющийся деревом. Дерево также имеет концевые вершины, которые будем называть вершинами типа 2 в дереве . Аналогичным образом определяются вершины типа 3 и так далее.

Легко видеть, что в конечном дереве имеются лишь вершины конечного числа типов, причём число вершин максимального типа равно одному или двум, так как в соответствующем дереве каждая вершина является концевой.

Теорема 16.2. Центрами дерева являются вершины максимального типа и только они.

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

Определение. Цикломатическим числом конечного неориентированного графа называется число, равное . Здесь количество связных компонентов графа, количество рёбер, количество вершин.

Цикломатическое число дерева равно нулю. Цикломатические числа остальных конечных графов положительны.

  1. Ориентированные графы.

Понятие ориентированного графа (орграфа) было определено ранее. Сейчас рассмотрим подробнее, как выглядят в таком графе пути и циклы.

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

Дадим определение пути в ориентированном графе. Сразу оговоримся, что это понятие можно определять различными способами; мы приводим только один.

Определение. Путь из вершин и рёбер – это такая последовательность рёбер и вершин графа , в которой вершина является началом го ребра, а вершина его концом. Вершина называется началом пути , вершина его концом, число рёбер длиной пути.

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

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

Начало цикла обычно не фиксируется, иначе говоря, все пути, получающиеся друг из друга циклическими сдвигами – это один и тот же цикл. Определение простого ориентированного цикла аналогично соответствующему определению для неориентированного цикла – это цикл, в котором каждая вершина инцидентна ровно двум его рёбрам. Любой граф, содержащий циклы, можно “укоротить” до простого. Граф, не содержащий циклов, называется ациклическим.

Определение. Вершина ориентированного графа называется начальной, если в неё ни входит ни одно ребро и конечной, если из неё не выходит ни одно ребро.

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

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

Понятия длины путей, протяжённости и расстояния между вершинами определяются для ориентированного графа так же, как для неориентированного графа.

  1. Графы с помеченными вершинами и рёбрами.

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

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

  1. Обходы графов

Поиск в ширину (breadth-first search)

Пусть задан граф G = (V, E) и фиксирована начальная вершина s. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по ребрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина (число ребер) кратчайшего пути. В процессе поиска из графа выделяется часть, называемая “деревом поиска в ширину” с корнем s. Она содержит все достижимые из s вершины (и только их). Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм применим и к ориентированным, и к неориентированным графам.

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

Алгоритм.

d[u] – расстояние по ребрам от s до u

Q — очередь

BFS(G, s)

for (для) каждой вершины u из V[G] – {S}

do color[u] = БЕЛЫЙ

d[u] = ∞

родитель[u] = NIL

color[s] = СЕРЫЙ

d[s] = 0

родитель[s] = NIL

Qs

while (очередь Q не пуста)

do u ← извлечь вершину из очереди Q

for (для) всех v смежных с u

do if color[v] == БЕЛЫЙ

then color[v] = СЕРЫЙ

d[v] = d[u] + 1

родитель[v] = u

положить v в очередь

color[u] = ЧЕРНЫЙ

Поиск в глубину

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

Алгоритм.

d[u] – время начала обработки вершины u

f[u] – время окончания обработки вершины u

time глобальное время

DFS(G)

for (для) всех вершин u из V[G]

do color[u] = БЕЛЫЙ

родитель[u] = NIL

time = 0

for (для) всех вершин u из V[G]

do if color[u] = БЕЛЫЙ

then DFS-Visit(u)

DFS-Visit(u)

color[u] = СЕРЫЙ

time++

d[u] = time

for (для) всех v смежных с u

do if color[v] = БЕЛЫЙ

then родитель[v] = u

DFS-Visit(v)

color[u] = ЧЕРНЫЙ

time++

f[u] = time

Где используется:

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

  • алгоритм топологической сортировки DAG’а (directed acyclic graph)

  • проверка графа на ацикличность

  1. Кратчайшие пути

Кратчайший путь из u в v – это любой путь p из u в v, для которого w(p) = δ(u, v), где:

  • w(p) = сумма весов всех ребер пути p

  • δ(u, v) = min{w(p): по всем путям p из u в v}, если существует путь из u в v; ∞ — в противном случае

Алгоритм Дейкстры

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех ребер неотрицательны.

Алгоритм.

d[u] – расстояние до вершины u из исходной вершины s

Q – очередь с приоритетами. Извлекается вершина, для которой d[u] минимально

Initialize-Single-Source(G, s)

for (для) всех вершин v из V[G]

do d[v] = ∞

родитель[v] = NIL

d[s] = 0

Relax(u, v, w)

if d[v] > d[u] + w(u, v)

then d[v] = d[u] + w(u, v)

предок[v] = u

Dijkstra(G, w, s)

Initialize-Single-Source(G, s)

S = Ø

Q ← V[G]

while Q <> Ø

do u ← извлечь вершину, для которой d[u] минимально

S = S U {u}

for (для) всех вершин v смежных с u

do Relax(u, v, w)

Суть алгоритма. d[u] – эта оценка пути по каждой из вершин на данном шаге. Изначально нам известно, что до исходной вершины путь 0, до остальных оценка на первом шаге бесконечность. На каждом шаге берем вершину u для которой оценка минимальна. Для неё можно доказать, что оценка является кратчайшим путем. Для смежных с ней вершин v, если оценка через вершину u оказывается меньше, чем текущая оценка вершины v, то уменьшаем оценку (релаксация).

Оценка времени работы. Оценка времени работы зависит от эффективности реализации очереди с приоритетами. При использовании массива, оценка получается O(V2); при использовании двоичной кучи оценка будет O(E log V); при использовании фибоначчиевой кучи оценка O(V log V + E).

Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда решает задачу о кратчайших весах из одной вершины для случая, когда весам ребер разрешено быть отрицательными. Этот алгоритм возвращает TRUE, если в графе нет цикла отрицательного веса, достижимого из исходной вершины, и FALSE, если таковой цикл имеется. В первом случае алгоритм находит кратчайшие пути и их веса; во втором случае кратчайших путей (по крайней мере, для некоторых вершин) не существует.

Алгоритм.

d[u] – расстояние до вершины u из исходной вершины s

Initialize-Single-Source(G, s)

for (для) всех вершин v из V[G]

do d[v] = ∞

родитель[v] = NIL

d[s] = 0

Relax(u, v, w)

if d[v] > d[u] + w(u, v)

then d[v] = d[u] + w(u, v)

предок[v] = u

Bellman-Ford(G, w, s)

Initialize-Single-Source(G, s)

for i = 1 to |V[G]| — 1

do for (для) каждого ребра (u, v) из E[G]

do Relax(u, v, w)

for (для) каждого ребра (u, v) из E[G]

do if d[v] > d[u] + w(u, v)

then return FALSE

return TRUE

Оценка времени работы. Время работы алгоритма есть O(VE).

Алгоритм Флойда-Уоршолла

Может возникнуть задача, когда требуется найти кратчайшее расстояние между всеми парами вершин. Алгоритм Флойда-Уоршолла использует идею динамического программирования и позволяет за O(V3) найти кратчайшие пути между всеми парами вершин ориентированного взвешенного графа. Веса ребер могут быть отрицательными, но не допускается существования циклов отрицательного веса.

Алгоритм.

Wматрица весов n x n

Dматрица расстояний n x n

Floyd-Warshall(W)

D = W

for k = 1 to n

do for i = 1 to n

do for j = 1 to n

do D[i, j] = min(D[i, j], D[i, k] + D[k, j])

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

  1. Остовные деревья

Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют остовным деревом этого графа.

Минимальным остовным деревом является остовное дерево, сумма весов ребер которого минимальна.

Алгоритм Прима

Q – очередь с приоритетами, ключом в которой является величина key[v] равная минимальному весу ребра из вершины v в вершину из множества уже обработанных

r – корень остовного дерева

MSTPrim(G, w, r)

Q = V[G]

for (для) каждой вершины u из Q

do key[u] = ∞

key[r] = 0

предок[r] = NIL

while Q <> Ø

do u ← извлечь вершину, для которой key[u] минимально

for (для) каждой вершины v смежной с u

do if (v Є Q) AND (w(u, v) < key[v])

then предок[v] = u

key[v] = w(u, v)

Оценка времени работы. Оценка времени работы зависит от эффективности реализации очереди с приоритетами. При использовании двоичной кучи оценка будет O(E log V); при использовании фибоначчиевой кучи оценка O(E + V log V).

Алгоритм Крускала

MSTKruskal(G, w)

A ← Ø

for (для) каждой вершины v из V[G]

do MakeSet(v)

упорядочить рёбра E по весам

for (для) (u, v) из E (в порядке возрастания веса)

do if Find-Set(u) <> Find-Set(v)

then A ← A U {(u, v)}

Union(u, v)

return A

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

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

Практическое занятие №1. Булева алгебра

1. Требуется привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка. Номер варианта определить следующим образом N % 10 (где N — номер по порядку в журнале)

2. В задаче а) написать по данной ДНФ полином Жегалкина, от ДНФ перейти к КНФ, а затем перейти к СКНФ; в задаче б) перейти от данной КНФ к ДНФ, а затем перейти к СДНФ. Номер варианта определить следующим образом 10 + N % 10 (где N — номер по порядку в журнале)

3. С помощью карт Карно по данной таблице истинности для функции 4 переменных найти её сокращённую ДНФ.Номер варианта определить следующим образом 30 + N % 10 (где N — номер по порядку в журнале)

 

31а.

 

 

 

 

 

31б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

0

0

1

 

0 0 0 0

1

0

0

1

0 1

1

0

1

1

 

0 1

1

0

0

1

1 1

1

1

0

1

 

1 1

1

0

0

1

1 0

1

1

1

1

 

1 0

0

1

1

0

 

 

32а.

 

 

 

 

 

32б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

0

0

1

 

0 0

0

1

1

0

0 1

1

0

0

1

 

0 1

0

1

1

0

1 1

0

1

1

0

 

1 1

0

0

0

0

1 0

0

0

0

1

 

1 0

1

0

0

1

 

 

33а.

 

 

 

 

 

33б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

1

1

0

 

0 0

0

0

1

0

0 1

1

1

0

0

 

0 1

0

1

1

0

1 1

1

1

0

0

 

1 1

1

0

0

0

1 0

1

0

0

1

 

1 0

1

0

0

1

34а.

 

 

 

 

 

34б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

0

0

1

 

0 0

1

0

1

1

0 1

1

0

0

1

 

0 1

1

0

0

1

1 1

0

1

1

0

 

1 1

1

0

0

1

1 0

0

1

1

1

 

1 0

0

0

0

1

 

35а.

 

 

 

 

 

35б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

0

0

1

0

 

0 0

1

0

1

1

0 1

1

0

0

1

 

0 1

0

1

0

0

1 1

0

0

1

0

 

1 1

0

0

1

0

1 0

1

0

0

1

 

1 0

1

0

0

1

 

 

36а.

 

 

 

 

 

36б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

0

1

1

1

 

0 0

1

1

0

1

0 1

1

1

0

1

 

0 1

1

0

0

1

1 1

1

1

0

0

 

1 1

0

1

0

1

1 0

0

0

1

0

 

1 0

1

0

0

1

 

 

37а.

 

 

 

 

 

37б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

0

1

1

0

 

0 0

1

0

1

1

0 1

0

0

1

1

 

0 1

0

0

1

1

1 1

0

0

0

1

 

1 1

1

0

1

0

1 0

1

0

0

0

 

1 0

0

0

1

0

 

 

38а.

 

 

 

 

 

38б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

1

1

0

 

0 0

1

0

0

0

0 1

1

1

0

0

 

0 1

1

0

1

0

1 1

1

1

1

1

 

1 1

1

1

0

1

1 0

1

1

1

0

 

1 0

1

1

1

1

 

39а.

 

 

 

 

 

39б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

0

0

0

 

0 0

1

1

0

1

0 1

1

0

1

1

 

0 1

1

0

0

1

1 1

1

0

1

1

 

1 1

0

1

1

0

1 0

0

1

1

0

 

1 0

1

0

0

1

40а.

 

 

 

 

 

40б.

 

 

 

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

 

x3 , x4

х1 , х2

 

0 0

 

0 1

 

1 1

 

1 0

0 0

1

1

1

1

 

0 0

1

1

0

1

0 1

0

1

1

0

 

0 1

1

1

0

0

1 1

0

0

0

0

 

1 1

1

1

1

0

1 0

1

0

1

1

 

1 0

1

0

0

1

 

Практическое занятие №2. Комбинаторика

  1. Номер варианта определить следующим образом N % 10 (где N — номер по порядку в журнале)

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

  2. У Димы есть пять шариков: красный, зеленый, желтый, синий и золотой. Сколькими способами он сможет украсить ими пять елок, если на каждую требуется надеть ровно один шарик?

  3. Монету бросают трижды. Сколько разных последовательностей орлов и решек можно при этом получить?

  4. Каждую клетку квадратной таблицы 2×2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

  5. Сколькими способами можно заполнить одну карточку в лотерее «Спортпрогноз»? (В этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча – победа одной из команд либо ничья; счет роли не играет).

  6. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

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

8.Ладья стоит на левом поле клетчатой полоски 1×30 и за ход может сдвинуться на любое количество клеток вправо. Сколькими способами она может добраться до крайнего правого поля?

9. Номер автомашины состоит из четырёх букв алфавита (используется 12 букв) и четырёх цифр. Сколько существует различных номеров автомашин?

10. Сколькими способами можно достать 5 разноцветных шаров из урны.

  1. Номер варианта определить следующим образом N % 10 (где N — номер по порядку в журнале)

1. Сколько существует трёхзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?

2. В пассажирском поезде 17 вагонов. Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник?

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

4. Сколькими способами можно построить замкнутую ломаную, вершинами которой являются вершины правильного шестиугольника (ломаная может быть самопересекающейся)?

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

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

7. Сколько существует ожерелий, составленных из 17 различных бусинок?

8. Числа 1, 2, 3, …, N записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число i, то где-то слева от него встретится хотя бы одно из чисел i + 1 и i – 1. Сколькими способами это можно сделать?

9. Сколькьми способами может выстроиться шеренга из 30 человек.

10. На складе находится 9 коробок. Сколькьми способами можно выстроить из них линию

  1. Номер варианта определить следующим образом N % 10 (где N — номер по порядку в журнале)

1. Сколькими способами можно разбить 15 человек на три команды по 5 человек в каждой?

2. В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем 12 открыток;

3. Сколькими способами 4 черных шара, 4 белых шара и 4 синих шара можно разложить в 6 различных ящиков?

4. При игре в преферанс каждому из трех игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре?

5. Сколькими способами можно выбрать 4 краски из имеющихся 7 различных?

6. Рота состоит из трех офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых?

7. Спортивный клуб насчитывает 30 членов, из которых надо выделить 4 человека для участия в забеге на 1000 метров. Сколькими способами это можно сделать?

8. Из класса, в котором учатся 28 человек, назначаются на дежурcтво в столовую 4 человека. Сколькими способами это можно сделать?

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

10. Человек имеет 6 друзей и в течение 5 дней приглашает к себе в гости каких-то троих из них так, чтобы компания ни разу не повторялась. Сколькими способами он может это сделать?

Практическое занятие №3. Комбинаторика. Закон Байеса

  1. Номер варианта определить следующим образом N % 10 (где N — номер по порядку в журнале)

1. Из 1000 ламп 380 принадлежат к 1 партии, 270 – ко второй партии, остальные к третьей. В первой партии 4% брака, во второй — 3%, в третьей – 6%. Наудачу выбирается одна лампа. Определить вероятность того, что выбранная лампа – бракованная.

2. Из 30 стрелков 12 попадает в цель с вероятностью 0,6, 8 — с вероятностью 0,5 и 10 – с вероятностью 0,7. Наудачу выбранный стрелок произвел выстрел, поразив цель. К какой из групп вероятнее всего принадлежал этот стрелок?

3. Сотрудники отдела маркетинга полагают, что в ближайшее время ожидается рост спроса на продукцию фирмы. Вероятность этого они оценивают в 80%. Консультационная фирма, занимающаяся прогнозом рыночной ситуации, подтвердила предположение о росте спроса. Положительные прогнозы консультационной фирмы сбываются с вероятностью 95%, а отрицательные – с вероятностью 99%. Какова вероятность того, что рост спроса действительно произойдет?

4. В группе спортсменов лыжников в 2 раза больше, чем бегунов, а бегунов в 3 раза больше, чем велосипедистов. Вероятность выполнить норму для лыжника 0,9, для бегуна 0,75, для велосипедиста — 0,8. Найти вероятность того, что спортсмен, выбранный наугад, выполнит норму.

5. В двух урнах находится соответственно 4 и 5 белых и 6 и 3 чёрных шаров. Из каждой урны наудачу извлекается один шар, а затем из этих двух наудачу берется один. Какова вероятность, что это будет белый шар?

6. В пирамиде 5 винтовок, три из которых снабжены оптическим прицелом. Вероятность того, что стрелок поразит мишень при выстреле из винтовки с оптическим прицелом, равна 0,95; для винтовки без оптического прицела эта вероятность равна 0,7. Найти вероятность того, что мишень будет поражена, если стрелок производит один выстрел из наудачу взятой винтовки.

7. Двигатель работает в трёх режимах: нормальном, форсированном и на холостом ходу. В режиме холостого хода вероятность его выхода из строя равна 0,05, при нормальном режиме работы – 0,1, а при форсированном – 0,7. 70% времени двигатель работает в нормальном режиме, а 20% – в форсированном. Какова вероятность выхода из строя двигателя во время работы?

8. На склад поступило 2 партии изделий: первая – 4000 штук, вторая – 6000 штук. Средний процент нестандартных изделий в первой партии составляет 20%, а во второй – 10%. Наудачу взятое со склада изделие оказалось стандартным. Найти вероятность того, что оно: а) из первой партии, б) из второй партии.

9. Три цеха завода производят однотипные детали, которые поступают на сборку в общий контейнер. Известно, что первый цех производит в 2 раза больше деталей, чем второй цех, и в 4 раза больше третьего цеха. В первом цехе брак составляет 12%, во втором – 8%, в третьем – 4%. Для контроля из контейнера берется одна деталь. Какова вероятность того, что она окажется бракованной? Какова вероятность того, что извлечённую бракованную деталь выпустил 3-й цех?

10. Имеются три одинаковые урны. В первой урне находятся 4 белых и 7 черных шаров, во второй – только белые и в третьей – только черные шары. Наудачу выбирается одна урна и из неё наугад извлекается шар. Какова вероятность того, что этот шар чёрный?

Лабораторное занятие №1. Представление деревьев в памяти

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

Класс должен поддерживать следующий функции:

— Добавление вершин

— Удаление вершин

— Поиск вершины

— Подсчёт высоты дерева

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

Лабораторное занятие №2. Алгоритмы обхода деревьев

Реализовать на классе, созданном в Лабораторной работе №1. Алгоритмы обхода указанные в лекции 10.4.

Лабораторное занятие №3. Алгоритмы построения кратчайших путей в дереве

Реализовать на классе, созданном в Лабораторной работе №1. Алгоритмы поиска кратчайшего пути указанные в лекции 10.5.

Лабораторное занятие №4. Алгоритмы построения остовных деревьев

Реализовать на классе, созданном в Лабораторной работе №1. Алгоритмы построения остовных деревьев указанные в лекции 10.6.

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

  1. Андерсон, Джеймс А. Дискретная математика и комбинаторика. — Пер. с англ. — М. : Издатель- Издательский дом «Вильямс», 2004. — 960 с.

  2. Акимов О.Е.Дискретная математика. Логика, группы, графы. — 2-е изд.- М., Лаборатория базовых знаний, 2001. — 376 с. — «Технический университет».

  3. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.

  4. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 288 стр. SBN 5-93972-076-5

  5. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд.- Лань, 2010. — 368 c. ISBN: 978-5-8114-1068-2

  6. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М., ГУ ВШЭ, 2006. — 300с. ISBN: 5-7598-0345-Х Серия: Учебники Высшей школы экономики

  7. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. — 3-е изд., стереотип. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. -744 с. (Сер. Математика в техническом университете; Вып. XIX).

  8. Бондаренко М.Ф. «Комп’ютерна дискретна математика»: підручник\ М. Ф. Бондаренко Н. В. Білоус А. Г. Руткас. — Харків: «Компанія СМІТ, 2004. — 480 с»

  9. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. Физматлит, 2000.—544с.

  10. Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Основание информатики. — М., Мир, 1998. — 704 с.

  11. Донской В.И. Дискретная математика. — Симферополь, Сонат, 2000. — 360 с.

  12. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. изд.3 — М.: Вузовская книга , 2000. — 200с.

  13. Зыков А.А. Основы теории графов.- М.: Вузовская книга, 2004. — 664 c. ISBN 5-9502-0057-8

  14. Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие/ Б. Н. Иванов. — М.: Лаборатория Базовых Знаний, 2003. — 288 с: ил. — серия «Технический университет»

  15. Кук Д., Бейз Г. Компьютерная математика. — М., Наука. Главная редакция физико-математической литературы, 1990. — 384 с.

  16. Липский В. Комбинаторика для программистов. — М.: Мир, 1988. — 200 с.

  17. Кузнецов О П.. Адельсон-Вельский Г. М. Дискретная математика дли инженера. — Изд.2, перераб. и доп— М.: 1988. — 408 с, ил.

  18. Maкоха А. Н., Сахнюк П. А., Червяков Н. И. Дискретная математика: Учеб. пособие. — М.: ФИЗМАТЛИТ, 2005. — 368 с.

  19. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. — М.: Логос, 2000. — 240 с.

  20. Нефедов В. Н., Осипова В. А. Курс дискретной математики: Учеб. пособие.—М.; Изд-во МАИ, 1992.—264 с: ил. ISBN 5-7035-0157-Х

  21. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. — СПб.: Питер, 2007. — 364 с: ил. — (Серия «Учебник для вузов»). ISBN 5-94723-741-5

  22. Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. — М.: Новое знание, 2005. — 288 с.

  23. Редькин Н.П. Дискретная математика. — СПб, Изд. Лань, 2003. — 96 с.

  24. Риордан Дж. Введение в комбинаторный анализ. — М.,Изд. иностр. лит. 1963. — 287 с.

  25. Романовский И. В. Дискретный анализ. — Невский Диалект; БХВ-Петербург, 2003. — 320 с.

  26. Соболева Т.С. Дискретная математика: учебник для студ. вузов / Т. С.Соболева, А. В.Чечкин; под ред. А. В.Чечкина. — М.: Издательский центр «Академия», 2006. — 256 с. — (Университетский учебник. Сер. Прикладная математика и информатика). ISBN 5-7695-2823-0

  27. Спирина М. С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. — М.: Издательский центр «Академия», 2004. — 368 с. ISBN 5-7695-1496-5

  28. С. В. Судоплатов, Е. В. Овчинникова Элементы дискретной математики. Учебник. — М.: Инфра-М, Новосибирск, Изд.НГТУ. — 2002. -280 с.

  29. Таран Т.А. Основы дискретной математики.— К.: Просвіта, 2003,— 288 с.

  30. Тишин В. В. Дискретная математика в примерах и задачах. — СПб.: БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература для вузов) — ISBN 978-5-9775-0232-0

  31. Фомичев В.М. Дискретная математика и криптология. Курс лекций. -М., Диалог-МИФИ, 2003. — 400 с.

  32. Хаггарти Р. Дискретная математика для программистов — 2-е изд. дополненное. — М., Техносфера, 2005. — 400с. ISBN 5-94836-016-4 — Мир программирования

  33. Эвнин А.Ю. Дискретная математика: Конспект лекций. Челябинск: ЮУрГУ 1998. — 176 с.

  34. Эвнин А.Ю. Задачник по дискретной математике. — 2-е изд.- Челябинск: Издательство ЮУрГУ, 2002. — 164 с.

  35. Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с.