Rang 3 AND/OR/NOT используется в нормальной дезъюнктивной форме доказательство: карта Карно (см. 2.6) все элементарные конъюнкции ранга равного количеству переменных функции покрывают все клетки таким образом определяя функцию для всех наборов.
Rang 2 AND/NOT X OR Y = (X# AND Y#)# OR/NOT X AND Y = (X# OR Y#)# задача сведена к AND/OR/NOT
Rang 1 NOR NOT X = X NOR X X AND Y = X# NOR Y# = (X NOR X) NOR (Y NOR Y) X OR Y = (X# AND Y#)# задача сведена к AND/OR/NOT NAND NOT X = X NAND X X NOR Y = (X# NOR #Y)# задача сведена к NOR
Вообще для двоичной логики базис должен обладать следующими свойствами: Функции входящие в него должны иметь веcь набор следующих свойств: (т.е. одна может иметь одно свойство, другая пару других, но весь базис должен иметь все свойства): не сохранять 0 функция сохраняет 0, если F(0,0,...,0) = 0 x1 x2 | F ------+--- 0 0 | 0 0 1 | X 1 0 | X 1 1 | X не сохранять 1 функция сохраняет 1, если F(1,1,...,1) = 1 [OR сохраняет и 0 и 1] [XOR cохраняет 0] x1 x2 | F ------+--- 0 0 | X 0 1 | X 1 0 | X 1 1 | 1 не cамодвойственны Функция самодвойственна, если F(x1,x2,..,xN) = F(x1#,x2#,..,xN#)# [NOT самодвойственная] x1 x2 | F ------+--- 0 0 | A 0 1 | B 1 0 | B# 1 1 | A# не линейны Функция линейна, если ее можно представить в виде F = a0 + a1x1 + ... + aNaN [Тождественные 0,1,x1,x1#,x2,x2#, XOR и XNOR линейные] (линейность в арифметическом смысле) не монотонны Функция монотонна если она все время увеличивается или уменьшается. Упорядоченность для рабочих наборов определяется так: a = (a1,...,aN) b = (b1,...,bN) a <= b, если ai <= bi, для всех i [OR монотонная, XOR нет]
Пример диаграмм для монотонности Для случая 2х переменных (1-2-1):
Для случая 3х переменных (1-3-3-1):
В случае 3 переменных (1-4-6-4-1) плоскости не хватает Приходиться расщеплять зоны.
Доказательство приводить не будем.
Две функции алгебры логики называются двойственными если одна вытекает из другой путем замены всех коньюнкций на дизъюнкции и дизъюнкций на конъюнкции. __ __ __ _____________ F(x1,x2,...,xN) = G(x1,x2,..Xn) Пример: _ для F(a,b) = a * b + a * b двойственной будет функция: _ F'(a,b) = (a + b) * (a + b) Примеры двойственных функций: 0 и 1 AND и OR XOR и EQV NAND и NOR < и => (IMP и Запрет) > и <= (IMP и запрет)
Две функции алгебры логики называются инверсными, если она вытекает из другой путем замены операций на двойственные и инверсией всех переменных. Пример: _ для F(a,b) = a * b + a * b инверсная функция будет: _ _ _ _ F(a,b) = (a + b) * (a + b)
THIS SECTION IS UNDER CONSTRUCTION
--------------------------------------------------------------------------------- x1 x2 сохр сохр само 00 01 10 11 Имя 0 1 линейна двойств монотонна --------------------------------------------------------------------------------- 0 0 0 0 0 1 0 1 0 1 0 0 0 1 AND 1 1 0 0 1 0 0 1 0 x1>x2 1 0 0 0 0 0 0 1 1 x1 1 1 1 1 1 0 1 0 0 x2>x1 1 0 0 0 0 0 1 0 1 x2 1 1 1 1 1 0 1 1 0 XOR 1 0 1 0 0 0 1 1 1 OR 1 1 0 0 1 1 0 0 0 NOR 0 0 0 0 0 1 0 0 1 XNOR 0 1 1 0 0 1 0 1 0 ~x2 0 0 1 1 0 1 0 1 1 x2->x1 0 1 0 0 0 1 1 0 0 ~x1 0 0 1 1 0 1 1 0 1 x1->x2 0 1 0 0 0 1 1 1 0 NAND 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 --------------------------------------------------------------------------------- Базис должен содержать 0 во всех классах. Из этого следует что можно сделать базис из: импликации и константы 0