Символът на Шефер и стрелата на Пиърс, връзката им с други логически операции
Стрелата на Пиърс (логическо ИЛИ-НЕ) на твърдениятаa иb е ново твърдение, което ще бъде вярно тогава и само ако и двете твърдения са неверни.
Знакът със стрелка на Пиърс е ↓
Стойностите на функциятастрелка на Пиърс са представени в таблицата:
Логическият елемент на операциятастрела на пробиване е:
| а | b | a↓b |
Стрелата на Пиърс е двоична логическа операция, булева функция над две променливи. Въведен от Чарлз Пърс през 1880-1881 г.
Стрелката на Пиърс, обикновено означавана с ↓, е еквивалентна на операцията NOR и се дава от следната таблица на истината:
Така твърдението „X ↓ Y“ означава „нито X, нито Y“. Промяната на местата на операндите не променя резултата от операцията.
| X | Y | X↓Y |
Штрихът на Schaeffer е двоична логическа операция, булева функция върху две променливи. Въведена от Хенри Шефър през 1913 г. (в някои източници наричана пунктираната линия на Чулков), чертата на Шефър, обикновено означавана , е еквивалентна на операцията NAND и се дава от следната таблица на истината:
| х | Y | XY |
Така твърдението X Y означава, че X и Y са несъвместими, т.е. не са верни едновременно. Промяната на местата на операндите не променя резултата от операцията. Простото число на Шефер, подобно на стрелката на Пиърс, формира основа за пространството на булеви функции на две променливи. Тоест, използвайки само щриха на Schaeffer, можете да изградите останалите операции. Например,
-отрицание
- дизюнкция
- съчетание
- константа 1
В електрониката това означава, че един типичен елемент е достатъчен, за да се реализира цялото разнообразие от схеми за преобразуване на сигнали, представящи логически стойности. От друга страна, този подход увеличава сложността на схемите, които изпълняват логически изрази и по този начин намалява тяхната надеждност. Пример за това е индустриалната серия 155.
Елементът 2I-NOT (2-in NAND), който реализира щриха на Schaeffer, е обозначен както следва (според стандартите ANSI):
В европейските стандарти е прието различно обозначение:
18.
Дизюнктивна нормална форма. Перфектна дизюнктивна нормална форма.
Перфектната дизюнктивна нормална форма (PDNF) е DNF, в която няма идентични елементарни връзки и всички връзки се състоят от един и същ набор от променливи, в които всяка променлива се среща само веднъж (евентуално с отрицание).
Перфектната конюнктивна нормална форма (PCNF) е CNF, в която няма идентични елементарни дизюнкции и всички дизюнкции се състоят от един и същ набор от променливи, в които всяка променлива се среща само веднъж (евентуално с отрицание).
Алгоритъм за получаване на sdnf според таблицата на истината.
1. Маркирайте онези редове от таблицата на истината, в последната колона на които има 1:
| X | Y | F(X,Y) |
| 1* | ||
| 1* |
2. За всеки маркиран редизпишете конюнкциятана всички променливи, както следва: ако стойността на някоя променлива в дадения реде равна на 1, тогава включететази променлива в конюнкцията, ако е равна на 0,тогава нейнотоотрицание:—заот 2-ри ред;- за3-ти ред.
3. Всичкисвържете получените съюзи в дизюнкция: (1*)
(Алгоритъм за редуциране на формулата на булева функция до SDNF)
Стъпка 1. Използвайки алгоритъма за конструиране на DNF, намираме формула B, която е DNF на формула A.
Стъпка 2. Зачеркнете в B всички елементарни връзки, които едновременно включват някаква променлива и нейното отрицание. Това е оправдано от еквивалентностите:
A&ØA º 0, B&0 º 0, CV0 º C.
Стъпка 3. Ако в елементарната конюнкция на формулата B някоя променлива или нейното отрицание се среща няколко пъти, тогава оставяме само едно от нейните появявания. Това е оправдано от закона за идемпотентност за връзката: A&A º A.
Стъпка 4. Ако елементарната връзка C на формула B не включва нито променливата x, нито нейното отрицание Øx, тогава, въз основа на 1-вия закон на разделяне, заместваме C с (C&x) V (C&Øx).
Стъпка 5. Във всяка елементарна конюнкция на формула B пренаредете конюнктивните членове така, че за всяко i (i = 1, . n) i-тата позиция да съдържа или променливата xi, или нейното отрицание Øxi.
Стъпка 6. Елиминирайте възможните повторения на конюнктивни термини съгласно закона за идемпотентност за дизюнкция: CVC º C.