Умножение в информатике знак

Умножение в информатике знак

Обозначения в логических операциях

Обозначения для логических связок:

отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

конъюнкция (логическое умножение, логическое И) обозначается /

дизъюнкция (логическое сложение, логическое ИЛИ) обозначается /

следование (импликация) обозначается (например, А → В);

тождество обозначается (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

символ 1 (единица) используется для обозначения истины (истинного высказывания);

символ 0 (ноль) используется для обозначения лжи (ложного высказывания).

Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) / В равносильны, а А / В и А / В – нет (значения выражений разные, например, при А = 1, В = 0).

Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А / В / С / D означает то же, что и

Возможна запись А / В / С вместо (А / В) / С. То же относится и к конъюнкции: возможна запись А / В / С вместо (А / В) / С.

Свойства логических операций

Общие свойства логических операций

Для набора из n логических переменных существует ровно 2n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2n строк.

Дизъюнкция

Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.

Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.

Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.

Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

Конъюнкция

Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.

Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.

Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.

Значение конъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

Простые дизъюнкции и конъюнкции

Назовем (для удобства) конъюнкцию простой, если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой, если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания.

Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.

Простая дизъюнкция принимает значение (ложь) ровно на одном наборе значений переменных.

Импликация

Импликация A →B равносильна дизъюнкции (¬А) / В. Эту дизъюнкцию можно записать и так: ¬А / В.

Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.

Конъюнкция
И, AND

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

Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И» [1] .

Конъюнкция может быть бинарной операцией (т. e. иметь два операнда), тернарной операцией (т. e. иметь три операнда), или n-арной операцией (т. e. иметь n операндов).

Содержание

Обозначения [ править | править код ]

Наиболее часто встречаются следующие обозначения для операции конъюнкции:

a ∧ b , a & & b , a & b , a ⋅ b , a A N D b , min ( a , b ) <displaystyle aland b,quad aAnd And b,quad aAnd b,quad acdot b,quad a,,mathrm ,,b,quad min(a,b)>

Читайте также:  Как сделать вазу из стеклянной бутылки

(в случае использования точки, как знака логического умножения, этот знак, как и при обычном умножении в алгебре, может быть опущен: a b <displaystyle ab> [1] ).

При этом обозначение a ∧ b <displaystyle aland b> , рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда & [1] ; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия) [2] [3] . Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком ⋅ <displaystyle cdot > — как обычное умножение [4] . Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930) [5] .

Обозначение ⋀ для конъюнкции было использовано и в раннем языке программирования Алгол 60 [6] . Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .AND. и & (с возможностью замены последнего на ключевое слово AND ) [7] ; в языках Паскаль и Ада используется зарезервированное слово and [8] [9] ; в языках C и C++ применяются обозначения & для побитовой конъюнкции и && для логической конъюнкции [10] ).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что 0 1 <displaystyle 0 ), оказывается, что ( a ∧ b ) = min ( a , b ) . <displaystyle (aland b),=,min(a,b).> Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: ( a ∧ b ) = a b ( mod ⁡ k ) <displaystyle (aland b),=,ab;(operatorname k)> в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком < 0 , … , k − 1 ><displaystyle <0,dots ,k-1>> полугруппы N <displaystyle mathbb > натуральных чисел) [11] [12] .

Булева алгебра [ править | править код ]

Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).

Правило: результат равен наименьшему операнду.

Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества < 0 , 1 ><displaystyle <0,1>> . Результат также принадлежит множеству < 0 , 1 ><displaystyle <0,1>> . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений 0 , 1 <displaystyle 0,1> может использоваться любая другая пара подходящих символов, например f a l s e , t r u e <displaystyle false,true> или F , T <displaystyle F,T> или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, false>"> t r u e > f a l s e <displaystyle true>false> false"/> , при цифровом обозначении старшинство естественно 0>"> 1 > 0 <displaystyle 1>0> 0"/> .
Правило: результат равен 1 <displaystyle 1> , если все операнды равны 1 <displaystyle 1> ; во всех остальных случаях результат равен 0 <displaystyle 0> .

Таблицы истинности:
для бинарной конъюнкции

для тернарной конъюнкции

Многозначная логика [ править | править код ]

Операции, называемой в двоичной логике конъюнкция, в многозначных логиках обычно сопоставляется операция минимум: m i n ( a , b ) <displaystyle min(a,b)> , где a , b ∈ < 0 , … , k − 1 >, <displaystyle a,bin <0,dots ,k-1>,> а k <displaystyle k> — значность логики; впрочем, возможны и другие варианты обобщения обычной конъюнкции на многозначный случай. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов 0 <displaystyle 0> и k − 1 <displaystyle k-1> .

Читайте также:  Растение похожее на мак

Следует отметить, что название этой операции минимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия конъюнкция, логи́ческое «И», логическое умноже́ние и просто «И» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.

Классическая логика [ править | править код ]

В классическом исчислении высказываний свойства конъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства конъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для конъюнкции:
a ∧ b → a <displaystyle aland b o a>
a ∧ b → b <displaystyle aland b o b>
a → ( b → ( a ∧ b ) ) <displaystyle a o (b o (aland b))>

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

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

Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения [13] . Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:

  • «1» тогда и только тогда, когда на всех входах есть «1»,
  • «0» тогда и только тогда, когда хотя бы на одном входе есть «0»

Теория множеств [ править | править код ]

С точки зрения теории множеств, конъюнкция аналогична операции пересечения.

Программирование [ править | править код ]

В компьютерных языках используется два основных варианта конъюнкции: логическое «И» и побитовое (поразрядное) «И». Например, в языках C/C++ логическое «И» обозначается символом «&&», а побитовое — символом «&». В терминологии, используемой в C#, операцию «&» принято называть логическим «И», а операцию «&&» — условным «И», поскольку значения операндов являются условиями для продолжения вычисления. В языках Pascal/Delphi оба вида конъюнкции обозначаются с использованием ключевого слова «and», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.

Логическое «И» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата f a l s e <displaystyle false> или t r u e <displaystyle true> . Например:

Сравнение в данном случае будет продолжаться до конца выражения, независимо от промежуточных результатов. Принцип работы условного «И» в аналогичной ситуации:

Проверка истинности выражения в данном случае остановится после проверки переменной a, так как дальнейшее сравнение не имеет смысла.

Результат будет равен t r u e <displaystyle true> , если оба операнда равны t r u e <displaystyle true> (для числовых типов не равны 0 <displaystyle 0> ). В любом другом случае результат будет равен f a l s e <displaystyle false> .

При этом применяется стандартное соглашение: если значение левого операнда равно f a l s e <displaystyle false> , то значение правого операнда не вычисляется (вместо b <displaystyle b> может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

подобное поведение. Например, если левый операнд проверяет возможность вычисления правого операнда:

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт деления на ноль.

Побитовое «И» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,

если
a = 01100101 2 <displaystyle 01100101_<2>>
b = 00101001 2 <displaystyle 00101001_<2>>
то
a И b = 00100001 2 <displaystyle 00100001_<2>>

Связь с естественным языком [ править | править код ]

Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение «A и B» считается истинным, когда истинны оба утверждения A и B, в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как 1 <displaystyle 1> , а «ложь» как 0 <displaystyle 0> . При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической остроумно выразил американский математик Стивен Клини, заметив, что в естественном языке «Мэри вышла замуж и родила ребёнка» — не то же самое, что «Мэри родила ребёнка и вышла замуж».

Читайте также:  Спальня адажио ангстрем отзывы
НЕКОТОРЫЕ

СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ

1. Обозначения

1.1. Обозначения для логических связок (операций):

a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

b) конъюнкция (логическое умножение, логическое И) обозначается /
(например, А / В) либо & (например, А & В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается /
(например, А / В);

d) следование (импликация) обозначается → (например, А → В);

e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) / В равносильны, а А / В и А / В – нет (значения выражений разные, например, при А = 1, В = 0).

1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А / В / С / D означает то же, что и

Возможна запись А / В / С вместо (А / В) / С. То же относится и к конъюнкции: возможна запись А / В / С вместо (А / В) / С.

2. Свойства

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

2.1. Общие свойства

  1. Для набора из n логических переменных существует ровно 2n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2n строк.

2.2.Дизъюнкция

  1. Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
  2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.
  3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
  4. Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.3. Конъюнкция

  1. Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
  2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
  3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.
  4. Значение конюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.4. Простые дизъюнкции и конъюнкции

Назовем (для удобства) конъюнкцию простой, если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой, если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания.

  1. Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
  2. Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.

2.5. Импликация

  1. Импликация AB равносильна дизъюнкции А) / В. Эту дизъюнкцию можно записать и так: ¬А / В.
  2. Импликация AB принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация AB истинна при любом значении B.
Ссылка на основную публикацию
Adblock detector