# 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 ...

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

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 Yes, absolutely. Every boolean function can be implemented by a circuit. In this case, it suffices to XOR bits 1 and$n$; bits 2 and$n-1$; and so on; and then take the NOR of all of the outputs of these XOR gates. 1 If$f,g$are two$\pm1$-valued functions and$f \lor g$is their maximum (this is the standard notation for maximum;$\land$stands for minimum), then $$f \lor g = \frac{1 + f + g - fg}{2}.$$ Since$\chi_S \chi_T = \chi_{S \Delta T}\$, this shows that $$\chi_S \lor \chi_T = \frac{1}{2} + \frac{\chi_S}{2} + \frac{\chi_T}{2} - \frac{\chi_{S\Delta T}}{2}.$$ ...

1

I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits. \

1

\begin{align*} x'y' + yz + x'yz' &= x'y' (z+z') + (x+x')yz +x'yz' &\mbox{(identity)} \\&= x' y' z + x' y' z' + xyz + x'yz + x'yz' &\mbox{(distributivity)} \\&= x' y' z + x' y' z' + xyz + x'yz + x'yz + x'yz' &\mbox{(idempotence)} \\&= x'(y' z + y' z' + y z + y z') + (x+x')yz &\mbox{(distributivity)} \\&= x'+yz. &\... 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

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