- •Универсальное множество: Универсальное множество (универсум) — множество, содержащее все мыслимые объекты. Упорядоченное множество — множество, на котором задано отношение порядка.
- •Множество. Способы задания множеств (перечислением или списком, порождающей процедурой, описанием характеристического свойства). Привести примеры.
- •Объединение более чем двух множеств. Пусть дано семейство множеств Тогда его объединением называется множество, состоящее из всех элементов всех множеств семейства:
- •Алгебра множеств. Законы алгебры множеств. Доказать один из законов алгебры множеств.
- •Множество. Мощность множества. Нахождение мощности объединения множеств (для двух множеств, для трех множеств, для n-множеств). Привести пример.
- •Векторы. Прямое произведение множеств. Мощности прямого произведения множеств.
- •Отношения. Основные понятия отношений (отношения; унарные, бинарные, n-местные отношения)
- •Отношения. Бинарные отношения. Основные понятия (определение, обозначения, область определения, область значений, способы задания бинарных отношений). Привести примеры.
- •Способы задания бинарных отношений
- •Отношения. Свойства бинарных отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). Привести примеры.
- •Переключательные (булевы) функции. Происхождение булевых функций.
- •Булевы функции от одного аргумента. (Определение. Все булевы функции от одного аргумента).
- •Булевы функции от двух аргументов (Определение булевой функции двух аргументов, тождественный ноль, тождественная единица, конъюнкция, штрих Шеффера, дизъюнкция, стрелка Пирса (функция Вебба)).
- •Свойства дизъюнкции, конъюнкции и отрицания (теорема 4.3).
- •Свойства эквиваленции, импликации и отрицания (теорема 4.4).
- •Выражение одних булевых функций через другие (теорема 4.5).
- •Булевы функции от n аргументов (определение, равенство булевых функций, суперпозиция булевых функций). Булевы функции от n переменных
- •Булевы функции и формулы алгебры высказываний.
- •Нормальные формы булевых функций.
- •Применение булевых функций к релейно-контактной схеме. Две основные задачи теории релейно-контактных схем.
- •Релейно-контактные схемы в эвм. Двоичный полусумматор. Одноразрядный двоичный сумматор.
- •Графы. Основные понятия и определения (вершины, ребра, петли, кратность ребра, псевдограф, мультиграф, граф, орграф, неориентированный граф). Привести примеры.
- •Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.
- •Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.
- •Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.
- •Графы. Матрицы связности. Утверждение о матрицах связности, матрицы достижимости, матрицы сильной связности.
- •Графы. Поиск путей (маршрутов) с минимальным числом дуг (ребер). Алгоритм фронта волны.
- •Графы. Минимальные пути (маршруты) в нагруженных орграфах (графах). Алгоритм Форда-Беллмана.
Переключательные (булевы) функции. Происхождение булевых функций.
Булевы функции названы так по фамилии математика Джорджа Буля.
Булевы функции от одного аргумента. (Определение. Все булевы функции от одного аргумента).
Если n=1, то число наборов N=21=2, а количество ПФ (таблица 3.2)
Таблица 3.2
N набора |
A |
F0 |
F1 |
F2 |
F3 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
Функция F0 называется константой нуля, так как на всех наборах принимает нулевое значение (F0=0). Функция F3 - константа единицы, так как всегда равна единице (F3=1). Функция F2=A называется повторением, а – инверсией (отрицанием – не А).
Булевы функции от двух аргументов (Определение булевой функции двух аргументов, тождественный ноль, тождественная единица, конъюнкция, штрих Шеффера, дизъюнкция, стрелка Пирса (функция Вебба)).
Если n=2, то число наборов N=22 =4, а количество ПФ (таблица 3.3)
Отметим из этих шестнадцати функций 2-х переменных наиболее часто использующиеся:
F0 – константа нуля;
F15 – константа единицы;
F8=А В=А*В – конъюнкция (логическое умножение (логическое “И”));
F14=А В=А+В – дизъюнкция (логическое сложение (логическое “ИЛИ”));
F6= – исключающее ИЛИ (сумма по модулю два, неравнозначность, неэквивалентность);
– равнозначность (эквивалентность);
– ИЛИ-НЕ;
– И - НЕ.
Булевы функции от двух аргументов (Определение булевой функции двух аргументов, импликация, отрицание импликации, антиимпликация (обратная импликация), отрицание антиимпликации, эквивалентность, сложение по модулю два (сумма Жегалкина)). Равенство двух булевых функций.
Функция f, зависящая от n переменных x1,x2,....,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов xi, (i = 1..n) принимают значения только из множества {0, 1}. Аргументы булевой функции также называются булевыми.
Свойства дизъюнкции, конъюнкции и отрицания (теорема 4.3).
Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных:
Конъюнкцией n переменных f (x1, x2, …, xn) = x1 x2…xn называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).
Дизъюнкцией n переменных f (x1, x2, …, xn) = x1Ú x2Ú … Ú xn называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).
Из этих определений видно, что конъюнкция и дизъюнкция коммутативны, т. е. обе функции не зависят от порядка переменных.
Будем обозначать через (x1, x2, … , xn) новую функцию, которая на наборе переменных x1, x2, …, xn принимает значение, противоположное f(x1, x2, …, xn).
Заметим, что в перечисленных далее свойствах в роли x, y, z может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.
1. Универсальные границы:
xЪ1 = 1; xЪ 0 = х; х1 = х; х0 = 0.
2. Ассоциативность конъюнкции и дизъюнкции:
x(yz) = (xy)z; xЪ (yЪ z) = (x Ъy)Ъ z.
Это свойство означает, что в конъюнкции или дизъюнкции нескольких переменных можно как угодно расставлять скобки (а значит, можно вообще их не ставить).
3. Поглощение (“целое поглощает часть”):
хЪ ху = х(1Ъ у) = х.
4. Два распределительных закона:
х (yЪ z) = x y Ъ x z; хЪ (y z) = (xЪ y)(xЪ z),
оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, если х = 1, то справа стоит yЪ z и слева будет то же самое).
5. Правила де Моргана:
оба эти правила обобщаются на любое число переменных:
6. Правило Блейка:
Пусть К1 и К2 – какие-то логические функции, тогда
что легко доказывается справа налево:
Следствием правила Блейка являются два правила обобщенного поглощения:
Заметим, что правила Блейка и следствия из него часто используются для упрощения дизъюнкции (см. разд. 5)
Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.
Например, пусть W – некоторое множество точек (или элементарных событий в теории вероятности), В – множество подмножеств из W . Если A, B принадлежат В , то можно ввести сумму множеств (дизъюнкцию) A+B = AЪ B (равную объединению точек из А и В), произведение множеств (конъюнкцию) АВ = АЩ В (равное набору точек, входящих и в А, и в B одновременно) и дополнение (отрицание А), т. е. – множество точек из W , не входящих в А. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств из W является булевой алгеброй.