# Tag Info

Accepted

### Prolog: Deletion of all appearances of an element in a list

There are some rules of thumb I follow when writing prolog. Two of them are: Use dif instead of \=. From the reference manual: &...
• 146
Accepted

### In predicate logic, is the "environment" only needed when free variables are present?

It is not so that the model alone allows you to make inferences and that you don't need an environment at all; it is rather that, if no free variables occur, then you may as well start with an empty ...
• 5,017
Accepted

### Must $x$ and $y$ be different in a statement of the form $\forall x \forall y \cdots$?

For any formula $\varphi$ in which $x$ and $y$ are free variables, $\forall x \> \forall y \> \varphi$ quantifies over all possible values for $x$ and $y$. As a result, $x$ and $y$ may be ...
• 5,017
Accepted

• 1,110
Accepted

### Combining Predicate Logic and BigO

What the definition is saying is: $f\in O(g)$ if there's a number $n_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n_0$. In simple ...
• 14.8k
Accepted

• 277k
1 vote

### Computability: Proving a predicate is not recursively enumerable

Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false. The rest of the answer ...
• 277k
1 vote

### Hoare triple: Loop invariant and correctness

I believe the loop invariant is the same as the postcondition, except with j and m swapped with i and n, respectively. That statement can be proven true at the start and end of each loop. This is true ...
1 vote

### predicate logic proof of 2 numbers

As a hint, for any two numbers there is a third number in between.
1 vote

### predicate logic/binary relation help

This sounds like homework, and I do not wish to ruin the value of your homework for you by giving answers too quickly; the point of homework is to exercise and solidify the skills learned in the ...
• 254
1 vote
Accepted

### Discrete Mathematics Proofs for ∃ and ∀

Your solution is a good one, and that's how I'd prove it also. I don't believe a more straightforward or simpler version is possible.
• 7,138

Only top scored, non community-wiki answers of a minimum length are eligible