Аналитическое представление переключательных функций

Номер логического набора. Характеристические функции

Номером двоичного набора называется такое десятичное число i, которое получается следующим образом:

,

где 2 – основание двоичной системы счисления.

Например, для логического набора (001) число i примет следующее значение: i = 2²*0+2¹*0+2⁰*1=1.

Рассмотрим следующие характеристические функции:

1. Дизъюнктивный терм (макстерм) — это терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции:

Например, или .

2. Конъюнктивный терм (минтерм) — это терм, связывающий переменные в прямой или инверсной форме знаком конъюнкции:

Например, F₁ = x₁x₂x₃.

Рангом терма называется количество переменных, образующих данный терм.

Числовое представление ФАЛ

Часто для упрощения записи ФАЛ, вместо полного перечисления термов, используют номера наборов, на которых функция принимает значения 0 или 1. Такую форму записи называют числовой.

Пример

Функцию, заданную следующей таблицей истинности

х1	х2	х3

в числовой форме можно представить в следующем виде:

f(x₁ x₂ x₃) = \/₁ F(1,3,4,6) или f(x₁ x₂ x₃) = &₁ Ф(0,2,5,7).

Нормальные формы (НФ) представления ФАЛ

Теорема 1. Любая таблично заданная ФАЛ, кроме константы нуля, может быть представлена аналитически в следующем виде:

. (1)

Доказательство:

- если на каком–то наборе функция обращается в 1, то вследствие того, что по аксиоме , то в правой части (6.1)найдётся обязательно элемент, равный 1. Если же на i-м наборе функция обращается в 0, то все элементы нулевые. Таким образом, каждому набору i, для которого функция обращается в 1, соответствует терм, равный 1. А на наборе i, при котором функция обращается в 0, нет ни одного терма, равного 1. Поэтому любая таблица истинности однозначно изображается записью приведенного вида, которая называется объединением термов;

- если ФАЛ представлена в базисе , то такая форма представления называется нормальной.

Дизъюнктивная нормальная форма (ДНФ) – это объединение термов, включающих минтермы переменного ранга.

Количество всех минтермов, входящих в формулу (1), равно количеству единичных строк в таблице истинности. Например, произвольная ФАЛ в ДНФ будет выглядеть следующим образом: .

Следствие из теоремы 1. Любая таблично заданная ФАЛ может быть представлена в следующем аналитическом виде:

. (2)

Такая форма называется полиномиальной нормальной формой (ПНФ, здесь используется базис ).

Теорема 2. Любая таблично заданная ФАЛ, кроме константы единицы, может быть представлена в следующем аналитическом виде:

. (3)

Такая форма представления ФАЛ называется конъюнктивной нормальной формой (КНФ).

Например, КНФ произвольной ФАЛ: .

Следствие из теоремы 2. Любая таблично заданная ФАЛ, кроме константы 1, может быть представлена в виде

. (4)

Такая форма представления ФАЛ называется эквивалентной нормальной формой (ЭНФ).

Совершенные нормальные формы

КНФ, ДНФ, ПНФ и ЭНФ не дают однозначного представления таблично заданной ФАЛ. Поэтому необходимо рассмотреть совершенные нормальные формы. Введем определение логической степени.

Логической степенью называется показатель степени a_i логической переменной x_i, обладающий следующими свойствами:

x_i, если a_i = 1,

= , если a_i = 0.

Теорема 3. Любая ФАЛ, кроме константы 0, может быть представлена в следующем виде:

. (5)

В результате получаем дизъюнктивную совершенную нормальную форму (ДСНФ).

Приведем основные свойства ДСНФ:

1) отсутствие в любом минтерме одинаковых минтермов;

2) отсутствие в любом минтерме одинаковых переменных;

3) отсутствие в любом минтерме переменной вместе с ее инверсией;

4) все минтермы имеют одинаковый максимальный ранг.

Рассмотрим алгоритм получения ДСНФ.

Алгоритм 2:

Шаг 1. Выделить все единичные значения функции.

Шаг 2. Записать все возможные минтермы при единичных значениях функции, причем, переменная х _i будет без инверсии, если , и с инверсией, если .

Шаг 3. Все минтермы объединить знаком дизъюнкции.

Пример

Определить ДСНФ ФАЛ от трёх переменных, принимающей значение 1 на наборах: 0, 1, 5, 7.

Составим таблицу истинности:

N	x1	x2	x3	f	Единичные значения ФАЛ	Минтермы
					+
					+
					+
					+

Таким образом, ДСНФ данной ФАЛ имеет вид

Для получения ПСНФ (полиномиальная совершенная нормальная форма) необходимо в приведенном выше алгоритме на шаге 3 все минтермы объединить знаком неравнозначности.

Для нашего примера 2. ПСНФ ФАЛ имеет вид

Теорема 4. Любая ФАЛ, кроме константы 1, может быть представлена в следующем виде:

. (6)

В результате получаем конъюнктивную совершенную нормальную форму (КСНФ).

Приведем основные свойства КСНФ:

1) отсутствие в любом макстерме одинаковых макстермов;

2) отсутствие в любом макстерме одинаковых переменных;

3) отсутствие в любом макстерме переменной вместе с ее инверсией;

4) все макстермы имеют одинаковый максимальный ранг.

Рассмотрим алгоритм получения КСНФ.

Алгоритм 3:

Шаг 1. Выделить все нулевые значения функции.

Шаг 2. Записать все возможные макстермы при нулевых значениях функции, причем переменная х_i будет без инверсии, если , и с инверсией, если .

Шаг 3. Все макстермы объединить знаком конъюнкции.

Следствие из теоремы 4. Любая ФАЛ, кроме константы 1, может быть представлена в следующем виде:

. (7)

Такая форма представления ФАЛ называется эквивалентной совершенную нормальной формой (ЭСНФ). Она получается по алгоритму КСНФ заменой знака конъюнкции на эквивалентность.

Пример

Определить КСНФ, ЭСНФ ФАЛ от трёх переменных, принимающей значение 0 на наборах: 2, 3, 4, 6.

Составим таблицу истинности данной функции:

N	х1	х2	х3	f	Нулевые значения	Макстермы
					+
					+
					+
					+

Таким образом, КСНФ для данной ФАЛ имеет следующий вид:

ЭСНФ данной ФАЛ имеет следующий вид:

Способы преобразования НФ в СНФ

Совершенная нормальная форма отличается от НФ тем, что всегда содержит термы только максимального ранга и дает однозначное представление логической функции. Рассмотрим варианты перехода от НФ к СНФ.

1. Преобразование ДНФ к ДСНФ производится по следующей схеме:

Пусть f_ДНФ = F₁, тогда f _ДСНФ = F₁x_i \/ F₁x_i, где x_i - переменная, которая не входит в данный терм F₁.

Пример Логическую функцию, заданную в ДНФ f(x₁,x₂,x₃) = \/ , преобразовать в ДСНФ.

Решение: обозначим F₁ = , F₂ = . В минтерме F₁ отсутствует переменная x₃, таким образом, необходимо выполнить следующее преобразование:

F^’₁ = F₁

В F₂ отсутствует переменная x₂, тогда необходимо выполнить следующее преобразование:

F^’₂ = F₂

В результате получим: f(x₁,x₂,x₃) =

2. Преобразование КНФ к КСНФ производится следующим образом.

Пусть f_КНФ = Ф₁, тогда f_КСНФ = Ф₁ \/ = (Ф₁ \/ x_i) (Ф₁ \/ ), где x_i – переменная, которая не входит в данный терм Ф₁.

Пример Логическую функцию, заданную в КНФ f(x₁,x₂,x₃) = , преобразовать в КСНФ.

Решение: обозначим Ф₁ = . В макстерме Ф₁ отсутствует переменная х₃, таким образом, необходимо выполнить следующее преобразование:

Ф^’₁= Ф₁ \/ = () \/ = ( )( ).

В результате получаем: f(x₁,x₂,x₃) = ( )( ).