Переход от табличной формы представления
Логической функции к аналитической
Всякую логическую функцию можно представить в виде СДНФ и СКНФ. Причем у каждой булевой функции может быть только по одной СДНФ и СКНФ.
Таблица 1.8 – Функция 3 – х переменных
| х1 х2 х3 | F | конституента 1 | конституента 0 |
| 0 0 0 | 0 | х1 Ú х2 Ú х3 | |
| 0 0 1 | 1 | ù х1 ù х2 х3 | |
| 0 1 0 | 1 | ù х1 х2 ù х3 | |
| 0 1 1 | 0 | х1 Ú ù х2 Úù х3 | |
| 1 0 0 | 0 | ù х1 Ú х2 Ú х3 | |
| 1 0 1 | 1 | х1 ù х2 х3 | |
| 1 1 0 | 1 | х1 х2 ù х3 | |
| 1 1 1 | 0 | ù х1 Úù х2 Ú ù х3 |
Отсюда переходим к аналитическим выражениям логической функции:
СДНФ: F = ù х1 ù х2 х3 Ú ù х1 х2 ù х3 Ú х1 ù х2 х3 Ú х1 х2 ù х3,
СКНФ: F = (х1 Ú х2 Ú х3) (х1 Ú ù х2 Úù х3) (ù х1 Ú х2 Ú х3) (ù х1 Úù х2 Ú ù х3).
Примечание: функция, для которой не существует СДНФ – константа 0, функция, для которой не существует СКНФ – константа 1.
Импликанты и имплициенты булевых функций
Определение: булевая функция G (x1, … , xn) называется импликантой логической функции F (x1, … , xn), если для любого набора переменных, на котором G (x1, … , xn) = 1, справедливо и F (x1, … , xn) = 1.
Определение: булевая функция H (x1, … , xn) называется имплициентой логической функции F (x1, … , xn), если для любого набора переменных, на котором H (x1, … , xn) = 0, справедливо и F (x1, … , xn) = 0.
|
|
|
Таблица 1.9 – Импликанты функции 3 – х переменных
| х1 х2 х3 | F | G1 | G2 | G3 | G4 | G5 | G6 | G7 |
| 0 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 0 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 1 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 1 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 0 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 1 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 1 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Функция F имеет семь импликант:
СДНФ: F = ù х1 х2 х3 Ú х1 х2 ù х3 Ú х1 х2 х3 = G7,
G1 = х1 х2 х3,
G2 = х1 х2 ù х3 ,
G3 = х1 х2 ù х3 Ú х1 х2 х3 = х1 х2,
G4 = ù х1 х2 х3 ,
G5 = ù х1 х2 х3 Ú х1 х2 х3 = х2 х3,
G6 = ù х1 х2 х3 Ú х1 х2 ù х3 .
Определение: импликанта G булевой функции F, являющаяся элементарной конъюнкцией, называется простой импликантой, если никакая часть импликанты G не является импликантой функции F.
В нашем примере простые импликанты G3 = х1 х2 и G5 = х2 х3.
Определение: дизъюнкция любого числа импликант булевой функции F также является импликантой этой функции.
|
|
|
Все выше сказанное касается и имплициент, если мы рассматриваем логическую функцию исходя из СКНФ.
Сокращенные, минимальные и тупиковые формы
Определение: Любая булевая функция F эквивалентна дизъюнкции своих простых импликант. Такая форма булевой функции называется сокращенной дизъюнктивной нормальной формой.
В нашем случае сокращенная ДНФ: F = G3 Ú G5 = х1 х2 Ú х2 х3.
Определение: сокращенная ДНФ булевой функции называется тупиковой ДНФ, если в ней отсутствуют лишние простые импликанты.
Примечание: булевая функция может иметь несколько тупиковых ДНФ.
Определение: тупиковая ДНФ булевой функции, содержащая минимальное число аргументов, называется минимальной ДНФ.
Примечание: минимальных ДНФ у логической функции также может быть несколько.
Аналогично определяются сокращенные, тупиковые и минимальные конъюнктивные нормальные формы.
1.10 Метод карт Карно (диаграммы Вейча)
Карта Карно – матричная форма представления булевых функций, заданной в СДНФ или СКНФ. Выглядят как развертка куба на площади. Аргументы записываются в таком порядке, чтобы соседние отличались не более, чем в одном разряде. В этом случае склейке подлежат наборы, для которых единицы (нули) располагаются в соседних клетках матрицы. Причем это должны быть прямоугольные конфигурации единиц (нулей), содержащие число клеток, равное целой степени 2.
|
|
|
Получающееся элементарное произведение (дизъюнкции для СКНФ) определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах.
1.10.1 Минимизация функции трех переменных
Таблица 1.10 – Карта Карно для трех переменных
 x1 \ x2 x3
| 0 0 | 01 | 11 | 10 |
| 0 | 1 | 
|  1
|  1
|
| 1 | 
| 
| 1 | 
|
x2 x3 ù x1 ù x3
 |
Примечание: - склейка,
- лишняя склейка ù x1 x2.
Таким образом минимальная ДНФ: F = x2 x3 Ú ù x1ù x3.
1.10.2 Минимизация функции четырех переменных
Таблица 1.11 – Карта Карно 1 для четырех переменных
 |
| x1 x2\ x3 x4 | 00 | 01 | 11 |  10
|
| 00 |  1
|  1
| ||
| 01 |   1
| 1 | ||
| 11 | 1 |   1
| ||
 10
| 1 |  1
|
|
|
|
x1 ù x2 ù x4 x2 x4
ù x1 ù x3 x4 ù х2 x3 ù x4
Таблица 1.12 – Карта Карно 2 для четырех переменных
 x1 x2\ x3 x4
| 00 | 01 |  11
| 10 |
  00
| 1 | 1 | ||
| 01 | 1
| 1 | ||
| 11 | 1 | 1 | ||
| 10 |  1
| 
|   1
|
ù x2 ù x4 x2 x4
 |
Таблица 1.13 – Карта Карно 3 для четырех переменных
ù x1 x4
 x1 x2\ x3 x4
| 00 |  01
| 11 | 10 |
| 00 | 1 | 1 | 1 | |
| 01 | 1 | 1 | 1 | |
| 11 | 1 | 1 | 1 | |
| 10 | 1 | 1 | 1 |
1.10.3 Минимизация функции пяти переменных
Строятся две карты Карно для четырех переменных: одна для х5 = 0, а вторая для х5 = 1. Используется метод наложения: по пятой переменной производится склейка в том случае, если при наложении одной карты на другую группы единиц совпадают.
Пример: даналогическая функция пяти переменных.
Таблица 1.14 – Карта Карно для пяти переменных
| x1 x2\ x3 x4 | 00 | 01 | 11 | 10 | x1 x2\ x3 x4 | 00 | 01 | 11 | 10 | ||
| 00 | 00 | ||||||||||
| 01 | 
|  1
| 01 |  1
| |||||||
| 11 | 1 | 1 |  1
|  11
| 1 | ||||||
| 10 | 1 | 1 | 10 |
х5 = 0 х5 = 1
х1ù х3 ù х5 х2 х3 ù х4
Получили минимальную ДНФ: F = х1ù х3 ù х5 Ú х2 х3 ù х4.
1.10.4 Минимизация систем булевых функций по картам Карно
Анализируются карты Карно и выделяются общие импликанты.
В результате строятся схемы не для каждой функции отдельно, а общая упрощенная схема для системы функций.
Таблица 1.15 - система трех функций от четырех переменных
y1 y2 y3
| x3x4 x1x2 | 00 | 01 | 11 | 10 | x3x4 x1x2 | 00 | 01 | 11 | 10 | x3x4 x1x2 | 00 | 01 | 11 | 10 | ||
| 00 | 1 | 00 | 00 | 1 | ||||||||||||
| 01 | 1 | 1 | 1 | 01 | 1 | 1 | 1 | 01 | 1 | 1 | ||||||
| 11 | 1 | 1 | 11 | 1 | 1 | 11 | 1 | 1 | ||||||||
| 10 | 1 | 10 | 10 | 1 |
y1= x2x4Ú ùx2 ùx3 ùx4Ú ùx1x2x3 Имеем общие части:
y2= x2x4Ú ùx1x2x3 a = x2x4
y3= x2x4Ú ùx2x3ù x4 b = ùx1x2x3
Т.е. получили функции:
y1= x2x4Úùx2ù x3ù x4Ú ùx1x2x3 = aÚbÚ x2 x3 x4 = y2Úx2 x3 x4
y2= x2x4Ú ùx1x2x3 = aÚb
y3= x2x4Ú ùx2x3ùx4 = aÚùx2x3ùx4
Отсюда схема для системы функций:
x1x2 x 3 x4ùx1ùx2ù x3ùx4
Дата добавления: 2018-05-12; просмотров: 459; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!