1 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-пресс, 2007. – 176 с.

2 Таран, Т. А. Сборник задач по дискретной математике / Т.А. Таран, Н.А. Мыценко, Е.Л. Темникова. – 2-е изд., перераб. и доп. – Киев: Инрес, 2005. – 64 с.

Лабораторная работа 2

Булевы функции. Многочлены Жегалкина

Цель работы: Изучить свойства булевых функций, методы построения ДНФ, КНФ, СДНФ, СКНФ, алгоритмы построения многочлена Жегалкина булевой функции.

Теоретические сведения.

Свойства элементарных булевых функций

1. Для булевых функций справедливы равенства, аналогичные формулам, сформулированным для высказываний. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности.

2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности.

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

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

Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний

Конъюнктивным одночленом от переменных х₁, х₂, ..., х_п называется конъюнкция этих переменных или их отрицаний.

Дизъюнктивным одночленом от переменных х₁, х₂, ..., х_п называется дизъюнкция этих переменных или их отрицаний.

Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных конъюнктивных одночленов, называется дизъюнктивной нормальной формой (ДНФ) данной формулы.

Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных дизъюнктивных одночленов, называется конъюнктивной нормальной формой (КНФ) данной формулы.

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм

Алгоритм построения

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

(3)Избавиться от знаков двойного отрицания.

(4)Применить, если нужно, к операциям конъюнкция и дизъюнкции свойства дистрибутивности и формулы поглощения.