Изключителен или използван в режим. Пример за решаване на задачата XOR - изключително ИЛИ

Изключителен или използван в режим.  Пример за решаване на задачата XOR - изключително ИЛИ
Изключителен или използван в режим. Пример за решаване на задачата XOR - изключително ИЛИ

Всичко цифрови микросхемисе състоят от едни и същи логически елементи - "градивните елементи" на всеки цифров възел. Ето за това ще говорим сега.

Логически елемент- Това е схема, която има няколко входа и един изход. Всяко състояние на сигналите на входовете отговаря на определен сигнал на изхода.

И така, какви са елементите?

Елемент "И" (И)

В противен случай се нарича "конюнктор".

За да разберете как работи, трябва да начертаете таблица, която изброява изходните състояния за всяка комбинация от входни сигнали. Такава таблица се нарича таблица на истината". Таблиците на истината се използват широко в цифровите технологии за описание на работата на логическите схеми.

Ето как изглежда елементът И и неговата таблица на истината:

Тъй като ще трябва да общувате както с руска, така и с буржоазна техника. документация, ще дам условни графични означения (УГО) на елементи както по наши, така и по не наши стандарти.

Разглеждаме таблицата на истината и изясняваме принципа в мозъка. Не е трудно да го разберете: единица на изхода на елемента „И“ се появява само когато единиците се прилагат и към двата входа. Това обяснява името на елемента: единиците трябва да бъдат И на един И на другия вход.

Ако погледнете малко по-различно, тогава можете да кажете следното: изходът на елемента „И“ ще бъде нула, ако поне един от неговите входове е нула. Помним. Продължавай.

ИЛИ елемент (ИЛИ)

С други думи името му е "дизюнктор".

Възхищаваме се на:

Отново името говори само за себе си.

Единица се появява на изхода, когато единица е приложена към един ИЛИ към друг ИЛИ към двата входа едновременно. Този елемент може също да се нарече елемент „И“ за отрицателна логика: неговият изход е нула само ако нули са приложени към единия и втория вход.

Елемент "НЕ" (НЕ)

По-често се нарича "инвертор".

Трябва ли да кажете нещо за работата му?

NAND елемент (NAND)

NAND елементът работи точно по същия начин като AND, само изходният сигнал е напълно противоположен. Когато елементът „И“ трябва да има „0“ на изхода, елементът „И-НЕ“ има единица. И обратно. Лесно е да се разбере от еквивалентна схемаелемент:

ИЛИ-НЕ (НИТО) елемент

Същата история - елементът "ИЛИ" с инвертор на изхода.

Следващият другар е малко по-хитър:
Изключително ИЛИ (XOR) елемент

Той е такъв:

Операцията, която изпълнява, често се нарича "събиране по модул 2". Всъщност цифровите суматори са изградени върху тези елементи.

Нека да разгледаме таблицата на истината. Кога е изходът на уреда? Точно така: когато входовете са различни сигнали. На единия - 1, на другия - 0. Ето колко е хитър.

Еквивалентната схема е нещо подобно:

Не е необходимо да го запомняте.

Всъщност това са основните логически елементи. На тяхна база са изградени абсолютно всякакви цифрови микросхеми. Дори любимият ви Pentium 4.

И накрая - няколко микросхеми, които съдържат цифрови елементи. В близост до щифтовете на елементите са посочени номерата на съответните крака на микросхемата. Всички интегрални схеми, изброени тук, имат 14 крака. Захранването се подава към щифтове 7 (-) и 14 (+). Захранващо напрежение - виж таблицата в предходния параграф.

В булевата алгебра, на която се основава цялата цифрова технология, електронни елементитрябва да извърши определени действия. Това е така наречената логическа основа. Ето три основни стъпки:

    ИЛИ - логическо добавяне ( дизюнкция) - ИЛИ;

    И - логическо умножение ( съчетание) - И;

    НЕ - логическо отрицание ( инверсия) - НЕ.

Нека вземем за основа положителната логика, където високото ниво ще бъде "1", а ниското ниво ще се приеме като "0". За да можете по-ясно да разгледате изпълнението на логическите операции, има таблици на истинност за всяка логическа функция. Веднага е лесно да се разбере, че изпълнението на логическите функции "и" и "или" предполага броят на входните сигнали поне два, но може да има повече.

Логически елемент I.

Фигурата показва таблицата на истината на елемента " И" с два входа. Ясно се вижда, че на изхода на елемента се появява логическа единица само ако има единица на първия вход Ина втория. В останалите три случая изходът ще бъде нула.

Вход X1 Вход X2 Изход Y
0 0 0
1 0 0
0 1 0
1 1 1

На електрически схемилогическият елемент "И" се обозначава по следния начин.

В чужди схеми обозначението на елемента "И" има различен стил. Накратко се нарича И.

Логически елемент ИЛИ.

елемент " ИЛИ" с два входа работи малко по-различно. Логически на първия вход е достатъчен илина втория като изход ще бъде логическа единица. Две единици също ще дадат единица в изхода.

Вход X1 Вход X2 Изход Y
0 0 0
1 0 1
0 1 1
1 1 1

В диаграмите елементът "ИЛИ" е изобразен по следния начин.

На чужди диаграми той е изобразен малко по-различно и се нарича елемент ИЛИ.

Логическият елемент е НЕ.

Елемент, който изпълнява функцията на обръщане " НЕима един вход и един изход. Обръща нивото на сигнала. Ниският потенциал на входа дава висок потенциал на изхода и обратно.

Въведете X Изход Y
0 1
1 0

Ето как е показано на диаграмите.

В чуждестранна документация елементът "НЕ" е изобразен по следния начин. Наричат ​​го накратко НЕ.

Всички тези елементи в интегрални схемимогат да се комбинират в различни комбинации. Това са елементите: И-НЕ, ИЛИ-НЕ и по-сложни конфигурации. Време е да поговорим за тях.

Логически елемент 2I-НЕ.

Нека разгледаме няколко реални логически елемента на примера на серия транзисторно-транзисторна логика (TTL) K155 с ниска степен на интеграция. Фигурата показва някога много популярния чип K155LA3, който съдържа четири независими елемента 2I - НЕ. Между другото, с него можете да сглобите най-простия маяк на микросхема.

Числото винаги означава броя на входовете на гейта. В случая това е двувходов елемент "И", чийто изходен сигнал е инвертиран. Обърнат, което означава, че "0" става "1" и "1" става "0". Да обърнем внимание на кръгът на изходите е символ на инверсия. В същата серия има елементи 3I-NOT, 4I-NOT, което означава елементи "И" с различен брой входове (3, 4 и т.н.).

Както вече разбрахте, един елемент от 2I-NOT е изобразен така.

Всъщност това е опростено изображение на два комбинирани елемента: елемент 2I и елемент NOT на изхода.

Чуждестранно обозначение на елемента И-НЕ (в този случай 2I-НЕ). Наречен NAND.

Таблица на истината за елемент 2I-НЕ.

Вход X1 Вход X2 Изход Y
0 0 1
1 0 1
0 1 1
1 1 0

В таблицата на истината на елемента 2I - НЕ виждаме, че благодарение на инвертора се получава картина, която е противоположна на елемента "И". За разлика от три нули и една единица, имаме три единици и една нула. Елементът И-НЕ често се нарича елемент на Шефер.

Логически елемент 2ИЛИ-НЕ.

Логически елемент 2ИЛИ - НЕпредставен в серията K155 от чипа 155LE1. Съдържа четири независими елемента в един корпус. Таблицата на истината също се различава от веригата "ИЛИ" чрез инвертиране на изходния сигнал.

Таблица на истинност за логически елемент 2ИЛИ-НЕ.

Вход X1 Вход X2 Изход Y
0 0 1
1 0 0
0 1 0
1 1 0

Изображение на диаграмата.

По чужд начин се изобразява по следния начин. Наречен като НИТО.

Имаме само един висок потенциал на изхода, поради подаването на нисък потенциал към двата входа едновременно. Тук, както във всяка друга електрическа схема, кръгът на изхода означава инверсия на сигнала. Тъй като схемите И - НЕ и ИЛИ - НЕ са много често срещани, всяка функция има своя собствена символ. Функцията И НЕ се обозначава с иконата " & ", а функцията ИЛИ НЕ е с иконата " 1 ".

За единичен инвертор таблицата на истината вече е дадена по-горе. Може да се добави, че броят на инверторите в един корпус може да бъде до шест.

Логически елемент "изключително ИЛИ".

Обичайно е да се отнася към броя на основните логически елементи елемент, който изпълнява функцията "изключително ИЛИ". В противен случай тази функция се нарича "нееквивалентност".

Висок изходен потенциал възниква само ако входните сигнали не са еднакви. Тоест един от входовете трябва да е единица, а другият нула. Ако на изхода на логическия елемент има инвертор, тогава се изпълнява обратната функция - „еквивалентност“. Висок потенциал на изхода ще се появи при еднакви сигнали и на двата входа.

Таблица на истината.

Вход X1 Вход X2 Изход Y
0 0 0
1 0 1
0 1 1
1 1 0

Тези логически елементи намират своето приложение в суматорите. "Изключително ИЛИ" е изобразено на диаграмите със знак за равенство пред единицата " =1 ".

По чужд начин се нарича "изключително ИЛИ". XORи на диаграмите те рисуват така.

В допълнение към горните логически елементи, които много често изпълняват основни логически функции, се използват елементи, комбинирани в различни комбинации. Ето, например, K555LR4. Нарича се много сериозно 2-4I-2OR-NOT.

Неговата таблица на истината не е дадена, тъй като микросхемата не е основен логически елемент. Такива микросхеми изпълняват специални функции и са много по-сложни от горния пример. Логическата основа включва и прости елементи "И" и "ИЛИ". Но те се използват много по-рядко. Може да възникне въпросът защо тази логика се нарича транзистор-транзистор.

Ако погледнете в референтната литература диаграма на, да речем, елемент 2I - НЕ от микросхемата K155LA3, тогава можете да видите няколко транзистора и резистори там. Всъщност в тези микросхеми няма резистори или диоди. Само транзисторите се отлагат върху силициев кристал чрез шаблон, а функциите на резистори и диоди се изпълняват от емитерни преходи на транзистори. Освен това многоемитерните транзистори се използват широко в TTL логиката. Например на входа на елемент 4I има четири емитер

Битът е най-малката единица информация, защото съхранява една от двете стойности - 0 (False) или 1 (True). False и True, преведени на руски, са съответно false и true. Тоест, една битова клетка може да бъде едновременно само в едно състояние от възможните две. Нека ви напомня, че двете възможни състояния на битовата клетка са 1 и 0.
Има определени операции за манипулиране на битове. Тези операции се наричат ​​логически или булеви операции, по името на един от математиците - Джордж Бул (1815-1864), допринесъл за развитието на тази област на науката.
Всички тези операции могат да бъдат приложени към всеки бит, независимо дали има стойност 0 (нула) или 1 (едно). По-долу са основните логически операции и примери за тяхното използване.

Логическа операция И (И)

И нотация: &

Логическата операция И се извършва върху два бита, нека ги наречем a и b. Резултат от изпълнението логическа операцияИ ще бъде равно на 1, ако a и b са равни на 1, а във всички останали (други) случаи резултатът ще бъде равен на 0. Разглеждаме таблицата на истината на логическата операция and.

а (бит 1) b (бит 2) a(бит 1) & b(бит 2)
0 0 0
0 1 0
1 0 0
1 1 1

Логическа операция ИЛИ (ИЛИ)

ИЛИ нотация: |

Логическата операция ИЛИ се извършва върху два бита (a и b). Резултатът от изпълнението на логическа операция ИЛИ ще бъде 0, ако a и b са 0 (нула), а във всички други (други) случаи резултатът е 1 (едно). Разглеждаме таблицата на истината на логическата операция ИЛИ.

а (бит 1) b (бит 2) a(бит 1) | b (бит 2)
0 0 0
0 1 1
1 0 1
1 1 1

Логическа операция изключващо ИЛИ (XOR).

Нотация XOR: ^
Логическата операция XOR се извършва върху два бита (a и b). Резултатът от изпълнението на логическа операция XOR ще бъде равен на 1 (едно), ако един от битовете a или b е равен на 1 (едно), във всички останали случаи резултатът е 0 (нула). Разглеждаме таблицата на истината на логическата операция XOR.

а (бит 1) b (бит 2) a(бит 1) ^ b(бит 2)
0 0 0
0 1 1
1 0 1
1 1 0

Логическа операция НЕ (не)

НЕ нотация: ~
Логическата операция НЕ се извършва върху един бит. Резултатът от тази логическа операция директно зависи от състоянието на бита. Ако битът е бил в състояние нула, тогава резултатът от изпълнението на NOT ще бъде равен на единица и обратно. Разглеждаме таблицата на истината на логическата операция НЕ.

а (бит 1) ~a(битово отрицание)
0 1
1 0

Запомнете тези 4 логически операции. Използвайки тези логически операции, можем да получим всеки възможен резултат. Прочетете повече за използването на логически операции в C++.

Сервизно задание. Онлайн калкулаторът е предназначен за конструиране на таблица на истинност за логически израз.
Таблица на истината - таблица, съдържаща всички възможни комбинации от входни променливи и съответните им изходни стойности.
Таблицата на истината съдържа 2n реда, където n е броят на входните променливи, а n+m са колони, където m са изходните променливи.

Инструкция. Когато въвеждате от клавиатурата, използвайте следните конвенции: Например, логическият израз abc+ab~c+a~bc трябва да бъде въведен така: a*b*c+a*b=c+a=b*c
За да въведете данни под формата на логическа диаграма, използвайте тази услуга.

Правила за въвеждане на логическа функция

  1. Използвайте знака + вместо v (дизюнкция, ИЛИ).
  2. Преди логическата функция не е необходимо да указвате обозначението на функцията. Например, вместо F(x,y)=(x|y)=(x^y) просто ще въведете (x|y)=(x^y) .
  3. Максималният брой променливи е 10.

Проектирането и анализът на компютърни логически схеми се извършва с помощта на специален раздел на математиката - алгебрата на логиката. В алгебрата на логиката могат да се разграничат три основни логически функции: "НЕ" (отрицание), "И" (конюнкция), "ИЛИ" (дизюнкция).
За да се създаде всяко логическо устройство, е необходимо да се определи зависимостта на всяка от изходните променливи от текущите входни променливи, такава зависимост се нарича превключваща функция или функция на логическата алгебра.
Функция на логическата алгебра се нарича напълно дефинирана, ако са дадени всичките 2 n от нейните стойности, където n е броят на изходните променливи.
Ако не всички стойности са дефинирани, функцията се нарича частично дефинирана.
Едно устройство се нарича логическо, ако неговото състояние е описано с помощта на функция от алгебрата на логиката.
Използват се следните методи за представяне на функцията на логическата алгебра:

  • словесното описание е форма, която се използва в началния етап на проектиране и има условно представяне.
  • описание на функцията на алгебрата на логиката под формата на таблица на истината.
  • описание на функцията на алгебрата на логиката под формата на алгебричен израз: използват се две алгебрични форми на FAL:
    а) DNF - дизюнктивна нормална формае логическата сума на елементарните логически продукти. DNF се получава от таблицата на истината съгласно следния алгоритъм или правило:
    1) онези редове от променливи, за които изходната функция =1 са избрани в таблицата.
    2) за всеки ред от променливи се записва логически продукт; а променливите =0 се записват с инверсия.
    3) полученият продукт е логично обобщен.
    Fdnf = X 1 * X 2 * X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
    Казва се, че DNF е перфектен, ако всички променливи имат еднакъв ранг или ред, т.е. всяка работа трябва задължително да включва всички променливи в пряка или обратна форма.
    б) CNF - конюнктивна нормална формае логическият продукт на елементарни логически суми.
    CNF може да се получи от таблицата на истината, като се използва следният алгоритъм:
    1) изберете набори от променливи, за които изходната функция е = 0
    2) за всеки набор от променливи записваме елементарна логическа сума, а променливите =1 се записват с инверсия.
    3) получените суми се умножават логически.
    Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
    CNF се нарича перфектенако всички променливи имат еднакъв ранг.
От алгебричната форма може да се конструира верига на логическо устройство, използвайки логически порти.

Фигура 1 - Схема на логическо устройство

Дефинирани са всички операции на алгебрата на логиката таблици на истинатастойности. Таблицата на истината определя резултата от извършване на операция за всички възможни x логически стойности на оригиналните изрази. Броят на опциите, които отразяват резултата от прилагането на операциите, ще зависи от броя на изразите в логическия израз. Ако броят на изявленията в логическия израз е N, тогава таблицата на истината ще съдържа 2 N реда, тъй като има 2 N различни комбинации от възможни стойности на аргументи.

Операция НЕ - логическо отрицание (инверсия)

Логическата операция НЕ се прилага към един аргумент, който може да бъде прост или сложен логически израз. Резултатът от операцията НЕ е следният:
  • ако оригиналният израз е верен, тогава резултатът от неговото отрицание ще бъде неверен;
  • ако оригиналният израз е фалшив, тогава резултатът от неговото отрицание ще бъде верен.
Следните конвенции НЕ се приемат за операцията за отрицание:
не A, Ā, не A, ¬A, !A
Резултатът от операцията за отрицание НЕ се определя от следната таблица на истината:
Ане А
0 1
1 0

Резултатът от операцията за отрицание е верен, когато първоначалното твърдение е невярно и обратно.

Операция ИЛИ - логическо събиране (дизюнкция, обединение)

Логическата операция ИЛИ изпълнява функцията на комбиниране на две твърдения, които могат да бъдат прост или сложен логически израз. Изявленията, които са начални за логическа операция, се наричат ​​аргументи. Резултатът от операцията ИЛИ е израз, който ще бъде верен тогава и само ако поне един от оригиналните изрази е верен.
Използвани обозначения: A или B, A V B, A или B, A||B.
Резултатът от операцията ИЛИ се определя от следната таблица на истината:
Резултатът от операцията OR е true, когато A е true, или B е true, или и A, и B са true, и false, когато и A, и B са false.

Операция И - логическо умножение (конюнкция)

Логическата операция И изпълнява функцията на пресичане на две твърдения (аргументи), които могат да бъдат както прост, така и сложен логически израз. Резултатът от операцията И е израз, който е верен тогава и само ако и двата оригинални израза са верни.
Използвани символи: A и B, A Λ B, A & B, A и B.
Резултатът от операцията И се определя от следната таблица на истината:
АбА и Б
0 0 0
0 1 0
1 0 0
1 1 1

Резултатът от операцията AND е верен тогава и само ако изявленията A и B са верни и неверни във всички останали случаи.

Операция "АКО-ТОГАВА" - логическо следствие (импликация)

Тази операция свързва два прости логически израза, от които първият е условие, а вторият е следствие от това условие.
Приложени обозначения:
ако A, тогава B; А привлича Б; ако A тогава B; А → Б.
Таблица на истината:
АбA→B
0 0 1
0 1 1
1 0 0
1 1 1

Резултатът от операцията следствие (импликация) е неверен само когато предпоставка А е вярна и заключение Б (следствие) е невярно.

Операция "A ако и само ако B" (еквивалентност, еквивалентност)

Приложимо обозначение: A ↔ B, A ~ B.
Таблица на истината:
АбA↔B
0 0 1
0 1 0
1 0 0
1 1 1

Операция за добавяне по модул 2 (XOR, изключителна или стриктна дизюнкция)

Използвана нотация: A XOR B, A ⊕ B.
Таблица на истината:
АбA⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Резултатът от операция за еквивалентност е верен само ако и двете A и B са истина или и двете неистини.

Предимство на логическите операции

  • Действия в скоби
  • Инверсия
  • Съчетание (&)
  • Дизюнкция (V), Изключително ИЛИ (XOR), сума по модул 2
  • Извод (→)
  • Еквивалентност (↔)

Перфектна дизюнктивна нормална форма

Перфектна дизюнктивна нормална форма на формула(SDNF) е еквивалентна на него формула, която е дизюнкция на елементарни конюнкции, която има следните свойства:
  1. Всеки логически член на формулата съдържа всички променливи, включени във функцията F(x 1 ,x 2 ,...x n).
  2. Всички логически членове на формулата са различни.
  3. Никой логически термин не съдържа променлива и нейното отрицание.
  4. Нито един логически термин във формула не съдържа една и съща променлива два пъти.
SDNF може да се получи или с помощта на таблици на истината, или с помощта на еквивалентни трансформации.
За всяка функция SDNF и SKNF са уникално дефинирани до пермутация.

Перфектен конюнктив нормална форма

Перфектна конюнктивна нормална форма на формула (SKNF)е еквивалентна на него формула, която е конюнкция на елементарни дизюнкции, която удовлетворява следните свойства:
  1. Всички елементарни дизюнкции съдържат всички променливи, включени във функцията F(x 1 ,x 2 ,...x n).
  2. Всички елементарни дизюнкции са различни.
  3. Всяка елементарна дизюнкция съдържа променлива веднъж.
  4. Нито една елементарна дизюнкция не съдържа променлива и нейното отрицание.

Често, за да демонстрират ограничените възможности на еднослойните персептрони при решаване на проблеми, те прибягват до разглеждане на т.нар. XOR - Изключително ИЛИ.

Същността на проблема е следната. Дадена е логическата функция XOR - изключително ИЛИ. Това е функция от два аргумента, всеки от които може да бъде нула или едно. Приема стойността, когато един от аргументите е равен на единица, но не и двата, в противен случай. Проблемът може да бъде илюстриран с еднослойна система с един неврон и два входа, показана на фигурата по-долу.

Означим единия вход с , а другия с , тогава всички техни възможни комбинации ще се състоят от четири точки на равнината. Таблицата по-долу показва необходимата връзка между входове и изход, където входните комбинации, които трябва да произведат нулев изход, са означени с , а един изход е означен с .

точки Значение Значение Задължителен изход
0 0 0
1 0 1
0 1 1
1 1 0

Един неврон с два входа може да образува повърхност за вземане на решение под формата на произволна права линия. За да може мрежата да приложи функцията XOR, дадена от таблицата по-горе, трябва да позиционирате линията така, че точките да са от едната страна на линията, а точките да са от другата. Опитвайки се да начертаем такава права линия на фигурата по-долу, се убеждаваме, че това е невъзможно. Това означава, че без значение какви стойности са присвоени на теглата и прага, еднослойната невронна мрежа не е в състояние да възпроизведе връзката вход-изход, необходима за представяне на функцията XOR.

Функцията XOR обаче се формира лесно от двуслойна мрежа и то по много начини. Нека разгледаме един от тези начини. Нека модернизираме мрежата на фигурата, като добавим още един скрит слой от неврони:

Забележи, че тази мрежададено както е, т.е. може да се предположи, че е вече обучена. Числата над стрелките показват стойностите на синаптичните тегла. Като функция за активиране използваме функцията за скок на единица с прага, която има следната графика:

Тогава резултатът от работата на такава невронна мрежа може да бъде представен като следната таблица:

точки Значение Значение Задължителен изход
0 0 0 0 0 0
1 0 1 1 0 1
0 1 1 0 1 1
1 1 0 0 0 0

Всеки от двата неврона на първия слой образува повърхност на решение под формата на произволна права линия (разделя равнината на две полуравнини), а невронът на изходния слой комбинира тези две решения, образувайки повърхност на решение в форма на лента, образувана от успоредни прави линии на неврони от първия слой:

Невронната мрежа, използвана в тази статия за решаване на проблема с XOR, е примитивна и не използва всички характеристики на многослойните мрежи. Очевидно многопластов невронни мрежиимат по-голяма представителна сила от еднослойните, само при наличие на нелинейност. И в тази мрежа се прилага функция за прагово линейно активиране. Такава мрежа не може да бъде обучена, например, чрез прилагане на алгоритъма за обратно разпространение.