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

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 представить в виде конъюнкции недостающей переменной и её отрицания. После этого необходимо применить дистрибутивный закон.

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

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