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

Если п = 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.

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