# Questions tagged [logic]

Questions related to mathematical logic and its use in computer science

745 questions
Filter by
Sorted by
Tagged with
2answers
33 views

0answers
14 views

### Using a PDA, show that ( x * y ) + x is a valid string

Using a PDA, show that ( x * y ) + x is a valid string. im having trouble with part C
2answers
28 views

### Are these two sensible and related or unrelated ways of regarding a logic system as a programming language?

When I am trying to understand logic programming languages e.g. Prolog, I am immediately confused by the following two ways of relating logic systems and programming languages or type systems. In ...
1answer
60 views

### Is there a model of ZF¬C where some program always terminates but has no loop variant?

Wikipedia has a proof that every loop that terminates has a loop variant—a well-founded relation on the state space such that each iteration of the loop results in a state that is less than the ...
0answers
22 views

### How to prove following two statements are equivalent in Hilbert System?

statement 1: $Γ$ is satisfiable implies $Γ$ is consistent. statement 2: If $Γ$ derives $α$ then $Γ$ entails $α$. I can easily prove statement 1 from 2 , but not 2 from 1 (without using strong ...
1answer
44 views

### Meaning of $a\lor b \to b' \lor c'$

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
1answer
23 views

### Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
1answer
45 views

### General resolution in first order logic

Assuming you have a formula in first order logic like $$(\forall_x p(x) \land \forall_x q(x)) \rightarrow \forall_x(p(x) \land q(x))$$ (which seems valid?) Converting the formula to ...
3answers
122 views

### Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
0answers
46 views

### On the complexity of existential and universal quantifiers

I'm trying to analyze the time complexities of the two former kind of quantifiers, I need help figuring out if I'm following the right path or if I'm making mistakes, here's what I've produced so far: ...
1answer
37 views

### Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...
1answer
20 views

### What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams)

For example, this gate: looks like an OR gate, except there's a dot to the right. The dot is reminiscent of the fact that there's a dot in the NOT gate, so I wonder if it has something to do with ...
1answer
39 views

### Combining Predicate Logic and BigO

I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand ...
2answers
2k views

### Language to define perfectly a programming problem

Is there any language, which can be used to define all programming problems perfectly? By perfectly, I mean with these two properties: p is the problem. d is the definition in the language. P(d, p): ...
1answer
39 views

### 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 ...
0answers
14 views

### How to compute (partial) consequence set for premises of the first order logic?

I am playing with the Sequent Calculus Trainer https://www.uni-kassel.de/eecs/fachgebiete/fmv/projects/sequent-calculus-trainer.html . It is game with judgments, where each judgment consists from: 1) ...
1answer
64 views

### Can a dfa return only the final state?

I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow: increment x+1 and if x+1 is larger than 15 then x+1 ...
0answers
19 views

### Determining Cumulative Benefit of Orders with Various Items

I'm working on a project to change the location of items in a warehouse to allow me to ship items together which were bought in the purchase order (currently impossible due to conveyor logistics). The ...
0answers
53 views

### Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable? [duplicate]

On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it's said in Section 3.3 that Because of the finiteness of a natural number in contrast to, for example, a real number, many ...
2answers
38 views

### Why there is forward chaining inference engine (reasoner) for description logics only and not for other logics?

Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic_reasoner) as opposite to Prolog backward chaining SAT solver (for queries). Why there is reasoner for description ...
1answer
31 views

### Complexity of negation cancellation

Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. Notation: $| \alpha |$ is the length of formula $\alpha$. We are given a formula $\phi$. Cancel all cancellable ...
2answers
30 views

### How to show all false outputs in a circuit?

I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks!
1answer
52 views

### Can someone explain the logic diagram for the Boolean expression NOT A OR B AND C

An IB question requests: Construct the logic diagram for the Boolean expression NOT A OR B AND C. The answer looks to me like not A or (B and C), whereas what I expected only gets partial credit. ...
2answers
199 views

### checking '<' for two binary numbers in a cnf-formula

I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf: Lets say n and m are two-digit ...
0answers
36 views

### Did I prove the language is not regular?

I am trying to prove the following language that is not regular. I used Pumping Lemma proof and my proof goes as follows: Assume that L is regular and let p be the constant of Pumping-Lemma. This ...
0answers
10 views

### Do forward chaining (Rete) business rules (Drools, ILOG) / production rules support higher order rules and compositionality?

There is this talk http://andrewcropper.com/pubs/jelia19-typed.pdf about higher order Prolog, about use of higher-order predicates (that takes other predicates as arguments) and compositionality of ...
1answer
46 views

### How to Implement a reversible OR operator with a Fredkin gate (controlled swap)?

How to implement a reversible OR operator with a Fredkin gate ?
1answer
31 views

### How to correctly negate a predicate bounded by some quantifiers?

this is a problem which was asked in GATE CS 2010. This is question statement: Q: Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which ...
0answers
38 views

### How to write negation of an 'AND' statement in logic

Suppose the given proposition is: "Zach blocks emails and texts from Jennifer" Where, P implies "Zach blocks emails from Jennifer". Q implies "Zach blocks texts from Jennifer". So it's P AND Q in ...
0answers
27 views

### Are there lightweight logic of commonsense reasoning?

Logic generally is hard and probabilistic logic (with model counting, like ProbLog2) is even harder. But commonsense knowledge and reasoning is quite lightweight. There have been efforts to represent ...
2answers
66 views

### Euclidean Models

I am asked to prove that every Euclidean models satisfies $\diamond \diamond \diamond \varphi \to \diamond \diamond \varphi$. How can this be done? I don't see how it could even be true.
2answers
40 views

### prove that {$↔,⊕$} is incomplete set?

How do i prove that Is {$↔,⊕$} not a complete set ? I have no clue how to prove it .
1answer
107 views

### Are these 2 equivalent?

Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ? The only thing I can think of is that this question can be answered if we show that ...
0answers
30 views

### Mutually contradicting rules in Prolog

What will happen in a Prolog program, if I set two rules/facts which contradict each other.. will it go with the rule/fact that appears first.. or it will show an error?
0answers
58 views

### How shall I understand the definitions of let expression?

let as used in programming languages is defined in lambda calculus as per https://en.wikipedia.org/wiki/Let_expression#Let_definition_defined_from_lambda_calculus ...
0answers
15 views

2answers
65 views

### Is there a formal definition for iteration?

I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. ...
0answers
32 views

### Using Hoare logic to show an invariant holds or using induction?

I want to know if given a while loop: x = 0 while(x < 5){ x = x + 1 } I want to show that x (at the a ith iteration of the loop), the value of i is ...
1answer
462 views

### Representation of the concatenation at the type level

I would like to learn more about concatenative programming through the creation of a small simple language, based on the stack and following the concatenative paradigm. Unfortunately, I haven't found ...
0answers
57 views

### Datalog Program Equivalence with Fixed Universe Size

It is well known that to compute equivalence of two Datalog programs (or equivalently of two first order formulas with the least fixed point operator) wrt all possible inputs and universes, is ...
1answer
74 views

### Confusion about assignment axiom in Hoare logic

I wanted to know if we are given the f.f.g. Hoare triple: {x = 43}x := x + 1{x = 44} How do we show that this is a valid Hoare triple? My attempt was: Using the assignment axiom: {x + 1 = 43} x := ...
0answers
47 views

### What are necessity and sufficiency?

I was reading deadlock topic from Operating Systems book by Stallings. It states four pre requisites for deadlock: Mutual exclusion No preemption Hold and wait Circular wait It then have following ...
0answers
127 views

### Second Order QBF

Consider a universe with two elements 0,1 and a second order formula, i.e. of the form "forall R exists S ... such that F", where R,S are relation symbols of some given arity, and F is some first ...
1answer
40 views

### Substructural Prolog?

Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer....
1answer
127 views

### Create NOT gate from other gates

If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?
2answers
91 views

### Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an ...