Способы_задания_булевых_функций

1.

ЛЕКЦИЯ 2
Построение
канонических форм
СДНФ и СКНФ
Теория, алгоритмы и полный разбор примеров

2.

ВВЕДЕНИЕ
О чём эта лекция
Методические материалы, теория и примеры для практического занятия
Построение СКНФ по нулевым строкам таблицы истинности.
Аналитическое построение СДНФ из формулы.
Аналитическое построение СКНФ из формулы.
Разбор четырёх сложных практических вариантов.
Литерал - это переменная или её отрицание: x или ¬x. Запись xy означает x ∧ y.
Базовые определения булевых функций вынесены в материал Лекции 1.
Итоги
02

3.

МАРШРУТ
Структура материала
Итоги
1
СКНФ по таблице истинности: выбор литералов, составление скобок и сборка результата.
2
СДНФ из формулы: устранение операций, раскрытие скобок и восполнение единицей.
3
СКНФ из формулы: второй закон дистрибутивности и восполнение нулём.
4
Практика у доски: четыре варианта со всеми промежуточными преобразованиями.
03

4.

ЧАСТЬ 1
Построение СКНФ
по таблице истинности
Дуальный метод: выбираем строки, где функция равна нулю, и строим по ним
конституенты нуля.
СКНФ по таблице
1
04

5.

ТЕОРИЯ
Дуальный принцип построения
Для СДНФ выбирают строки, где функция равна 1. Для СКНФ используют
строки, где функция равна 0.
СДНФ: строки f = 1
СКНФ: строки f = 0
Эти способы дуальны: меняются выбранные значения функции, вид конституент и операция,
соединяющая их.
СКНФ по таблице
05

6.

ОПРЕДЕЛЕНИЕ
Литералы и конституента нуля
Литерал - это переменная или её отрицание: x или ¬x.
Конституента нуля - дизъюнкция литералов всех переменных. Она равна 0 только на одном
конкретном наборе.
(литерал₁ ∨ литерал₂ ∨ … ∨ литералₙ)
В скобке должна присутствовать каждая переменная функции ровно один раз: без отрицания или с
отрицанием.
СКНФ по таблице
06

7.

ПРАВИЛО
Зеркальное правило знаков
Берём одну строку, где f = 0, и смотрим на значение каждой переменной.
Если значение равно 0, выбираем литерал x
Если значение равно 1, выбираем литерал ¬x
Выбранные литералы соединяем знаком ∨ и заключаем в одну скобку.
СКНФ по таблице
07

8.

ПО ТАБЛИЦЕ ИСТИННОСТИ
Алгоритм построения СКНФ
1
Найти все строки таблицы, в которых f = 0.
2
В каждой выбранной строке заменить значение 0 литералом без отрицания, а значение 1 литералом с отрицанием.
3
Литералы одной строки соединить знаком ∨ и заключить в скобки.
4
Скобки всех нулевых строк соединить знаком ∧. Получится СКНФ.
СКНФ по таблице
08

9.

БАЗОВЫЙ АЛГОРИТМ
Пример 1. Таблица функции f(x, y)
x
y
f
0
0
1
0
1
0
1
0
0
1
1
1
Для СКНФ нужны две строки: 01 и 10.
СКНФ по таблице
09

10.

ПОСТРОЕНИЕ
Пример 1. Две конституенты
Строка 01: x = 0, поэтому x; y = 1, поэтому ¬y
Скобка: (x ∨ ¬y)
Строка 10: x = 1, поэтому ¬x; y = 0, поэтому y
Скобка: (¬x ∨ y)
В каждой скобке есть обе переменные.
Знаки выбраны так, чтобы скобка была равна 0 именно на своей строке.
СКНФ по таблице
10

11.

СБОРКА
Пример 1. Результат
Скобки-конституенты соединяем знаком ∧.
f(x, y) = (x ∨ ¬y) ∧ (¬x ∨ y)
Полученная формула равна 0 ровно на наборах 01 и 10, то есть на тех строках, которые мы
выбрали.
СКНФ по таблице
11

12.

ОТ УСЛОВИЯ К НУЛЯМ
Пример 2. Словесное условие
f(x, y, z) = 0 только тогда, когда все переменные равны между собой.
Наборы нулей:
000: три нуля
(x ∨ y ∨ z)
111: три единицы
(¬x ∨ ¬y ∨ ¬z)
Для 0 берём литерал без отрицания. Для 1 берём литерал с отрицанием.
СКНФ по таблице
12

13.

СБОРКА
Пример 2. Результат
Каждый нулевой набор даёт одну скобку. Соединяем две скобки знаком ∧.
f(x, y, z) = (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)
СКНФ по таблице
13

14.

ЧАСТЬ 2
Аналитическое построение
СДНФ из формул
Преобразуем исходную формулу в сумму полных конъюнкций, не строя
большую таблицу истинности.
СДНФ из формулы
2
14

15.

ТЕОРИЯ
Когда нужен аналитический способ
Если функция задана сложной формулой, таблица истинности на 8 или 16
строк может быть нерациональной.
Вместо таблицы применяют алгебраические преобразования: оставляют операции ∧, ∨, ¬,
раскрывают скобки и дополняют неполные конъюнкции недостающими переменными.
Цель: получить дизъюнкцию полных конъюнкций
СДНФ из формулы
15

16.

ШАГИ 1–3
Алгоритм построения СДНФ
1
Устранить импликации и эквивалентности: A → B = ¬A ∨ B; A
2
Раскрыть отрицания: ¬(A ∨ B) = ¬A ∧ ¬B; ¬(A ∧ B) = ¬A ∨ ¬B.
3
Раскрыть скобки по дистрибутивности, получить простую ДНФ и удалить нули: x ∧ ¬x = 0.
СДНФ из формулы
B = AB ∨ ¬A¬B.
16

17.

ШАГИ 4–5
Восполнение до СДНФ
Если в конъюнкции не хватает переменной y, умножаем её на тождественную
единицу:
y ∨ ¬y = 1
A = A ∧ (y ∨ ¬y) = Ay ∨ A¬y
После раскрытия скобок удаляем дубликаты по закону A ∨ A = A.
СДНФ из формулы
17

18.

ИСХОДНАЯ ФУНКЦИЯ
Пример 3. Простое восполнение
Сначала убираем импликацию по правилу A → B = ¬A ∨ B.
f(x, y) = x → y = ¬x ∨ y
Получили ДНФ, но оба слагаемых неполные: в ¬x отсутствует y, а в y отсутствует x.
Каждое слагаемое дополняем недостающей переменной через тождественную
единицу.
СДНФ из формулы
18

19.

ПРЕОБРАЗОВАНИЕ
Пример 3. Восполнение слагаемых
В ¬x не хватает y:
¬x = ¬x ∧ (y ∨ ¬y) = ¬xy ∨ ¬x¬y
В y не хватает x:
y = y ∧ (x ∨ ¬x) = xy ∨ ¬xy
Собираем вместе:
f = ¬xy ∨ ¬x¬y ∨ xy ∨ ¬xy
СДНФ из формулы
19

20.

РЕЗУЛЬТАТ
Пример 3. СДНФ
Слагаемое ¬xy встретилось дважды, поэтому записываем его один раз.
f = xy ∨ ¬xy ∨ ¬x¬y
СДНФ из формулы
20

21.

РАСКРЫТИЕ СКОБОК
Пример 4. Функция трёх переменных
Раскрываем скобки по распределительному закону: x(A ∨ B) = xA ∨ xB.
f(x, y, z) = x ∧ (y ∨ ¬z) = xy ∨ x¬z
Теперь восполняем каждое слагаемое: в xy не хватает z, а в x¬z не хватает y.
xy = xy ∧ (z ∨ ¬z) = xyz ∨ xy¬z
x¬z = x¬z ∧ (y ∨ ¬y) = xy¬z ∨ x¬y¬z
СДНФ из формулы
21

22.

РЕЗУЛЬТАТ
Пример 4. СДНФ
Объединяем полные конъюнкции и удаляем повтор xy¬z.
f = xyz ∨ xy¬z ∨ x¬y¬z
СДНФ из формулы
22

23.

ЧАСТЬ 3
Аналитическое построение
СКНФ из формул
Преобразуем формулу в произведение полных дизъюнкций. Главный
инструмент – второй закон дистрибутивности.
СКНФ из формулы
3
23

24.

ШАГИ 1–3
Алгоритм построения СКНФ
Аналитическое построение СКНФ обычно сложнее, потому что требует неочевидного
применения дистрибутивного закона.
1
Устранить все операции, кроме ∧, ∨, ¬.
2
Раскрыть отрицания по законам де Моргана.
3
Применять A ∨ BC = (A ∨ B) ∧ (A ∨ C), чтобы получить произведение сумм, то есть КНФ.
СКНФ из формулы
24

25.

ШАГИ 4–5
Восполнение до СКНФ
Если в дизъюнкции не хватает переменной y, прибавляем тождественный ноль:
y ∧ ¬y = 0
A ∨ (y ∧ ¬y) = (A ∨ y) ∧ (A ∨ ¬y)
В результате одна неполная скобка превращается в две полные дизъюнкции.
СКНФ из формулы
25

26.

ИСХОДНАЯ ФУНКЦИЯ
Пример 5. Готовая КНФ
f(x, y) = x ∧ ¬y
Это уже КНФ, но не совершенная: множители x и ¬y содержат только по одной
переменной.
В множителе x не хватает y. Прибавляем ноль y ∧ ¬y и раскрываем по второму закону
дистрибутивности.
x ∨ (y ∧ ¬y) = (x ∨ y) ∧ (x ∨ ¬y)
СКНФ из формулы
26

27.

ВОСПОЛНЕНИЕ
Пример 5. Вторая скобка
В множителе ¬y не хватает x. Прибавляем ноль x ∧ ¬x и раскрываем скобки.
¬y ∨ (x ∧ ¬x) = (¬y ∨ x) ∧ (¬y ∨ ¬x)
Одинаковые скобки (x ∨ ¬y) и (¬y ∨ x) совпадают, поэтому одну из них удаляем.
СКНФ из формулы
27

28.

РЕЗУЛЬТАТ
Пример 5. СКНФ
f = (x ∨ y) ∧ (x ∨ ¬y) ∧ (¬x ∨ ¬y)
СКНФ из формулы
28

29.

ИСХОДНАЯ ФУНКЦИЯ
Пример 6. Второй закон дистрибутивности
f(x, y, z) = x ∨ (y ∧ z)
Применяем правило A ∨ BC = (A ∨ B) ∧ (A ∨ C).
f = (x ∨ y) ∧ (x ∨ z)
Получили КНФ. Теперь каждую скобку нужно дополнить третьей переменной.
СКНФ из формулы
29

30.

ВОСПОЛНЕНИЕ Z
Пример 6. Первая скобка
В дизъюнкции (x ∨ y) отсутствует z, поэтому прибавляем z ∧ ¬z.
(x ∨ y) ∨ (z ∧ ¬z)
= (x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z)
СКНФ из формулы
30

31.

ВОСПОЛНЕНИЕ Y
Пример 6. Вторая скобка и итог
(x ∨ z) ∨ (y ∧ ¬y)
= (x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ z)
Скобка (x ∨ y ∨ z) получилась дважды, поэтому оставляем её один раз.
f = (x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z)
СКНФ из формулы
31

32.

ЧАСТЬ 4
Практика у доски
Четыре типовых экзаменационных и практических варианта: упрощение
функции, затем СДНФ и СКНФ.
Практика
4
32

33.

ПРИВЕСТИ К СДНФ И СКНФ
Вариант I. Условие
f(x, y, z) = ¬(¬x ∨ ¬z)
(¬(y ∧ z) → z)
Начинаем с упрощения левой и правой частей эквивалентности.
Практика
33

34.

ШАГ 1
Вариант I. Упрощение частей
Левая часть. Закон де Моргана:
¬(¬x ∨ ¬z) = x ∧ z
Правая часть. Убираем импликацию:
¬(y ∧ z) → z
= ¬(¬y ∨ ¬z) ∨ z
= (y ∧ z) ∨ z = z
Для правой части использован закон поглощения.
Практика
34

35.

ШАГ 1
Вариант I. Упрощение эквивалентности
После упрощения частей: f = (x ∧ z)
z
Раскрываем эквивалентность A
B = AB ∨ ¬A¬B:
(x ∧ z ∧ z) ∨ (¬(x ∧ z) ∧ ¬z)
= xz ∨ ((¬x ∨ ¬z) ∧ ¬z)
= xz ∨ ¬z
= x ∨ ¬z
Итог после упрощения: f = x ∨ ¬z.
Практика
35

36.

ШАГ 2
Вариант I. СДНФ
В x не хватает y и z. В ¬z не хватает x и y. Умножаем каждое слагаемое на тождественные
единицы.
f = x(y ∨ ¬y)(z ∨ ¬z) ∨ ¬z(x ∨ ¬x)(y ∨ ¬y)
Раскрываем скобки и удаляем одинаковые слагаемые. Получается шесть полных конъюнкций.
СДНФ = xyz ∨ xy¬z ∨ x¬yz ∨ x¬y¬z
∨ ¬xy¬z ∨ ¬x¬y¬z
Практика
36

37.

ШАГ 3
Вариант I. СКНФ
В дизъюнкции x ∨ ¬z отсутствует y. Прибавляем тождественный ноль y ∧ ¬y.
f = (x ∨ ¬z) ∨ (y ∧ ¬y)
СКНФ = (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z)
Практика
37

38.

УСЛОВИЕ
Вариант II. Упрощение функции
f(x, y, z) = ¬(x ∨ z) → (yz
y)
Закон де Моргана: ¬(x ∨ z) = ¬x ∧ ¬z
Раскрываем эквивалентность yz
yz ∨ ((¬y ∨ ¬z) ∧ ¬y)
= yz ∨ ¬y = z ∨ ¬y
y:
Убираем импликацию:
f = ¬x¬z → (¬y ∨ z) = x ∨ ¬y ∨ z
Практика
38

39.

ШАГ 2
Вариант II. Канонические формы
Выражение x ∨ ¬y ∨ z содержит все три переменные и является полной
дизъюнкцией.
СКНФ = (x ∨ ¬y ∨ z)
Это СКНФ из одной полной дизъюнкции. Она равна 0 только на наборе 010. Поэтому в СДНФ
входят остальные семь наборов.
СДНФ содержит все наборы, кроме 010
Практика
39

40.

УСЛОВИЕ
Вариант III. Начальное упрощение
f(x, y, z) = (x → ¬y)
(¬x ∨ z)
Убираем импликацию: x → ¬y = ¬x ∨ ¬y
f = (¬x ∨ ¬y)
(¬x ∨ z)
Далее раскрываем эквивалентность по формуле A
Практика
B = AB ∨ ¬A¬B.
40

41.

ШАГ 1
Вариант III. Два произведения
Первое произведение AB. Дистрибутивность:
(¬x ∨ ¬y)(¬x ∨ z)
= ¬x ∨ (¬y ∧ z) = ¬x ∨ ¬yz
Второе произведение ¬A¬B. Закон де Моргана:
¬(¬x ∨ ¬y) ∧ ¬(¬x ∨ z)
= (x ∧ y) ∧ (x ∧ ¬z) = xy¬z
МДНФ: f = ¬x ∨ ¬yz ∨ xy¬z
Практика
41

42.

ШАГ 2
Вариант III. Восполнение единицей
В ¬x не хватает y и z:
¬x = ¬x(y ∨ ¬y)(z ∨ ¬z)
= ¬xyz ∨ ¬xy¬z ∨ ¬x¬yz ∨ ¬x¬y¬z
В ¬yz не хватает x:
¬yz = ¬yz(x ∨ ¬x) = x¬yz ∨ ¬x¬yz
xy¬z уже является полной конъюнкцией
При объединении удаляем повтор ¬x¬yz.
Практика
42

43.

РЕЗУЛЬТАТ
Вариант III. СДНФ
СДНФ = ¬xyz ∨ ¬xy¬z ∨ ¬x¬yz ∨ ¬x¬y¬z
∨ x¬yz ∨ xy¬z
Получилось шесть конституент единицы.
Практика
43

44.

ШАГ 3
Вариант III. Переход к КНФ
Так как в СДНФ шесть слагаемых из восьми возможных, в СКНФ ожидаются две
конституенты нуля.
f = ¬x ∨ ¬yz ∨ xy¬z
Используем правило A ∨ BC = (A ∨ B)(A ∨ C). При длинном преобразовании результат нужно
проверять по числу нулевых наборов: неполная одна скобка здесь недостаточна.
Нулевые наборы: 100 и 111
Практика
44

45.

ПРОВЕРЕННЫЙ АНАЛИТИЧЕСКИЙ ПУТЬ
Вариант III. Корректная СКНФ
1. Дважды применяем A ∨ BC = (A ∨ B)(A ∨ C):
¬x ∨ (¬y ∨ xy¬z)(z ∨ xy¬z)
2. Раскрываем каждое произведение внутри скобок:
(¬y ∨ xy¬z) = (x ∨ ¬y)(¬y ∨ ¬z)
(z ∨ xy¬z) = (z ∨ x)(z ∨ y)
3. Вносим ¬x в каждую скобку:
= (¬x ∨ x ∨ ¬y) ∧ (¬x ∨ ¬y ∨ ¬z)
∧ (¬x ∨ x ∨ z) ∧ (¬x ∨ z ∨ y)
4. Удаляем скобки, содержащие x ∨ ¬x:
СКНФ = (¬x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z)
Практика
45

46.

XOR И ЗАКОН ДЕ МОРГАНА
Вариант IV. Упрощение
f(x, y, z) = ¬(x
y) ∨ (x ∧ ¬z)
Отрицание эквивалентности, то есть XOR:
¬(x
y) = x¬y ∨ ¬xy
Подставляем в функцию: f = x¬y ∨ ¬xy ∨ x¬z
Выносим x из первого и третьего слагаемых:
f = x(¬y ∨ ¬z) ∨ ¬xy
Практика
46

47.

ШАГ 2
Вариант IV. СДНФ
x¬y(z ∨ ¬z) = x¬yz ∨ x¬y¬z
¬xy(z ∨ ¬z) = ¬xyz ∨ ¬xy¬z
x¬z(y ∨ ¬y) = xy¬z ∨ x¬y¬z
Удаляем повтор x¬y¬z.
СДНФ = x¬yz ∨ x¬y¬z ∨ ¬xyz ∨ ¬xy¬z ∨ xy¬z
Практика
47

48.

ШАГ 3
Вариант IV. Простая КНФ
f = x(¬y ∨ ¬z) ∨ ¬xy
f = (¬xy ∨ x) ∧ (¬xy ∨ ¬y ∨ ¬z)
¬xy ∨ x = (x ∨ ¬x)(x ∨ y) = x ∨ y
¬xy ∨ ¬y ∨ ¬z = ¬x ∨ ¬y ∨ ¬z
КНФ = (x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬z)
Практика
48

49.

ВОСПОЛНЕНИЕ НУЛЁМ
Вариант IV. СКНФ
В первой скобке (x ∨ y) не хватает z. Добавляем z ∧ ¬z.
(x ∨ y) ∨ (z ∧ ¬z)
= (x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z)
Вторая скобка уже содержит три переменные.
СКНФ = (x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z)
∧ (¬x ∨ ¬y ∨ ¬z)
Практика
49

50.

ИТОГ
СДНФ и СКНФ: что проверять
СДНФ
СКНФ
Выбираем единичные наборы.
Выбираем нулевые наборы.
Строим полные конъюнкции.
Строим полные дизъюнкции.
Соединяем их знаком ∨.
Соединяем их знаком ∧.
Финальная проверка: в каждой конституенте присутствуют все переменные, дубликаты
удалены, а число конституент совпадает с числом выбранных строк таблицы.
Итоги
50