Дискретная математика 03

Вариант 7

I. Дискретные множества

Докажите тождества двумя способами:

А) используя определения равенства множеств и операций над множествами;

Б) с помощью алгебры логики.

Решение:

А)

Б) . Преобразуем левую часть по формулам алгебры логики:

, что и требовалось доказать.

II. Функции алгебры логики. Многочлены Жегалкина

Для заданной булевой функции трех переменных:

А) Постройте таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ,

Б) Найдите двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная булева функция линейной,

В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.

Решение:

А) Составим таблицу истинности:

Двоичная форма функции: 01010011.

СДНФ: .

СКНФ: .

Б) Преобразуем данную функцию к многочлену Жегалкина:

Функция линейной не является.

Построим полином Жегалкина методом неопределенных коэффициентов. Общий вид полинома Жегалкина:

Найдем коэффициенты:

Функция примет вид:

.

Итак, .

Оба метода дали один и тот же результат.

В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.

Вариант 8

I. Дискретные множества

Докажите тождества двумя способами:

А) используя определения равенства множеств и операций над множествами;

Б) с помощью алгебры логики.

Решение:

А)

Б) . Преобразуем левую часть по формулам алгебры логики:

, что и требовалось доказать.

II. Функции алгебры логики. Многочлены Жегалкина

Для заданной булевой функции трех переменных:

А) Постройте таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ,

Б) Найдите двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная булева функция линейной,

В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.

Решение:

А) Составим таблицу истинности:

Двоичная форма функции: 10101100.

СДНФ: .

СКНФ: .

Б) Преобразуем данную функцию к многочлену Жегалкина:

Функция линейной не является.

Построим полином Жегалкина методом неопределенных коэффициентов. Общий вид полинома Жегалкина:

Найдем коэффициенты:

Функция примет вид:

.

Итак, .

Оба метода дали один и тот же результат.

В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.

< Предыдущая		Следующая >