Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
17 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
36 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
68 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
64 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
23 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
17 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
21 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
56 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
15 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
25 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
17 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
0answers
8 views

Which of the boolean expressions is a max-/minterm?

I have a exercise where I have to decide whether a term is a max-/minterm and reduce the expression to its corresponding max-/mintern or neither of them and for the following expression I do not know ...
0
votes
1answer
42 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
0answers
12 views

How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey ...
0
votes
0answers
21 views

Prove the boolean function E = F + G contains of the sum of the minterms of F and G

I'm given a boolean function E which is result of the sum of F and G (Where both F and G are boolean functions for sure). By using K-Map I can easily understand why E would have the sum of the ...
0
votes
1answer
40 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
50 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
40 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
33 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
213 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
45 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
21 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
79 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
19 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
74 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
28 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 ...
0
votes
0answers
18 views

Is the number of sub-boolean algebras of a set with size of n equal to Bell(n)?

In boolean algebra (P(S),+,.,’) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements. We must have S-x for every subset x⊆S to hold complements. It seems like ...
0
votes
0answers
80 views

Note down the possible states in a truth table

You are required to automate the control of the water tank in your home. There are two water contact sensors that turn to a TRUE state when in contact with water and a FALSE state when not. Sensor $1 (...
4
votes
0answers
26 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
34 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
45 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
55 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
37 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
41 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
94 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
15 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
0answers
45 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
29 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
vote
1answer
29 views

Relationship between circuit size and formula size in Sipser text

The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
3
votes
0answers
131 views

Boolean function minimization

Does there exist a Boolean function for which no sum-of-products expression that minimizes the number of products also simultaneously minimizes the number of literals (counting repetitions)? ...
1
vote
0answers
64 views

Petrick's Méthod With Maxterms

I recently learnt about Quine-McCluskey and Petrick's methods and they are all okay by me using minterms the procedure is as follows : 1- Reduce the prime implicant chart by eliminating the essential ...
2
votes
0answers
42 views

Boolean matrix / satisfiability problem [duplicate]

Let $M$ be an $m\times n$ matrix with all elements in $\{1,0\}$, $m >> n$. Let $\mathbf{v}_0, \ldots, \mathbf{v}_n$ be the columns of $M$. I want to find all sets of columns $S = \{\mathbf{v}_{...
2
votes
0answers
22 views

Simulating Boolean Circuit with RAM

Statement: Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM). Could you please supply me with a reference to an ...
2
votes
1answer
51 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
0
votes
0answers
27 views

Which gates are “pre computation” universal?

In the following, by “functions” I will mean 2 input 1 output Boolean logic functions (for conciseness). A function is called “universal” if by using it (sometimes multiple times, chained together), ...
1
vote
1answer
32 views

Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...

1
2 3 4 5