Questions tagged [logic]

Questions related to mathematical logic and its use in computer science

695 questions
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?
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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)$.
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 ...
112 views