Making complex boolean circuits that give true as output only for a specific combination of boolean inputs

This is my first question on a stack exchange website so please bear with me. I am making challenges for a jeopardy style capture the flag event in my college and I had come across the minetest challenge in the hardware section of google CTF qualifier conducted last year. A clean and organized solution to this problem has been provided by liveoverflow.

I would like to design a simpler version of this problem for my college’s CTF event but I am unable to design a complex circuit that gives true output only for a specific combination of inputs. I know that a circuit with this functionality is not very difficult to implement and just needs to represent the following logic:

trueinput1 AND trueinput2 AND ... NOT falseinput1 AND NOT falseinput2 ...  

However I want it to be vast and complicated so that participants cannot decode its functionality just by doing a visual analysis. Is there any technique to complicate the boolean logic above and to design a corresponding circuit that looks ugly even for a small number of inputs(32/64).

Partially defined boolean function

Consider boolean function $ f(x_{1}, x_{2}, \dots, x_{n})$ . The value of $ f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $ ?$ ). It is possible to set $ f$ ‘s value on some inputs, no matter if they were initially defined.

The problem is to set some of the inputs such that:

  • all initially undefined inputs become defined (i. e. no $ ?$ in function truth table);
  • $ f$ is monotone in the common sense.

The optimization part is to use the minimum possible assignments. How can one find an optimal way in the time $ \mathcal{O} \left( p(n) \left( 2^{n} \right)^{2} \right)$ , where $ p(n)$ is polynomial?

Boolean circuit multigraph

Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer]. He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some functions which come from a set of possible operations (called basis).

Let us say that we only allow the operation $ \land$ for our circuit (i.e. the basis only consists of $ \land$ ). Is $ x \land x$ a circuit if $ x$ denotes an input gate? I don’t think so, because the input gate $ x$ is only allowed to occure once in the graph and then we would need two edges to the $ \land$ -node, i.e. we would need a multigraph. A way around would be to force a basis to have an identity operation. For instance using the basis $ \land, id$ we could of course build the $ x \land x$ circuit (this is also the case if we can build the identity operation in any other way, e.g. if we have $ \neg$ in our basis) even though we have to increase the size of the circuit by using $ id$ . It seems very counterintuitive that such a simple circuit is in fact not a circuit over the basis $ \land$ , so is my reasoning correct?

[Vollmer] Heribert Vollmer, Introduction to Circuit Complexity

Different way of solving boolean satisfiability

I know there are commonly used boolean satisfiability problem-solving methods (such as DPLL etc.). As far as I know, such methods mostly depend on converting boolean expression into the CNF or DNF form. However, I’m trying to solve the given expressions “as-is”, without conversion to other forms. So, for boolean expression, I’m building a tree, consisting of many logical gates (AND, OR, NOT, XOR, VAR, CONST) and trying to propagate the right values by applying boolean laws.

step 1 – Common boolean laws

In such an approach there are some trivial steps like if AND has a value of 1 then the inputs must be both 1 and 1, or if XOR has a value of 1, and one input is 0, then the second input must be 1, etc. This step I call “propagation of values”, and it is performed until there are no values to resolve.

step 2 – Resolution by conflict

The second step is to assign value to the random gate, without a value assigned/resolved yet, name it X temporarily, then do “propagation of values”, and observe if in the expression tree some conflicts occurred. By conflict, I mean illegal state of the gate like AND(1,1)->0. So if the conflict occurred, this tells us that value assigned to the X gate is illegal, so I can assign the opposite value, and get back to the first step. This step I call “resolution by conflict”.

step 3 – Resolution by commons

The third step is to assign a value of 0 to the random gate, without a value assigned/resolved yet. Perform “propagation of values”, collect results (the assigned values of gates from the tree), in other words, do a “snapshot” of the tree after assignment. Then back to the original state before this step, assign a value of 1 to the same gate, perform propagation of values, then collect the second “snapshot”, then back to the original state again. Now, if the snapshots are both conflict-free, we could look at values that are both the same in the first and the second snapshot. These values are independent of the initial gate assignment and valid, so we can safely assign them to their gates. This step I call “resolution by commons”.

These steps were tested by me (program in C++) and worked pretty well.


So, the question is, what other kinds of steps can apply for this kind of resolution / BSAT solving? I’m asking because there are still some problems that with these steps I can’t go further (algorithm with these steps “see” that is nothing to do more).

If something is unclear, please let me know in the comments. Also if such an approach is known I’ll be thankful for references or links to resources about the topic.

Boolean matrix / satisfiability problem [duplicate]

This question already has an answer here:

  • How to enumerate minimal covers of a set 2 answers

Let $ M$ be an $ m\times n$ matrix with all elements in $ \{1,0\}$ , $ m >> n$ . Let $ \mathbf{v}_0, \ldots, \mathbf{v}_n$ be the columns of $ M$ .

I want to find all sets of columns $ S = \{\mathbf{v}_{i_1}, \ldots, \mathbf{v}_{i_k}\}$ so that for every row there is at least one column $ \mathbf{v}_{i_j}, \ldots, \mathbf{v}_{i_k}$ that has a $ 1$ in that row, with the constraint that $ S$ is minimal in the sense that deleting any element of $ S$ means $ S$ no longer meets these requirements.

Without the minimalness constraint, this is a trivial instance of (monotone) SAT – define a variable corresponding to each column of $ M$ , and just read the CNF clauses from the rows of $ M$ .

How can I approach the problem as described? I tried encoding the minimalness requirement as additional boolean constraints (which would make the problem regular SAT and I could use a SAT solver), but this gives $ n^m$ additional clauses in CNF form, which is intractably large.

Can the following problem be reduced to each other to show that the satisfiability of the given boolean formular is NP hard?

Inspired by this problem: MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

I am interested to know whether or not if the satisfiability check of the following boolean expression is also NP-hard:

$ \bigwedge_{a\in V}\left(\bigvee_{b\in N[a]}(x_a\veebar x_b)\right)$

In the formula above $ V$ are formulas, $ N[a]$ is the set of neighbours of $ a$ a node from $ V$ . $ x\in\{0,1\}$ the formula above is satisfied when each node of type $ 0$ is adjacent to atleast one node of type $ 1$ and vice versa.

How to present boolean options along with selecting exactly 1 of them as “primary”?

I have a situation in a web browser where I have a number (let’s say 3-10) of alternatives to present to the user.

  • The end user must choose at least one of these options to be enabled
  • The end user must choose exactly one of the enabled options to be the “primary” option.

I’m not sure how best to do this, though. Here’s a contrived situation about a stew that might help illustrate this better:

enter image description here

There are 7 potential ingredients, the user has to enable or disable each of them (cries out for a checkbox) but at least one of them has to be enabled; and exactly one of them must be the primary ingredient (cries out for a radio button).

  • If I choose a dumb form with no constraint checking, this is easy to implement, but they could choose Beef, Pork, and Carrots as the enabled ingredients and then Potatoes as the primary ingredient (which is a problem since they did not check the Potatoes box among the enabled ingredients)

  • Or I could put the primary ingredient first, then allow them to select secondary ingredients, and force the primary ingredient to be selected in the list of secondary ingredients (beef in the example below) and not allow it to be unselected. Not too hard to implement in HTML / Javascript, but then there’s some trickiness… what if I start with the UI state below, then select the primary ingredient as Onions, then as Chicken, and then Pork? What happens to the checkboxes for Onions, Chicken, and Beef?

enter image description here

Both of these options require duplicating the list twice.

  • Or I could try to use some kind of multichoice slider to select the primary ingredient… which would eliminate the need to duplicate the list… but this isn’t a built-in HTML feature and I’d have to roll my own or try to apply some 3rd-party UI element.

  • Or I could place a radiobutton and a checkbox in front of each ingredient (radiobutton for primary ingredient, checkbox to enable non-primary ingredients) which is compact and simple in presentation, but most likely confusing in semantics.

Any suggestions?

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 equivalent to ¬ (except it’s suffixed instead of prefixed). But I’m not sure what the addition and multiplication of the variables/propositional atoms would mean. Furthermore, I don’t know how a boolean logic formula can “output” something other than just a truth value…

I can’t seem to piece together with certainty the meaning of this representation. Could anyone take a look at the below example and maybe make a guess as to a translation of this representation to the more traditional ^, v, and ¬ symbols?

This arose in the context of digital logic in terms of logic gates and such on a CPU, if that makes a difference.

enter image description here

An alleged truth table of the above two expressions (the first row is filled in as an example):

enter image description here

All 16 Boolean Logic Gates

I was doing some reseach and I came across a website that had listed 16 different boolean logic operators. I was wondering if all of them were real, and if so, what do they do.