Stack Exchange Network

Stack Exchange network consists of 175 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

Questions tagged [boolean-algebra]

The tag has no usage guidance.

2
votes
2answers
43 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 ...
0
votes
0answers
22 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
32 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
33 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
50 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?
1
vote
1answer
25 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
68 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
76 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
29 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
33 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.
0
votes
0answers
26 views

Can I use the Quine-McCluskey to simplify a CNF which is not a product of maxterms?

As I understand it the Quine-McCluskey method allows you to start with a set of maxterms (or minterms), and combine them pairwise in a systematic way into a smaller set of clauses with a smaller set ...
2
votes
2answers
168 views

Absorption rule in Boolean algebra

I am confused regarding the absorption rule which states: A OR (A AND B) = A. I do not completely understand how the expression simplifies to A and while i have seen proofs for this question, i still ...
0
votes
1answer
51 views

Simplifying SOP: implementing OR with NAND

I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such: $a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$ In other ...
0
votes
1answer
41 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
73 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 ...
0
votes
1answer
43 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
61 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
53 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. ...
0
votes
0answers
8 views

OR functions and SQ-Learning

Anyone can describe or give a reference which has a clear description and detailed proof of the SQ-Learning algorithm for the OR class of Boolean functions?
-1
votes
1answer
38 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
65 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
72 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 ...
2
votes
1answer
56 views

how many boolean functions exist that satisfy the condition

How many boolean functions exist that satisfy the following condition? $$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$
0
votes
1answer
36 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
17 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
33 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
45 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
105 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
97 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
107 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
42 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
86 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
21 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
15 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
54 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
37 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 ...
2
votes
1answer
611 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 ...
3
votes
0answers
101 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
35 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
106 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
1k 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
42 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
246 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
262 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
79 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
58 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
38 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
56 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 ...