Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
31 views

Efficient bit-level implementation of Boolean polynomials with few variables

A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
0
votes
1answer
35 views

What boolean algebra simplification is applied in this Shannon's expansion?

Found this question about Shannon's expansion. While I am trying to follow its logic, found one super convenience simplification used. Can we do this in general while dealing with boolean algebra? or ...
0
votes
1answer
42 views

Boolean formula for graph 3COL

For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be ...
2
votes
3answers
441 views

Why is SAT based on the CNF?

I have been reading up on Boolean logic and, specifically, the Boolean satisfiability problem. I have seen several people mention that the expression must be converted to conjunctive normal form (CNF) ...
0
votes
1answer
65 views

Sorting by boolean algebra (hardware) instead of algorithm (software)

Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11] Maybe that case seems complicated,...
0
votes
0answers
32 views

Functions expressible in conjunctive normal form, but with XOR replacing OR

What are all the functions $f:\{0,1\}^n\rightarrow\{0,1\}$ that can be expressed as a product of affine Boolean functions? For example, if $x_1,x_2,x_3\in\{0,1\}$ then $x_1x_2x_3\oplus x_2x_3 \oplus ...
0
votes
0answers
20 views

Doubt regarding the physical folding of a two dimensional K-map

While grouping terms in a k-map, if we pair terms on the first row with the ones on the last, it can be interpreted as the folding the 2-D map in the form of a cylinder, along the horizontal axis. ...
-1
votes
1answer
147 views

Four Queens Problem to a Conjunctive Normal Form

Given a chessboard with 4 rows and 4 columns (4x4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Assign a Boolean variable to each cell of the board as below (1, 2, 3, etc. are variable names) If a ...
3
votes
2answers
51 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-...
2
votes
1answer
43 views

What are the limits of Boolean Algebra?

Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, ...
1
vote
1answer
25 views

Definition and use of a Boolean equation system

According to google, a system of boolean equations is defined as follows Essentially, a Boolean equation system is an ordered sequence of fixed point equations over Boolean variables, with associated ...
0
votes
0answers
9 views

Minimization of an expression through K-map, in which there are more chances of errors and with Quine-McCluskey Method there are less chance of errors

Minimization of any expression of 4 variables through K-map, in which there are more chances of errors (like error in grouping) and the same expression with Quine-McCluskey Method there are less ...
-2
votes
1answer
60 views

Simplify $X'(X+Y) + (Y+X.X) ( X + Y') + Z + X.Z$

I wanna know if $X'(X+Y)$ means $X'.X+Y.X'$? Does it have an AND gate after $X'$? Notation: $X'$ : NOT $X$ $X + Y$: $X$ OR $Y$ (OR gate) $X.Y$ : $X$ AND $Y$ (AND gate) New to boolean, can't seem ...
1
vote
2answers
34 views

Simplifying the boolean expression xy + (!x)z + yz with boolean algebra?

So using K-maps I was able to simplify xy + (!x)z + yz to xy + (!x)z, and I double-checked that the truth tables are the same. I'm having trouble understanding how I would have used boolean algebra to ...
1
vote
1answer
39 views

How to perform AND on binary "recursive repeating sequences"?

Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
-1
votes
1answer
81 views

Prove x . y' . z' is y' . z'

Please, how can I prove that x . y' . z' simplifies to y' . z'? I have tried without success. Below is the context of my question; I am taking a course on Coursera
2
votes
0answers
69 views

Prove lower bound on boolean circuit

Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$: $ A = \begin{...
1
vote
1answer
27 views

How to find the reverse of a binary string with simple binary operators?

I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome? So my approach is to feed the input to a circuit that reverses the input, ie if ...
0
votes
0answers
21 views

Newbie 2s complement to binary circuits help

I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (...
2
votes
1answer
22 views

What can be said about the Fourier expansion of compositions of Boolean functions, if anything?

Let $\chi_S: \mathbb{F}_2^n \to \{\pm 1\}, x \mapsto (-1)^{\sum_{i \in S}x_i}$ for every $S \subseteq [n]$ denote the parity functions from $\mathbb{F}_2^n$ to $\{\pm 1\}$. Then, of course, every $f: \...
1
vote
0answers
13 views

Intuition for a 2-Monotone Boolean Function

I am currently studying Chapter 8 of Krama and Hammer's textbook on Boolean Functions, and having a hard time understanding what it means for a function to be "k-monotone." I am currently ...
3
votes
1answer
61 views

What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
1
vote
0answers
23 views

What is the intuitive logic behind the working of the Variable Entered K-Map (VEM)?

In this site here they have just said how to minimize a function using VEM. But no intuitive logic behind the same has been stated, making it too mechanical. And I am very bad at memorizing things, so ...
2
votes
0answers
27 views

closure property violated by palindrome language

It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
1
vote
1answer
21 views

Functions with small support have small circuits

I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand: Show that if a function $f\colon \{0,1\}^n→\...
0
votes
1answer
45 views

Simplify Boolean expression

The following Boolean expression is simplified into its minimal number of literals: $$x'y' + yz +x'yz' \implies x'+yz.$$ How do you logically conclude this using the Boolean Laws?
0
votes
1answer
52 views

is duality principle in boolean algebra is true for every expression

Let say A = 1 and B = 1 and then A+B = 1 now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0 but this is not 0, because 1.1 = 1, so please anyone clear my ...
3
votes
0answers
61 views

Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...
0
votes
0answers
72 views

Karnaugh Map: does maximal overlap always produce simplest boolean expression?

Suppose I have a 4x4 Karnaugh map with a few cells that are don't cares, and there are two ways of producing 3 groups of 4 cells. One of these ways overlaps groupings more that the other. Is one way ...
1
vote
1answer
35 views

Distribution of random Fourier coefficients

Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by $$ \hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot ...
4
votes
0answers
230 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 ...
0
votes
1answer
62 views

For a logic gate to be universal, must it necessarily be able to perform duplication?

It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
1
vote
0answers
24 views

Computational complexity in Boolean network

An Boolean control networks can be expressed as \begin{equation} \label{ControlBN} \left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {x_{...
1
vote
2answers
83 views

How to convert $(0.11001100...)_2$ to a decimal number

I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number. But I have a hard time finding an algorithm for converting a binary number with ...
0
votes
0answers
24 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
0
votes
1answer
91 views

What does it mean to "show algebraically" in propositional logic?

The biconditional operator $\iff$ of Propositional Logic can be defined by the identity $p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$ Use the identity $(1.1)$ and identities ...
2
votes
1answer
41 views

Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$

Let $\mathbb{Z}_2^n$ be the field of bitvectors of length $n$ and define the xor operator $\oplus$ and the addition operator $+$ over this field, with $+$ having the usual overflow semantics (take ...
0
votes
0answers
43 views

How can I parse a boolean expression to group it based on the conjunction?

I have to design an algorithm to parse an array of terms and conjunctions into a grouped boolean expression. I never studied computer science and don't usually need this for web development, but today ...
4
votes
0answers
28 views

Constructing xor separable boolean upper bound

Problem statement Suppose I have a boolean function $f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$ where $\mathbb{F}_2 = \{0,1\}$. I define two boolean functions $h: \mathbb{F}_2^n \to \...
0
votes
0answers
49 views

Program to Translate Turing Machine to Tableau?

Is a program available to translate a Turing Machine program to Boolean tableau format as used for example in proofs of the Cook-Levin theorem?
0
votes
0answers
47 views

Implementation of logic function using a multiplexer

A question asks me to simplify the following boolean expression then use a multiplexer to implement it. $$\overline{A}BC + \overline{A+B+C}+A\overline{B}\overline{C} + B\overline{C}$$ I evaluated ...
1
vote
1answer
79 views

Worst simultaneous blowup when converting to CNF and DNF

I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the ...
17
votes
11answers
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: ...
3
votes
0answers
39 views

How do I optimize a set of sub-lists which can combine to recreate higher level lists?

I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list ...
1
vote
0answers
49 views

Partially defined boolean function

Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
1
vote
1answer
27 views

How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]

I need help how to interpret the following notation for $f$: Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a ...
1
vote
0answers
116 views

Examples of relatively complex truth tables/logic gates in real life?

I'm researching truth tables, logical gates, and boolean algebra expressions. I'm trying to find specific real-life examples of logic gates and/or truth tables used in algorithm or circuit design in ...
1
vote
0answers
16 views

Boolean circuit multigraph

Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer]. He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
4
votes
1answer
100 views

Why do Karnaugh maps work?

The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, ...
1
vote
0answers
33 views

Logic minimization via 2 inputs NOR gates: Is it monotone w.r.t to adding a minterm?

notation: $x+y:=\mbox{OR}(x,y)$, $\bar x:=\mbox{NOT}(x)$, $xy:=\mbox{AND}(x,y)$, 1:=TRUE, 0:=FALSE. Let $f$ be a Boolean function of $n$-variables, i.e. $f: \{0,1\}^n \to \{0,1\}$. minterm:= any ...

1
2 3 4 5