Студопедия — Аналитическое представление переключательных функций
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

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

,

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

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

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

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

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

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

Например, F1 = x1x2x3.

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

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

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

Пример

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

х1 х2 х3
       
       
       
       
       
       
       
       

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

f(x1 x2 x3) = \/1 F(1,3,4,6) или f(x1 x2 x3) = &1 Ф(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)

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

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

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

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

xi, если ai = 1,

= , если ai = 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ДНФ = F1, тогда f ДСНФ = F1xi \/ F1xi, где xi - переменная, которая не входит в данный терм F1.

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

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

F1 = F1

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

F2 = F2

В результате получим: f(x1,x2,x3) =

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

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

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

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

Ф1= Ф1 \/ = () \/ = ( )( ).

В результате получаем: f(x1,x2,x3) = ( )( ).







Дата добавления: 2015-09-07; просмотров: 2097. Нарушение авторских прав; Мы поможем в написании вашей работы!



Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Вопрос. Отличие деятельности человека от поведения животных главные отличия деятельности человека от активности животных сводятся к следующему: 1...

Расчет концентрации титрованных растворов с помощью поправочного коэффициента При выполнении серийных анализов ГОСТ или ведомственная инструкция обычно предусматривают применение раствора заданной концентрации или заданного титра...

МЕТОДИКА ИЗУЧЕНИЯ МОРФЕМНОГО СОСТАВА СЛОВА В НАЧАЛЬНЫХ КЛАССАХ В практике речевого общения широко известен следующий факт: как взрослые...

СИНТАКСИЧЕСКАЯ РАБОТА В СИСТЕМЕ РАЗВИТИЯ РЕЧИ УЧАЩИХСЯ В языке различаются уровни — уровень слова (лексический), уровень словосочетания и предложения (синтаксический) и уровень Словосочетание в этом смысле может рассматриваться как переходное звено от лексического уровня к синтаксическому...

Плейотропное действие генов. Примеры. Плейотропное действие генов - это зависимость нескольких признаков от одного гена, то есть множественное действие одного гена...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия