# Questions tagged [logic]

Questions related to mathematical logic and its use in computer science

640 questions
69 views

### Why use logic gates in this situation? (XOR gates)

I came across this circuit that swaps logical signals: However I don't understand why would you need to use logic gates. Would it be possible to just connect the A on the left to the B on the right ...
54 views

### What are constraints on some new logic programming language and system?

As I understand, everyone can create logic programming language and system by declaring that the valid program of some logic programming language is the set of statements in the form: ...
78 views

### Predicate Logic - Natural Deduction; Assumptions about exists-elimination

I am stuck on how to progress with this proof; i cannot see my next move. The task is to show $S \to \exists x Q(x) \vdash \exists x (S \to Q(x))$ using natural deduction for predicate logic. My ...
28 views

63 views

### Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
110 views

58 views

### Complexity of Solving a System of Polynomial Equations

It can be easily seen that solving systems of polynomial (i.e. not necessarily linear) equations is NP-Hard via reduction from SAT. Furthermore, because the existential theory of the reals is ...