1.Понятие множества. Бесконечное, конечное, пустое множество. Подмножество. Понятие равенства множеств. Универсальное множество. Основные способы задания множеств.
2.Что называют пересечением, объединением, разностью, дополнением множеств? Изображение операций над множествами с помощью диаграмм Эйлера-Венна.
3.Мощность конечного множества. Понятие эквивалентности множеств. Счётное множество.
4.Понятие нечёткого множества. Функция принадлежности и способы её задания. Операции над нечёткими множествами.
5.В чём состоит правило суммы и правило произведения комбинаторики?
6.Что называют размещениями, сочетаниями, перестановками? Как подсчитать их число?
7.Что называют простым высказыванием, составным высказыванием, логической связкой? Истинностные значения, множество истинностных значений, таблица истинности высказываний.
8.Что называют отрицанием, дизъюнкцией, конъюнкцией, импликацией, эквиваленцией? Запишите их таблицы истинности.
9.Алфавит логики высказываний. Понятие формулы логики высказываний. Список переменных формулы, оценка списка переменных, таблица истинности формулы логики высказываний.
10.Какую формулу называют тавтологией, а какую формулу называют тождественно-ложной? Правильные рассуждения. Определение правильности рассуждений. Проблема разрешимости для логики высказываний.
11.Понятие равносильности формул. Основные равносильности логики высказываний.
12.Какие логические операции являются двойственными по отношению друг к другу? Какие формулы называют двойственными? Принцип двойственности логики высказываний?
13.Что называют элементарной конъюнкцией, дизъюнктивной нормальной формой (ДНФ), совершенной дизъюнктивной нормальной формой (СДНФ) формулы?
14.Что называют элементарной дизъюнкцией, конъюнктивной нормальной формой (КНФ), совершенной конъюнктивной нормальной формой (СКНФ) формулы?
15.Что называют -местной булевой функцией? Основные способы задания булевых функций. Существенные и фиктивные переменные. Понятие двойственной булевой функции.
16.Элементарные булевы функции , таблицы их значений.
17.Что называют полной системой булевых функций? Приведите их примеры. Базис системы булевых функций.
19.Критерии полноты систем булевых функций. Теорема Поста.
20.Представление булевой функции формулой логики высказываний в СДНФ, в СКНФ, полиномом Жегалкина.
21.Какую ДНФ называют минимальной? В чём состоит метод минимизирующих карт?
22.Контакты: замыкающие и размыкающие. Функция проводимости контактной схемы. Представление функции проводимости формулами логики высказываний (для 2-х последовательно соединённых контактов, для 2-х параллельно соединённых контактов). Упрощение контактных схем.
23.Понятие графа. Вершины и рёбра графа. Кратные рёбра, петли, дуги. Псевдограф, мультиграф, орграф, простой граф. Операции над графами.
24.Понятие инцидентности и смежности для графа. Матрица смежности и матрица инцидентности графа.
25.Понятие маршрута и пути в графе. Что называют длиной маршрута, цепью, циклом? Что называют эйлеровой цепью и циклом? Что называют гамильтоновой цепь и циклом? Понятие связности графа. Что называют деревом?
Приложения.
Образец решения контрольных задач типового варианта.
Решение типовых примеров.
1-10.Решить уравнение: .
Решение. 1)Найдём область допустимых значений неизвестной . Учитывая, что для числа размещений , находим .Таким образом : .
2)Найдём решение уравнения. Для этого преобразуем его, учитывая, что:
, .
Получим: . Решая уравнение , находим: , .
Ответ: , .
11-20.Сколько существует целых четырёхзначных чисел не делящихся на 5.
Решение.Четырёхзначное число, не делящееся на 5 – это число, которое не может начинаться с цифры и не должно заканчиваться цифрами или . Предполагается, что цифры в числе могут повторяться. Число таких чисел, подсчитаем, используя правило произведения комбинаторики (представив образование числа как упорядоченный повторный выбор первой, второй, третьей и четвёртой цифр из множества цифр ). Первую цифру можно выбрать 9 способами, вторую – 10 способами, третью – 10 способами, четвёртую – 8 способами. Тогда по правилу произведения комбинаторики: .
Ответ: .
21-30. В урне 5 черных и 6 белых шаров. Случайным образом вынимают 4 шара. Найти число способов их выбора, при котором среди них окажется:
а) 2 белых шара;
б) меньше чем 2 белых шара;
в) хотя бы один белый шар.
Решение. Подсчитаем число способов выбора n(A), n(B), n(C) благоприятствующих событиям А, В и С, соответственно.
а) Событие А означает, что среди вынутых шаров имеется 2 белых и 2 черных шара. Следовательно, благоприятствующими событию А являются всевозможные комбинации по 4 шара (двух белых и двух черных шаров). Их число n(A) находим по правилу произведения комбинаторики:
n(A)= × =15·10=150.
б) Событие В состоит из двух несовместных событий: В1={среди вынутых шаров один белый и три черных шара}, В2={среди вынутых шаров нет ни одного белого шара, т.е. все четыре шара - черные}. Следовательно, благоприятствующими событию В являются всевозможные комбинации по 4 шара (одного белого и трех черных или четырех черных шаров). Используя правила суммы и произведения комбинаторики находим:
n(B) = n(B1) + n(B2) = × + × = 6·10+1·5 = 65.
в) Событие С определяется словами «хотя бы один». Учитывая, что событие С состоит из четырех несовместных событий: С1=={среди вынутых шаров - один белый и три черных}, С2={среди вынутых шаров - два белых и два черных}, С3={среди вынутых шаров - три белых и один черный}, С4={среди вынутых шаров - четыре белых}, используя правила суммы и произведения комбинаторики находим:
.
Прямое решение задачи, как видно, приводит к громоздким вычислениям. Проще сначала найти число способов выбора, благоприятных событию ={среди вынутых шаров нет ни одного белого шара, все шары – черные}, а затем по формуле найти Здесь - общее число способов выбора четырёх шаров. В этом случае . Тогда .
Ответ: а) ; б) в) .
31-40.Составить таблицы истинности для формул логики высказываний.
а)в виде формулы в СДНФ (совершенной дизъюнктивной нормальной форме)
б)в виде формулы в СКНФ (совершенной конъюнктивной нормальной форме);
в)в виде формулы в минимальной ДНФ (методом минимизирующих карт).
Решение:Строим таблицу истинности формулы:
а)Спомощью таблицы истинности записываем формулу в СДНФ:
б)Спомощью таблицы истинности записываем формулу в СКНФ:
.
в)Для нахождения МДНФ:
1в) Построим карту метода ММК и отметим знаком ( ) строки, в которых соответствующие им конъюнкты входят в СДНФ, и знаком строки, в которых соответствующие им конъюнкты не входят в СДНФ.
+
-
+
-
+
+
-
+
2в) Строки, отмеченные знаком вычеркнем из таблицы. Получим:
+
+
+
+
+
3в) Двигаясь по столбцам таблицы, вычеркнем из строк, отмеченных знаком , все конъюнкты, совпадающие с конъюнктами вычеркнутых строк. Получим:
+
-
+
-
+
+
-
+
4в) В каждой строке оставляем лишь клетки, отвечающие конъюнктам с наименьшим числом сомножителей, вычеркивая при этом все остальные клетки. Получим:
+
-
+
-
+
+
-
+
5в) Из каждой строки выбираем по одному из оставшихся конъюнктов и составляем из них всевозможные различные ДНФ. Получим: , , .
6в) Из полученных ДНФ выбираем минимальную (их будет две): , .
Ответ: а) ;
б) ;
в) , .
51-60. Функция проводимости контактной схемы задана булевой функцией . Требуется по функции проводимости построить контактную схему и упростить её методом минимизирующих карт. Изобразить исходную и упрощённую контактные схемы.
-местной булевой функцией? Основные способы задания булевых функций. Существенные и фиктивные переменные. Понятие двойственной булевой функции.
, таблицы их значений.
.
неизвестной 
. Учитывая, что для числа размещений 
, находим 
.Таким образом 
.
, 
.
. Решая уравнение 
, 
.
, 
.
и не должно заканчиваться цифрами 
. Предполагается, что цифры в числе могут повторяться. Число 
). Первую цифру можно выбрать 9 способами, вторую – 10 способами, третью – 10 способами, четвёртую – 8 способами. Тогда по правилу произведения комбинаторики: 
.
.
× 
=15·10=150.
× 
+ 
× 
= 6·10+1·5 = 65.
.
={среди вынутых шаров нет ни одного белого шара, все шары – черные}, а затем по формуле 
найти 
Здесь 
- общее число способов выбора четырёх шаров. В этом случае 
. Тогда 
.
; б) 
в) 
.
~ 
~ 
записать:
.
) строки, в которых соответствующие им конъюнкты входят в СДНФ, и знаком 
строки, в которых соответствующие им конъюнкты не входят в СДНФ.
, все конъюнкты, совпадающие с конъюнктами вычеркнутых строк. Получим:
, 
, 
.
, 
.
;
;
. Требуется по функции проводимости построить контактную схему и упростить её методом минимизирующих карт. Изобразить исходную и упрощённую контактные схемы.