# Questions tagged [boolean-algebra]

The tag has no usage guidance.

173 questions
Filter by
Sorted by
Tagged with
58 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 ...
40 views

65 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 ...
80 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 ...
56 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)$$
40 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 ...
17 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 ...
36 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 ...
46 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, ...
112 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. ...
108 views

### Is any sudoku solver an SAT solver?

I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning ...
114 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) = ...
21 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 ...
43 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)
86 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 ...
58 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?
39 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 ...
682 views

1k 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)
43 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