# Questions tagged [predicate-logic]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
1answer
23 views

### Complexity of pattern matching for modus ponens logical conclusions

Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) ...
1answer
35 views

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

I am trying to create a predicate in Prolog which allows me to delete all occurrences of X in a list L. I have the following code: ...
2answers
173 views

### Encoding the theorem on friends and strangers in predicate logic

In every group chat of six (distinct) people on Instagram, there is a group of three (distinct) people such that either: everyone in the group are friends everyone in the group are strangers (i.e not ...
0answers
32 views

### Show that exist a finite set of clauses F in first-order logic that Res*(F) is infinite

I'm kind of desperate at this point about this question. A predicate-logic resolution derivation of a clause $C$ from a set of clauses $F$ is a sequence of clauses $C_1,\dots,C_m$, with $C_m = C$ ...
1answer
94 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
80 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 ...
2answers
96 views

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

Suppose there exist no free variables in a given predicate logic formula. Is then a model alone sufficient to fully interpret the formula and make inferences? Don't we need an environment or variable ...
1answer
52 views

### Predicate Logic - negating the conclusion to prove logical consequence?

In Predicate Logic, if you want to prove the logical consequence using the method of resolution, do you ALWAYS start off by negating the conclusion?
1answer
24 views

### Predicate Logics - double negation HELP me understand

Sorry for maybe a silly question but i need to understand how ¬(¬∀x ¬A(x)) equals ∀x ¬A(x) In my mind, the negation before the parenthesis will be applied to both ¬∀x and ¬A(x). So it would look like ...
1answer
60 views

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

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
0answers
23 views

### Natural deduction proof without any predicate

I am gaving trouble proving a natural deduction proof when there is no predicate given. Only conclusion is given. I understand the rules of elimnations, inclusions, IPs and others but I having trouble ...
1answer
151 views

### Hoare triple: Loop invariant and correctness

The following Hoare triple in which variable a is an array of integers, and len, max, i, n, j and m are integer-valued variables. Provide a loop invariant (using predicate logic) suitable for proving ...
0answers
105 views

### Hoare triple: Loop invariant and partial correctness

Below there is Hoare triple in which variable $a$ is an array of integers, $len$, $x, i$ are integer-valued variables, and $r$ is a Boolean-valued variable. I have to provide a loop invariant (using ...
1answer
544 views

1answer
43 views

### predicate logic proof of 2 numbers

For any two different numbers there is an number in between. I'm trying to write this in predicate logic and have no idea how to do it, since I need 2 variables X and Y? For all x there exists a y ...
1answer
78 views

### predicate logic/binary relation help

(1) ∀x, y, z (x < y ∧ y < z → x < z) (transitivity) (2) ∀x ¬(x < x) (antisymmetry) (3) ∀x, y (x < y ∨ x = y ∨ y < x) (linearity) I need to give an example of a (nonempty) ...
1answer
64 views

### Discrete Mathematics Proofs for ∃ and ∀

Premises or Givens: $∃x(A(x) → B(x))$ $∀x (B(x) → K(x))$ To Prove: $∃x(A(x) → K(x))$ My Solution: $A(z) → B(z)$ From premise and Existential instantiation $x$ for $z$ $B(z) → K(z)$ From ...