Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
78 views

How do you represent basic arithmetic using boolean function? [closed]

Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers? ...
1
vote
0answers
101 views

Connection between formula size and time complexity

Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree. Is there a connection between ...
1
vote
1answer
53 views

Function with minimum sensitivity

Let sensitivity be defined as in Sensitivity and Block sensitivity Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$? Is ...
5
votes
2answers
672 views

Sensitivity and Block sensitivity

May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity. Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let ...
2
votes
2answers
479 views

Karnaugh map simplification

I'm working through an example that looks like a fairly simple Karnaugh map and simplification, but I feel stupid that I can't seem to understand the correct answer. This is the map: My groupings: ...
1
vote
0answers
54 views

How do I triangularise a netlist?

I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
1
vote
1answer
34 views

Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
1
vote
2answers
458 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): ...
0
votes
1answer
101 views

Unique boolean functions with one input

I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique". I thought about writing down the truth table for a NOT, ...
1
vote
1answer
132 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
710 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
161 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
137 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
115 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
61k 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
190 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
119 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
328 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
177 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
113 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
319 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) $$ ...