Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
273
questions
0
votes
2
answers
114
views
If it's Possible to Create the If-Statement from Simpler Primitives
This question is about how to create an if statement (one of the control-flow statements) from scratch.
An if-statement is typically a built-in construct in ...
- 1,190
2
votes
1
answer
28
views
Emulating equal operator using multiplication
I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use ...
- 275k
0
votes
1
answer
173
views
Boolean expression to a truth table
How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS.
Y=(A+B)C+AB`+(A+C)C`+(`AB)
- 4,301
3
votes
1
answer
105
views
Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?
When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?
- 8,051
2
votes
1
answer
170
views
Simplifying this Boolean Expression
I have to simplify A+C'+B'CD but I don't see how.
I had to deduce the expression starting from a logic diagram in which two AND gates were used for the B'CD part. Seeing the diagram all I can think ...
CommunityBot
- 1
1
vote
1
answer
104
views
When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?
When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable.
What I wonder about is if I can use this technique to remove ...
D.W.♦
- 156k
0
votes
1
answer
228
views
Unique boolean functions with one input
I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique".
I thought about writing down the truth table for a NOT, ...
CommunityBot
- 1
1
vote
0
answers
41
views
About sign-rank of Boolean functions
Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
- 493
3
votes
3
answers
111k
views
Which law is this expression X+ X’.Y=X+Y
Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y
...
1
vote
1
answer
629
views
Does XNOR of three variable equals XOR of same three variables
I came across following excerpt:
$(x'y'+xy)'z'+(x'y'+xy)z=x\oplus y\oplus z$
What I see is left hand side is XNOR of $x,y$ and on right, $z$ and I get XOR of of $x,y$ and $z$ !!!
In other word,
...
- 275k
0
votes
1
answer
3k
views
Proof of Demorgan's law [duplicate]
how can i prove Demorgan's law (X+Y)'=X'. Y'?I already tried studying book but doesn't understand the first step so plz answer in detail.(beginner here)
- 117
0
votes
1
answer
301
views
What's difference between SUM and OR?
While studying ALU I came across this example, now what's difference between operations of OR Gate and SUM(Adder), in binary language
- 451
1
vote
3
answers
2k
views
How many 3-SAT expressions with up to N variables are satisfiable?
TL;DR
There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
- 475
0
votes
1
answer
459
views
How can i design this function using only NAND and XOR gates?
I have this initial function \begin{split}(\overline{A}+\overline{B})(\overline{D}+\overline{C})+AB\overline{(\overline{C}+\overline{D})}\end{split}
Which i reduced to \begin{split}{\overline{AB}*\...
- 695
3
votes
1
answer
131
views
Programmatically checking equivalence of statements
So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as ...
- 29.7k
4
votes
1
answer
98
views
Common parse tree for several formulas
I have a large (~1k) number of boolean formulas like:
f1(x) = p1 AND p2
f2(x) = (p1 AND p2) OR p3
f3(x) = p4 OR !p5
The argument x is a set, and the predicates (...
D.W.♦
- 156k
1
vote
1
answer
80
views
Does the 3SAT problems have to have consistent operators?
What are the rules pertaining to 3SAT as to the actual boolean equation?
The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR ...
- 1,429
0
votes
1
answer
32
views
Taking mod $2$ with LTF gates
Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?
I do not mean that the ...
- 275k
0
votes
1
answer
106
views
LTF circuits and $AC^0$
Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).
For any vector $w \in \mathbb{R}^n$ and any number $c \in \...
- 275k
-1
votes
1
answer
293
views
A Combinational circuit Problem
A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 9 by 1001. A Combinational circuit is to be designed which takes these 4
bits as input and ...
- 3,469
1
vote
3
answers
63
views
Simplyfing a particular boolean expression
I'm having a lot of trouble with two problems the first is:
...
- 9,757
2
votes
0
answers
231
views
Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?
Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they ...
3
votes
1
answer
482
views
Infinite Boolean circuits as a model of computation
Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
D.W.♦
- 156k
1
vote
1
answer
77
views
Determine whether a variable has positive influence in Boolean function
Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$.
Given a ...
- 275k
1
vote
0
answers
111
views
Is such variant of SAT always satisfiable?
Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once.
Non-example: $(x\lor y\lor z)\land(x\...
- 1,429
1
vote
0
answers
66
views
Determining when equal 2CNF has pure literal
Let us assume that we have a 2CNF $\varphi(X,y)$. Then we want to see if there is equal formula where $y$ (or $\overline y$) is pure literal. Can this be done in polynomial time? Are there some ...
- 1,429
2
votes
1
answer
51
views
2CNF with 3 variable occurences
If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable?
Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one ...
- 275k
2
votes
0
answers
49
views
Maximal combinations in a Boolean algebra
Consider a finite set $X$ and the boolean algebra $\mathcal{P}(X)$ of the subsets of $X$. While I focus on $\mathcal{P}(X)$ in this question, the problem could be expressed more generally in any ...
- 221
2
votes
1
answer
685
views
How to find minimum number of k-input LUTs needed to express a n variable boolean function?
An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to ...
- 23
0
votes
1
answer
94
views
Understanding kQBF: changing order of quantification?
2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(...
- 1,429
1
vote
1
answer
158
views
Boolean Logic Equation
How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1.
...
- 1,483
1
vote
1
answer
255
views
Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?
Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).
Output: unsatisfiable formula.
Restrictions:
Every clause contains exactly 3 variables.
Every clause differs ...
- 1,429
3
votes
1
answer
46k
views
Two's complement Using ONLY Logic Gates
How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?
(This question was redirected to CS from Stack Overflow)
2
votes
1
answer
1k
views
Extracting Boolean Function using Machine Learning
How can machine learning help extract a Boolean relationship in a given binary input-output data set?
Let us assume that the given data set is exhaustive - ie. it cover all possible input ...
CommunityBot
- 1
-1
votes
1
answer
2k
views
How to convert a graph into a Boolean formula that represents all paths from a source node to a sink node?
I have a DAG. I want to construct a boolean formula $\varphi$ that represents all paths from a source node to a sink node.
In particular, I have a variable for each vertex. A path $v_1 \to v_2 \to \...
6
votes
1
answer
67
views
Small world theorem for set constraints
Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
D.W.♦
- 156k
0
votes
1
answer
990
views
Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law
If I have the sum-of-products expression B~CD + ACD how would I convert this so it could be implemented using 3-input NAND gates through DeMorgan's Law? Would this ...
- 28.3k
3
votes
1
answer
151
views
Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula
I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption ...
- 12.7k
1
vote
1
answer
133
views
Boolean expression to logic gates
Hello I need help with xy xor z, do I do the logic AND first or the XOR, no parenthesis. Thank You
- 81.4k
2
votes
1
answer
38
views
How to fill cell-network partition matrix of a function?
I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 1), but I can't make it past the first paragraph:
Consider the $x_l … x_{k - 1} | x_k$ partition matrix of a ...
D.W.♦
- 156k
2
votes
1
answer
221
views
Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?
In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:
$$ \langle x, u_i \rangle \leq n-2 $$
but not:
$$ \langle x, u_i \rangle \leq n-1 $$
?
To add context:
I was reading understanding machine ...
- 3,000
7
votes
1
answer
6k
views
What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?
I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in ...
D.W.♦
- 156k
2
votes
0
answers
59
views
substituting expressions
I have a set of expressions $E_1 .. E_n$ over boolean variables and I'm looking for an assignment to the variables so that all expressions are satisfied. Normally this would be NP-complete, but I ...
- 2,469
5
votes
2
answers
2k
views
Boolean absorption
A and ( A or C ) = A
And
A or A and C = A
How do these identities work?
Using the rule
A and ( B or C ) = A and B or A and C
For the first identity, I get
A and A or A and C = A or A ...
0
votes
1
answer
802
views
What is the simplification of AB + BC + (~B)C?
AB + C is not the answer.
The correct answer is AB + BC. HOW?
- 460
0
votes
2
answers
421
views
Is 2QBF in P^NP?
2QBF is the following problem: given a CNF formula $\psi$ on $2n$ variables, determine the truth value of
$$\forall x \in \{0,1\}^n . \exists y \in \{0,1\}^n . \psi(x,y).$$
Question: Is 2QBF in $P^{...
D.W.♦
- 156k
0
votes
1
answer
1k
views
How to simplify sum of products boolean expression?
I started with this sum of products:
abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d
I have been able to simplify to this:
...
- 317
4
votes
1
answer
440
views
Random forests on monotone training set yields a monotone classifier?
Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function?
Suppose I apply the ID3 algorithm (the greedy algorithm) to ...
D.W.♦
- 156k
2
votes
1
answer
115
views
Boolean Algebra: Operation Linkage Laws
Im studying some properties of Boolean Algebra and found the Operation Linkage Laws.
Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can ...
- 275k
-2
votes
3
answers
133
views
How does the following truth table show Y's behaviour? [closed]
a b c Y
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 1 0
1 1 0 0
...
- 1,483