Донецкий национальный университет
ДИСКРЕТНАЯ МАТЕМАТИКА
кафедра инженерной и компьютационной педагогики

Вопросы

На зачете (экзамене) по дисциплине Дискретная математика студент должен ответить на один теоретический вопрос и решить три практические задачи. Список, из которого выбираются теоретические вопросы, приведен ниже

Теоретический коллоквиум №1: БУЛЕВЫ ФУНКЦИИ

1.1. Определение булевой функции. Задание булевой функции таблицей истинности. Примеры.

1.2. Количество строк в таблице истинности. Зависимость количества булевых функций от числа аргументов. Примеры.

1.3. Существенные и несущественные аргументы булевой функции. Булевы функции одного аргумента.

1.4. Дизъюнкция и ее свойства.

1.5. Конъюнкция и ее свойства.

1.6. Импликация, ее выражение через дизъюнкцию, конъюнкцию и отрицание.

1.7. Эквивалентность, ее выражение через импликацию.

1.8. Сумма по модулю два. Выражение дизъюнкции через конъюнкцию и сумму по модулю два.

1.9. Реализация булевых функций формулами. Тождества алгебры булевых функций.

1.10. Совершенная дизъюнктивная нормальная форма (СДНФ).

1.11. Совершенная конъюнктивная нормальная форма (СКНФ).

1.12. Полином Жегалкина. Линейные и нелинейные булевы функции.

1.13. Двойственность и самодвойственность булевых функций.

1.14. Монотонные и немонотонные булевы функции.

1.15. Полные системы булевых функций.

1.16. Замкнутые классы булевых функций.

1.17. Теорема Поста о полноте системы булевых функций.

1.18. Различные способы представления булевых функций. Карты Карно.

1.19. Представление булевых функций деревьями. Сокращение деревьев. Представление булевых функций бинарными диаграммами.

Задачи

На зачете (экзамене) по дисциплине Дискретная математика студент должен ответить на один теоретический вопрос и решить три практические задачи. Список, из которого выбираются практические задачи, приведен ниже

1. Совершенная дизъюнктивная нормальная форма (СДНФ) и дизъюнктивная нормальная форма (ДНФ)

1. Записанное в десятичной системе счисления натуральное число 152 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

2. Записанное в десятичной системе счисления натуральное число 67 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

3. Записанное в десятичной системе счисления натуральное число 164 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции h (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции h совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

4. Записанное в десятичной системе счисления натуральное число 74 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

5. Записанное в десятичной системе счисления натуральное число 100 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

2. Доказательство тождеств алгебры булевых функций

1. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(a ↓ c) ∨ a b c = (a ↔ c)(a | b)(b → (1 ⊕ c))

2. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(b ↓ c) ∨ a b c = (a → (1 ⊕ b))(a | c)(b ↔ c)

3. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(a ↓ b) c ∨ a c = (a ⊕ c)(b → a)(b | c)

4. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

a b c ∨ (1 ⊕ (a | b)) = (a ↔ b)(c ⊕ a b ⊕ a b c)

5. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

b c ∨ (a ↓ c) b =(a | b)(a → c)(b ⊕ c)