# Questions tagged [boolean-algebra]

The tag has no usage guidance.

273 questions
Filter by
Sorted by
Tagged with
6k views

### Measuring Complexity of Boolean Satisfiability Problem

How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. ...
40 views

### Simulating Boolean Circuit with RAM

Statement: Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM). Could you please supply me with a reference to an ...
58 views

### Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
33 views

### Which gates are “pre computation” universal?

In the following, by “functions” I will mean 2 input 1 output Boolean logic functions (for conciseness). A function is called “universal” if by using it (sometimes multiple times, chained together), ...
1 vote
45 views

### Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
1k views

### Addition, multiplication, and apostrophe used to represent boolean algebra expressions?

I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before. I can make a guess that the apostrophe is ...
1 vote
287 views

### All 16 Boolean Logic Gates

I was doing some reseach and I came across a website that had listed 16 different boolean logic operators. I was wondering if all of them were real, and if so, what do they do. https://www....
125 views

### Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)

I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e ..." ...
348 views

### Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?

I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm: elimination of equivalence Elimination of ...
134 views

### Simplifying the Boolean expression $A + \bar{A}\bar{B}$?

So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$. I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), ...
57 views

### Expressing unsigned comparison through signed comparison of 2's complement

Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that <...
91 views

### 3-CNF to "independent form"

Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the ...
1 vote
51 views

### What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
393 views

### Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
98 views

1 vote
381 views

### How do I get the NAND gate configuration for full adder from the logic table?

I'm self-studying, but I've gotten stuck already. If I'm given the logic table for a full-adder or any two-output table, how do I figure out the NAND-gate configuration, preferably methodically? ...
51 views

### Truth table and logic circuit problem

Does anyone know how to make this into a truth table and a logic circuit? (x•y)+x If so please send me the answer.
1 vote
197 views

### Can I use the Quine-McCluskey to simplify a CNF which is not a product of maxterms?

As I understand it the Quine-McCluskey method allows you to start with a set of maxterms (or minterms), and combine them pairwise in a systematic way into a smaller set of clauses with a smaller set ...
1k views

### Absorption rule in Boolean algebra

I am confused regarding the absorption rule which states: A OR (A AND B) = A. I do not completely understand how the expression simplifies to A and while i have seen proofs for this question, i still ...
485 views

### Simplifying SOP: implementing OR with NAND

I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such: $a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$ In other ...
72 views

### How to "logically" solve boolean logic

I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate. ...
338 views

### Why are there two not operators in lambda calculus?

From Wikipedia: $\mathrm{true} = \lambda a. \lambda b. a$ $\mathrm{false} = \lambda a. \lambda b. b$ Because true and false choose the first or second parameter they may be combined to provide logic ...
5k views

### Number of literals in the given boolean expression

Count the number of literals in the following expression : F = AB' + BC' + CD' + DE' According to me, the answer should be 8. But my solution suggests that the answer should be 6. Can anyone help me ...
150 views

### Boolean Functions

Say you have N input Boolean function, let's use a parity tree for the example. The function outputs a one or a zero depending on the values of the N inputs. Are the N inputs considered the preimage ...
1 vote
442 views

### Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...