Примеры задач, приводящих к необходимости подсчета числа размещений
1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?
2) Сколькими способами можно из 20 книг отобрать 12 и расставить их в ряд на полке?
В
задачах о размещениях полагается k < n.
В случае, если k = n,
то легко получить
Для
подсчета
используем тот же метод, что использовался
для подсчета Pn,
только здесь возьмем лишь k
ячеек. Первую ячейку можно заполнить n
способами, вторую, при заполненной
первой, можно заполнить n–1
способами. Таким образом, существует
п(п – 1)
вариантов заполнения первых двух ячеек.
Можно продолжать этот процесс до
заполнения последней k–й
ячейки. Эту ячейку при заполненных
первых k – 1
ячейках можно заполнить
n–(k–1)
(или n–k+1)
способами. Таким образом, все k
ячеек заполняются числом способов,
равным
A |
B |
C |
E |
F |
E & F |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
Отсюда
получаем:
Пример. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?
14 Перечислить все биекции одного множества в другое и проверить их
количество.
Если функция является и сюръективной, и инъективной, то такую функцию называют биективной или взаимно однозначной.
15 По словесному описанию логической функции построить ее выражение и
таблицу истинности.
Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции. При построении таблицы истинности необходимо учитывать порядок выполнения логических операций.
Порядок выполнения логических операций в сложном логическом выражении:
инверсия;
конъюнкция;
дизъюнкция;
импликация;
эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
Алгоритм построения таблиц истинности для сложных выражений:
Определить количество строк: количество строк = 2n + строка для заголовка, n - количество простых высказываний.
Определить количество столбцов: количество столбцов = количество переменных + количество логических операций;
определить количество переменных (простых выражений);
определить количество логических операций и последовательность их выполнения.
Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Пример: Составить таблицу истинности логического выражения:
D = ¬ А & (B C).
Решение:
Определить количество строк: на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 23 +1 = 9.
Определить количество столбцов:
простые выражения (переменные): А, В, С;
промежуточные результаты (логические операции): ¬ А - инверсия (обозначим через E); B C - операция дизъюнкции (обозначим через F); а также искомое окончательное значение арифметического выражения: D = ¬ А & (B C). т.е. D = E & F - это операция конъюнкции.
Заполнить столбцы с учетом таблиц истинности логических операций.
Построение логической функции по ее таблице истинности:
Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):
X |
Y |
Z |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Составить логическую функцию для заданной таблицы истинности.
Правила построения логической функции по ее таблице истинности:
Выделить в таблице истинности те строки, в которых значение функции равно 1.
Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.
Решение.
В первой и третьей строках таблицы истинности значение функции равно 1.
Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).
Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).
Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию: Z (X, Y) =(¬ X & ¬Y) V (X & ¬Y).
16 Для заданного логического тождества найти двойственное.
Двойственность.
Определение 1. Функцией, двойственной к функции алгебры логики f (x1, ..., xn), назы-
вается функция f ∗x , ...,x f x , ...,x . 1n1n
Утверждение. Для любой функции алгебры логики f (x1, ..., xn) справедливо равенство f (x1, ..., xn)=f** (x1, ..., xn).
∗Доказательство. f ∗∗f x1 , ..., xn f x1 , ..., xn f x1 , ..., xn , и утверждение доказано.
17 По таблице истинности построить СДНФ и СКНФ булевой функции.
В теории
дискретных функциональных систем
булевой функцией называют функцию типа
,
где
–
булево множество, а n – неотрицательное
целое число, которое называют арностью
или местностью функции. Элементы 0 (ноль)
и 1 (единица) стандартно интерпретируют
как истину и ложь, хотя в общем случае
их смысл может быть любым. Элементы
называют
булевыми векторами. В случае n = 0 булева
функция превращается в булеву константу.
Каждая
булева функция арности n
полностью определяется заданием своих
значений на своей области определения,
то есть на всех булевых векторах длины
n.
Число таких векторов равно 2n.
Поскольку на каждом векторе функция
может принимать значение либо 0, либо
1, количество всех n-арных булевых функций
равно
.
То, что каждая булева функция задаётся
конечным массивом данных, позволяет
представлять их в виде таблиц. Такие
таблицы носят название таблиц истинности
и в общем случае имеют вид:
x1 |
x2 |
… |
xn |
f(x1, x2,…, x1) |
0 |
0 |
… |
0 |
f (0,0,…, 0) |
1 |
0 |
… |
0 |
f (1,0,…, 0) |
0 |
1 |
… |
0 |
f (0,1,…, 0) |
1 |
1 |
… |
0 |
f (1,1,…, 0) |
|
|
|
|
|
0 |
1 |
… |
1 |
f (0,1,…, 1) |
1 |
1 |
… |
1 |
f (1,1,…, 1) |
Пример. По данной таблице истинности построить СДНФ. Решение.
Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные X,Y,Z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные X,Y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная Z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна ¬X¬YZ. Очевидно, что конъюнкция ¬X¬Y¬Z равна 1 только на наборе (0,0,0), а ¬X¬YZ равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция ¬X¬Y¬Z v ¬X¬YZ равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д. Т.е. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так, для нашего примера, имеем ¬X¬YZ v ¬XY¬Z v X¬YZ v XY¬Z v XYZ Задача. По данной таблице истинности построить СКНФ. Конституента_0 для набора нулей и единиц (которые принимают переменные X,Y,Z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание. Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем: f=(XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ) Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции ¬f , а затем использовать f=¬(¬f) и законы де Моргана. Построим СКНФ для нашего примера на основании замечания. 1. Строим СДНФ для отрицания. ¬X¬Y¬Z v ¬XYZ v X¬Y¬Z 2. Используем законы де Моргана f=¬(¬f)=¬(¬X¬Y¬Z v ¬XYZ v X¬Y¬Z)=¬(¬X¬Y¬Z)&¬(¬XYZ)&¬(X¬Y¬Z)= =(XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ) Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм. 1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ. 2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная Y, то этот конъюнкт заменяем на эквивалентную формулу K&(Yv¬Y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (Yv¬Y). 3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ. Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную Y добавляем формулу вида Y¬Y, т.е. этот дизъюнкт заменяем на эквивалентную формулу D v Y¬Y и, применяя 2-й закон дистрибутивности. Пример. Построить СДНФ для функции f при помощи эквивалентных преобразований. f=XvYZ=X(Yv¬Y)(Zv¬Z)vYZ(Xv¬X)=XYZvXY¬ZvX¬YZvX¬Y¬ZvYZXvYZ¬X= =XYZvXY¬ZvX¬YZvX¬Y¬ZvYZ¬X |
Алгоритм получения СКНФ:
1. Получить таблицу истинности для определенного количества переменных;
2. Заполнить значения функции для каждого из наборов таблицы истинности;
3. Отметить те строки таблицы истинности, на которых функция приняла значение 0;
4. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму переменную, если =1, то ее отрицание;
5. Все полученные дизъюнкции связать в конъюнкцию;
18 Методом Карно получить минимальную дизъюнктную (конъюнктную) форму
функции.
У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников. Для краткости обозначим родственников Коли через буквы: мама — х1 папа — х2 дедушка — х3 бабушка — х4 Условимся обозначать согласие родственников единицей, несогласие - нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0. Составим таблицу истинности:
Перерисуем
таблицу истинности в 2-х мерный
вид:
Переставим
в ней строки и столбцы в соответствии
с кодом Грея. Получили Карту Карно:
Заполним
её значениями из таблицы
истинности:
Минимизируем
в соответствии с правилами:
1. Все области содержат 2^n клеток;
2. Так как Карта Карно на четыре переменные, оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
3. Так как Карта Карно на четыре переменные, все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных);
4. Области S3, S4, S5, S6 максимально большие;
5. Все области пересекаются (необязательное условие);
6. В данном случае рациональный вариант только один.
Теперь
по полученной минимальной ДНФ можно
построить логическую
схему:
Из-за отсутствия в наличии шести-входового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы(D7, D8). Составим мин. КНФ:
