Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
62 views

How to "logically" solve boolean logic

I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate. ...
4
votes
1answer
133 views

Why are there two not operators in lambda calculus?

From Wikipedia: $\mathrm{true} = \lambda a. \lambda b. a$ $\mathrm{false} = \lambda a. \lambda b. b$ Because true and false choose the first or second parameter they may be combined to provide logic ...
0
votes
1answer
4k views

Number of literals in the given boolean expression

Count the number of literals in the following expression : F = AB' + BC' + CD' + DE' According to me, the answer should be 8. But my solution suggests that the answer should be 6. Can anyone help me ...
-3
votes
2answers
110 views

Boolean Functions

Say you have N input Boolean function, let's use a parity tree for the example. The function outputs a one or a zero depending on the values of the N inputs. Are the N inputs considered the preimage ...
1
vote
1answer
295 views

Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
-1
votes
1answer
51 views

Minimal representation of an AND with two-input NOR

Let $x_1,x_2,x_3,x_4$ be boolean variables (i.e $x_i \in \{0,1\}$) Consider $f(x_1,x_2,x_3,x_4) = x_1 \wedge x_2 \wedge x_3 \wedge x_4 $ I want to write $f$ in terms of two-input NOR gates. I.e, $\...
2
votes
1answer
75 views

how do I simplify this particular boolean expression?

so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to ...
4
votes
1answer
154 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 ...
0
votes
1answer
492 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 ...
1
vote
1answer
59 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 ...
2
votes
1answer
138 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, ...
1
vote
2answers
161 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 ...
21
votes
7answers
221k views

How to construct XOR gate using only 4 NAND gate?

xor gate, now I need to construct this gate using only 4 nand gate ...
2
votes
3answers
165 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. ...
3
votes
1answer
155 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
183 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) = ...
0
votes
2answers
96 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 ...
2
votes
1answer
26 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
107 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)
2
votes
1answer
93 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?
2
votes
1answer
164 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 ...
1
vote
1answer
70 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 ...
0
votes
1answer
177 views

Unique boolean functions with one input

I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique". I thought about writing down the truth table for a NOT, ...
1
vote
0answers
39 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?
3
votes
3answers
98k views

Which law is this expression X+ X’.Y=X+Y

Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y ...
1
vote
1answer
501 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
3k 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
232 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
1
vote
3answers
1k 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-...
0
votes
1answer
423 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}*\...
3
votes
1answer
107 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
91 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
64 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
29 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 ...
0
votes
1answer
75 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 \...
-1
votes
1answer
277 views

A Combinational circuit Problem

A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 9 by 1001. A Combinational circuit is to be designed which takes these 4 bits as input and ...
1
vote
3answers
62 views

Simplyfing a particular boolean expression

I'm having a lot of trouble with two problems the first is: ...
2
votes
0answers
222 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 ...
3
votes
1answer
371 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
54 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
90 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\...
1
vote
0answers
63 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
1answer
47 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 ...
2
votes
0answers
48 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
430 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
81 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
151 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
225 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 ...
2
votes
1answer
39k views

Two's complement Using ONLY Logic Gates

How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)? (This question was redirected to CS from Stack Overflow)
2
votes
1answer
1k 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 ...