Тема 11. Канонические формы логических формул.

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

Каноническая форма- форма, построенная по какому либо правилу, закону-канону.

Логической (булевой) функцией называют функцию 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