|
Урок по теме "Истинностные (булевы) функции"
Раздел 1. Алгебра высказываний.
Тема: Истинностные (булевы) функции
Цель: ввести понятие «булева функция», булевы функции двух переменных.
Ход работы:
I. Изучение теоретического материала
II. Практическая работа студентов
III. Самостоятельная работа студентов
IV. Анализ работы
I. Изучение теоретического материала.
Рассмотрим множество В из двух элементов, которые будем обозначать 0, 1, то есть . Наиболее распространенная интерпретация двоичных переменных 0, 1 – логическая: "да " – "нет"; "истинно" – "ложно". Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики. Функцией алгебры логики от двоичных переменных называется -арная операция на В , то есть , где .
Функции алгебры логики называются также булевыми функциями (по имени Дж. Буля (G. Bool (1815 – 1864)), логическими функциями, переключательными функциями и двоичными функциями.
Отметим, что, поскольку всего имеется наборов () нулей и единиц , существует ровно булевых функций от переменных. Например, 4 булевых функции от одной переменной, 16 функций от двух переменных, 256 – от трех и т.д.
Любая логическая функция переменных может быть задана таблицей, в левой части которой перечислены все наборов значений переменных (т.е. двоичных векторов длины ), а в другой части – значения функции на этих наборах. Приведем пример задания функции трех переменных.
Элементарной дизъюнкцией (конъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделенных операциями дизъюнкции (конъюнкции).
Пример: ; - элементарные конъюнкции; - элементарная дизъюнкция.
Дизъюнктивной (конъюнктивной) нормальной формой называется дизъюнкция (конъюнкция) конечного числа элементарных дизъюнкций (конъюнкций). Сокращенно обозначается ДНФ (КНФ).
Нормальная форма называется совершенной, если в каждой ее элементарной конъюнкции (дизъюнкции) представлены все переменные, входящие в данную функцию (либо сами, либо с отрицанием).
Любая булева функция и любая формула алгебры логики могут быть представлены множеством различных дизъюнктивных (конъюнктивных) форм, равносильных между собой.
СДНФ можно получить двумя способами:
1) с помощью таблицы истинности; 2) с помощью равносильных преобразований.
Правило получения СДНФ (СКНФ):
1. Для формулы получаем любую ДНФ (КНФ).
2. Из ДНФ (КНФ) путем равносильных преобразований получаем СДНФ (СКНФ).
II. Практическая работа студентов.
1. Найти формулу, определяющую функцию F(x,y,z), по заданной таблице истинности
|
x
|
y
|
z
|
F(x,y,z)
|
|
1
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
|
1
|
0
|
1
|
0
|
|
1
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
|
0
|
0
|
1
|
1
|
|
0
|
0
|
0
|
1
|
2. Формулу привести к СДНФ, предварительно приведя её к ДНФ равносильными преобразованиями.
3. Для формулы из примера 2 найти СДНФ путем составления таблицы истинности.
4. Для формулы из примера 2 найти СКНФ, предварительно приведя её к КНФ равносильными преобразованиями.
5. Для формулы из примера 2 найти СКНФ, записав предварительно СДНФ её отрицания, а потом воспользовавшись формулой.
6. По таблицам истинности найдите формулы, определяющие функции F1(x,y,z), F2(x,y,z), F3(x,y,z) и F4(x,y,z).
|
x
|
y
|
z
|
F1(x,y,z)
|
F2(x,y,z)
|
F3(x,y,z)
|
F4(x,y,z)
|
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
III.Самостоятельная работа студентов.
1 вариант
1 .Проверьте, являются ли булевы функции эквивалентными:
2. По заданной функции постройте таблицу истинности, приведите функцию к СКНФ.
2 вариант
1.Проверьте, являются ли булевы функции эквивалентными:
2.По заданной функции постройте таблицу истинности, приведите функцию к СДНФ.
3 вариант
1.Проверьте, являются ли булевы функции эквивалентными:
2. По заданной функции постройте таблицу истинности, приведите функцию к СКНФ.
4 вариант
1. Проверьте, являются ли булевы функции эквивалентными:
2.По заданной функции постройте таблицу истинности, приведите функцию к СДНФ.
.
IV. Подведение итогов.
Критерии оценок:
«5» - выполнены верно два задания
«4» - верно выполнено первое задание и во втором задании построена таблица истинности
«3» - верно выполнено одно задание
«2» - не выполнено ни одно задание.
Литература:
1. Игошин В.И. Математическая логика и теория алгоритмов. М.: Издательский центр «Академия», 2010.
2. Спирин М.С., Спирина П.А. Дискретная математика. М.: Издательский центр «Академия», 2007.
3. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Часть 2 Задачник – практикум и решения. М.: Издательский цент «Академия», 2007
Автор: Серкина Екатерина Николаевна, КОГОБУ СПО "Слободской государственный колледж педагогики и социальных отношений"
|
УМК школа