Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
2k views

Proof of Demorgan's law [duplicate]

how can i prove Demorgan's law (X+Y)'=X'. Y'?I already tried studying book but doesn't understand the first step so plz answer in detail.(beginner here)
0
votes
1answer
47 views

What's difference between SUM and OR?

While studying ALU I came across this example, now what's difference between operations of OR Gate and SUM(Adder), in binary language
0
votes
1answer
320 views

How can i design this function using only NAND and XOR gates?

I have this initial function \begin{split}(\overline{A}+\overline{B})(\overline{D}+\overline{C})+AB\overline{(\overline{C}+\overline{D})}\end{split} Which i reduced to \begin{split}{\overline{AB}*\...
1
vote
3answers
292 views

How many 3-SAT expressions with up to N variables are satisfiable?

TL;DR There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
3
votes
1answer
84 views

Programmatically checking equivalence of statements

So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as ...
4
votes
1answer
64 views

Common parse tree for several formulas

I have a large (~1k) number of boolean formulas like: f1(x) = p1 AND p2 f2(x) = (p1 AND p2) OR p3 f3(x) = p4 OR !p5 The argument x is a set, and the predicates (...
1
vote
1answer
48 views

Does the 3SAT problems have to have consistent operators?

What are the rules pertaining to 3SAT as to the actual boolean equation? The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR ...
0
votes
1answer
57 views

LTF circuits and $AC^0$

Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights). For any vector $w \in \mathbb{R}^n$ and any number $c \in \...
0
votes
1answer
28 views

Taking mod $2$ with LTF gates

Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates? I do not mean that the ...
1
vote
0answers
164 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
212 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
39 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
32 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
53 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
42 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
1answer
112 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
181 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
57 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
128 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
120 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
761 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
57 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
63 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
588 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 ...
3
votes
1answer
59 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
105 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
147 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
10k 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
306 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
138 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
429 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
210 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
90 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
4k 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
659 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
119 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
146 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
216 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
548 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
1k 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 ...