Есть | / а! операторы, достаточные для создания всех возможных логических выражений?
логическое выражение ( a && b )(как a и b имеем логические значения) может быть записан как !(!a || !b), например. Разве это не значит, что && это "ненужную"? Значит ли это, что все логические выражения могут быть сделаны только с помощью || и !?
6 ответов:
да, как указывали другие ответы, набор операторов, состоящий из
||и!и функционально полностью. Вот конструктивное доказательство этого, показывающее, как использовать их для выражения всех шестнадцати возможных логических связок между булевыми переменнымиAиB:
- правда:
A || !A- A NAND B:
!A || !B- B подразумевает a:
!B || A- A подразумевает B:
!A || B- A ИЛИ B:
A || B- Б:
!B- Не A:
!A- A XOR B:
!(!A || B) || !(A || !B)- A XNOR B:
!(!A || !B) || !(A || B)- A:
A- B:
B- A NOR B:
!(A || B)- A не означает B:
!(!A || B)- B не означает:
!(!B || A)- A И B:
!(!A || !B)- ложные:
!(A || !A)вот график, отображающий диаграммы Венна для каждого из перечисленных выше связок:
[источник]
что вы описываете, это функциональная полнота.
здесь описывается набор логических операторов, достаточный для"выражения всех возможных таблиц истинности". Ваш набор операторов Java, {
||,!}, достаточно; это соответствует множеству { ∨ ,}, которое перечислено в разделе "минимальные функционально полные наборы операторов".набор всех таблиц истинности означает все возможные наборы из 4 булевых значений, которые могут быть результат операции между 2 логическими значениями. Поскольку существует 2 возможных значения для логического значения, есть 24, или 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.
да.
все логические элементы могут быть сделаны из элементов NOR.
Так как ни ворота могут быть сделаны из не и или, результат следует.
найдите время, чтобы прочитать на законы деморгана если вы можете.
вы найдете ответ в чтении есть, а также ссылки на логические доказательства.
но по существу, ответ да.
EDIT: для ясности моя точка зрения заключается в том, что можно логически вывести выражение OR из выражения AND и наоборот. Есть еще несколько законов для логической эквивалентности и вывода, но я думаю, что это самое главное по поводу.
EDIT 2: вот доказательство через таблицу истинности, показывающее логическую эквивалентность следующего выражения.
закон деморгана:
!(!A || !B) -> A && B_____________________________________________________ | A | B | !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 | _______________________________________________________
NAND и , ни универсальны они могут быть использованы для создания любой логической операции, которую вы хотите в любом месте; другие операторы доступны на языках программирования, чтобы сделать его легко писать и делать читаемые коды.
также все логические операции, которые должны быть жестко связаны в цепи, также разрабатываются с использованием NAND или не только ICs.
Да, согласно булевой алгебре, любая Булева функция может быть выражена как сумма minterms или произведение maxterms, которое называется каноническая нормальная форма. Нет никаких причин, по которым такая логика не могла бы быть применена к тем же операторам, которые используются в информатике.
Comments