Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
0answers
15 views

Minimal realization of a boolean function in terms of NOR gates?

Let we have $n$ boolean variables $x_1,\dots,x_n$. Let $y=f(x_1,\dots,x_n)$ be a boolean function which is given, say as a truth table. How to find a realization (i.e., boolean algebraic form) using ...
4
votes
1answer
40 views

A universal operator necessarily generates $\neg x$ for input $x,…,x$

I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more. I saw a claim in a slideshow from a basic computer architecture course ...
1
vote
0answers
26 views

how many boolean functions exist that satisfy the condition

how many boolean functions exist that satisfy the condition : $Not[f(x_1,x_2,x_3,....,x_n)]$ = $f(Not(x_1), Not(x_2),...,Not(x_n))$
0
votes
1answer
27 views

Logic gate which checks if the input is a negative number and changes its output based on that

I need to create a HDL which will use logic gates to demonstrate if something is a negative number in two's complement. The input is 8 bits, while the output is 1 bit, and if the input is a negative ...
0
votes
0answers
16 views

Specifying a Neural Network for a Boolean function

So I have tried doing this problem and made a truth table for 16 variables but now I am stuck trying to brute force the solution. (It is easier to visualize it with 2 variables but 4 is making it ...
1
vote
1answer
14 views

what does it mean to extend an assignment?

For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a? Sorry if this is super trivial, I did not find an answer e.g here: No Small Linear ...
1
vote
2answers
27 views

Principle of Duality

I would like to know how to alter/add NOTs when applying Duality principle. Suppose I have P = XY(X+Y) + NOT(Y), how to find its dual? My book says that while applying Duality Principle to a ...
2
votes
1answer
22 views

Intuition for maxterms

I understand that in terms of minterms, F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true. But I am unable to develop any intuition for maxterms, ...
2
votes
3answers
96 views

Is $A\odot B\odot C = A\oplus B\oplus C$?

(The notations used: $\oplus$ is XOR operator $\odot$ is XNOR operator) I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. ...
1
vote
1answer
55 views

Is any sudoku solver an SAT solver?

I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning ...
2
votes
1answer
21 views

When is a 1-in-3 SAT clause satisfied?

How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative. We know that the results are if they are all positive given that: R(Xi, Xy, Xz) = ...
2
votes
1answer
21 views

Emulating equal operator using multiplication

I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use ...
0
votes
1answer
40 views

Boolean expression to a truth table

How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS. Y=(A+B)C+AB`+(A+C)C`+(`AB)
0
votes
2answers
85 views

If it's Possible to Create the If-Statement from Simpler Primitives

This question is about how to create an if statement (one of the control-flow statements) from scratch. An if-statement is typically a built-in construct in ...
0
votes
0answers
20 views

How to Represent an If Statement with Boolean Algebra Primitives

I saw this: Generic method for implementing if-else statement in hardware (using gates,mux-demux,flip flops ) etc. However it's a bit over my head atm. I am wondering, instead of an ...
0
votes
0answers
14 views

Application-scope, run-time disable-able conditional statements

Background Mainstream programming languages support conditional statements, such as: if( condition ) { operation; } Once coded, changing the condition often ...
2
votes
1answer
49 views

Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?

When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?
1
vote
1answer
26 views

When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?

When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable. What I wonder about is if I can use this technique to remove ...
1
vote
0answers
190 views

Boolean Algebra : Using identities, prove x(x + y) = x

Example: Prove the ABSORPTION LAW: $$ x(x + y) = x $$ $ Solution: \\ x(x + y) \\ = (x + 0)(x + y) \;\;\;\;\; Identity \;Law \\ = x + (0 · y) \;\;\;\;\;\;\;\;\;\;\; Distributive \;Law \\ = x + y · 0 ...
2
votes
0answers
55 views

Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? ...
1
vote
0answers
31 views

About sign-rank of Boolean functions

Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
1
vote
1answer
60 views

Does XNOR of three variable equals XOR of same three variables

I came across following excerpt: $(x'y'+xy)'z'+(x'y'+xy)z=x\oplus y\oplus z$ What I see is left hand side is XNOR of $x,y$ and on right, $z$ and I get XOR of of $x,y$ and $z$ !!! In other word, ...
0
votes
1answer
509 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
38 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
128 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
176 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
66 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
50 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
23 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
52 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
89 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
57 views

Simplyfing a particular boolean expression

I'm having a lot of trouble with two problems the first is: ...
2
votes
1answer
117 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
36 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
54 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
26 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
37 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
37 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
82 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 ...
3
votes
1answer
109 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
44 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
92 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
69 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
484 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
53 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
59 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
425 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
36 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
82 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