Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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
0answers
9 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
16 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
19 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 ...
2
votes
0answers
34 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
26 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 ...
4
votes
0answers
191 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 ...
1
vote
1answer
24 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 ...
0
votes
1answer
35 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
2answers
73 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 ...
1
vote
0answers
20 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_{...
0
votes
1answer
50 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 ...
0
votes
0answers
18 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 ...
2
votes
1answer
40 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 ...
3
votes
2answers
166 views

Is every X3SAT instance with no cycles satisfiable?

Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
0
votes
0answers
23 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
52 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
25 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
22 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
39 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
43 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: ...
5
votes
3answers
5k views

Boolean algebraic expression vs Propositional logic expression

There is a lot of similarity between Propositional logic and Boolean algebraic expressions. Similar aspects : 1) Both has variables of two states. 2) Operations of Boolean algebra and ...
3
votes
0answers
35 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
34 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
25 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
16 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
38 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, ...
4
votes
0answers
101 views

Can minimal CNF contain clause longer than initial CNF?

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$. Can $\Phi_{min}$ contain a clause of size $m > k$? What ...
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 ...
0
votes
4answers
6k views

Why is A(A+B) = A [Absorption Law]?

Could you proof it to me that A(A+B) = A? AA + BA [AA = A] A + AB Then what?
3
votes
0answers
129 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
48 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
40 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}_{...
4
votes
3answers
3k views

Measuring Complexity of Boolean Satisfiability Problem

How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. ...
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
48 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
11 views

K Maps: Getting simplified boolean form

I have been trying to work out the simplest Boolean form for the following K-map: I get the following expression: (x2 AND X3) OR (x1 AND x2) OR (x0 AND x2) However, via Boolean algebra, I get (x3 OR ...
0
votes
0answers
24 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
29 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 ...
2
votes
1answer
150 views

Addition, multiplication, and apostrophe used to represent boolean algebra expressions?

I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before. I can make a guess that the apostrophe is ...
1
vote
1answer
72 views

All 16 Boolean Logic Gates

I was doing some reseach and I came across a website that had listed 16 different boolean logic operators. I was wondering if all of them were real, and if so, what do they do. https://www....
2
votes
1answer
35 views

Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)

I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e ..." ...
0
votes
2answers
93 views

Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?

I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm: elimination of equivalence Elimination of ...
2
votes
2answers
57 views

Simplifying the Boolean expression $A + \bar{A}\bar{B}$?

So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$. I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), ...
1
vote
1answer
97 views

Why can't we reduce register automata to symbolic automata?

When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity). ...
0
votes
1answer
26 views

Expressing unsigned comparison through signed comparison of 2's complement

Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that <...

1
2 3 4 5