Questions tagged [boolean-algebra]

The tag has no usage guidance.

1
vote
0answers
151 views

Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?

Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they ...
1
vote
3answers
58 views

Simplyfing a particular boolean expression

I'm having a lot of trouble with two problems the first is: ...
2
votes
1answer
194 views

Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
1
vote
1answer
38 views

Determine whether a variable has positive influence in Boolean function

Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$. Given a ...
1
vote
0answers
71 views

Is such variant of SAT always satisfiable?

Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once. Non-example: $(x\lor y\lor z)\land(x\...
2
votes
1answer
31 views

2CNF with 3 variable occurences

If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable? Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one ...
1
vote
0answers
50 views

Determining when equal 2CNF has pure literal

Let us assume that we have a 2CNF $\varphi(X,y)$. Then we want to see if there is equal formula where $y$ (or $\overline y$) is pure literal. Can this be done in polynomial time? Are there some ...
2
votes
0answers
41 views

Maximal combinations in a Boolean algebra

Consider a finite set $X$ and the boolean algebra $\mathcal{P}(X)$ of the subsets of $X$. While I focus on $\mathcal{P}(X)$ in this question, the problem could be expressed more generally in any ...
2
votes
0answers
109 views

Is boolean formula isomorphism NP-complete?

Problem. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as ...
2
votes
1answer
174 views

How to find minimum number of k-input LUTs needed to express a n variable boolean function?

An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to ...
0
votes
1answer
54 views

Understanding kQBF: changing order of quantification?

2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(...
1
vote
1answer
121 views

Boolean Logic Equation

How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1. ...
1
vote
1answer
102 views

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable). Output: unsatisfiable formula. Restrictions: Every clause contains exactly 3 variables. Every clause differs ...
-1
votes
1answer
734 views

How to convert a graph into a Boolean formula that represents all paths from a source node to a sink node?

I have a DAG. I want to construct a boolean formula $\varphi$ that represents all paths from a source node to a sink node. In particular, I have a variable for each vertex. A path $v_1 \to v_2 \to \...
6
votes
1answer
55 views

Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
4
votes
1answer
62 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 ...
0
votes
1answer
548 views

Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law

If I have the sum-of-products expression B~CD + ACD how would I convert this so it could be implemented using 3-input NAND gates through DeMorgan's Law? Would this ...
2
votes
1answer
50 views

Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula

I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption ...
1
vote
1answer
103 views

Boolean expression to logic gates

Hello I need help with xy xor z, do I do the logic AND first or the XOR, no parenthesis. Thank You
2
votes
1answer
21 views

How to fill cell-network partition matrix of a function?

I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 1), but I can't make it past the first paragraph: Consider the $x_l … x_{k - 1} | x_k$ partition matrix of a ...
1
vote
1answer
136 views

Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is: $$ \langle x, u_i \rangle \leq n-2 $$ but not: $$ \langle x, u_i \rangle \leq n-1 $$ ? To add context: I was reading understanding machine ...
2
votes
1answer
157 views

Simplifying this Boolean Expression

I have to simplify A+C'+B'CD but I don't see how. I had to deduce the expression starting from a logic diagram in which two AND gates were used for the B'CD part. Seeing the diagram all I can think ...
2
votes
3answers
8k views

Absorption Law Proof by Algebra

I'm struggling to understand the absorption law proof and I hope maybe you could help me out. The absorption law states that: $X + XY = X$ Which is equivalent to $(X \cdot 1) + (XY) = X$ No problem ...
2
votes
1answer
2k views

What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in ...
2
votes
0answers
50 views

substituting expressions

I have a set of expressions $E_1 .. E_n$ over boolean variables and I'm looking for an assignment to the variables so that all expressions are satisfied. Normally this would be NP-complete, but I ...
5
votes
2answers
1k views

Boolean absorption

A and ( A or C ) = A And A or A and C = A How do these identities work? Using the rule A and ( B or C ) = A and B or A and C For the first identity, I get A and A or A and C = A or A ...
0
votes
1answer
282 views

What is the simplification of AB + BC + (~B)C?

AB + C is not the answer. The correct answer is AB + BC. HOW?
0
votes
2answers
121 views

Is 2QBF in P^NP?

2QBF is the following problem: given a CNF formula $\psi$ on $2n$ variables, determine the truth value of $$\forall x \in \{0,1\}^n . \exists y \in \{0,1\}^n . \psi(x,y).$$ Question: Is 2QBF in $P^{...
0
votes
1answer
403 views

How to simplify sum of products boolean expression?

I started with this sum of products: abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d I have been able to simplify to this: ...
1
vote
1answer
73 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). ...
2
votes
1answer
200 views

Random forests on monotone training set yields a monotone classifier?

Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function? Suppose I apply the ID3 algorithm (the greedy algorithm) to ...
2
votes
1answer
89 views

Boolean Algebra: Operation Linkage Laws

Im studying some properties of Boolean Algebra and found the Operation Linkage Laws. Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can ...
-2
votes
4answers
3k 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?
1
vote
1answer
629 views

Extracting Boolean Function using Machine Learning

How can machine learning help extract a Boolean relationship in a given binary input-output data set? Let us assume that the given data set is exhaustive - ie. it cover all possible input ...
-2
votes
3answers
117 views

How does the following truth table show Y's behaviour? [closed]

a b c Y 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 ...
0
votes
0answers
140 views

how to evaluate a boolen expression

what is an easy but efficient way to evaluate Boolean Expression. I have been searching a lot in google but not really finding a good book or site which has working algorithm. Input string (A=100) ...
1
vote
1answer
185 views

Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates. A Turing machine may halt or not in a particular ...
1
vote
1answer
83 views

How to reduce C′A′B + CAB′ to C′B + CB′?

I faced this Boolean expression: $C'(A'B+A)+C(A'+AB')$ It was solved as follows: $C'(A'B+A)+C(A'+AB')$ $=C'(A+B)+C(A'+B') $ ...by applying absorption laws $(I)$ $=C'A+C'B+CA'+CB'$ $=(C\oplus ...
3
votes
1answer
528 views

Relation between Lattice and Boolean Algebra

In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). ...
4
votes
2answers
1k views

Simplest combination of logic gates to produce a given set of outputs

Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the ...
1
vote
2answers
953 views

How do i simplify this SOP expression?

Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer ...
3
votes
4answers
1k views

Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$

I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow. I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ ...
3
votes
2answers
1k 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. ...
0
votes
0answers
37 views

How storage affect if we use tertiary language? [duplicate]

as we uses binary language in all the computer systems around us which consist of 0s and 1s (Off and On) bits. Let assume that someone is developing a computer system based on tertiary system -1, 0, 1 ...
-1
votes
2answers
519 views

How to prove the following xor equation?

In a test paper, a question is given as : ...
1
vote
3answers
3k views

Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image ...
2
votes
1answer
474 views

Algorithm for simplifying ANF or polynomials?

I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates. For instance: $B_{out} = B_1 B_2 \oplus B_1 B_3$ I was wondering, are there any ...
0
votes
2answers
88 views

How do I simplify this boolean expression?

I have constructed truth tables to prove that: $ABC + ABC'+ AB'C +A'BC = AB+AC+BC$ How do I prove it by simplifying the expression? I know that I can simplify: $ABC + ABC' = AB(C+C')=AB$. However I ...
1
vote
1answer
110 views

Boolean expression logic law confusion

I've been trying to attempt a particular question that I need to translate truth table into boolean expression but I'm completely stuck on one point now. First, I worked it out by using Sums of ...
1
vote
1answer
56 views

Counterexample for equality in Quantified Boolean Formula

I'm looking for a counterexample for the following (false) equality. It should exist. $n$ is an odd integer. $f(x_1, x_2 .. x_n)$ is a boolean expression in 3 CNF form with boolean variables x. $A =...