Брянский торгово-экономический
техникум
Реферат по
теме:
Элементы Комбинаторики
Предмет: теория вероятности
Работу выполнил: студент группы П-24,
Симонцев Александр
Преподаватель: Курдикова Елена Николаевна
Оглавление
Комбинаторика
раздел математики, в котором
изучаются задачи выбора элементов
из заданного множества и расположения
их в группы по заданным
правилам, в частности задачи
о подсчете числа комбинаций (выборок),
получаемых их элементов заданного
множества. В каждой из них
требуется подсчитать число возможных
вариантов осуществления некоторого
действия, ответить на вопрос: «Сколькими
способами?» Многие комбинаторные
задачи могут быть решены с
помощью следующих 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 элементов,
причем один и тот же элемент может входить
в комбинацию более одного раза.
Обозначается – Č и вычисляется по форм:
Бином
Ньютона
Бином Ньютона – это формула, представляющая
выражение
в виде многочлена.
Она имеет вид:
Её можно записать иначе:
, где
- число сочетаний из n элементов по k,
Известные формулы сокращенного умножения:
квадрат суммы, квадрат разности, куб суммы,
куб разности являются частными случаями
бинома Ньютона.
Когда степень бинома невелика, коэффициенты
многочлена могут быть получены с помощью
треугольника Паскаля.
Любой элемент треугольника паскаля, расположена
в n-ой строке на k-ом месте выражает
,
Где отчет n ведется от 1, а отчет k ведется
от 0.
Пример: Представить в виде многочлена
Решение:
Булевы
функции. Определение. Примеры
Алгебра логики, выстроенная в XIX веке, долго
существовала как абстрактная, хотя и
очень красивая наука. Но в середине XX века
оказалось, что она имеет конкретное и
очень важное применение в современной
жизни. Булева алгебра в настоящее время
служит основой для описания логики работы
аппаратных и программных средств ЭВМ.
Она использует логические переменные,
которые принимают лишь два значения 0
и 1. Аналогично и ЭВМ использует лишь сигналы
0 и 1, воспринимая их как логические переменные.
Рассмотрим множество В = {0;1}.
Тогда В2 = {(0;0),(0;1),(1;0),(1;1). Снимем разделительный
к внутри каждой пары и уберём скобки.
Тогда В2 = {00, 01,10,11}. Аналогично В3 = В В2 ={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. Реализация булевых функций формулами.
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
,
- отрицание
- конъюнкция (логическое умножение)
- дизъюнкция
- импликация
- отрицание импликации
- эквиваленция
- сумма по модулю 2
- стрелка Пирса
│
- штрих Шеффера
Порядок действий в формулах определяется
с помощью скобок. Чтобы уменьшить их количество,
на множестве функций вводится порядок
действий.
Самой старшей считается «отрицание»
Затем – «конъюнкция», «штрих Шеффера»,
«стрелка Пирса»
Затем – «дизъюнкция»
Затем – «импликация»
На самом низком уровне – эквиваленция
и сумма по модулю 2.
Булевы функции называют равными, если
совпадают их таблицы истинности. Функции,
соответствующие равным формулам, называются
равносильными. Следует отметить, что
одна и та же функция может быть представлена
разными формулами.
Итак, стрелка Пирса равна анти дизъюнкции
, штрих Шеффера равен анти конъюнкции.
Любую булеву функцию можно представить
с помощью отрицания, конъюнкции и дизъюнкции.
Совершенная
конъюнктивная нормальная форма
Представление
булевой функции
в виде
конъюнкции несовпадающих элементарных
дизъюнкций называется конъюнктивной
нормальной формой (КНФ) этой функции.
Пример
Это конъюнкция трех несовпадающих элементарных
дизъюнкций.
Чтобы из неполной элементарной дизъюнкции
получить полную необходимо неполную
элемент дизъюнкцию дополнить 0, а 0 представить
в виде конъюнкции недостающей переменной
и её отрицания. После этого необходимо
применить дистрибутивный закон.
Любую булеву функцию можно представить
в виде КНФ, причем любая булева функция
может быть представлена множеством различных
КНФ, равносильных между собой.
Если каждая входящая в КНФ элементарная
дизъюнкция является полной относительно
набора
, то КНФ называется совершенно конъюнктивной
нормальной формой (СКНФ)
Пример:
Любую булеву функцию
, не равную тождественной единице,
можно представить в виде СКНФ.
Получить СКНФ можно преобразовывая формулы,
а можно по таблице истинности.
Совершенная
дизъюнктивная нормальная форма
Представление булевой функции
в виде дизъюнкции несовпадающих элементарных
конъюнкций называется дизъюнктивной
нормальной формой (ДНФ) этой функции.
Пример
Одна третья конъюнкции является полной
элементарной.
Чтобы из неполной элементарной конъюнкции
получить полную необходимо неполную
элемент конъюнкцию логически умножить
на 1, а 1 представить в виде дизъюнкции
недостающей переменной и её отрицания.
После этого необходимо применить дистрибутивный
закон.
Любую булеву функцию можно представить
в виде ДНФ, причем любая булева функция
может быть представлена множеством различных
ДНФ, равносильных между собой.
Если каждая входящая в ДНФ элементарная
конъюнкция является полной относительно
набора
, то ДНФ называется совершенно дизъюнктивной
нормальной формой (СДНФ)
Пример:
Получить СДНФ можно преобразовывая формулы,
а можно по таблице истинности.
Переключательные
функции Способы задания
Переключательные функции широко применяются
на практике в исследовании и разработке
вычислительной техники, дискретных автоматов,
релейно-контактных схем. Они используются
в теории преобразования, кодирования
и передачи информации.
Основы переключения функций заложил
англ. метем. Дж. Буль в 19 веке.
Пусть предметом изучения является поведение
сложных систем, а не их устройство. В этом
случае интересуют лишь входные и выходные
сигналы, а не процессы, происходящие внутри
устройства.
Отсутствие сигнала как на входе, так и
на выходе будет сигнализировать 0, наличие
– 1.
Каждому кортежу
, состоящему из 0 и 1, соответствует
одно из 2х значений 0 или 1. По сути, имеем
булеву функцию
. В данном случае её называют переключательной
функцией.
Переключательную функцию можно задать
аналитически, геометрически. А также
ее можно задать матричным способом и
с помощью логической схемой системы.
Рассмотрим этот метод подробнее. Примерами
логических схем является обыкновенные
микросхемы, которые в большом кол-ве присутствуют
в электробытовых приборах и компьютерах..
Переключательные
функции от 2-х и п переменных
Переключательные функции от 2х переменных
– это булевы функции двух переменных.
Определение
и примеры функционально полных базисов
Система F переключательных функций
называется функционально полной,
если любую переключательную функцию
φ можно выразить с помощью суперпозиции
некоторого набора переключательных функций
системы F.
Очевидно, что если F – функционально полная
система, то добавление любого числа переключения
функций не изменит статуса вновь полученной
системы, т.е. она останется функцией полной.
Функционально полная система функции
называется функциональным базисом, если
она минимальна, т.е. удаление хотя бы одной
из функций
приводит к тому, что система теряет
свойство полноты.
Система из 3х функций: дизъюнкции, конъюнкции
и отрицания, является полной, т.к. через
них можно выразить любые функции алгебры
логики.
Заметим, что в силу законов де Моргана:
Дизъюнкцию можно представить через конъюнкцию
и отрицание. Следовательно, функционально
полной является система функций
и
(конъюнкция и отрицание).
Также конъюнкцию можно представить через
дизъюнкцию и отрицание. Следовательно,
функционально полной является система
функций
и
(дизъюнкция и отрицание).
Итак, примеры функциональных систем:
Системы F3 и F4 являются базисами, т.к. удаление
из них любой функции приводит к системе,
не являющейся полной.
Специальные
разложения переключательных функций
Любую перекл функцию кроме тожд. нуля
можно представить в виде СДНФ. А в свою
очередь, любую функцию, представленную
в виде СДНФ, можно представить с помощью
суммы по модулю 2, конъюнкции и константы
1. Т.е. любую перекл. функцию можно представить
с помощью функций: сумма по модулю 2, конъюнкция
и константы 1. Отсюда следует, что система
функций
явл. полной.
Более того эта система является еще и
базисом.
Базис
называется системой Жегалкина.
Теорема. Каждая перекл. функция единственным
образом допускает представление в виде
полинома Жегалкина.
Пример:
. Представим эту функцию в виде полинома
Жегалкина.
Решение
Другим, более распространенным способом
нахождения полинома Жегалкина явл. метод
неопределенных коэффициентов, который
основан на выше указанной теореме
Классы
Поста Теорема о функциональной полноте
Под классом функций будем понимать множество
функций, замкнутых относительно операций
взятия суперпозиции.
Существуют 5 классов перекл. функций.
Это классы Поста (Пост – Америк
логик 20 века.