# Questions tagged [logic]

Questions related to mathematical logic and its use in computer science

817 questions
Filter by
Sorted by
Tagged with
8 views

### How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey ...
15 views

### Prove the boolean function E = F + G contains of the sum of the minterms of F and G

I'm given a boolean function E which is result of the sum of F and G (Where both F and G are boolean functions for sure). By using K-Map I can easily understand why E would have the sum of the ...
17 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 ...
18 views

### Automated algorithm design

There is a huge field of study dedicated to automated theorem proving. Is there any similar research dedicated to automated algorithm design? And is there any form of "duality" between these ...
22 views

### Is it a safety property?

Show that for any transition system TS, the set closure(Traces(TS)) is a safety property such that T S |= closure(Traces(TS)).
27 views

### Check if given safety properties are regular, and if so construct NFAs

Let $\mathit{AP} = \{a, b, c\}$. Consider the following LT properties: Between two neighboring occurrences of $a$, $b$ always holds. Between two neighboring occurrences of $a$, $b$ occurs more often ...
26 views

### Is it invariance, safety property, or liveness property?

Consider the set AP of atomic propositions defined by AP = {A, B}. Formulate the following properties as LT properties and characterize each of them as being either an invariance, safety property, or ...
29 views

### Name for a function on formulae that does not break the structure of given formula

I have two logics, $L_1$ and $L_2$, and a mapping $f: Formulas_{L1} \rightarrow Formulas_{L2}$, and want to argue that the mapping is "nice", in the sense that it is structure-preserving. ...
30 views

### NP and NP-hard problem

Can anyone help? I have no idea how to prove it.
184 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 ...
85 views

### How expensive is it to verify that a gate is universal?

I know that a NAND gate is considered universal because we can use it to implement an AND, OR, and NOT gate. Given an arbitrary gate, or set of gates, how many operations would it take to verify if ...
33 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 ...
25 views

### first order logic to normal form order of operations

∃y∀x [A(x) ∧ B(y) -> C(x,y)] ∃y∀x [¬(A(x) ∧ B(y)) v C(x,y)] ∃y∀x [¬A(x) v ¬B(y) v C(x,y)] I need to convert the above to conjunctive normal form. I'm a ...
55 views

...
38 views

### Universal Quantifiers in QBFs

I've been looking into reductions to/from the TQBF language and have managed to get stuck on something that is almost certainly not true (or, if it is true I'm missing a significant computational cost ...
30 views

### Lambda calculus simplification excercise

Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem. (λx.λy.yx)z (λw.w) I am lost with this. if anyone could lead me in ...
22 views

### Two variants of Fredkin gate

Sometimes two outpus of Fredkin gate are swapped when constant bit is 0, sometimes when it is 1. What variant is right or more modern? If it was conscious decision to change behavior what was ...
20 views

### In theory, should neuromorphic computers be more efficient than traditional computers when performing logic?

There is this general sentiment about neuromorphic computers that they are simply "more efficient" than von Neuman. I've heard a lot of talk about neuromorphic computers in the context of ...
23 views

### Represent a DNF formula as a multivariate linear formula?

Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$ How do I convert that into a polynomial form?
33 views

44 views

### How are prime implicates of HORN-Formulas defined?

I'm confused about the definition of prime implicates in Horn formulas. For example in the paper of Kira 2012 on page 109 it is stated: Now in the paper of Boros 2010 on page 82 the following ...
34 views

51 views

26 views

### Show that exist a finite set of clauses F in first-order logic that Res*(F) is infinite

I'm kind of desperate at this point about this question. A predicate-logic resolution derivation of a clause $C$ from a set of clauses $F$ is a sequence of clauses $C_1,\dots,C_m$, with $C_m = C$ ...