Являются || и ! операторы достаточны, чтобы сделать каждое возможное логическое выражение?

294

Логическое выражение ( a && b ) (оба aи bимеют логические значения) может быть написано !(!a || !b), например, как. Разве это не значит, что &&это «ненужное»? Означает ли это, что все логические выражения могут быть сделаны только с использованием ||и !?

JakeTheSnake
источник
83
Это больше вопрос символической логики, чем проблема Java, но да. ИЛИ и НЕ в комбинации могут быть использованы для построения всего остального. То же самое с AND и NOT. Например, когда я учился в школе, нас учили строить все, используя только вентили NAND, потому что они брали меньше транзисторов.
azurefrog
79
Не путайте возможность написать заявление таким способом с желательностью сделать это. Синтаксический сахар - это хорошо .
Azurefrog
20
Многие микросхемы логических элементов предоставляют только шлюзы NAND или NOR, поскольку с ними можно выполнять все операции, что делает их дешевыми в производстве - A and B == !A nor !B == !(!A or !B). Точно так же A or B == !A nand !B == !(!A and !B). Очевидно, что передача одного и того же значения на оба входа NAND или NOR даст тот же результат, что и простое NOT. XOR и XNOR также возможны, но более сложны. См. Теорему де Моргана
Основное
16
Разве это не вопрос информатики? Я не вижу здесь никакого кода. В частности, правда ли это на практике, будет зависеть от реализации, например, в C ++ с рабочей перегрузкой это не так .
Гонки легкости на орбите
6
@ SnakeDoc Я не думаю, что кто-то здесь выступает за такую ​​вещь. Я считаю, что этот вопрос был скорее вопросом теоретической логики, чем вопросом программирования.
ryuu9187

Ответы:

425

Да, как указывалось в других ответах, набор операторов состоит из ||и !является функционально полным . Вот конструктивное доказательство этого, показывающее, как использовать их для выражения всех шестнадцати возможных логических связок между булевыми переменными Aи B:

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

Вот график, показывающий диаграммы Венна для каждого из перечисленных выше соединительных элементов:

введите описание изображения здесь

[ источник ]

Питер Олсон
источник
20
Трудно сказать, намеревается ли этот вопрос вопрос, но этот ответ не касается поведения короткого замыкания (уместно, так как вопрос задает вопрос, ||а не |) или побочных эффектов (уместно, потому что расширение истинных, ложных, XOR и XNOR оценивает их аргументы чаще, чем исходная константа или оператор).
Дэвид Ричерби
5
Круги, содержащие круги и переходы, образуют диаграмму Хассе ( en.wikipedia.org/wiki/Hasse_diagram ). (Да, я узнал кое-что новое сегодня!)
Каспер ван ден Берг
5
@DavidRicherby Это правда. Помимо XOR, XNOR, true и false, насколько я могу судить, побочные эффекты и количество оценок должны быть такими же, как и у встроенных эквивалентов (например, !(!A || !B)имеет такое же количество коротких замыканий и оценок, что и A && B). Я не думаю, что вы можете сделать это для XOR и XNOR без дополнительных конструкций (например a ? !b : b), и true или false не проблема, если вы можете сохранить значения, так как вы могли бы запустить вашу программу, определив trueи falseиспользовав некоторую фиктивную логическую переменную.
Питер Олсон
Интересно отметить, что приведенный выше список состоит из 16 операций. Это согласуется с тем фактом, что существует 16 возможных таблиц истинности для случая, когда у вас есть 2 входа и 1 выход.
Пол Р
1
Просто хотел добавить еще одну визуализацию в качестве таблицы для справки людей. Тот же источник, что и выше.
Авг
125

То, что вы описываете, является функциональной полнотой .

Это описывает набор логических операторов, достаточных для «выражения всех возможных таблиц истинности». Ваш набор операторов Java { ||, !} достаточен; оно соответствует набору {∨, ¬}, указанному в разделе «Минимальные функционально полные операторные множества».

Набор всех таблиц истинности означает все возможные наборы из 4 логических значений, которые могут быть результатом операции между 2 логическими значениями. Поскольку для логического значения есть 2 возможных значения, существует 2 4 или 16 возможных таблиц истинности.

A B | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+------------------------------------------------
T T | T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T F | T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F T | T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F 
F F | T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

Ниже приведена таблица из чисел таблицы истинности (0-15), то ||и !комбинаций , которые дают его, и описание.

Table  |  Operation(s)                    | Description
-------+----------------------------------+-------------
  0    | A || !A                          | TRUE
  1    | A || B                           | OR
  2    | A || !B                          | B IMPLIES A
  3    | A                                | A
  4    | !A || B                          | A IMPLIES B
  5    | B                                | B
  6    | !(!A || !B) || !(A || B)         | XNOR (equals)
  7    | !(!A || !B)                      | AND
  8    | !A || !B                         | NAND
  9    | !(A || !B) || !(!A || B)         | XOR
 10    | !B                               | NOT B
 11    | !(!A || B)                       | NOT A IMPLIES B
 12    | !A                               | NOT A
 13    | !(A || !B)                       | NOT B IMPLIES A
 14    | !(A || B)                        | NOR
 15    | !(A || !A)                       | FALSE

Существует множество других таких функционально полных наборов, включая наборы одного элемента {NAND} и {NOR}, которые не имеют соответствующих отдельных операторов в Java.

rgettman
источник
4
+1 за редактирование. Несмотря на разницу в подсчете голосов, я думаю, что ваш ответ сейчас более подробный, чем мой.
Питер Олсон
Таблицы правды Я думал, что оставил их после первого года в университете
Barkermn01
80

Да.

Все логические ворота могут быть сделаны из ворот NOR.

Поскольку ворота NOR могут быть сделаны из NOT и OR, результат следует.

Пол Боддингтон
источник
64
@PaulDraper или NAND ворота
Slebetman
25
Для высадки двух человек на Луну потребовалось 4100 ворот.
Ганс Пассант
4
@ HansPassant И немного строки. Много строк. (Ядро памяти веревки, а не разновидность консервной банки.)
CVn
3
@ HansPassant Иногда я хотел бы, чтобы Stack Exchange был Wikipedia, тогда я бы вставил [citation-needed]отметку прямо здесь
Саймон Форсберг
11
Да, извините, компьютер- помощник Аполлона .
Ханс Пассант
64

Потратьте время, чтобы прочитать законы DeMorgan, если вы можете.

Вы найдете ответ в чтении там, а также ссылки на логические доказательства.

Но по сути, ответ - да.

РЕДАКТИРОВАТЬ : Для ясности, моя точка зрения заключается в том, что можно логически вывести выражение ИЛИ из выражения И, и наоборот. Есть и другие законы для логической эквивалентности и умозаключения, но я думаю, что это самое подходящее.


РЕДАКТИРОВАТЬ 2 : Вот доказательство через таблицу истинности, показывающее логическую эквивалентность следующего выражения.

Закон Деморгана: !(!A || !B) -> A && B

 _____________________________________________________
| A | Б | ! A | ! B | ! A || ! B | ! (! A ||! B) | A && B |
-------------------------------------------------- -----
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
_______________________________________________________
ryuu9187
источник
19
Некоторым людям приходится понизить голосование как часть их «функциональной полноты»
Джесси
3
При + 27 / -2 я бы не стал сильно беспокоиться о шальных понижениях.
CVn
2
@ MichaelKjörling Мне просто любопытно, почему некоторые люди считают мой ответ бесполезным / вредным.
ryuu9187
3
Обычно ответы, которые основаны на ссылках, не очень нравятся (поскольку ссылки умирают), но в этом случае есть столько альтернативных объяснений законов ДеМоргана, что я не вижу проблемы - тем не менее, это мое предположение относительно DV
user2813274
@ user2813274 Спасибо за объяснение. Надеюсь, мои правки помогут преодолеть разрыв между личными исследованиями и получением ответа.
ryuu9187
11

NAND и NOR универсальны, их можно использовать для построения любой логической операции, которую вы хотите где угодно; другие операторы доступны на языках программирования, что упрощает написание и создание читаемых кодов.

Кроме того, все логические операции, которые необходимо встроить в схему, также разрабатываются с использованием микросхем NAND или только NOR.

Ананд
источник
10

Да, согласно булевой алгебре, любая булева функция может быть выражена как сумма минтермов или произведение макротерм, которое называется канонической нормальной формой . Нет причин, по которым такую ​​логику нельзя было бы применить к тем же операторам, которые используются в информатике.

https://en.wikipedia.org/wiki/Canonical_normal_form

Михал Шидловский
источник