Элементы комбинаторики. Правила умножения и сложения

1. Элементы комбинаторики.  Правила умножения и сложения.

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

Правило умножения.

Если из нек  множ первый объект (элемент х) можно выбрать n1 способами и после каждого такого выбора второй объект (элем у) можно выбр n2 способами, то оба объекта (х и у) в указ порядке можно выбрать n1*n2 способами.

Это правило  распр-ся на случай трех и более объектов.

Пример: сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если: а) числа не повт; б) числа могут повтор.

Решение: а) 1ую цифру  выбираем 5мя способами, 2ую – 4мя, 3 – 3мя 5*4*3=60 способов

 б) 5*5*5=125 сособов

Правило сложения

Если некот  объект х можно выбр n1 способами, а объект у можно выбр n2 способами, причем первые и вторые выборы таковы, что они взаимно искл друг друга и не могут быть получены одновременно, то объект хUу (х или у) можно выбр n1+n2 способами.

Пример: Четыре города M,N,P,K соединены дорогами так, что из M в N ведут 5дорог, из N в K – 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги.

Сколькими способами  можно проехать из М в К?

Решение: Из М  в К через N ведут 5*6=30 дорог, Из М в К через P ведут 4*3=12 дорог

Из М в К  ведут 30+12=42 дороги. 

2.   Размещения, перестановки, сочетания.

Размещениями из n-элементов по m элементов в каждом называются такие комбинации, из которых каждая содержит m элементов из данных n элементов, и которые отличаются друг от друга порядком их следования, либо самими элементами.

Если элементы комбинации не повторяются.

Размещениями из n-элементов по m элементов с повторениями называются такие комбинации, в которых каждая содержит m элементов из данных n элементов, записанных в каком нибудь порядке, причем один и тот же элемент может входить в комбинацию более одного раза.

Размещения с  повторениями обозначаются Ã и вычисляются по формуле:

Примеры в 1ом вопросе!

Перестановками из n-элементов называются такие комбинации, которые отличаются лишь порядком следования этих элементов.

Пример: Имеется 5 равных геом фигур: 3 желтых и 2 белых круга. Сколько различных узоров можно составить из этих кругов, располагая их в ряд?

Решение: Желтые круги будут повт 2! раз

Белые - 3! раз

Число разл узоров будет равно 5!/2!*3!=10

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

Где

Сочетаниями из n-элементов по m элементов в каждом называются такие комбинации, каждая из которых состоит из m элементов, выбранных из данных n элементов, и которые отличаются друг от друга хотя бы одним элементом.

Пример: Сколькими  способами можно выбрать 3 представителей учебной группы в студ совет, если в группе 25чел.

Сочетаниями из n-элементов по m с повторениями назыв такие комбинации, каждая из которых состоит из m элементов из данных n элементов, причем один и тот же элемент может входить в комбинацию более одного раза.

Обозначается  – Č и вычисл по форм:

 

3.   Бином  Ньютона.

Бином Ньютона  – это формула, представляющая выражение  в виде многочлена.

Она имеет вид:

Её можно записать иначе:

, где  - число сочетаний из n элементов по k,

Известные формулы  сокращенного умножения: квадрат суммы, квадрат разности, куб суммы, куб  разности являются частными случаями бинома Ньютона.

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

Любой элемент  треугольника паскаля, распол в n-ой строке на k-ом месте выражает ,

Где отчет n ведется от 1, а отчет k ведется от 0.

Пример: Представить в виде многочлена

Решение:  

4. Булевы  функции. Определение. Примеры.

Алгебра логики, выстроенная в XIX веке, долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Она использует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично и ЭВМ использует лишь сигналы 0 и 1, воспринимая их как логические переменные.

Рассмотрим множество  В = {0;1}.

Тогда В² = {(0;0),(0;1),(1;0),(1;1). Снимем разделительный к внутри каждой пары и уберём скобки. Тогда В² = {00, 01,10,11}. Аналогично В³ = Вх В² ={000,001,010,011,100,101,110,111} и т. д.,

Каждому элементу множества Вⁿ поставим в соответствие единственный элемент множества В - {0; 1}. Полученное соответствие наз булевой функцией. Элементы множества Вⁿ являются значениями аргумента булевой функции. Они представляют собой наборы, состоящие из нулей и единиц, и называются кортежами. Длиной кортежа называется число цифр, образующих кортеж. Множество Вⁿ  - область определения функции

Множества значений булевой функции, вообще говоря это  значение функции В = {0;1}.

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

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

Область определения  D(f) булевой функции n = 1 это совокупность двух точек 0 и 1 числовой прямой, т.е. одномерного куба

Если    п = 2, то     D(f) = {00,01,10,11}- это множество вершин квадрата, т. е. двухмерного куба

Если    п = 3,   то    D(f) = {000,001,010,01 1,100,101,110,111}   

множество вершин трёхмерного куба в декартовой системе координат.

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

Если n=1, то число простейших булевых функций равно 4, если n=2, то их 16, если n=3, то их 256

Если n=1, то существует 4 простейших булевых функций:

- константа 0(тождественный 0)

- константа 1(тождественная 1)

- тождественная функция

- отрицание 

5.   Реализация  булевых функций формулами.

 

, - отрицание

- конъюнкция (логическое умножение)

- дизъюнкция

- импликация

- отрицание импликации

- эквиваленция

 - сумма по модулю 2

- стрелка Пирса

‌‌‌ ‌‌‌‌‌‌│ - штрих Шеффера

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

Самой старшей  считается «отрицание»

Затем – «конъюнкция», «штрих Шеффера», «стрелка Пирса»

Затем – «дизъюнкция»

Затем – «импликация»

На самом низком уровне – эквиваленция и сумма  по модулю 2.

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

Итак, стрелка  Пирса равна антидизъюнкции, штрих  Шеффера равен антиконъюнкции.

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

6.   Совершенная  конъюнктивная нормальная форма.

Представление булевой функции в виде конъюнкции несовпадающих элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) этой функции.

Пример 

Это конъюнкция трех несовпадающих элементарных дизъюнкций.

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

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

Если каждая входящая в КНФ элементарная дизъюнкция является полной относительно набора , то КНФ называется совершенно конъюнктивной нормальной формой (СКНФ)

Пример:

Любую булеву функцию , не равную тождественной единице, можно представить в виде СКНФ.

Получить СКНФ можно преобразовывая формулы, а  можно по таблице истинности.  

7.   Совершенная  дизъюнктивная нормальная форма.

Представление булевой функции  в виде дизъюнкции несовпадающих элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Пример 

Одна третья конъюнкции является полной элементарной.

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

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

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора , то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

Получить СДНФ можно преобразовывая формулы, а можно по таблице истинности.  
 

8.   Переключательные функции. Способы задания.

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

Основы перекл функций заложил англ матем Дж.Буль в 19 веке.

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

Отсутствие сигнала как на входе, так и на выходе будет сигнализировать 0, наличие – 1.

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

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

Рассмотрим этот метод подробнее. Примерами логических схем явл обыкновенные микросхемы, которые в большом кол-ве присутствуют в электробытовых приборах и компьютерах..

НЕ ПОЛНОСТЬЮ!!!!

 

9.   Переключательные  функции от 2-х и п переменных.

Переключательные  функции от 2х переменных – это  булевы функции двух переменных. 

10. Определение и примеры функционально полных базисов.

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

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

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

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

Заметим, что  в силу законов де Моргана:

Дизъюнкцию можно  представить через конъюнкцию и  отрицание. Следовательно, функционально  полной является система функций  и (конъюнкция и отрицание).

Также конъюнкцию можно представить через дизъюнкцию и отрицание. Следовательно, функционально полной является система функций и (дизъюнкция и отрицание).

Итак, примеры функциональных систем:

Системы F3 и F4 являются базисами, т.к. удаление из них любой функции приводит к системе, не являющейся полной. 
 

11. Специальные  разложения переключательных функций.

Любую перекл функцию  кроме тожд нуля можно представить  в виде СДНФ. А в свою очередь,  любую функцию, представленную в  виде СДНФ, можно представить с  помощью суммы по модулю 2, конъюнкции и константы 1. Т.е. любую перекл функцию можно представить с помощью функций: сумма по модулю 2, конъюнкция и константы 1. Отсюда следует, что система функций явл полной.

Более того эта  система является еще и базисом.

Базис называется системой Жегалкина.

Теорема.Каждая перекл функция единственным образом допускает представление в виде полинома Жегалкина.

Пример: . Представим эту функцию в виде полинома Жегалкина.

Решение

 

Другим, более  распространенным способом нахождения полинома Жегалкина явл метод  неопределенных коэффициентов, который  основан на выше указанной теореме 
 

12. Классы Поста.  Теорема о функциональной полноте.

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

Существуют 5 классов  перекл функций. Это классы Поста (Пост – Америк логик 20 века.

1. Класс линейных функций

Перекл функция  назыв линейной, если она представима  полиномом Жегалкина первой степени:

Число линейных функций рано например при n=2 число линейных функций равно 8:

2. Класс функций, сохраняющих 0

Если перекл функция на кортеже 00…0 равна нулю, то говорят, что функция сохран нуль

Т.о. функция  принадлежит классу функций, сохраняющих 0, если

Для 2х переменных таких функций 8.

3. Класс функций, сохраняющих 1

Если перекл функция на кортеже 11…1 равна 1, то говорят, что функция сохран единицу

Т.о. функция  принадлежит классу функций, сохраняющих 1, если

Для 2х переменных таких функций 8

4. Класс монотонных функций

- монотонная функция

Таких функций 6

5. Класс самодвойственных функций.

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

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

Теорема Поста  о функциональной полноте. Для того чтобы система булевых функций  была полной необходимо и достаточно, чтобы она содержала: 
-хотя бы одну функцию, не сохраняющую 0

-хотя бы одну  функцию, не сохраняющую 1

-хотя бы одну  функцию, не явл линейной

-хотя бы одну  функцию, не явл монотонной

-хотя бы одну  функцию, не явл самодвойственной.

Каждый базис  содержит не более 4х булевых функций. 

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

14. Способы построения  минимальных ДНФ.

Минимизация ДНФ  включает следующие этапы:

1. Получение простых импликант и сокращенной ДНФ
2. Получение тупиковой ДНФ
3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем  применять один из след методов: Метод  Квайна, геометрический, карты Карно

Метод Квайна

В его основе лежат следующие равносильности:

1. Полного склеивания 

2. Поглощения 

3. Не полного  склеивания 

Если в СДНФ провести все операции неполного  склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ. 

Геометрический  метод

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

Суть метода: 1) для функции n переменных отмечаются вершины куба, соответств кортежам, на которых функция принимает значение 1.

2) проводят склеивание  – отмечают ребра, содерж 2 отмеч вершины.

3) проводят поглощение  – отмечают грани, содерж все  4 склеенные вершины.

Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер. 
 

Карты Карно

Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4

Переменные кортежа  разбиваются на 2 части. Первая часть  является кодом столбца, вторах –  строк. Таким образом, карты Карно  неявно задают сами кортежи.

Например:  

 

Процесс минимизации  СДНФ представляет собой склеивание кодов кортежей для каждого сплошного  участка причем колво единиц на таком  сплошном участке должно быть степенью числа 2. 
 

15. Понятие графа.  Виды графов. Изоморфизм.

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

Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам , которое оно соединяет.

Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным.