# Questions tagged [logic]

Questions related to mathematical logic and its use in computer science

695 questions
1answer
237 views

### Draw a function by only using two input NOR gates [closed]

T = (BD + A'BC'+A'CD) How can i draw this by only using NOR-Gates? This is what i have done so far: https://imgur.com/a/JG2eU Have I understood this right?
0answers
61 views

### Hoare correctness proof for a recursive definition of multiplication

Given the program: {y=y0 ^ y>=0} z=0; while (y>0){ z=z+x; (1) y=y-1; } {z=x*y0} I am having trouble finding the ...
2answers
173 views

### Undecidable predicate logic is decidable by people?

Logic in computer science (By Michael Huth,Mark Ryan, second edition, page 132) says Every φ can, in principle, be discovered to be valid or not, if you are prepared to work arbitrarily hard at ...
0answers
37 views

### Modern presentation of Ackermann's “Solvable Cases?”

Ackermann's book "Solvable Cases of the Decision Problem" discusses decidable instances of first order logic, particularly monadic logic, and so called "equality formulas". However, the book is from ...
1answer
68 views

### What is the transitive and reflective closure of the derivation relationship?

This question is asked during a class of Computer Science. What is the transitive and reflective closure of the derivation relationship? I know that if $R$ is a relationship on $A^2$, a ...
0answers
101 views

### DPLL algorithm for 3SAT [closed]

This question is from my complexity theory course. How to change the standard DPLL algorithm for SAT in order to solve 3-SAT instances? The general DPLL algorithm for SAT is defined: ...
1answer
418 views

### Monadic Second Order Logic for Dummies

I am programmer with a grip on automata, but not on logic. I read in papers that the two are very tightly related. Deterministic Finite Automata (DFA), Tree Automata and Visibly Pushdown Automata are ...
1answer
110 views

### How logic programming (especially ASP) is related to the reasoning in (first-order) logic?

How logic programming (https://en.wikipedia.org/wiki/Logic_programming, especially answer set programming) is related to the reasoning in the (first-order) logic? Maybe logic programming can be ...
2answers
288 views

### Can we apply De Morgan's to any operator? (boolean , arithmetic , relational)

I have seen various statements with negation( or complement) operators and when i try to negate them using De Morgan's law , i become confused about how to negate. The main doubts are what variables ...
1answer
21 views

### Defining a predicate on the structure of a string

I have the following homework question. (For a bit of context - the study unit is Formal Languages and Automata). Define the predicate $\mathrm{pre}(s,t)$ over $s, t\in\Sigma^*$ by induction on the ...
0answers
18 views

### Subsymbolic/multimedia knowledge - query, creation and reasoning? Reference request?

One can consider multimedia data as a matrix of pixels, but, of course - multimedia data contains higher-order knowledge as well. E.g. everyone can describe famous paintings in terms of colours, ...
1answer
619 views

### Greater than or equal to operation (32-bit ALU)

I'm trying to construct a greater than or equal to operation by adding some logic gates or building blocks (i.e. multiplexor and decoder) to my current 32-bit ALU I'm not quite sure how to do this ...
0answers
60 views

### Unable to have an equivalent of A(FG p) and AG(EF p)

It states in my lecture notes that there is no CTL formula that is equivalent to A(FG p) in LTL and likewise, there is no LTL formula that is equivalent to CTL formula AG(EF p). I am just starting to ...
11answers
4k views

### Why is $A \lor (A \land \neg B) \equiv A$?

I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.
1answer
2k views

### Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma [duplicate]

Question: L is a language defined as $\ L = \{1^l | l\in primes\}$ (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory ...
1answer
112 views

1answer
224 views

### What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?

Definitions: positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula. negative CNF is a conjunctive normal ...
1answer
199 views

### Is there a dual concept to “Turing Complete” in logic?

Two computing models can be shown to be co complete if each can encode a universal simulator for the other. Two logics can be shown to be co complete if an encoding of the rules of inferences (and ...