Мои Конспекты
Главная | Обратная связь

...

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

Операции суперпозиции и замыкания. Полнота, базис системы функций





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Однотактные (не содержащие элементов памяти) дискретные логические устройства реализуют на выходе некоторый набор функций алгебры логики `Fm=(F1,F2,…,Fm), которые в каждый момент времени зависят только от состояния входов устройства n=(x1,x2,…,xn): `Fm = `Fm (n). Практически такие устройства проектируют и изготавливают из отдельных неделимых элементов, реализующих некоторый набор (систему) {f} элементарных функций алгебры путем присоединения выходов одних элементов ко входам других.

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

1. Задана система элементарных функций {f}. Какие выходные функции Fi можно получить, используя функции из {f}?

2. Задано множество выходных булевых функций {F} (в частности, равное всему множеству функций алгебры логики Р2). Какой должна быть исходная система элементарных функций {f}, обеспечивающая возможность получения на выходе любой из функций множества {F}?

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

Определение. Рассмотрим множество логических связок {F}, соответствующее некоторой системе функций {f}. Суперпозицией над {f} называется любая функция j, которую можно реализовать формулой над {F}.

Практически суперпозицию можно представить как результат подстановки функций из {f} в качестве аргументов в функции из этого же множества.

Пример 1. Рассмотрим систему функций {f}={f1(х) =`х , f2 (х,у)= х&у, f3(х,у)= хÚу }. Подставляя в функцию f3 (х,у) вместо первого аргумента х функцию f1(х), вместо второго — f2 (х,у), получим суперпозицию h(х,у)= f3 (f1(х), f2(х,у))=Ú х & у. Физическая реализация подстановки дана на рис.1.18.

Рис.1.18

Определение. Пусть М —некоторое множество функций алгебры логики(P2). Множество всех суперпозиций над М называется замыканием множества М и обозначается [М]. Получение [М]по исходному множеству М называется операцией замыкания. Множество М называется функционально замкнутым классом, если [М] = М. Подмножество m Í M называется функционально полной системой в М, если [m] = М.

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

Замечания. 1. Очевидно, любая система функций {f} является функционально полной в себе самой.

2. Без ограничения общности можно считать, что тождественная функция f(х), не изменяющая значений истинности переменных, изначально входит в состав любой системы функций.

Пример 2. Для рассмотренных ниже систем функций {f} выполнить следующие действия:

1) найти замыкание [f ],

2) выяснить, будет ли система {f} замкнутым классом,

3) найти функционально полные системы в {f}.

Решение.

I. {f}={0}. При подстановке функции {0} в саму себя получаем ее же, т.е. никаких новых функций не образуется. Отсюда следует: [f] = {f}. Рассмотренная система является функционально замкнутым классом. Функционально полная система в ней одна и равна всей {f}.

II. {f}={0,Ø }. Подстановка Ø (Ø х)дает тождественную функцию, которая формально не расширяет исходную систему. Однако при подстановке Ø (0) получим тождественную единицу — новую функцию, которой не было в исходной системе: Ø (0)=1. Применение всех других подстановок не приводит к появлению новых функций, например: ØØ 0=0, 0(Ø х)=0.

Таким образом, применение операции суперпозиции позволило получить более широкое по сравнению с исходным множество функций [f]={0,Ø ,1}. Отсюда следует строгое вхождение: {f} Ì [f]. Исходная система {f}не является функционально замкнутым классом. Кроме самой системы {f}других функционально полных систем в ней нет, поскольку в случае её сужения из одной функции f=0 нельзя путем подстановки получить отрицание, а из одной функции отрицания нельзя получить тождественный нуль.

III. {f} = {& ,Ú ,Ø }.Замыканием данной системы является все множество функций алгебры логики P2, так как формулу любой из них можно представить в виде ДНФ либо КНФ, в которых используются элементарные функции {f} = {& ,Ú ,Ø}. Данный факт является конструктивным доказательством полноты рассмотренной системы функций в P2: [f] =P2.

Поскольку в P2 содержится бесконечное множество других функций, отличных от {f} = {& ,Ú ,Ø }, то отсюда следует строгое вхождение: {f}Ì[f]. Рассмотренная система не является функционально замкнутым классом.

Помимо самой системы функционально полными в ней будут подсистемы {f}1 = {& ,Ø } и {f}2= {Ú ,Ø }. Это следует из того, что при помощи правил де Моргана функцию логического сложения Úможно выразить через {& ,Ø},а функцию логического умножения & — через {Ú, Ø}:

(х & у) = Ø (`хÚ`у), (х Ú у) = Ø (х &`у).

Других функционально полных подсистем в {f} нет.

Проверку полноты подсистемы функций {f}1 Ì {f}во всей системе {f}можно производить путем сведения {f}1 к другой, заведомо полной в {f}системе.

Неполноту подсистемы {f}1 в {f}можно проверить, доказав строгое вхождение [f1] Ì [f].

Определение. Подмножество m Í M называют функциональным базисом (базисом) системы М, если [m] = М , а после исключения из нее любой функции множество оставшихся не полно в М .

Замечание. Базисами системы функций {f} являются все ее функционально полные подсистемы {f}1, которые невозможно уменьшить без потери полноты в {f}.

Пример 3. Для всех систем, рассмотренных в Примере 2, найти базисы.

Решение.В случаях 1 и 2 функционально полными являются только сами системы и сузить их невозможно. Следовательно, они же являются и базисами.

В случае 3 есть две функционально полные в {f}подсистемы {f}1 = {&,Ø } и {f}2={Ú,Ø }, которые невозможно сократить без потери полноты. Они будут базисами системы {f} = {&,Ú,Ø}.

Определение. Пусть система {f}является замкнутым классом. Ее подмножество {f}1 Ì {f}называют предполным классом в {f}, если {f}1 не полно в {f} ([f1] Ì [f]), а для любой функции jиз системы{f}, не входящей в {f}1(jÎ{f} \ {f}1) справедливо: [j È {f}1] = [f], т.е. прибавление jк {f}1 делает ее полной в {f}.

Задачи

1. Проверить замкнутость множеств функций:

а) {Ø }; б) {1, Ø }; в) {(0111); (10)};г) {(11101110); (0110)};д) {(0001); (00000001); (0000000000000001); … }.

2. Проверить полноту систем функций в P2:

а) {0,Ø }; б) {(0101) , (1010) }; в ) {¯ }; г ) {(0001) , (1010) }.

3. Найти замыкание системы функций и ее базис:

а) {0 , 1 , Ø }; б) {(1000) , (1010), (0101) }; в) {(0001) , (1110), ( 10) }; г ) {(1010) , (0001), (0111) }.

1.10.2 Функции, сохраняющие константы. Классы Т0 и Т1

Определение. Функция f(`хn) сохраняет 0, если f (0,..., 0) = 0. Функция f(n) сохраняет 1, если f(1, ... , 1) = 1.

Множества функций n переменных, сохраняющих 0 и 1, обозначают, соответственно, Т0nи Т1n. Все множества функций алгебры логики, сохраняющих 0 и 1, обозначают Т0 и Т1. Каждое из множеств Т0и Т1 является замкнутым предполным классом в Р2.

Из элементарных функций в Т0и Т1одновременно входят, например, &и Ú. Принадлежность любой функции к классам Т0 , Т1 можно проверить по первому и последнему значению ее вектора значений в таблице истинности либо непосредственной подстановкой нулей и единиц в формулу при аналитическом задании функции.

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

 

ЗАДАЧИ

1.Проверить принадлежность к классам Т0 и Т1 функций:

а) обощенного сложения, б) обощенного умножения, в) констант, г) ху Ú yz , д) х ® у ® ху , е) х Å у , ж)( х1ÅÅ хn) ® ( y1ÅÅ ym) при n,mÎ N.

2. Доказать замкнутость каждого из классов Т0 и Т1.

3. Доказать, что если f (n) ÏТ0, то из нее путем дублирующей подстановки можно получить константу 1 либо отрицание.

4. Доказать, что если f (n) ÏТ1 , то из нее путем дублирующей подстановки можно получить константу 0 либо отрицание.

5. Доказать предполноту каждого из классов Т0 и Т1 (например, сведением дополненной системы к {f} = {& ,Ú ,Ø } ).

6. Найти мощность классов Т0nи Т1n.

 

Самодвойственность. Класс S

Функции f (n) и g (`х n) двойственны (f = g*), если они принимают противоположные значения на обратных наборах значений переменных f(n) =`g (n*).

Определение. Функция f (`хn) называется самодвойственной, если f = f *

Множество самодвойственных функций n переменных обозначают Sn, а все множество самодвойственных функций алгебры логики — S. Это множество является замкнутым предполным классом в Р2.

Из определения самодвойственных функций несложно показать, что первая половина их векторов истинности после симметричного отражения слева—направо и последующего инвертирования должна совпадать со второй половиной.

Пример. Проверить самодвойственность функций:

а) Øх , б)¯ у , в) (00101011).

Решение.Проверку производим по векторам истинности с использованием описанного выше их свойства для самодвойственных функций.

а) Делим вектор истинности функции Øх на две половины: (1÷ 0). Поскольку в первой половине один символ (1), то симметричное отражение дает его же. Инвертируя его, получим символ 0, который совпадает со второй половиной вектора. Следовательно, отрицание — самодвойственная функция.

б) Вектор истинности функции¯ у делим на две половины: (00÷ 10). Симметричное отражение первой половины относительно разделяющей черты не меняет ее. После инвертирования получим последовательность (11), которая не совпадает со второй половиной вектора истинности (10). Поэтому¯ у — не самодвойственная функция.

в) Делим вектор истинности на две половины (0010÷1011). Симметрично отразим первую половину относительно разделяющей черты — (0100) и инвертируем ее — (1011). Полученная последовательность совпала со второй половиной вектора истинности, следовательно, рассмотренная функция — самодвойственная.

Ответ: функции а) Øх и в) (00101011) — самодвойственны, функция б)¯у — нет.

Рассмотрим самодвойственность элементарных функций с учетом числа переменных n в них.

n=0. Константы 0 и 1 не являются самодвойственными.

n=1. Тождество и отрицание входят в S (х ÎS,Øх ÎS).

n=2. Ни одна из элементарных функций не входит в S. Все двухместные самодвойственные функции f (х,у)имеют одну фиктивную переменную и сводятся к функциям х, у, Øх, Øу.

Следовательно, для получения самодвойственных функций, имеющих две существенных переменных, необходимо рассматривать n ³ 3.

Для несамодвойственных функций справедлива

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.