Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрации Техника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ? Влияние общества на человека Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления	Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ Совершенно нормальные формы. ⇐ ПредыдущаяСтр 3 из 4Следующая ⇒   Т.к. переключательные функции могут иметь несколько ДИФ и КНФ, то последние не обеспечивают однозначность представления переключательнй функции. Однозначность возможна при записи ее в совершенных нормальных формах, которые получают с помощью таблиц истинности ЦА.     Табл.3   N Набора	Аргументы			F(X1,X2,X3)
Х1	Х2	Х3
0	0	0	0	0
1	0	0	1	Минтермы 1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	Макстермы 0
7	1	1	1	1

СНДФ представления переключательных функций – это запись функции в виде дизъюнктивной, (сумма произведений) для которых значение функции равно 1, т.е. в виде дизъюнкции минтермов. Каждая конъюнкция этой дизъюнкции включает каждую переменную только один раз в прямом или инверсном виде.

 

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

 

1. Составить минтермы для строк таблицы истинности, для которой ПФ= 1. Если значение переменной Хi = 0, то в минтерме записывается отрицание этой переменной.
2. Записать дизъюнкцию составленных минтермов, которая и представляет ПФ в СДНФ.

Это правило – правило записи ПФ по единицам для Табл.3

 

 

F_СДНФ (Х_1,Х₂,Х₃) = Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃ (6)

 

 

СДНФ – это запись функции в виде конъюнкции дизъюнкции (произведения суммы), для которых значение функции = 0.

Алгоритм перехода -  от таблицы ПФ к ее СКНФ.

 

1. Составить макстермы для строк табл. истинности, на которых функция = 0. Если значение переменной Х_i= 1, то в макстерме записывается отрицание этой переменной

2. Записать конъюнкцию составных макстермов, которая и есть ПФ в СДНФ.

Это правило – правило записи ПФ по нулям.

 

Для табл. 3

F_СДНФ(Х_1,Х₂,Х₃) = (Х₁^Х₂^Х₃) (Х₁^Х₂^Х₃) (Х₁^Х₂^Х₃) (Х₁^Х₂^Х₃)          (7)

Применив операцию инвертирования к (7), получим связь между СДНФ и СКНФ ПФ

 

(8)

                                                                                                                                

 

Не полностью определенные ПФ  - ПФ, для которых не определено их значение хотябы на одном наборе переменных (аргументов)

Доопределение такой ПФ, (т.е. положение = 0 или 1) производится на разных этапах обработки информации в зависимости от конкретной задачи.

 

Иногда при доопределении рассматривают 2 варианта СКНФ и 2 варианта СДНФ.

Конституенты СДНФ и СКНФ, соответствующие наборам аргументов, на которых ПФ не определена, называют условными.

Конституенты разложения 1, вошедшие в СДНФ, и Конституенты разложения 0, вошедшие в СКНФ, называют обязательными, е\а не вошедшие - запрещенными коституентами.

 

СДНФ и СКНФ широко используют при синтезе и анализе ложных схем ЭВМ.

 

Переход от нормальных к составным формам ПФ.

Аналитический способ

СДНФ и СКНФ содержат, в отличии от нормальной, дизъюнкции и конъюнкции только максимального ранга r.

Это дает возможность производить переход по следующим правилам.

 

Правило 1.    для перехода от произвольной ДНФ К- го ранга (К<r) к СДНФ r- го ранга необходимо конъюнкции ДНФ последовательно умножать на логическое выражение (Х_i^X_i) где,

                X_i – она из переменных, не вошедшая в данную конъюнкцию.

                Число таких преобразований для каждой конъюнкции д.б. (r-k)

Пример. Преобразовать ДНФ

                           

            F_СДНФ(Х_1,Х₂,Х₃) = Х₁*Х₂^Х₃ в СДНФ

             R = 3-го ранга

А) Х₁*Х₂(Х₃^Х₃) = Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃

Б) Х₃(Х₁^Х₁)= Х₃*Х₁^Х₃*Х₁ – 1-е преобразование

В) (Х₃*Х₁^Х₃*Х₁)(Х₂^Х₂) = Х1*Х₂*Х₃^Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃ = 2-е преобразование.

Г) F_СДНФ(Х₁,Х₂,Х₃) = Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃

Правило 2:  Для перехода от произвольной КНФ к СКНФ r-го ранга необходимо дизъюнкции, входящие в КНФ к-го ранга последовательно симулировать с логическим выражением Х_i*Х_i (Х^0) = Х

Где Х_i - одна из переменных, не входящая в данную дизъюнкцию. Число преобразований для каждой дизъюнкции д.б. (r-k)