Skip to main content

Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
2 answers
52 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 (...
Serge Rogatch's user avatar
-3 votes
2 answers
85 views

Building a XOR gate out of NOR gates

Can someone explain for me how to build a XOR gate using 5 NOR gates? The thing I'm looking for is a proof similar to this: $A^B\ =\ (!A)B\ +\ A(!B)$ $=\ !!((!A)B)\ +\ !!(A(!B))$ $=\ !(!!A\ +\ !B)\ +\ ...
Francesco Altura's user avatar
3 votes
1 answer
406 views

What is special about a canonical representation of Boolean functions?

My textbook (Saurabh's Introduction to VLSI Design Flow) mentions while discussing formal verification that a representation of a Boolean function is said to be canonical if the following holds: If a ...
EE18's user avatar
  • 133
3 votes
1 answer
35 views

Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?

The problem: Given two boolean formulas in 2-CNF, decide if they are equivalent. I know that the problem is $\mathsf{coNP}$-hard when at least one formula is in 3-CNF. However, the same proof of $\...
rus9384's user avatar
  • 1,684
2 votes
0 answers
67 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: ...
An5Drama's user avatar
  • 203
0 votes
1 answer
82 views

Prove that it is impossible to construct the toffoli gate using only CNOT gates

Show that it is not possible to construct the toffoli gate using only CNOT gates, given we are allowed to choose any number of ancilla bits. My Attempt The action of a toffoli gate can be defined as, ...
Sooraj S's user avatar
  • 139
0 votes
3 answers
60 views

Is there an algorithm to implement N-input-gates using smaller gates?

To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I ...
HappMacDonald's user avatar
0 votes
1 answer
62 views

what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?

What is the smallest 3-CNF system of equations possible that enforces the boolean expression: a = b + c for boolean variables a, b, c? 'Smallest' can be defined as: (1) Number of 3 CNF clauses. (2) ...
J.Doe's user avatar
  • 789
1 vote
0 answers
23 views

CNF Horn-renamability to 3-CNF Horn-renamability reduction?

A CNF formula is Horn-renamable if you can invert variables in such a way that each clause has at most one positive literal. There is an algorithm based on a reduction to 2-SAT given in Renaming a Set ...
rus9384's user avatar
  • 1,684
3 votes
1 answer
84 views

Number of n-variable symmetric boolean functions that are linear

How many symmetric boolean functions exist that are linear? Let $f$ be a $n$-variable boolean function. $f$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-...
M3n4p's user avatar
  • 33
0 votes
0 answers
32 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 ...
rotatinglemur's user avatar
6 votes
1 answer
712 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 ...
Andrew Baker's user avatar
0 votes
2 answers
84 views

Polynomial representations of Boolean functions

The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions: Is there a similar polynomial for the PARITY boolean function? Is there a ...
user avatar
2 votes
0 answers
26 views

Equivalent-symmetric (E-symmetric) variables check for Boolean functions

In [1], it states that checking $f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$ (variables $x_i$ and $x_j$ are E-symmetric) is equivalent to checking $f_{x_ix_j} = f_{\bar{x}_i\...
Drzw's user avatar
  • 21
0 votes
0 answers
17 views

Complexity Class of the Problem: Existence of Unsatisfying Interpretations in Boolean Formulas

What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does ...
Lupital's user avatar
1 vote
1 answer
44 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$...
G S's user avatar
  • 13
1 vote
1 answer
191 views

Why is conjunctive normal form (CNF) "better" for SAT than disjunctive normal form (DNF)?

When hand-manipulating algebra DNF (sum of products) is easier than CNF (product of sums). Possibly because factoring is more difficult than expanding. So why is it the opposite for computational ...
Gaslight Deceive Subvert's user avatar
-3 votes
2 answers
61 views

!(ab)*(!a+b)(!b+b)=!a Boolean Algebra

How can I prove that !(ab)(!a+b)(!b+b)=!a* in boolean algebra? This is an exercise from a past paper of my teacher but I can't really find the way to the answer. I would appreciate some help.
user160560's user avatar
0 votes
1 answer
94 views

How to solve boolean SAT with equality constraints

Say I have boolean formula in form of a CNF(x1,x2,...) with $x_i$ being boolean variables. Testing the satisfiability of the CNF is the SAT problem, i.e. determine ...
Andreas H.'s user avatar
5 votes
5 answers
996 views

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is ...
Ntwali B.'s user avatar
  • 161
0 votes
0 answers
91 views

Is this a valid method to merge clauses in CNF formulas?

Assume $$C_1 = (x_1 \lor x_2 \lor \lnot x_3)\hspace{0.2cm} C_2 = (x_4 \lor x_5 \lor x_3) \hspace{0.2cm} C_3 = (x_3 \lor x_5 \lor x_6)$$ Let $$ \phi_1 = C_1 \land C_2 \land C_3$$ and $$ \phi_2 = (x_1 \...
C Marius's user avatar
  • 185
0 votes
0 answers
27 views

Is this language PSPACE complete

Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
Vahan's user avatar
  • 3
1 vote
1 answer
109 views

Boolean Integer Linear Optimization/Programming

Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results. Let's say I am doing 5 coin ...
B.D.'s user avatar
  • 11
0 votes
1 answer
49 views

7 segment decoder Combinational Logic Circuits using Logic Gates

How can a 7 segment decoder operation be implemented using boolean NOR gate ONLY? Question: Here's my truth table and k-map: Normal circuit diagram:
Colin Newmann's user avatar
0 votes
2 answers
189 views

Two's complement using logic gates

How can a 4-bit two's complement operation be implemented using boolean NOR gate? I search lots of 4-bit two's complement videos and articals, but most of them are using XOR gate.
Colin Newmann's user avatar
0 votes
1 answer
22 views

influence of neighourhood points

Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...
wwjohnsmith's user avatar
1 vote
0 answers
97 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 ...
hotmeatballsoup's user avatar
0 votes
2 answers
136 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 ...
P. Patil's user avatar
0 votes
1 answer
99 views

Is there a notation for boolean algebra complexity?

To represent complexity of an algorithm, Computer Scientist is used to using big-O notation. How about complexity of boolean algebra? Boolean algebra is commonly used in digital circuit design with ...
Muhammad Ikhwan Perwira's user avatar
2 votes
1 answer
1k views

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
HighAsAKiteOnMath's user avatar
0 votes
0 answers
112 views

Time complexity of negating a CNF formula

Suppose i have a CNF formula. If i negate the CNF formula, then i obtain DNF formula. However, i can't find anywhere on internet that mention the time complexity. What is the time complexity of ...
LLL's user avatar
  • 113
1 vote
2 answers
301 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 ...
Muhammad Ikhwan Perwira's user avatar
1 vote
1 answer
84 views

How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
vreithinger's user avatar
1 vote
1 answer
57 views

Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?

I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?
CST's user avatar
  • 11
1 vote
0 answers
36 views

Fourier Dimension of Boolean functions

I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
kleinbottle's user avatar
1 vote
2 answers
250 views

Clarification regarding linear boolean functions!

I am a little confused when it comes to linear boolean functions. According to this post: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
Reppiz's user avatar
  • 13
1 vote
1 answer
24 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 ...
Iva l's user avatar
  • 11
1 vote
1 answer
71 views

Influence of a variable in composition of Boolean functions

Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$? To me it ...
kleinbottle's user avatar
2 votes
1 answer
67 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 ...
Berk U.'s user avatar
  • 429
1 vote
1 answer
57 views

Is [F(a, b, c) = a' + b] functionally or logically complete?

I'm having a problem determining whether [F(a, b, c) = a' + b] is functionally(logically) complete or not. I would really appreciate it if you could help me. P.S: I can't have 1 or 0 as input.
Reza Masoumi's user avatar
0 votes
1 answer
43 views

Can element occur in a CNF formula?

For example, is $(X \vee 1)$ a valid formula in conjunctive normal form (CNF)? If yes, then I would have to consider such formulas when trying to prove a statement about all CNF formulas.
LLL's user avatar
  • 113
1 vote
0 answers
31 views

Is there an algorithm for generating non comparable boolean vectors?

First some context: A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself. The dynamical behavior of a ...
Raúl Astete's user avatar
2 votes
1 answer
29 views

sum of Boolean characters larger degree

I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then $$ \frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1 $$ if and ...
postasguest's user avatar
0 votes
0 answers
33 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}$. ...
JoeBass's user avatar
  • 121
0 votes
0 answers
64 views

graph representation of a Boolean function

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
kleinbottle's user avatar
3 votes
1 answer
78 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 ...
Leop's user avatar
  • 53
1 vote
1 answer
51 views

Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?

I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
user023049's user avatar
-1 votes
1 answer
32 views

Can anyone solve this? Is the answer 4 or 7. I'm confused

I'm trying to solve this but I'm confused with different answers. I'm getting 4 but the answer written is 7. Please guide me.
user9544852's user avatar
1 vote
0 answers
48 views

Efficient bit-level implementation of Boolean polynomials with few variables

A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
BubbleZ's user avatar
  • 11
0 votes
1 answer
229 views

What boolean algebra simplification is applied in this Shannon's expansion?

Found this question about Shannon's expansion. While I am trying to follow its logic, found one super convenience simplification used. Can we do this in general while dealing with boolean algebra? or ...
Maxfield's user avatar
  • 227

1
2 3 4 5 6