12. Правило суммы:

Пусть элемент можно выбрать способами, а элемент - m способами, причем, если любой способ выбора отличается от любого способа выбора (независимо) то выбор «» можно сделать К+m способами.

(в группе 16 юношей и 14 девушек, то преподаватель может вызвать к доске 1 учащегося 14+16=30 способами.)

13. Правило произведения комбинаторики.

Если элемент можно выбрать способами, а элемент способами, то пару ()можно выбрать _m способами(всего 26 человек, м-21, ж -5, то 21*5=105 способов.)

14. Размещение – упорядоченное подмножество m элементов, составленное из всего множества, содержащего n элементов Пр-р: Сколькими способами можно распределить 3 путевки между 4мя желающими?

Размещение с повторением – случай, когда размещение из n элемениов по m элементов может содержать любой элемент сколько угодно раз от 1 до m включительно или не содержать его совсем. Пр-р: сколько различных двоичных чисел длинной 6 можно записать с помощью цифр 0 и 1?

15. Перестановка – упорядоченные множества состоящие из n различных элементов

Пр-р: сколько можно составить все возможных комбинаций из букв АВСД?

Перестановка с повторениями – если множество имеет повторяющиеся элементы

Пр-р: в слове математика: а-3, м-2, т-2, е-1, и-1, к-1

16. Сочетание из n элементов по m наз неупорядоченное подмножество, состоящее из m элементов, взятых из множества, состоящего из n элементов Пр-р: сколькими способами могут взойти 3 зерна пшеницы если посажено 7 зерен?

Сочетания с повторениями – каждое сочетание с повторением из n элементов по m элементов может содержать не только из различных элементов, но и из m каких угодно и как угодно повторяющихся элементов или не содержать совсем. Пр-р: студент покупает 4 тет. В магазине выставлены тет 8ми видов. Сколько сущ различных способов купить 4 тет?

17. Рассмотрим множество E_n = {1,2,3…n}, каждый элемент в котором представлен только 1 раз, тогда взаимоодназначное отображение τ_n: E_n⇒ E_n множества E_n на себя называется подстановкой степени n. Отношение E_n⇒ E_n бинарное, поэтому подстановки принято записывать в виде двухрядной матрицы, в первой строке которой записаны прообразы, а во второй - их образы. Подстановку вида

τ = (1,2,3,…,n) = е называют тождественной. ∀х ∈ E_n , е(х)=х Такую подстановку называют единичной.

Натуральной степенью подстановки называется подстановка τⁿ=τ*…*τ, т.е. произведение n-функций, каждая из которых есть τ.

18. Если прообразы (аргументы) расположены в порядке возрастания (при i<j, x_i<x_j), запись подстановки называется канонической. Пусть заданы две подстановки τ₁ и τ₂, причем E_n^τ1⇒ E_n^τ2⇒E_n”. Тогда произведение отображений τ₁ * τ₂: также является подстановкой и называется произведением подстановок τ₁ и τ₂ и записывается τ = τ₂ * τ1

19. 1) Умножение выполняется только для подстановок с одинаковой степенью.

2) Для умножения подстановок не выполняется переместительный закон.

3) Для умножения подстановок выполняется сочетательный закон.

4) Подстановка не изменится, если ее умножить на тождественную (единичную).

5) Поскольку любая подстановка τ – биекция, для нее существует обратная функция, тоже являющаяся подстановкой: можно указать обратную τ^-1∈ E_n, т.е. такую, что τ^-1* τ = е

6) Обратная подстановка единственна.

7) Подстановка, обратная единичной, также является тождественной e^-1=е

8) Для того, чтобы перемножить степени подстановки τ, нужно подстановку возвести в степень, равную сумме показателей множителей, т.е.: τ^m * τⁿ = τ^m+n, ∀m,n∈Z

20. Назовем порядком подстановки наименьшее натуральное число λ, такое, что τ^λ=е, λ(τ)=min{|τ^p-e|} Подстановка, обратная произведению подстановок τ₁ и τ₂ равна произведению обратных подстановок, взятых в обратном порядке.

Инверсия – перестановка (рокировка) двух соседних значений в нижнем ряду канонической записи. Следует напомнить, что при этом подстановка меняется. Иногда употребляется запись sqh(Q), Если Е(0) = 1, то подстановка чётная, Если Е(0)=-1, то подстановка нечетная. Транспозиция.

21. Суждение – форма мышления, в которой что-либо утверждается или отрицается о существовании предмета, связях между предметом и его свойствами или об отношениях между предметами. (Идет дождь)

Высказывание – всякое суждение, утверждающее что-либо о чем-либо, если можно сказать, истинно оно или ложно в данных условиях места и времени. (В Сургуте сейчас светит солнце)

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

Утвердительные предложения, не содержащие (содержащие) логические связки, называют элементарными (составными) высказываниями.

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

Дизъюнкция (нестрогая или соединительная) – высказывание А∨В, которое истинно, когда истинно хотя бы 1 высказывание. (или)

Конъюнкция – высказывание А&В, которое истинно тогда, когда истинны оба высказывания. А∧В, А&В (и)

Строгая дизъюнкция – высказывание, которое истинно тогда и только тогда, когда истинно только 1 из высказываний (либо)

Импликация – высказывание А→В, которое ложно тогда и только тогда, когда из истины следует ложь (если, то)

Эквиваленция – высказывание А↔В, которое истинно тогда и только тогда, когда либо истинны, либо ложны одновременно оба высказывания (тогда и только тогда)

23. Любые простые и сложные высказывания, полученные из элементарных высказываний с помощью конечного числа логических операций - Формула алгебры логики.

Равносильные, если они принимают одинаковые логические значения, при любом наборе значений элементарных высказываний, входящих в них.(=).

Тавтология(тождественно-истинная), если она принимает значение «истина» при всех значениях переменных, входящих в нее.

Тождественно ложные – если она принимает значение 0 при всех значениях переменных, входящих в нее.

24. Переместительный закон: аb=ba

Сочетательный: a∨(b∨c)=(a∨b)∨c

Распределительный: a(b∨c)=ab∨ac

Правила идемпотентности: a∨a=a; a*a=a

Законы Де Моргана: ¬( a∨b)= ¬a*¬b; ¬(ab) = ¬a∨¬b

Правила операций с константами: a∨0=a; a∨1=1; a*0=0; a*1=1

Законы поглощения: a∨ab=a; a∨(¬ab)=a∨b; a(a∨b)=a; a(¬a∨b)=ab

Законы отрицания: a∨¬a=1; a*¬a=0

Законы склеивания: ab∨a¬b=a; (a∨b)*(a∨¬b)=a

Снятие операции: ¬¬a= ¬a; a→b= ¬a∨b; a↔b=ab∨¬a¬b; a>>b=¬ab∨a¬b

25. Булевой алгеброй называется непустое множество A с двумя бинарными операциями конъюнкция, дизъюнкция, с отрицанием и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

ассоциативность

коммутативность

законы поглощения

дистрибутивность

дополнительность

Булевой функцией от n аргументов называется функция f из n-ой степени множества {0,1} в множество { 0, 1 }. Bn → B, где B = {0,1}.

Областью определения булевой функции являются картежи длиной n и состоящие из символов 0 и 1.

F(0,1,1,0)=0

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

F1-тождественный ноль f1(1)=0, f1(0)=0

F2-тождественная функция f2(0)=0, f2(1)=1

F3-инверсия f3(0)=1, f3(1)=0

F4-тождественная еденица f4(0)=1, f4(1)=1

Булева функция двух переменных.

x	y	0	x & y	x→y	x	x←y	y	x⊕y	x ∨ y	x↓y	x ≡ y	Не y	x←y	Не x	x→y	x|y	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

1. тождественный ноль

2. НЕ

3. инверсия обратной импликации

4. отрицание (негация, инверсия) первого операнда

5. инверсия прямой импликации

6. отрицание (негация, инверсия) второго операнда

7. сложение по модулю 2

8. штрих Ше́ффера

9. конъюнкция

10. эквивалентность

11. второй операнд

12. прямая (материальная) импликация (от первого аргумента ко второму)

13. первый операнд

14. обратная импликация

15. дизъюнкция

16. тождественная единица

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

27. Булевых функции двух неизвестных. Примеры.

28. Используя законы алгебры логики, можно заменить громоздкие булевы функции им равносильными, но более простыми – Минимизация. Минимизировать булевы функции надо, приводя их к Нормальной форме.

29. Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделённых отрицаниями конъюнкции (дизъюнкции).

Конъюнктивной (дизъюнктивной) нормальной формой называется конъюнкция (дизъюнкция) конечного числа элементарных дизъюнкций (конъюнкций).

30. Начальная форма называется совершенной, если в каждой её элементарной дизъюнкции (конъюнкции) представлены все переменные, входящие в данную функцию (либо сами, либо с отрицаниями).

На СДНФ накладываются следующие требования:

-формула не является тождественно-ложной;

-формула приведена к одному из видов ДНФ;

-из формулы удалены элементарные конъюнкции, включающие одновременно переменную и её отрицание, согласно закону инверсии.;

-из формулы удалены одинаковые элементарные конъюнкции, кроме одной, согласно правилу идемпотентности;

-каждая элементарная конъюнкция в ДНФ включает все логические переменные, входящие в эту формулу

1 x а = а а(отрицание) v а = 1

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

-формула не является тождественно-ложной;

-формула приведена к одному из видов КНФ;

-из формул удалены одинаковые элементарные дизъюнкции кроме одной;

-каждая элементарная дизъюнкция в КНФ включает все логические переменные, входящие в эту формулу

а v 0 = a а x а(отрицание) = 0

31. Заменив в СДНФ ¬x_i=1⊕x_i и используя распределительный закон для конъюнкции относительно сложения суммы по модулю два имеем:

(1⊕x_i)( 1⊕x_j) = 1⊕x_i⊕ x_j⊕ x_i* x_j