Карты Карно

Карты Карно Лекция 1 8 февраля 2021 г. 1 / 12 ДНФ и СДНФ Обозначения: x0 = x̄, x1 = x Рассмотрим множество переменных X = {x1 , . . . , xn } Элементарная конъюнкция ранга k: xαi11 . . . xαikk , причем ij 6= ik при j 6= k, то есть все переменные различны Дизъюнктивная нормальная форма (ДНФ): дизъюнкция попарно различных элементарных конъюнкций Минтерм: элементарная конъюнкция ранга n. Имеет смысл только при указании множества X Каждый минтерм истинен ровно на одном наборе значений переменных X Совершенная дизъюнктивная нормальная форма (СДНФ): ДНФ, составленная из минтермов 2 / 12 Единственность СДНФ СДНФ является канонической формой: f (x1 , . . . , xn ) = g(x1 , . . . , xn ) ⇐⇒ СДНФ(f ) = СДНФ(g) В частности, если СДНФ(f ) 6= СДНФ(g), то f 6= g, то есть найдется набор (α1 , . . . , αn ), такой что f (α1 , . . . , αn ) 6= g(α1 , . . . , αn ) Это верно потому, что существует взаимно-однозначное соответствие между СДНФ(f ) и таблицей истинности для f : αn 1 в СДНФ(f ) входят те и только те минтермы xα 1 . . . xn , для которых f (α1 , . . . , αn ) = 1 Номер 1 2 3 4 5 6 7 x1 x2 x3 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 f 1 1 1 Различные способы записи f (x1 , x2 , x3 ) = (01100001) = (1, 2, 7) = Σm(1, 2, 7) = x̄1 x̄2 x3 ∨ x̄1 x2 x̄3 ∨ x1 x2 x3 3 / 12 Отсутствие единственности ДНФ Другая каноническая форма: полином Жегалкина (алгебраическая нормальная форма) АНФ(f ) 6= АНФ(g) =⇒ f 6= g В отличие от СДНФ или АНФ, булева функция может иметь много различных ДНФ Примеры 1. x = xy ∨ xȳ 2. x∨ x̄y∨yz ∨xz = x(1∨z)∨ x̄y∨yz = x∨ x̄y∨yz = x∨y∨yz = x∨y 3. xyz̄ ∨ x̄yz ∨ xz = xyz̄ ∨ x̄yz ∨ xyz ∨ xyz ∨ xyz ∨ xȳz = (xyz̄ ∨ xyz) ∨ (x̄yz ∨ xyz) ∨ (xyz ∨ xȳz) = xy ∨ yz ∨ xz В п. 3 последняя формула имеет меньше вхождений переменных, чем начальная 4 / 12 Минимизация ДНФ Определение Минимальная ДНФ — это ДНФ, которая имеет наименьшее число вхождений переменных среди всех ДНФ. f (x, y, z) = x ∨ x̄y ∨ yz ∨ xz: 3 переменных, но 7 вхождений Определение Сокращенная ДНФ — это ДНФ, которую нельзя упростить с помощью преобразований: • wx ∨ wx̄ = w (склейка) • w ∨ wx = w (поглощение) Пример: xyz̄ ∨ x̄yz ∨ xz (предыдущий слайд) является сокращенной. Однако она не является минимальной, так как равна xy ∨ yz ∨ xz Теорема Минимальная ДНФ является сокращенной. Обратное в общем случае неверно 5 / 12 n-мерный булев куб n-мерный булев куб состоит из всевозможных наборов (α1 , . . . , αn ), которые считаются его вершинами. Два набора соединены ребром, если они отличаются ровно в одной компоненте 1 z n=1 (0, 1, 1) (0, 1) (1, 1) (1, 1, 1) (0, 0, 1) (1, 0, 1) y (0, 1, 0) (0, 0, 0) (0, 0) (1, 1, 0) (1, 0, 0) x (1, 0) n=2 n=3 6 / 12 Склейка вершин куба x3 (0, 1, 1) (1, 1, 1) (0, 0, 1) (1, 0, 1) x2 (0, 1, 0) (0, 0, 0) (1, 1, 0) (1, 0, 0) x1 Каждой вершине (α1 , α2 , α3 ) соответствует минтерм xα1 1 xα2 2 xα3 3 , который истинен только в этой вершине Если в ДНФ входят минтермы, соответствующие ребру, грани или всему кубу, то их можно склеить 7 / 12 Склейка вершин куба x3 (0, 1, 1) (1, 1, 1) (0, 0, 1) (1, 0, 1) x2 (0, 1, 0) (0, 0, 0) (1, 1, 0) (1, 0, 0) x1 Каждой вершине (α1 , α2 , α3 ) соответствует минтерм xα1 1 xα2 2 xα3 3 , который истинен только в этой вершине Если в ДНФ входят минтермы, соответствующие ребру, грани или всему кубу, то их можно склеить • x̄1 x2 x3 ∨ x1 x2 x3 = x2 x3 7 / 12 Склейка вершин куба x3 (0, 1, 1) (1, 1, 1) (0, 0, 1) (1, 0, 1) x2 (0, 1, 0) (0, 0, 0) (1, 1, 0) (1, 0, 0) x1 Каждой вершине (α1 , α2 , α3 ) соответствует минтерм xα1 1 xα2 2 xα3 3 , который истинен только в этой вершине Если в ДНФ входят минтермы, соответствующие ребру, грани или всему кубу, то их можно склеить • x̄1 x2 x3 ∨ x1 x2 x3 = x2 x3 • (x̄1 x2 x3 ∨ x1 x2 x3 ) ∨ (x̄1 x2 x̄3 ∨ x1 x2 x̄3 ) = x2 x3 ∨ x2 x̄3 = x2 Таким образом, x2 = 1 на дальней грани и только не ней 7 / 12 Карты Карно–Вейча z (0, 1, 1) (1, 1, 1) (0, 0, 1) y (0, 1, 0) (0, 0, 0) x2 x3 11 10 00 01 (1, 0, 1) (1, 1, 0) x1 1 (1, 0, 0) x Edward W. Veitch (1924–2013), Maurice Karnaugh (род. 1924) Статьи о картах Карно-Вейча вышли в 1952-1953 гг. Важно: соседние клетки в карте Карно соответствуют смежным вершинам в булевом кубе Самая левая и самая правая клетки в каждом ряду тоже соседние Поэтому это не плоская таблица, а цилиндр (правый и левый края склеены) 8 / 12 Варианты карт Карно Основной принцип: соседние клетки в карте Карно соответствуют смежным вершинам в булевом кубе =⇒ порядок строк и столбцов не такой, как в таблице истинности! При соблюдении этого условия порядок строк и столбцов неважен x2 x3 11 10 00 01 x1 x2 1 x3 x2 x3 00 01 11 10 x1 1 x̄2 x1 x̄1 x̄3 x3 x1 x2 11 01 00 10 x3 1 В первой строке карты одинаковые, оформление разное Во второй строке карты отличаются порядком строк и столбцов 9 / 12 Карты Карно для 3 и 4 переменных Будем использовать следующие карты (с целью облегчения проверки контрольных за другое оформление оценка будет снижена) x2 x3 11 10 00 01 x1 1 x3 x3 x4 11 10 00 01 x1 x2 11 10 00 01 x2 x̄2 x1 x̄1 x̄3 x3 x3 x̄3 x2 x1 x̄2 x̄1 x2 x4 x̄4 x4 10 / 12 Примеры минимизации y x ∨ x̄y ∨ yz ∨ xz = x ∨ y ȳ x x̄ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ ∗ ∗ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ ∗ ∗ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ ∗ ∗ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ ∗ ∗ z z̄ z 11 / 12 Примеры минимизации x ∨ x̄y ∨ yz ∨ xz = x ∨ y y ȳ x ∗ ∗ ∗ ∗ x̄ ∗ ∗ z z̄ z 11 / 12 Примеры минимизации y xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz ȳ x x̄ z z̄ z 12 / 12 Примеры минимизации y xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz ȳ ∗ x x̄ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz y ȳ x ∗ x̄ ∗ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz y ȳ x ∗ ∗ ∗ x̄ ∗ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz y ȳ x ∗ ∗ ∗ x̄ ∗ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz y ȳ x ∗ ∗ ∗ x̄ ∗ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz y ȳ x ∗ ∗ ∗ x̄ ∗ z z̄ z 12 / 12 Примеры минимизации xyz̄ ∨ x̄yz ∨ xz = xy ∨ yz ∨ xz Пусть функция принимает n аргументов y ȳ x ∗ ∗ ∗ x̄ ∗ z z̄ z кол-во клеток • Элементарная конъюнкция ранга r r n=3 n=4 (то есть из r переменных) 1 4 8 соответствует прямоугольнику 2 2 4 из 2n−r клеток 3 1 2 • Таким образом, чем больше 4 1 прямоугольник, тем меньше переменных • Участки, не являющиеся прямоугольниками, не соответствуют элементарной конъюнкции • Следует помнить, что противоположные края карты склеены, то есть она представляет собой цилиндр (при n = 3) или тор (при n = 4) 12 / 12