# Questions tagged [boolean-algebra]

The tag has no usage guidance.

273 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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)
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?
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 ...
1 vote
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 ...
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, ...
1 vote
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?
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
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, ...
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)
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
1 vote
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-...
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}*\...
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 ...
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 (...
1 vote
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 ...
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 ...
106 views

1 vote
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 ...
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 ...
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 ...
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 ...
94 views

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 ...
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 ...
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 ...
1 vote
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
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 ...
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 ...
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 ...
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 ...
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 ...
802 views

### What is the simplification of AB + BC + (~B)C?

AB + C is not the answer. The correct answer is AB + BC. HOW?
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^{...
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: ...
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 ...