Цель: ввести понятие булевых функций, научить восстанавливать аналитическое выражение для булевых функций по их таблице истинности.
Каноническая форма- форма, построенная по какому либо правилу, закону-канону.
Логической (булевой) функцией называют функцию F(х1,х2,х3,..Хn), аргументы которой и сама функция принимают значения 0 или 1.
Логические функции могут быть заданы табличным способом или аналитическим – в виде соответствующих формул.
Элементарная конъюнкция-конъюнкция конечного множества логических переменных и их инверсий.
Элементарная дизъюнкция- дизъюнкция конечного множества логических переменных и их инверсий.
Число аргументов, образующих элементарную конъюнкцию или дизъюнкцию, называют ее рангом.
Пример1.
X&Y&Z, X&Y&Z - элементарные конъюнкции третьего ранга.
Дизъюнктивная нормальная форма (ДНФ)-– содержит элементарные конъюнкции, связанные между собой операцией дизъюнкции.
Конъюнктивная нормальная форма (КНФ)- содержит элементарные дизъюнкции, связанные между собой операцией конъюнкции.
Одну и ту же логическую функцию можно представить разными ДНФ и КНФ.
Совершенная дизъюнктивная нормальная форма (СДНФ) отвечает следующим требованиям:
1) в ней нет двух одинаковых элементарных конъюнкций;
2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных;
3) ни одна элементарная конъюнкция не содержит переменной вместе с ее инверсией
4) все конъюнкции имеют один и тот же набор переменных.
Совершенная конъюнктивная нормальная форма (СКНФ) отвечает следующим требованиям:
1) в ней нет двух одинаковых элементарных дизъюнкций
2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных
3) ни одна элементарная дизъюнкция не содержит переменной вместе с ее инверсией
4) все дизъюнкции имеют один и тот же набор переменных.
Пример 2
X1&X2 v X1&X2 - СДНФ –X1 X2+X1 X2
X1v X2&X3- не СДНФ
X1&X2 v X2& X2 – не СДНФ
(X1 v X2 ) & (X1 v X2)- СКНФ
(X1 v X1) & (X2 v X3) –не СКНФ
Теорема 1. Пусть F(х1,х2,х3,..Хn)-булева функция от n переменных, не равная тождественно нулю. Тогда существует СДНФ, выражающая функцию F.
Теорема 2. Пусть F(х1,х2,х3,..Хn)-булева функция от n переменных, не равная тождественно единице. Тогда существует СКНФ, выражающая функцию F.
СДНФ и СКНФ можно получить по таблице истинности логической функции.
Алгоритм построения СДНФ по таблице истинности
1) выделить в таблице все наборы переменных, на которых функция принимает единичные значения.
2) Для каждого выбранного набора записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3) все полученные элементарные конъюнкции соединить знаком дизъюнкции.
Алгоритм построения СКНФ по таблице истинности
1) выделить в таблице все наборы переменных, на которых функция принимает нулевые значения.
2) Для каждого выбранного набора записать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3) все полученные элементарные дизъюнкции соединить знаком конъюнкции.
Пример 3 Пусть функция F(x1,x2,x3) задана таблицей истинности. Используя описанный алгоритм построим для нее СДНФ.
X1 X2 X3 F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
Ответ: (x1 & x2 & x3) v ( x1 & x2 & x3) v (x1&x2&x3)
Задания: 1.По заданным таблицам истинности дайте аналитическое представление
1) импликации
2) эквивалентности
3) строгой дизъюнкции
2. По таблице истинности записать СДНФ и СКНФ для F1 и F2.
x y z F1 F2
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 0
1 0 1 1 0
1 1 0 0 1
1 1 1 1 1