24. Сочетания без повторений. Сочетания с повторениями.

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

Число сочетаний без повторений (n различных элементов, взятых по m) вычисляется по формуле:

Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

Решение.

1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ

По формуле получаем:   наборов.

2. Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле получаем: наборов.

25. Понятие высказывания. Операции над высказываниями

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

Отрицание (инверсия) — высказывание истинно, когда А ложно и ложно, когда А истинно

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

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

Импликация — ложна, если из истины следует ложь и истинна во всех остальных случаях.

Эквиваленция — истинна, если истинностные значения обоих высказываний совпадают и ложна в противных случаях.

26. Определенные и переменные высказывания. Таблицы истинности, равносильность, тавтологии

Определенные высказывания — высказывания, про которых можно конкретно сказать, истинны они или ложны. Принимают постоянные значения 1 или 0.

Если X, Y, Z – переменные высказывания, то, применяя к ним

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

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

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

Равносильные формулы — могут быть, если они имеют одну и ту же таблицу истинности. Если все значения в таблице истинности равны 1, то формула называется тавтологией.

27. Определение булевой функции. Элементарные булевы функции одной и двух переменных

Булевой функцией (переключательной) — называется такая функция, которая принимает два значения 0 и 1 и зависит от переменных, каждая из которых может принимать значения 1 и 0

Булевы функции одной переменной

f1, f16 – константы 0 и 1.

f4 = х1, f11 =¬х2, f6 = х2, f13 =¬х1

f2 = х1 ٨ х2; f8 = х1 ٧ х2

f15 – штрих Шеффера, х1 | х2.

f10 – эквивалентность, х1 ∼ х2.

f5 = х2 → х1

f7 = х1 ⊕ х2 или х1 + х2 (mod 2) – сложение по модулю два ; f12, f14 – импликация, х2 → х1 и х1 → х2

f9 – стрелка Пирса, х1 ↓ х2 (другое название – функция Вебба).

f3, f5 – функции запрета х1 и х2 соответственно. f3 = х1 → х2