# Questions tagged [boolean-algebra]

The tag has no usage guidance.

175 questions
Filter by
Sorted by
Tagged with
28 views

### Can numbers (not sets of numbers) in Linear Integer Arithmetic form a Boolean algebra?

As far as I understood, Boolean algebra is just one of the many first-order theories (1). It has the signature $\{\sqcap, \sqcup, \neg, \bot, \top\}$ and the axioms: associativity, commutativity, ...
20 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 <...
61 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

### 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 ...
68 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 ...
42 views

40 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? ...
3k views

### Why is A(A+B) = A [Absorption Law]?

Could you proof it to me that A(A+B) = A? AA + BA [AA = A] A + AB Then what?
38 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.
43 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 ...
239 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 ...
65 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 ...
45 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. ...
76 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 ...
143 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 ...
68 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 ...
78 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. ...
8 views

### OR functions and SQ-Learning

Anyone can describe or give a reference which has a clear description and detailed proof of the SQ-Learning algorithm for the OR class of Boolean functions?
39 views

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 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 ... 1answer 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 ... 1answer 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 ... 1answer 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 ... 1answer 47 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, ... 2answers 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 ... 7answers 159k 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 ... 3answers 113 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. ... 0answers 111 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 ... 1answer 113 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 116 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) = ... 2answers 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 ... 1answer 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 ...
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)