- •1.8. Анализ и синтез релейных управляющих схем
- •1.8.1. Релейные схемы. Связь их физической структуры и функций проводимости с алгеброй логики
- •1.8.2. Проектирование рс
- •1.9. Применение алгебры логики к анализу логических рассуждений
- •1.10. Замкнутость и полнота систем функций
- •1.10.1. Операции суперпозиции и замыкания. Полнота, базис системы функций
- •1.10.2 Функции, сохраняющие константы. Классы т0 и т1
- •1.10.3. Самодвойственность. Класс s
- •1.10.4. Монотонность. Класс м
- •1.10.5. Линейность. Класс l
- •1.10.6. Критерий Поста полноты системы функций в алгебре логики
- •Контрольные задания по теме
- •Операция суперпозиции.
- •Замыкание и полнота систем функций.
- •Предполные классы в алгебре логики
- •1.11. Анализ и синтез функциональных схем
- •Пример 1. В качестве фэ приняты { , , }. Произвести анализ фс, физическая структура которой дана на рис.1.19.
- •10. Оптимизировать фс из фэ { , , }, приведеную на рис.1.25.
- •Контрольные задания по теме применение алгебры логики к анализу и синтезу релейных и функциональных схем, проверке правильности высказываний
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 .
1.10.3. Самодвойственность. Класс 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). Поэтомух у — не самодвойственная функция.
в) Делим вектор истинности на две половины (00101011). Симметрично отразим первую половину относительно разделяющей черты — (0100) и инвертируем ее — (1011). Полученная последовательность совпала со второй половиной вектора истинности, следовательно, рассмотренная функция — самодвойственная.
Ответ: функции а) х и в) (00101011) — самодвойственны, функция б)ху — нет.
Рассмотрим самодвойственность элементарных функций с учетом числа переменных n в них.
n=0. Константы 0 и 1 не являются самодвойственными.
n=1. Тождество и отрицание входят в S (х S,х S).
n=2. Ни одна из элементарных функций не входит в S. Все двухместные самодвойственные функции f (х,у) имеют одну фиктивную переменную и сводятся к функциям х, у, х, у.
Следовательно, для получения самодвойственных функций, имеющих две существенных переменных, необходимо рассматривать n 3.
Для несамодвойственных функций справедлива
Лемма о несамодвойственной функции
Если f (х n) S , то из нее путем подстановки х их вместо переменных х1, х2 , ... , хn можно получить константу.
Доказательство. Из f (х n) S следует, что существует набор = (1, 2, ..., n ), для которого: f (1, 2, ... , n ) = f(1,2, ... , n ) = С. Подстановки выбираем по правилу: i (x)= x i , где i (x)= x при i =1, i (x) =x при i = 0. В итоге получаем функцию одной переменной F(x), которая принимает следующие значения: F(0) = f(1 (0), ... , n (0)) = C, F(1) = f(1 (1),..., n (1)) = C, т.е. является константой.
ЗАДАЧИ
1. Будут ли двойственными функции: а) и ; б) и ; в) (10100010) и (11100000) ; г) (10100010) и (10111010).
2. Найти с использованием принципа двойственности функции, двойственные к: а) ху уz ; б) ху (х z) у ; в) х у.
3. Доказать, что если f (х n) S, то в ее векторе значений будет равное число значений 1 и 0.
4. Будут ли самодвойственными функции: а) х ; б) х ; в) х у xz yz; г) (01001011); д) (1100101100101100) .
5. Доказать, что если f (х n) S, то f (х,х,...,х) (х,х).
6. Доказать, что все двухместные самодвойственные функции f(х, у) имеют ровно одну фиктивную переменную и сводятся к функциям х, у,х, у.
7. Доказать замкнутость класса S .
8. Доказать предполноту класса S (например, используя лемму о несамодвойственной функции и 3 — местную самодвойственную функцию f =(00010111) ).
9. Найти мощность класса S n.