Конспект урока Булевы функции.
Тема занятия: Булевы функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ).
Тип занятия: комбинированный урок
Просмотр содержимого документа «Конспект урока Булевы функции.»План учебного занятия
По дисциплине: «Элементы математической логики»
Тема занятия: Булевы функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ).
Тип занятия: комбинированный урок
Цели занятия:
Обучающая: Сформировать умение построения таблиц истинности для вывода СДНФ и СКНФ
Развивающая: аналитически контролировать правильность и точность своих рассуждений
Воспитательная: Формировать профессионально важные интегрированные качества личности.
Дидактические единицы:
Таблица истинности БФ для заданной формулы алгебры логики;
Законы де Моргана;
Правило снятия импликации.
План занятия:
постановка темы и задач урока
построение таблицы истинности булевой функции для заданной формулы
правило вывода СДНФ
правило вывода СКНФ
Составление СДНФ функции, заданной таблицы истинности
Составление СКНФ функции, заданной таблицы истинности
Составить таблицу истинности формулы высказываний
Построить СДНФ по составленной таблице истинности
Построить СКНФ по составленной таблице истинности
Подведение итогов занятия:
выставление оценок в соответствии с критериями
решение индивидуальных задач по вариантам
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. М.: Академия, 2010. 368 с
Ход и содержание занятия:
Вопросы и задания в соответствии с этапом занятия
дать определение бинарной логических операций;
дать определение унарной операции;
дать определение конъюнкции;
дать определение дизъюнкции;
дать определение импликации;
дать определение эквиваленции;
дать определение суммы по модулю два;
дать определение инверсии
Теоретическая часть занятия
построение таблицы истинности булевой функции для заданной формулы
Зачастую задача может быть поставлена обратным образом: имеется некоторая таблица истинности булевой функции, необходимо построить саму булеву функцию.
Рассмотрим основные понятия:
Если х – логическая переменная, – её значение в некотором наборе, то выражение
называется литерой.
Элементарной конъюнкцией называется конъюнкция попарно различных литер.
Пример 1: Имеется булева функция f(x1, x2, x3, x4) тогда элементарными конъюнкциями будут: ; и так далее.
Элементарной дизъюнкцией называется дизъюнкция попарно различных литер.
Пример 2: Имеется булева функция f(x1, x2, x3, x4) тогда элементарными конъюнкциями будут: ; и так далее
Замечание: в элементарную конъюнкцию (или дизъюнкцию) не обязаны входить все переменные!
Конституентой нуля набора (. n ) называется элементарная конъюнкция вида К 0 (. n) =
Замечание: обязательно входят все переменные!
Пример 3: Даны набора значений переменных. Для каждого из наборов необходимо построить конституенту единицы и конституенту нуля.
Замечание: в дальнейшем не будем расписывать по формулам в виде литер, а будем сразу переходить выражениям, вид которых записан справа.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнкция попарно различных конституент единицы.
Совершенной конъюнктивной нормальной формой (СКНФ) называется конъюнкция попарно различных конституент нуля.
Имеют место теоремы:
Теорема 1. Всякая булева функция, не тождественно равная нулю, может быть представлена как дизъюнкция конституент единицы, взятых на тех наборах переменных, на которых значение функции равно единице.
Теорема 2. Всякая булева функция, не тождественно равная единице, может быть представлена как конъюнкция конституент нуля, взятых на тех наборах переменных, на которых значение функции равно нулю.
На практике для построения СДНФ и СКНФ используют следующие алгоритмы:
правило вывода СДНФ
Алгоритм построения СДНФ:
Выберем наборы значений переменных, на которых значение функции равно единице. (f=1);
Для каждого такого набора построим Конституенту единицы;
Соединим конституенты единицы знаком дизъюнкции;
4. При необходимости упростить.
правило вывода СКНФ
Алгоритм построения СКНФ:
Выберем наборы значений переменных, на которых значение функции равно нулю. (f=0);
Для каждого такого набора построим Конституенту нуля;
Соединим конституенты нуля знаком конъюнкции;
При необходимости упростить.
Примеры решения задач
Пример 4. Дана таблица истинности. Построить булеву функцию при помощи СДНФ