Конспект урока Булевы функции.

Организационный момент:

минут:

2 мин

приветствие, рапорт

постановка темы и задач урока

Проверка ЗУН:

13 минут

устный опрос

Мини-лекция:

25 минут

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

• правило вывода СДНФ

• правило вывода СКНФ

Закрепление ЗУН:

45 минут

• Составление СДНФ функции, заданной таблицы истинности

• Составление СКНФ функции, заданной таблицы истинности

• Составить таблицу истинности формулы высказываний

• Построить СДНФ по составленной таблице истинности

• Построить СКНФ по составленной таблице истинности

Подведение итогов занятия:

3 минуты

• выставление оценок в соответствии с критериями

Домашнее задание:

2 минуты

• решение индивидуальных задач по вариантам

Итого:

90 минут

Этап занятия

Вопросы и задания в соответствии с этапом занятия

Проверка ЗУН

(устный опрос)

1. дать определение бинарной логических операций;

2. дать определение унарной операции;

3. дать определение конъюнкции;

4. дать определение дизъюнкции;

5. дать определение импликации;

6. дать определение эквиваленции;

7. дать определение суммы по модулю два;

8. дать определение инверсии

Мини-лекция

Теоретическая часть занятия

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

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

Рассмотрим основные понятия:

Если х – логическая переменная, {0, 1} – её значение в некотором наборе, то выражение

называется литерой.

Элементарной конъюнкцией называется конъюнкция попарно различных литер.

Пример 1: Имеется булева функция f(x₁, x_2, x₃, x₄) тогда элементарными конъюнкциями будут: ; и так далее.

Элементарной дизъюнкцией называется дизъюнкция попарно различных литер.

Пример 2: Имеется булева функция f(x₁, x_2, x₃, x₄) тогда элементарными конъюнкциями будут: ; и так далее

Замечание: в элементарную конъюнкцию (или дизъюнкцию) не обязаны входить все переменные!

Пусть x₁,x_2, …_, х_n – набор переменных, (__,.., _n )– набор значений переменных. Конституентой единицы набора (__,.., _n ) называется элементарная конъюнкция вида К¹(__,.., _n) =

Конституентой нуля набора (__,.., _n ) называется элементарная конъюнкция вида К⁰(__,.., _n) =

Замечание: обязательно входят все переменные!

Пример 3: Даны набора значений переменных. Для каждого из наборов необходимо построить конституенту единицы и конституенту нуля.

Замечание: в дальнейшем не будем расписывать по формулам в виде литер, а будем сразу переходить выражениям, вид которых записан справа.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнкция попарно различных конституент единицы.

Совершенной конъюнктивной нормальной формой (СКНФ) называется конъюнкция попарно различных конституент нуля.

Имеют место теоремы:

Теорема 1. Всякая булева функция, не тождественно равная нулю, может быть представлена как дизъюнкция конституент единицы, взятых на тех наборах переменных, на которых значение функции равно единице.

Теорема 2. Всякая булева функция, не тождественно равная единице, может быть представлена как конъюнкция конституент нуля, взятых на тех наборах переменных, на которых значение функции равно нулю.

На практике для построения СДНФ и СКНФ используют следующие алгоритмы:

• правило вывода СДНФ

Алгоритм построения СДНФ:

1. Выберем наборы значений переменных, на которых значение функции равно единице. (f=1);

2. Для каждого такого набора построим Конституенту единицы;

3. Соединим конституенты единицы знаком дизъюнкции;

4. При необходимости упростить.

• правило вывода СКНФ

Алгоритм построения СКНФ:

1. Выберем наборы значений переменных, на которых значение функции равно нулю. (f=0);

2. Для каждого такого набора построим Конституенту нуля;

3. Соединим конституенты нуля знаком конъюнкции;

4. При необходимости упростить.

• Примеры решения задач

Пример 4. Дана таблица истинности. Построить булеву функцию при помощи СДНФ

Решение:

Действуем согласно алгоритму:

1) Выберем наборы значений переменных, на которых значение функции равно единице. (f=1) и отметим их "галочкой" ()

2) Для каждого из таких наборов построим Конституенту единицы:

3) Соединим конституенты единицы знаком дизъюнкции, получим булеву функцию:

= ()()()()

4) Далее используя законы основных равносильностей, упростим полученную функцию:

первоначально необходимо постараться сгруппировать наборы таким образом, чтобы в каждом из наборов было по два общих множителя. По свойству дистрибутивности вынести их за скобки. Очевидно, для первого и второго слагаемого общим множителем является произведение , а для третьего и четвертого - . Тогда наша функция преобразуется:

= ((

Ответ: данной таблицей истинности была задана булева функция =

Пример 5: Дана таблица истинности. Построить СКНФ:

Решение:

Действуем согласно алгоритму:

1) Выберем наборы значений переменных, на которых значение функции равно нулю. (f=0) и отметим их "галочкой" ()

2) Для каждого из таких наборов построим Конституенту нуля:

3) Соединим конституенты нуля знаком конъюнкции, получим булеву функцию:

= ()()()()()

4) Далее используя законы основных равносильностей, упростим полученную функцию:

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

= ()()()()()()()()

сгруппируем первый и третий сомножитель и вынесем за скобки литеру :

()()

Ответ: данной таблицей истинности была задана булева функция =

Для того, чтобы проверить правильно ли составлена булева функция, достаточно составить таблицу истинности уже по полученной формуле

Закрепление ЗУН:

практическая часть занятия
(выполняется по вариантам 1-15 см. Приложение 1)

задание 1.

Составление СДНФ функции, заданной таблицы истинности

1. Составить СДНФ функции, заданной таблицей истинности

задание 2.

Составление СКНФ функции, заданной таблицы истинности

1. Составить СКНФ функции, заданной таблицей истинности для задания 1

задание 3.

Составить таблицу истинности формулы высказываний

1. Составить таблицу истинности формулы логики высказываний

задание 4.

Построить ДНФ по составленной таблице истинности

1. Составить СДНФ функции, заданной таблицей истинности (задание 3)

задание 5.

Построить КНФ по составленной таблице истинности

1. Составить СКНФ функции, заданной таблицей истинности (задание 3)

Подведение итогов занятия

критерии оценки

• «5» - если решены все задачи (5)

• «4» - если решены 4 задачи.

• «3» - если решены 2-3 задачи

• менее 2 задач

Домашнее задание

Выполнить письменно в тетради
упражнения № 4.3 стр. 200 учебник

Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. М.: Академия, 2010. 368 с.