All Questions
Tagged with logic boolean-algebra
64 questions
1
vote
0
answers
38
views
A confusion about Karnaugh Map
Consider the following four variable Boolean function:
$$F(A,B,C,D)=\sum(0,2,3,5,7,8,9,10,11,13,15)$$
If I show you the map, then what I get is:
I have marked the Essential Prime Implicants with a ...
- 111
2
votes
1
answer
32
views
Are all solutions to a HORN-SAT problem required to contain the minimal model as a subset?
I'm studying HORN-SAT problems and I have a specific question about the minimal model.
Given a HORN-SAT problem with multiple solutions, I understand that the minimal model is the one with the ...
1
vote
2
answers
62
views
Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?
AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (...
- 155
2
votes
0
answers
80
views
Prove or disprove that the Quine-McCluskey method generates the circuit with the minimum inputs and minimum gates?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, it says in 12.4 Minimization of Circuits which uses the Karnaugh Map or the Quine-McCluskey method:
...
- 203
0
votes
0
answers
45
views
Expressing Boolean Functions In Terms of Another Function
Given two boolean functions f1 and f2, are there any tools available that could be used to automate the process to represent f1 in terms of f2? I understand the process of this doing this by hand ...
6
votes
1
answer
716
views
Representing binary functions with a finite gate set without exponential blow-up?
It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
- 327
1
vote
1
answer
45
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
- 13
1
vote
0
answers
168
views
Method for simplifying complex logic tables
Not sure if this is the right StackExchange site, but back in college (20 years ago) I took a Digital Systems Design class where we learned how to reverse engineer a boolean function to meet the ...
- 111
0
votes
2
answers
158
views
Boolean Logic when one component switches from 0 to 1
I recently was constructing boolean logic for all sorts of examples from Morris Mano's "Digital Logic and Circuit Design".
I noticed that it is possible to construct a boolean logic wrt the ...
- 1
1
vote
2
answers
469
views
Combinational logic check if bits is prime
I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not.
For example given input fixed 8-bit that will produce 1-bit output.
00000101 will ...
1
vote
1
answer
25
views
How to come up with combination a short-circuit evaluation table?
(a || b) || (c && d))
Given the above, how do I derive the table below:
a
b
c
d
output
T
-
-
-
TRUE
F
T
-
-
TRUE
F
F
T
T
TRUE
F
F
T
F
FALSE
F
F
F
-
FALSE
I'm told that this is short ...
- 11
2
votes
1
answer
69
views
Is $f(X)f^d(X) = 0$ for a Boolean function $f$?
I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is ...
- 429
0
votes
0
answers
36
views
Is there an efficient way to generate a pseudo-boolean function from a linear constraint?
I would like to define a pseudo-boolean function $f$ such that $f(x) = 0$ for all logically valid combinations of $x\in{0,1}$ and $f(x) > 0$ for all logically invalid combinations of $x\in{0,1}$.
...
- 121
3
votes
1
answer
84
views
Stalmarck's method: x ≡ x → z, does z have to be true?
I have been researching Ståmarck's method 1. In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that:
y $\to$ z $\equiv$ x
where x, y and z are booleans which ...
- 53
2
votes
1
answer
205
views
Sorting by boolean algebra (hardware) instead of algorithm (software)
Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11]
Maybe that case seems complicated,...
3
votes
1
answer
371
views
What are the limits of Boolean Algebra?
Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, ...
- 33
3
votes
1
answer
193
views
What's the average number of transistor switches needed to do an N-bit x N-bit multiply?
I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
- 41
0
votes
2
answers
97
views
is duality principle in boolean algebra is true for every expression
Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my ...
4
votes
0
answers
297
views
Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?
There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
- 339
1
vote
2
answers
279
views
For a logic gate to be universal, must it necessarily be able to perform duplication?
It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
- 113
18
votes
11
answers
5k
views
Why do logic gates behave the way they do?
I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do.
Why for example:
...
- 317
1
vote
0
answers
52
views
Logic minimization via 2 inputs NOR gates: Is it monotone w.r.t to adding a minterm?
notation: $x+y:=\mbox{OR}(x,y)$, $\bar x:=\mbox{NOT}(x)$, $xy:=\mbox{AND}(x,y)$, 1:=TRUE, 0:=FALSE.
Let $f$ be a Boolean function of $n$-variables, i.e. $f: \{0,1\}^n \to \{0,1\}$.
minterm:= any ...
- 111
1
vote
1
answer
46
views
Simplification of a multi-index Boolean expression towards computation in fewer steps
Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
- 135
2
votes
1
answer
1k
views
Addition, multiplication, and apostrophe used to represent boolean algebra expressions?
I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before.
I can make a guess that the apostrophe is ...
- 209
2
votes
1
answer
100
views
3-CNF to "independent form"
Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the ...
- 201
2
votes
1
answer
107
views
Conjunctive normal form to simple elementary algebra
I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.
An example:
$$\phi=\left(x_1 \vee x_2 \right) \wedge \...
- 201
3
votes
1
answer
119
views
Polynomial size Boolean circuit for counting number of bits
Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
- 239
2
votes
1
answer
362
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)$...
- 1,041
2
votes
1
answer
96
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?
- 1,041
0
votes
2
answers
2k
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
1
vote
0
answers
385
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? ...
- 11
1
vote
0
answers
226
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 ...
- 315
2
votes
2
answers
2k
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 ...
- 23
0
votes
1
answer
692
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
1
answer
77
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
1
answer
206
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 ...
- 542
1
vote
1
answer
1k
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 ...
- 11
0
votes
1
answer
182
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)
- 234
0
votes
1
answer
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)
3
votes
1
answer
152
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 ...
- 31
1
vote
1
answer
160
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.
...
- 13
2
votes
1
answer
174
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 ...
- 21
0
votes
2
answers
478
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^{...
D.W.♦
- 166k
0
votes
1
answer
1k
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
1
answer
95
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 ...
- 1,727
4
votes
2
answers
2k
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 ...
- 564
3
votes
4
answers
2k
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$ ...
- 85
1
vote
1
answer
178
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 ...
- 13
2
votes
1
answer
71
views
About a universal (functionally complete) function producing a constant
I read in a note the following:
Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete.
Why is that? how does it imply that $f$ can't produce ...
- 313
1
vote
1
answer
463
views
Simplifying Boolean Expression
I am designing a 4-bit comparator with a look ahead unit using a bit slice approach. I have to break the propagation of the Logical expressions for (A<B)i and <...
- 113