Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
273
questions
5
votes
3
answers
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. ...
- 1
2
votes
0
answers
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 ...
- 161
2
votes
1
answer
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 ...
D.W.♦
- 156k
0
votes
0
answers
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), ...
- 250
1
vote
1
answer
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 ...
D.W.♦
- 156k
2
votes
1
answer
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 ...
CommunityBot
- 1
1
vote
1
answer
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....
- 489
2
votes
1
answer
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
..." ...
- 399
0
votes
2
answers
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 ...
- 116
2
votes
2
answers
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), ...
- 28.3k
0
votes
1
answer
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 <...
- 2,018
2
votes
1
answer
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 ...
- 14.4k
1
vote
1
answer
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 ...
CommunityBot
- 1
2
votes
1
answer
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 ...
- 12.7k
2
votes
1
answer
98
views
Conjunctive normal form to simple elementary algebra
I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.
An example:
$$\phi=\left(x_1 \vee x_2 \right) \wedge \...
- 4,979
3
votes
1
answer
104
views
Polynomial size Boolean circuit for counting number of bits
Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
- 275k
3
votes
1
answer
169
views
Is is possible to determine if a given number is xor combination of some numbers?
I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
- 275k
2
votes
2
answers
3k
views
Which is the correct XOR Gate Symbol
I'm confused between 2 XOR gate symbols, they have a minor difference but I'd still like to know if they truly are identical.
One looks like -
The other, like
Notice, how for one of them the ...
- 21.6k
6
votes
3
answers
40k
views
Absorption Law Proof by Algebra
I'm struggling to understand the absorption law proof and I hope maybe you could help me out.
The absorption law states that: $X + XY = X$
Which is equivalent to $(X \cdot 1) + (XY) = X$
No problem ...
3
votes
0
answers
121
views
Iterating over a union of sets denoted by bitmasks
Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$.
Such bitmask denotes a set $S \subset \mathbb{B}^...
- 131
0
votes
2
answers
2k
views
how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates
How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?
CommunityBot
- 1
2
votes
2
answers
691
views
Prime Implicants in Boolean Function
A Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six
variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0.
How many essential prime implicants does F ...
CommunityBot
- 1
6
votes
2
answers
2k
views
Converting truth table to algebraic normal form
Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?
I have seen that Sage has one implementation (official ...
- 307
2
votes
1
answer
278
views
Modeling equality in an ILP
Lets say we have integer variables $a \in\mathbb{Z}^n$ and $M \in\{0,1\}^{n\times L}$. I am promised $a_i \leq L$, for some fixed constant $L$. I want to model the constraint $$M_{i,j} \iff (a_i=j)$...
- 976
2
votes
1
answer
78
views
Logic of multiple variables in ILP
Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
- 976
2
votes
1
answer
195
views
how many boolean functions exist that satisfy the condition
How many boolean functions exist that satisfy the following condition?
$$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$
- 4,431
2
votes
1
answer
2k
views
State Transition Diagrams for XOR
I have found two different versions for State Transition Diagrams for XOR.
I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please?
Are they both ...
- 275k
0
votes
2
answers
142
views
Why is Boolean satisfiability such a rare case?
In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot ...
- 81.4k
3
votes
1
answer
8k
views
Boolean Algebra : Using identities, prove x(x + y) = x
Example: Prove the ABSORPTION LAW:
$$
x(x + y) = x
$$
$
Solution: \\
x(x + y) \\
= (x + 0)(x + y) \;\;\;\;\; Identity \;Law \\
= x + (0 · y) \;\;\;\;\;\;\;\;\;\;\; Distributive \;Law \\
= x + y · 0 ...
- 38.6k
1
vote
0
answers
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? ...
- 11
-1
votes
1
answer
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.
- 653
1
vote
0
answers
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 ...
- 315
2
votes
2
answers
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 ...
- 206
0
votes
1
answer
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 ...
- 7,038
0
votes
1
answer
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.
...
- 884
6
votes
1
answer
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 ...
CommunityBot
- 1
0
votes
1
answer
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 ...
- 12.7k
-3
votes
2
answers
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 ...
- 234
1
vote
1
answer
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.
...
- 38.6k
-1
votes
1
answer
52
views
Minimal representation of an AND with two-input NOR
Let $x_1,x_2,x_3,x_4$ be boolean variables (i.e $x_i \in \{0,1\}$)
Consider
$f(x_1,x_2,x_3,x_4) = x_1 \wedge x_2 \wedge x_3 \wedge x_4 $
I want to write $f$ in terms of two-input NOR gates. I.e, $\...
D.W.♦
- 156k
2
votes
1
answer
77
views
how do I simplify this particular boolean expression?
so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to ...
- 38.6k
4
votes
1
answer
185
views
A universal operator necessarily generates $\neg x$ for input $x,…,x$
I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more.
I saw a claim in a slideshow from a basic computer architecture course ...
- 275k
1
vote
1
answer
992
views
Logic gate which checks if the input is a negative number and changes its output based on that
I need to create a HDL which will use logic gates to demonstrate if something is a negative number in two's complement. The input is 8 bits, while the output is 1 bit, and if the input is a negative ...
- 1,151
1
vote
1
answer
69
views
what does it mean to extend an assignment?
For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a?
Sorry if this is super trivial, I did not find an answer
e.g here: No Small Linear ...
- 22.5k
2
votes
1
answer
176
views
Intuition for maxterms
I understand that in terms of minterms,
F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true.
But I am unable to develop any intuition for maxterms, ...
- 275k
1
vote
2
answers
215
views
Principle of Duality
I would like to know how to alter/add NOTs when applying Duality principle.
Suppose I have P = XY(X+Y) + NOT(Y), how to find its dual?
My book says that while applying Duality Principle to a ...
- 275k
23
votes
7
answers
246k
views
How to construct XOR gate using only 4 NAND gate?
xor gate, now I need to construct this gate using only 4 nand gate
...
- 785
2
votes
3
answers
245
views
Is $A\odot B\odot C = A\oplus B\oplus C$?
(The notations used:
$\oplus$ is XOR operator
$\odot$ is XNOR operator)
I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. ...
- 38.6k
3
votes
1
answer
198
views
Is boolean formula isomorphism NP-complete?
Problem. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as ...
- 2,255
2
votes
1
answer
204
views
When is a 1-in-3 SAT clause satisfied?
How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative.
We know that the results are if they are all positive given that:
R(Xi, Xy, Xz) =
...
- 275k