# Tag Info

77

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here: A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f -+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1 0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1 1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1 1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1 A and B are the inputs, 0 through f ...

25

It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions. Say you put two statements, $p,q$, together to form a new statement, $r$. In the case of and (logical conjunction), both $p$ and $q$ must be true for $r$ to be true. In the case of or (logical disjunction), $r$ ...

23

I think the questioner has it backwards. If we have a logical function such that A | B | result ---+---+------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 then we decide to call that function and because it is obvious that the result is 1 only when A and B are both 1. Similarly for or, exclusive-or, etc. There are 16 ...

9

The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that if you can reason about how human language works you can maybe reason about how reason works. Since the language I'm answering you in English let's use ...

4

Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.

4

What do you mean by real? You can define as many logic gates as you want and build them. However, in a boolean logic with 2 inputs, there are 16 different combination of outputs. On the other hand, it proven that $\{AND,NOT\}$, $\{OR,NOT\}$, $\{NAND\}$ and $\{NOR\}$ are functionally complete (which means we can build all other combination from 16 outputs ...

3

The boolean operators (and, or) are functions that map two inputs to an output, just like any other binary operator (i.e. +). Their exact behavior (the why question) is an axiom of boolean logic, just as the behavior of addition is an axiom of mathematics, which is to say that we agree that these operators do what they do. It is therefore the bedrock of ...

2

Let us consider the following decision version of your first problem: Given a SAT instance, does its multilinear representation have a term of degree at most $d$? I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones. Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear ...

2

It is equivalent to $$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$ This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.

2

Each Fourier coefficient on its own is the average of $2^n$ independent uniformly random $\pm1$ variables. Its distribution is roughly normal with mean $0$ and variance $2^{-n}$.

2

I'm not sure what you're asking, precisely, but it's certainly not true that a reversible universal gate requires the number of set bits in the output to be the same as in the input. Toffoli gates do not have that property, for example. EDIT Thanks for the clarification. The answer to your question is that any reversible circuit must have at least as many ...

2

Nope. For instance, you can't express the function $f(x)=x>>1$. In general, the least-significant bit of $f(x)$ depends only on the least-significant bit of $x$. You can prove that by structural induction, using the following two properties: $(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$ and $(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \... 1 AND I like red AND ripe apples. If the apple is red and the apple is ripe, then the result is true 1 and 1 makes 1 (true) The apple is green, so I don't like it 0 and 1 makes 0 (false) The apple is red but not ripe 1 and 0 makes 0 (false) OR I'll eat an apple if it's ripe OR if it's red The apple is red, but not ripe so I'll eat it 1 or 0 makes 1 (... 1 Let$x=0.11001100...$. in base$2$. Then$16x=1100.\overline{1100}\implies 15x=12\implies x=4/5$. 1 Classical formula for proper fraction is $$(0.a_{-1}a_{-2}a_{-3}\cdots)_2 = \left(\sum\limits_{k=1}^{\infty}\frac{a_{-k}}{2^k}\right)_{10}$$ Where for$a_{-k}$we have$k \in \mathbb{N}$and$a_{-k}\in \{ 0,1\}$. As you see for indexing is taken negative numbers. In your example$$(0.11001100...)_2 =\left( \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^5}+\frac{1}{... 1 I interpret question 'why' as asking for the purpose. So imagine OR, AND and NOT as the simplest building blocks from which you can build almost anything else. (Just remember it as some kind of simplification: NAND gate seems to be more universal and simpler from electronic engineering point of view but is less intuitive for learning purposes) As an ... 1 You can look at it as two stages. The first stage is that we want some particular outcome, such as wanting a 1 if either of the (2) inputs is a 1. We call this an “OR” gate. Another outcome that people want is to get a 1 only if both inputs are a 1. We call this an AND gate. The final stage is that we want a particular gate for every possible ... 1 To answer this, I think it is best to go back to those early 'Truth Tables' you probably saw in algebra. The first ones you see are 'and' & 'or'. We have two statements #1 & #2 (usually called p & q) which can either be true or false. Then, when we test them we have a result (usually called r). For example, #1 p = I like red #2 q = I like dogs ... 1 Yes, that's correct. See the Tseitin transform, which describes how. It doesn't matter how the circuit$C\$ was constructed.

1

I would say an importante difference is at least: one cannot add an axiom to Boolean algebra, while one can add one or multiple axioms in a propositional logic, although there is not that much one could add, since all consistant and interesting axiom set are already known (modulo their interpretations). — Edit — Yesterday I though about two other important ...

Only top voted, non community-wiki answers of a minimum length are eligible