Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
37 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
20 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
17 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
47 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 (...
-2
votes
0answers
16 views

Universal gate proof using De Morgan Theorem?

How to implement of Universal gate using NAND and NOR gates, and how to verify them with DeMorgan's theorem whether they are right? I need expert solution in simple English. Thanks in advance!
4
votes
0answers
24 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
17 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
37 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
33 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
31 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
13 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
13 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
31 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
24 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
26 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
127 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
44 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}_{...
1
vote
0answers
20 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 ...
1
vote
1answer
46 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
10 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
23 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 ...
0
votes
0answers
32 views

Why does this finite state machine state transition diagram solution has more states than my solution?

I can't figure out what is wrong with my solution and why does it differ from book's solution. I think the only thing that matters is the previous state of A so that there should be two states, one ...
2
votes
1answer
80 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
68 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
29 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 ..." ...
2
votes
2answers
56 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), ...
0
votes
2answers
73 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 ...
0
votes
1answer
25 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 <...
2
votes
1answer
73 views

3-CNF to “independent form”

Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the ...
2
votes
1answer
63 views

Conjunctive normal form to simple elementary algebra

I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra. An example: $$\phi=\left(x_1 \vee x_2 \right) \wedge \...
2
votes
1answer
131 views

Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
3
votes
1answer
64 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
3
votes
1answer
114 views

Is is possible to determine if a given number is xor combination of some numbers?

I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
2
votes
2answers
1k views

Which is the correct XOR Gate Symbol

I'm confused between 2 XOR gate symbols, they have a minor difference but I'd still like to know if they truly are identical. One looks like - The other, like Notice, how for one of them the ...
3
votes
0answers
58 views

Iterating over a union of sets denoted by bitmasks

Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$. Such bitmask denotes a set $S \subset \mathbb{B}^...
2
votes
2answers
153 views

Prime Implicants in Boolean Function

A Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0. How many essential prime implicants does F ...
1
vote
1answer
46 views

What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
1
vote
1answer
71 views

Modeling equality in an ILP

Lets say we have integer variables $a \in\mathbb{Z}^n$ and $M \in\{0,1\}^{n\times L}$. I am promised $a_i \leq L$, for some fixed constant $L$. I want to model the constraint $$M_{i,j} \iff (a_i=j)$...
2
votes
1answer
53 views

Logic of multiple variables in ILP

Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
0
votes
2answers
504 views

how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates

How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?
2
votes
1answer
372 views

State Transition Diagrams for XOR

I have found two different versions for State Transition Diagrams for XOR. I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please? Are they both ...
0
votes
2answers
89 views

Why is Boolean satisfiability such a rare case?

In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot ...
3
votes
2answers
154 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 ...
1
vote
0answers
248 views

How do I get the NAND gate configuration for full adder from the logic table?

I'm self-studying, but I've gotten stuck already. If I'm given the logic table for a full-adder or any two-output table, how do I figure out the NAND-gate configuration, preferably methodically? ...
-1
votes
1answer
45 views

Truth table and logic circuit problem

Does anyone know how to make this into a truth table and a logic circuit? (x•y)+x If so please send me the answer.

1
2 3 4 5