Базовые операции через стрелку пирса

Стрелка Пирса
ИЛИ-НЕ, NOR

Диаграмма Венна
Определение x + y ¯ <displaystyle <overline >>
Таблица истинности ( 1000 ) <displaystyle (1000)>
Логический вентиль
Нормальные формы
Дизъюнктивная x ¯ ⋅ y ¯ <displaystyle <overline >cdot <overline >>
Конъюнктивная x ¯ ⋅ y ¯ <displaystyle <overline >cdot <overline >>
Полином Жегалкина 1 ⊕ x ⊕ y ⊕ x y <displaystyle 1oplus xoplus yoplus xy>
Принадлежность предполным классам
Сохраняет 0 Нет
Сохраняет 1 Нет
Монотонна Нет
Линейна Нет
Самодвойственна Нет

Стре́лка Пи́рса (функция Вебба, отрицание дизъюнкции) [1] — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Чарльзом Пирсом в 1880—1881 годах.

Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции ИЛИ-НЕ [2] и задаётся следующей таблицей истинности:

Таким образом, высказывание «X ↓ Y» означает «(не X) и (не Y)». От перемены мест операндов результат операции не изменяется.

Стрелка Пирса, как и штрих Шеффера, образует функционально-полный логический базис для пространства булевых функций от двух переменных. Это означает, что, используя только стрелку Пирса, можно построить все остальные логические операции, например:

X ↓ X ≡ ¬ X <displaystyle Xdownarrow Xequiv
eg X> — отрицание ( X ↓ X ) ↓ ( Y ↓ Y ) ≡ X ∧ Y <displaystyle left(
ight)downarrow left(
ight)equiv > — конъюнкция ( X ↓ Y ) ↓ ( X ↓ Y ) ≡ X ∨ Y <displaystyle left(
ight)downarrow left(
ight)equiv Xvee Y> — дизъюнкция ( ( X ↓ X ) ↓ Y ) ↓ ( ( X ↓ X ) ↓ Y ) ≡ X → Y <displaystyle left(left(
ight)downarrow Y
ight)downarrow left(left(
ight)downarrow Y
ight)equiv X
ightarrow Y> — импликация

В электронике это означает, что для реализации всего многообразия схем преобразования сигналов, представляющих логические значения, достаточно одного типового элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NOR). С другой стороны, такой подход увеличивает сложность реализующих выражения схем и тем самым снижает их надёжность.

Функциональная операция, выполняемая при n <displaystyle n> входах, определяется следующим выражением:

F = x 1 + x 2 + x 3 + x 4 + . . . x n ¯ . <displaystyle F=<overline <1>+x_<2>+x_<3>+x_<4>+. x_>>.>

Схемы [ править | править код ]

Говоря простым языком, вентиль 2ИЛИ-НЕ − это 2ИЛИ с подключенным к нему инвертором. Для наглядности, ниже приведен пример логики 2ИЛИ-НЕ с выключателями. Как известно, логика 2ИЛИ близка к выражению «Или A, Или B, Или то и другое». Чтобы получить логику 2ИЛИ-НЕ, результат 2ИЛИ необходимо инвертировать, чтобы получить «Не A, и не B». На схеме ниже это выглядит следующим образом: Серым отмечены выключатели в состоянии «выключено», синим в состоянии «включено». На первой слева схеме оба выключателя находятся в положении «выключено». Таким образом, следуя выражению на выходе, получаем логический 0. Инвертированный результат будет равен 1, и тем самым логически удовлетворять выражению «Не А, Не B». Следующие схемы демонстрируют соответственно «ИЛИ А», «ИЛИ B», «И А, И B» с последующей инверсией результата.

Читайте также:  Заказ контента 9731 билайн как отключить

Слева представлены варианты реализации вентиля 2ИЛИ-НЕ с помощью диодно-транзисторной логики и с помощью МОП соответственно.

Представленная схема на МОП выполнена на однотипных МОП-транзисторах, однако существуют вариант схемы 2ИЛИ-НЕ на комплементарных (дополняющих) МОП-тразисторах. Такую схему получают путём последовательного соединения однотипных транзисторов и параллельного соединения группы транзисторов другого типа.

Стрелка Пирса (логическое «ИЛИ-НЕ») высказываний a и b — это новое высказывание, которое будет истинно тогда и только тогда, когда оба высказывания ложны.

Знаком стрелки Пирса является ↓

Значения функции стрелки Пирса представлены в таблице:

Логическим элементом операции стрелки Пирса является:

a b a↓b

Стре́лка Пи́рса — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Чарльзом Пирсом (Сharles Peirce) в 1880—1881 г.г.

Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции ИЛИ-НЕ и задаётся следующей таблицей истинности:

Таким образом, высказывание «X ↓ Y» означает «ни X, ни Y». От перемены мест операндов результат операции не изменяется.

X Y XY

Штрих Ше́ффера — бинарнаялогическая операция,булева функциянад двумя переменными. Введена в рассмотрениеГенри Шефферомв 1913 г. (вотдельных источниках именуется как Пунктир Чулкова) Штрих Шеффера, обычно обозначаемый |, эквивалентен операции И-НЕ и задаётся следующей таблицей истинности:

X Y X|Y

Таким образом, высказывание X | Y означает, что X и Y несовместны, т.е. не являются истинными одновременно. От перемены мест операндов результат операции не изменяется. Штрих Шеффера, как и стрелка Пирса, образует базис для пространства булевых функций от двух переменных. То есть используя только штрих Шеффера можно построить остальные операции. Например,

—отрицание

— дизъюнкция

— конъюнкция

— константа 1

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

Элемент 2И-НЕ (2-in NAND), реализующий штрих Шеффера обозначается следующим образом (по стандартам ANSI):

Читайте также:  Swiftkey keyboard для android

В европейских стандартах принято другое обозначение:

18.

Дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

Алгоритм получения сднф по таблице истинности.

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:

X Y F(X,Y)
1*
1*

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: — для 2-й строки; — для 3-й строки.

3. Все полученные конъюнкции связать в дизъюнкцию: (1*)

(Алгоритм приведения формулы булевой функции к СДНФ)

Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.

Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:

A&ØA º 0, B&0 º 0, СV0 º С.

Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A º A.

Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание Øx, то на основании 1- го закона расщепления заменяем С на (С&x) V (C&Øx).

Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, . n) на i-м месте была либо переменная xi, либо ее отрицание Øxi.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС º С.

Стрелка (символ) — У этого термина существуют и другие значения, см. Стрелка. Стрелка название ряда типографских символов, внешне похожих на стрелу, например: ← → ↑ ↓. В Юникоде 5.1 имеется 322 символа, содержащих в своём описании слово ARROW, 6 символов,… … Википедия

Читайте также:  Вакууматор для продуктов домашний видео

Стрелка — Стрелка: Стрелка символ «→». Стрелка указатель, например в часах (стрелка часов), в стрелочных измерительных приборах. Стрелка собака космонавт, успешно вернувшаяся из орбитального полёта. Стрелка место у впадения двух или … Википедия

ПИРСА СТРЕЛКА — двуместная логическая операция, обычно обозначаемая и задаваемая следующей истинностной таблицей: Таким образом, высказывание означает ни А, ни В . П. с. обладает тем свойством, что через нее выражаются все другие логические операции. Например,… … Математическая энциклопедия

Битовая операция — Битовые операции, иногда также булевы или логические операции[1] операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике. Содержание 1 Введение 1.1 … Википедия

Булевы операции — Битовые операции, иногда также булевы или логические операции[1] операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике. Содержание 1 Введение 1.1 … Википедия

Инвертор (логический элемент) — Битовые операции, иногда также булевы или логические операции[1] операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике. Содержание 1 Введение 1.1 … Википедия

Булева функция — В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок … Википедия

Логические элементы — Логические элементы устройства, предназначенные для обработки информации в цифровой форме (последовательности сигналов высокого «1» и низкого «0» уровней в двоичной логике, последовательность «0», «1» и «2» в троичной логике,… … Википедия

Штрих Шеффера — Штрих Шеффера бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Генри Шеффером в 1913 г. (в отдельных источниках именуется как Пунктир Чулкова) Штрих Шеффера, обычно обозначаемый |, задаётся… … Википедия

Список статей по логике — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не ус … Википедия