# Questions tagged [boolean-algebra]

The tag has no usage guidance.

234 questions
Filter by
Sorted by
Tagged with
70 views

### Petrick's Méthod With Maxterms

I recently learnt about Quine-McCluskey and Petrick's methods and they are all okay by me using minterms the procedure is as follows : 1- Reduce the prime implicant chart by eliminating the essential ...
43 views

57 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?
980 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?
723 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 ...
102 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 ...
185 views

### Is every X3SAT instance with no cycles satisfiable?

Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
330 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? ...
49 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.
130 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 ...
938 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 ...
253 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 ...
59 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. ...
124 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 ...
3k 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 ...
106 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 ...
254 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. ...
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, $\... 1answer 72 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 ... 1answer 139 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 ... 1answer 116 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)$$ 1answer 391 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 ... 1answer 52 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 ... 2answers 149 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 ... 1answer 124 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, ... 3answers 149 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. ... 2answers 333 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 ... 1answer 177 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) = ... 1answer 25 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 ...
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)