Разложение ФАЛ по переменным

Итак мы установили, что для логической переменной и

Полностью разумеется, что и тогда только тогда, когда . Как следует, конъюнкция равна 1 на единственном наборе значений аргументов, когда , т.е. .

Аксиома о разложении ФАЛ. Неважно какая ФАЛ для хоть какого ( может быть представлена в виде:

,

где дизъюнкция берется по различным наборам значений аргументов Разложение ФАЛ по переменным .

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

Разглядим правую часть. Так как 0 когда

и 1, то

, т.е совпадает со значением левой части. Аксиома подтверждена.

К примеру, если функцию представить в виде разложения, к примеру, по переменной , то она Разложение ФАЛ по переменным будет смотреться последующим образом:

.

Пример. Функцию разложить по переменным а и b.

Т.к. функцию требуется разложить по двум переменным, как следует, она будет представлена 4-мя слагаемыми:

.

Несложно узреть, что способ разложения ФАЛ по переменным является обычным и действенным средством упрощения ФАЛ для представления их, к примеру, в ДНФ.

Главные Разложение ФАЛ по переменным классы ФАЛ

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

Пусть имеются логические функции и . Будем считать, что функции зависят от одних и тех же аргументов (этого Разложение ФАЛ по переменным можно добиться, добавив, по мере надобности, к аргументам неких из функций фиктивные аргументы). Функцию

именуют суперпозицией функций q и . Разглядим некий класс A логических функций.

Определение: Класс А именуется замкнутым, если для всяких функций и из А их суперпозиция содержится в А.

Приведем некие принципиальные примеры замкнутых классов.

Класс функций, сохраняющих Разложение ФАЛ по переменным константу нуль, т.е. таких функций, для которых имеет место f(0,0,0,...,0)=0. Обозначим этот класс . Разумеется, что при фиксированном n число функций этого класса составляет половину всех ФАЛ, т.е. .

Аналогично, класс функций, сохраняющих константу единица определен как класс функций, для которых f(1,1,...,1)=1. Этот класс, состоящий также из функций, обозначен эмблемой .

Определение: Функция именуется двоякой к Разложение ФАЛ по переменным функции , если имеет место равенство:

=

Принципы и законы двойственности.

Принципы двойственности можно записать последующим образом: Если имеет место тождество , где , то справедливо также тождество , т.е. если в каком-либо тождестве произвести обоюдную подмену знаков 0 и 1 (если они имеются) и операций V и &, то будет получено также тождество. Два Разложение ФАЛ по переменным тождества, связанные меж собой таким макаром, являются двоякими. Истинность самого принципа двойственности не доказывается, т.к. данный принцип является внутренним свойством алгебры логики (заключен в ее теоремах). Законы двойственности (аксиомы де-Моргана) устанавливают метод отыскания инверсных функций, представляющих из себя V и & 2-х переменных. Клод Шеннон предложил Разложение ФАЛ по переменным обобщение этих теорем, позволяющее искать инверсию хоть какой функции f{x}, где {x}= .

Закон двойственности, установленный Шенноном имеет вид: , где {x}= , { }= .

Т.е. инверсию хоть какой функции f({x}) можно получить обоюдной подменой переменных и их инверсий (i=1,2, .....n) и операций V и &.

Пример:

, тогда .

На основании закона двойственности просто показать, что

.

Определение Функция Разложение ФАЛ по переменным именуется самодвойственной, если она совпадает с двоякой для себя функцией, т.е. имеет место равенство

= .

Класс самодвойственных функций обозначим эмблемой S. Число членов этого класса равно , т.к. самодвойственная функция от n аргументов на сто процентов определяется на половине наборов значений аргументов.

Определение. Функция именуется линейной, если она представима в последующем Разложение ФАЛ по переменным виде:

,

где может принимать значения 0 либо 1. Класс линейных функций обозначим буковкой L. Число членов этого класса равно .

Набор значений аргументов не меньше набора значений аргументов , если меж всеми компонентами наборов и установлено соотношение . К примеру, набор не меньше набора , а наборы и несравненны.

Определение. Функция именуется однотонной, если для 2-ух наборов Разложение ФАЛ по переменным и таких, что имеет место равенство

.

Класс однообразных функций обозначим буковкой M. Число функций класса M оценивается асимптотически формулой

,

где - число однообразных функций алгебры логики, A- константа. Нижняя оценка получена Э.Н. Гильбертом, верхняя- В.К. Коробовым.

Определение. Функция именуется симметричной, если она не меняется при случайной перенумерации аргументов.

= ,

где - неважно какая перестановка Разложение ФАЛ по переменным аргументов .

Полные системы функций

Определение. Система функций алгебры логики именуется полной в классе R, если неважно какая функция , принадлежащая R, может быть представлена суперпозицией функций .

Определение. Система функций , являющаяся полной в классе R, именуется базисом. Либо: Базисом именуется полная система ФАЛ, при помощи которой неважно какая ФАЛ может быть представлена Разложение ФАЛ по переменным суперпозицией начальных функций.

Определение. Наименьшим базисом именуется таковой базис, для которого удаление хотя бы одной из функций , образующих этот базис, превращает систему функций в неполную.

В силу аксиомы 1.1, общее число разных функций, зависящих от n аргументов, равно . Потому существует очевидная полная система , состоящая из всех функций этого класса. Т.к. неважно Разложение ФАЛ по переменным какая ФАЛ может быть представлена в СНДФ либо СНКФ, то, как следует, будет верным и утверждение о полноте системы, состоящей из 3-х функций: отрицания, конъюнкции, и дизъюнкции.

Воcпользовавшись правилом де-Моргана: и лицезреем, что в СНДФ и СНКФ можно поменять конъюнкцию (&) через отрицание (ù ) и дизъюнкцию (Ú), либо дизъюнкцию через конъюнкцию и отрицание. Т Разложение ФАЛ по переменным.е. базисы { &, ù } и {Ú, ù} являются наименьшими.

Из того факта, что всякая ФАЛ представима в СНПФ следует, что базис {&, Å, ù } является полным. Из этой системы можно исключить отрицание, т.к. . Если в СНПФ произвести такую подмену, то получим представление функции через { Å, &, 1}. Такое представление носит заглавие полинома Жегалкина (полином по Å).

Аналогично, из соотношений 1.27 и 1.33 следует Разложение ФАЛ по переменным, что полную систему функций образуют {ù, &, º }. Не считая того, из последней системы можно исключить конъюнкцию (&), (т.к. ), а отрицание выразить через импликацию и константу нуля ( ). Т.е. { ®, 0 } также образуют базис.

Аксиома 1.7 Функция Шеффера образует в полную систему.

Подтверждение:

Имеем: ; .

Т.к. отрицание и конъюнкция образуют в огромном количестве полную систему Разложение ФАЛ по переменным, как следует и функция Шеффера образует полную систему.

Аксиома 1.8 Функция Пирса (Вебба) образует в полную систему.

Подтверждение:

Имеем: ; .

А потому что отрицание и дизъюнкция образуют полную систему, как следует и функция Пирса образует полную систему.

Аксиома Поста-Яблонского (без подтверждения) Для того чтоб система ФАЛ была полной, нужно Разложение ФАЛ по переменным и довольно, чтоб она содержала хотя бы одну функцию:

· не сохраняющую нуль;

· не сохраняющую единицу;

· не являющейся линейной;

· не являющейся однотонной;

· не являющейся самодвойственной.

Применим аксиому для подтверждения, к примеру, полноты системы функций {ù, Ú }. Функция ù (отрицание) не сохраняет константы нуля и единицы и не является однотонной. Функция Ú (дизъюнкция) не является Разложение ФАЛ по переменным самодвойственной и линейной.

В таблице 1.2 приведена принадлежность простых функций тому либо иному из классов, применяемых в аксиоме Поста-Яблонского.

Таблица 1.2

ФАЛ класс
L M S
fº0 + + +
f= + + +
f= +
f= + + + + +
f= +
f= + + + +
f= + +
f= + + +
f=
f= + +
f= + +
f= +
f= +
f= + +
f=
fº1 + +

Глава 2

Минимизация ФАЛ

Малая форма представления Разложение ФАЛ по переменным ФАЛ есть такая форма представления, которая содержит малое количество термов и переменных в термах. Малая форма представления ФАЛ не допускает никаких упрощений.

Пусть задана СНДФ:

;

Т.к. xÚx=x, то

Ú

Ú .

Сейчас преобразуем это выражение, используя распределительный и сочетательный законы для конъюнкции и дизъюнкции, и используя также теорему . Получаем:

=

= Ú Ú

Ú = = Ú

= .

Как Разложение ФАЛ по переменным видно, итог преобразований позволил значительно упростить заданную ФАЛ.

Определение. Конъюнкция именуется простой, если в этой конъюнкции любая переменная встречается менее 1-го раза.

Определение. Дизъюнкция простых конъюнкций именуется дизьюнктивной обычной формой (ДНФ либо НДФ).

Определение. Длиной ДНФ именуется число простых конъюнкций, образующих эту ДНФ.

Определение. Дизъюнктивная обычная форма, имеющая меньшую длину по сопоставлению со Разложение ФАЛ по переменным всеми другими ДНФ, эквивалентными данной функции, именуется кратчайшей ДНФ

2.1 Числовое и геометрическое представление ФАЛ.

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

.

Это означает, что данная функция воспринимает значение логической единицы на Разложение ФАЛ по переменным наборах, номера которых равны 1, 2, 4, 6, 11, 13, 14. Такую форму записи именуют числовой либо числовой формой представленияФАЛ.

Функцию 2-ух переменных можно интерпретировать как некую плоскость, заданную в системе координат - . Отложив на осях единичные отрезки, получим квадрат, верхушки которого соответствуют композициям логических переменных и . Это проиллюстрировано на рис.2.1.

Рис. 2.1

Из такового геометрического представления функций 2-ух переменных следует Разложение ФАЛ по переменным: две верхушки, принадлежащие одному и тому же ребру и именуемые примыкающими, “склеиваются” по переменной, меняющейся повдоль этого ребра.

Геометрическое представление для функций 3-х переменных можно выполнить в виде куба (рис. 2.2) Полностью разумеется, что ребра куба поглощают верхушки. Грани куба поглощают свои ребра и, как следует, верхушки.

Рис Разложение ФАЛ по переменным. 2.2

Функция 4 переменных представляется уже в виде “четырехмерного” куба, как это приведено на рис. 2.3.

В геометрическом смысле каждый набор может рассматриваться как n-мерный вектор, определяющий точку n-мерного места. Координаты вершин куба должны быть указаны в порядке, соответственном порядку перечисления переменных в записи функции. Отметив точками (крестиками либо другими знаками Разложение ФАЛ по переменным) верхушки, в каких функция воспринимает значение, равное единице, получим геометрическое представление ФАЛ


Рис. 2.3

Терм наибольшего ранга принято именовать 0-кубом (точкой) и обозначать . К примеру, для

Если два 0-куба из комплекса различаются только по одной переменной (координате), то они образуют 1-куб (отрезок) - .

={ 0 x 0}, где x - независящая переменная.

Если два 1-куба Разложение ФАЛ по переменным имеют общую независимую компоненту и различаются только по одной координате, то они образуют 2-куб. ( )

Таким макаром, для построения одномерного единичного куба берут два 0-куба (точки) и соединяют отрезком прямой. Двумерный куб (грань) выходит, если верхушки 2-ух 1-кубов соединить параллельными отрезками Трехмерный куб выходит при соединении соответственных вершин 2-ух двумерных кубов Разложение ФАЛ по переменным отрезком единичной длины. Геометрическое представление применяется при разработке способов минимизации с внедрением минимизирующих карт.


razgovoru-vseh-uchashihsya-i-pokazatel-togo-naskolko-interesen-uchitelyu-kazhdij-uchenik.html
razgovorxi-natalya-vasileva-natalya-nekrasova.html
razgranichenie-gosudarstvennoj-sobstvennosti-otchet-ob-osushestvlenii-polnomochij-po-upravleniyu-i-rasporyazheniyu-gosudarstvennoj.html