Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [boolean-algebra]

The tag has no usage guidance.

1
vote
1answer
128 views

How to construct a truth table

Yes this is a homework problem, but I only need help setting it up, there are 7 parts to the question once I set it up: We want to build a function Y = 2X + 3 where X denotes a 3-bit unsigned ...
5
votes
2answers
1k views

Converting truth table to algebraic normal form

Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)? I have seen that Sage has one implementation (official ...
3
votes
1answer
639 views

Karnaugh map with don't care: increasing the number of groups instead of simplifying

AB 00 01 11 10 00 | x | 1 | 0 | 1 | CD 01 | 0 | 1 | x | 0 | 11 | 1 | x | x | 0 | 10 | x | 0 | 0 | x | The answer to the ...
2
votes
1answer
139 views

Can the Euclidean distance function be computed using only XOR's

The Eulidean distance function $d$ of $x$ and $y$ is given by: $ d(x,y)=\sqrt{x^2-y^2} $ Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. ...
1
vote
0answers
50 views

What is the current state of research on the representation of boolean functions using wavelets

The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google. http://cs.mcgill.ca/~hatami/comp760-2011/ http://...
2
votes
2answers
237 views

Is my simplified explaination of the XOR swap correct?

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows: a = a ^ b b = a ^ b a = a ^ b Now, I was ...
2
votes
2answers
135 views

What is the state of the art in efficient boolean function operations?

How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT? The most up-to-date work that I can find on this subject is about 20 years old (...
1
vote
1answer
45 views

Reducing a system of two boolean algebra assertions to a single one

Given a system of two Boolean Algebra equalities a = b. c = d. one can exhibit a single equation F(a,b,c,d) = 0. which is ...
1
vote
0answers
114 views

Simplifying circuits using boolean algebra

I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated. I have y'+z+w'x+wx' I feel like I could use DeMorgan'...
9
votes
2answers
2k 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
vote
3answers
53k 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 ...
5
votes
1answer
188 views

Finding a graph-theoretic representation of expressions in Boole's algebra

I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but ...
0
votes
1answer
1k views

Odd Parity Function [closed]

I am trying to define a Odd Parity Function that takes three 1 bit inputs and will output a 1 if the 3 bits are odd as a Boolean function. ...
6
votes
0answers
118 views

Boolean formula that agrees with most truth assignments

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
4
votes
1answer
315 views

Issue understanding the reduction of SAT to 3-SAT in poly time

Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-...
2
votes
1answer
155 views

Recognizing Horn clauses

I am currently studying model theory and I am trying to decide if a clause is a Horn Clause. I know that a Horn Clause is a clause with at most one positive literal, but there are some clauses that it ...
1
vote
0answers
107 views

Popcount Orders and Lexicographic Orders [closed]

A popcount order of a two bit vector {1,1}=3 can be given by: {{1, 1}, {1, 0, 1}, {1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}, {1, 
 0, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 0}} and as a ...
1
vote
1answer
307 views

Laws to simplify a boolean formula

$$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ can simplify down to  $$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ ...