Questions tagged [boolean-algebra]

The tag has no usage guidance.

281 questions
Filter by
Sorted by
Tagged with
250k 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 ...
• 785
6k views

Is it possible to write an AND gate using XOR gates?

How could I express an AND gate using only XOR gates ?
• 425
5k views

Why do logic gates behave the way they do?

I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do. Why for example: ...
• 317
4k views

Are Boolean functions Turing complete

A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$. The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left ...
• 1,624
178 views

• 404
2k views

Do Karnaugh maps yield the simplest solution possible?

I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example: Truth table (inputs are A B C; output is F): ...
115k 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 ...
407 views

Help me understand the logic behind x - y in binary by boolean?

x and y are 4 bit signed numbers (2s complement..) x - y can be obtained by: !(!x + y) I know that in 2s complement ...
• 358
576 views

What happens to uninterpreted predicates in Ackermann's reduction?

I know the procedure to apply the Ackermann's reduction to a formula that doesn't involve uninterpreted predicates. But, how do we treat the uninterpreted boolean predicates? Nearly all the examples I ...
1k views

What is the XNOR of 3 or more inputs?

We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's. But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 ...
445 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 ...
• 159k
77 views

Compact representation for quantified boolean formula

I got black-box (too big to analyze) boolean formula f(...) with 3 sets of input arguments: $x_1... x_i, y_1... y_j, z_1... z_k$. And I want to find such values for x-arguments that for every y-...
794 views

Number of solutions to linear system of equations over GF(2)

Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option. Is there a ...
• 13.4k
99 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 (...
• 43
2k views

Simplest combination of logic gates to produce a given set of outputs

Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the ...
288 views

Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
34 views

• 31
161 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 ...
732 views

Relation between Lattice and Boolean Algebra

In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). ...
• 2,191
675 views

Algorithm for simplifying ANF or polynomials?

I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates. For instance: $B_{out} = B_1 B_2 \oplus B_1 B_3$ I was wondering, are there any ...
• 1,358
78 views

Stalmarck's method: x ≡ x → z, does z have to be true?

I have been researching Ståmarck's method 1. In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that: y $\to$ z $\equiv$ x where x, y and z are booleans which ...
• 53