Questions concerning predicate calculus, i.e. the logic of quantifiers.

learn more… | top users | synonyms

0
votes
2answers
35 views

A better general definition of a predicate

What's a better definition for (an interpretation of) a predicate in general (i.e. non-theory-specifically): ...
1
vote
1answer
26 views

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$ My intuition tells me yes, these two things are equivalent. Assume the first, take some $x_0$ s.t. $P(x)\lor Q(x)$, ...
0
votes
2answers
38 views

How do you prove this logical equivalence?

$\\ (\exists! x:P(x)) \leftrightarrow ((\forall x:P(x) \rightarrow Q(x))\leftrightarrow(\exists x:P(x) \land Q(x)))$ If there's only one $x$ for which $P(x)$, then saying "all $x$ for which $P(x)$, ...
0
votes
1answer
60 views

Are these statements “truly” equal?

Consider a set $A$, elements $x,y$ in $A$ and the following propositions: \begin{equation} \exists x\in A\ |\quad x=x \end{equation} \begin{equation} \forall x\in A:\quad x=x \end{equation} ...
1
vote
1answer
25 views

How do I translate sentences from English to predicate logic?

This question was taken from the MIT OCW Math for Computer Science course. Translate the following sentences from English to predicate logic. The domain that you are working over is $X$, the set of ...
-1
votes
0answers
20 views

natural deduction proof for predicate logic [duplicate]

I have to prove the following logic equivelence ~∀xP(x)->∃x~P(x) I started by assuming ~∀xP(x),but I have no idea how to prove it. maybe you can help me,and explain! Thank you
1
vote
2answers
55 views

Can an open statement be a tautology?

A tautology is a statement which is true by dint only of the logical connectives contained therein. My question is about a statement which contains an unquantified variable. For example: P: ($x$ ...
1
vote
1answer
30 views

Are those formulas valid?

Consider the following formulas: $\forall x(A\to B)\to ((\exists x A) \to \exists x B)$ $\forall x(A\to B)\to ((\forall x A) \to \forall x B)$ Now, I claim that both formulas are indeed valid. ...
1
vote
1answer
29 views

Show a formula is satisfiable

Show that the following formula is satisfiable: $$(R(c)\land \forall x (R(x)\to R(f(x))))\to \forall xR(x)$$ here, $R$ is a relation and $f$ is a function. Now, if $R(c)=f$ then it easy to show ...
0
votes
1answer
21 views

Show that the formula is satisfiable

The formula is: $$P(f(a),g(b))\to R(h(a,b,c))\lor P(f(a),g(b)))$$ Here, $a,b$ are constants, $P,R$ are relations and $f,g,h$ are functions. Now, if we assume that $P(f(a),g(b)) = t$ then it's easy ...
0
votes
0answers
22 views

The right way of defining a predicate

My theory contains a definition of lists: L(H,T) is a list, H is the first element (head), T is the list of remaining elements (tail), nil is empty list. So [A,B,C] = L(A,L(B,L(C,nil))). I defined ...
0
votes
1answer
30 views

drawing tableaus for predicate logic?

I'm a bit confused about the rules. I know for existential ones, you replace the variable with a new constant and for universal you replace it with a closed term. $\forall x A(x) \to A(t)$ if $t$ is ...
2
votes
1answer
70 views

How to formalize a variable-binding operator, such like $\frac{d}{dx}$?

How to formalize a variable-binding operator, such like $\frac{d}{dx}f(x)$? For instance, I think we should treat $\frac{d}{dx}$ as a higher-order function of $x$, returning a function that takes it ...
0
votes
1answer
38 views

Unary predicate for finite number of values

I am working with automated prover. I am creating a theory, where an unary predicate PR should be true just for several constants, false otherwise. I made following axioms: ...
3
votes
0answers
51 views

Is there a name for this principle of logic? From $\exists a P(a), !bQ(b), \forall a(P(a) \rightarrow Q(a)),$ infer $\forall a(Q(a) \rightarrow P(a))$

In set theory, we have the following: Observation 0. Let $X$ denote a set. Let $A$ and $B$ denote subsets of $X$. Then if $A$ has at least one element, $B$ has at most one element, and $A ...
1
vote
2answers
37 views

Equivalence of $\forall x P(x) \lor\forall x Q(x)$ and $\forall x (P(x) \lor Q(x))$

What are examples of predicates $P(x)$ and $Q(x)$ and domains where the above two statements are equivalent? My stab at the problem: Let the domain of discourse be all positive whole numbers, $P(x)$ ...
0
votes
0answers
28 views

Formalising a problem given in natural language into predicate logic

I am working on a research paper and I want to formalise the problem which we tackle and process for solving it using predicate logic. I used predicate logic in the past for formalising simple ...
2
votes
1answer
47 views

Rewriting ∃! using predicate logic expressions ( “=” excluded)

A(x) is a predicate logic formula. A is a property (predicate), x is a variable. ∃!A(x) would mean that exactly one x exists which has the property A. First thing that comes up is: ∃x( A(x) ∧ ∀y( ...
0
votes
1answer
20 views

Counterexamples of existentially quantified statements

I just realized I have a serious problem in properly seeing the logical structure that involves counterexamples. Here there is an example: Proposition F: Assume $P$. Then, there is a function $f ...
4
votes
3answers
65 views

Undefinability of evenness in first order logic

My question is to show there is no sentence $\psi$ in a language of first order logic without any non-logical symbols such that for every finite structure $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; ...
0
votes
1answer
38 views

Use of quantors/quantifiers and variables in first-order logic.

Let $v_1,v_2,\dots,v_n$ be variables and $\beta$ the variable assignment $\beta(v_n)=2n$ for $n\geq 0$. Of the following, which are true and which false under $\beta$? $\forall v_0 \exists v_1 ...
1
vote
1answer
21 views

Help with logic notation, what are $S$ and $\underline0$?

This is a more or less literal translation from German, hopefully it's understandable, it's all the information available: Let $L_N=\{\underline0,S,+,\cdot~,<\}$ be the language of the natural ...
1
vote
1answer
32 views

Find $\Gamma$ such that any model of $\Gamma$ has an infinite domain.

As part of a homework assignment for a logic class, I'm supposed to find a finite set $\Gamma$ (I believe of wffs) such that any model of $\Gamma$ has an infinite domain. This is for the predicate ...
1
vote
2answers
38 views

Predicates and Indirectly Proving the last step of Mathematical Induction

Okay to illustrate this problem, I'm going to need to give an example, and go through the steps of Mathematical Induction to show where my question is aimed at. Example : Prove that $$ n^2 \geq 2n + ...
0
votes
0answers
22 views

Prove by induction that $\Gamma \vdash \varphi \Rightarrow \Gamma[x/c] \vdash \varphi[x/c]$.

As the title says: I want to prove by induction that $\Gamma \vdash \varphi \Rightarrow \Gamma[x/c] \vdash \varphi[x/c]$. I’m struggling with how to write this proof. I think I need to do induction ...
0
votes
2answers
44 views

question about logically true statements?

"Is the statement $(∃xQ(x) ∧ ∃xR(x)) ↔ ∃x(Q(x) ∧ R(x))$ logically true? If it is, explain why. If it isn’t, give an interpretation under which it is false." because this question exclusively uses ∃x, ...
1
vote
1answer
21 views

Showing that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements.

As the title says, I’m trying to show that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements. It’s from Logic and Structure, van Dalen (2013 edition). ...
1
vote
2answers
15 views

Implication vs Conjunction (Natural Language to Predicate Logic)

So im confused when should i use implication and when should i use conjunction. Let me give an example. "All parrots like fruits." I converted this sentence into 2 predicates. P(x) = "x" is a ...
0
votes
1answer
63 views

Formal deduction proof of predicates

I am trying to proof equality is transitive, that is, $\emptyset \vdash \forall x \forall y \forall z ((x=y) \land (y=z) \to(x=z))$ using formal deduction (17 rules) and also other rules (ex. To ...
0
votes
2answers
36 views

Proving a consistent set of sequences

Iam trying to prove that if $\sum$ is a consistent set of sequences (formulas in predicates without any free variables) then, for every sentences $A$, either $\sum \cup\,{A}$ or $\sum\cup\,\lnot A$ is ...
2
votes
2answers
27 views

Predicate Logic: Distinguishing structures in the first-order language having only multiplication

I am attempting to distinguish the below structures under the multiplication function. As of right now I have determined the following: <N, ⋅>|= ∃z∀x∀y ((x-x=z)∩(y-y=z)) (xy ≥ z) ...
0
votes
1answer
50 views

predicate and logical equivalency question

i've been given a question "Are the statements ¬(∀xA(x) → ∀x∀yB(x, y)) and ∀xA(x) ∧ ∃x∃y¬B(x, y) logically equivalent? If they are equivalent, prove that they are. If not, give an interpretation ...
2
votes
3answers
84 views

If Las Vegas is the capital of Fiji, then $x^2=4$.

If Las Vegas is the capital of Fiji, then $x^2=4$. I was asked to state either the above claim is true or false. I must give a proof if it is true and counter example if it is false. I prove its ...
2
votes
2answers
79 views

Valid inference in first-order predicate logic

I should prove for the following premises and conclusion if the inference/conclusion is valid by using general resolution for clauses. The conclusion is valid if it is possible to derivate a ...
1
vote
0answers
16 views

Prove that $\{Tri, \lnot \}$ is not functional complete

Let the function $Tri(p,q,r)$ which returns $t$ if and only if at least 2 out of 3 input variables are $t$. Prove that $\{Tri, \lnot\}$ is not functional complete. I'd be glad for help, because ...
1
vote
1answer
33 views

Prove/Disprove a claim in logic

Prove/Disprove: $A, B$ are two formulas without common variables (meaning, $p$ is a variable of $A$ iff $p$ isn't variable of $B$, and vice-versa) and $\vDash A\to B$. Then, at least one of the ...
0
votes
1answer
28 views

Prove/Disprove the logical implication

Let $$(p\land q)\to r, d\to p, d\to \lnot r \implies \vDash \lnot q$$ Disproving: we choose $d=f$. Therefore, $p=f, r=t$. Hence, since $(p\land q)\to r = t$ then it must be that $(p\land q)=t$. ...
0
votes
2answers
22 views

Help solving a predicate logic question:

A(x,y,z): adding vector y to vector x results in vector z Translate the statement into english: ∀x.∀y.∀z.A(x,y,z) --> A(y,x,z)
0
votes
0answers
21 views

What exactly is the extension of an individual variable in predicate logic?

My question pertains to the semantics of classical predicate logic. If I'm working with a model M = $\langle D, v \rangle$ in which D is a non-empty set consisting of all existing obejects and $v$ is ...
0
votes
1answer
29 views

Predicate Logic: Validity of three quantifier sentences using truth tree

I am having a lot of trouble figuring out how to close the paths of the Truth tree for the following argument: ∀x∀y∀z(Axy->Azx) Conclusion: (∃x∃yAxy ->∀x∀yAxy) My attempt is as follows: (1) ...
1
vote
2answers
24 views

Predicate logic: Symbolize a sentence using a dictionary and two-place predicates

Given the following dictionary, how would the sentences below be translated in to a language using quantifiers? My attempts are shown as well: Dictionary: $L$: a two place predicate which means ...
0
votes
0answers
8 views

Prenex form of an expression: is that a valid transformation?

My new course in this semester starts of with predicate-logic and on the way touches prenex form, quantifiers, skolemization and unification - all topics quite new for me. I do not start completely ...
1
vote
1answer
25 views

Prenex form of an expression: Cannot understand example

My new course in this semester starts of with predicate-logic and on the way touches prenex form, quantifiers, skolemization and unification - all topics quite new for me. I do not start completely ...
0
votes
1answer
26 views

How to prove that the following predicate formula is valid…

I've been having trouble with proving validity in predicate logic. A question was given to us during a lecture that I was not able to attend and so I can't figure out the answer to the following Show ...
0
votes
1answer
23 views

Formal proof of predicates

I need to provide a formal proof of the following argument: Premise: $\exists x[P(X)\land\forall y(Q(y) \to \lnot R(x,y))]$ Premise: $\forall x[P(x) \to \forall y(S(y) \to R(x,y))]$ Conclusion: ...
1
vote
0answers
51 views

Predicate Logic Problem: Proof Using Change of Quantifier rule +Rules of Inference [closed]

I'm struggling with a problem my professor gave me. The task is to prove that the argument is valid using the 18 rules of inference, the Change of Quantifier rules (they are given below). I thought ...
0
votes
1answer
21 views

Predicate logic, The placement of a one place predicate in a conditional from a sentence of English

I was having some confusion about where to place the 'N' predicate in the conditional below. My guess was to keep it with what it was grouped with in the english sentence, however if it is not placed ...
1
vote
4answers
44 views

How can I provide a counterexample for this predicate logic problem?

I'm honesty still unsure of what a counterexample even is, and what I've found on isn't helping me much in the way of understanding. I'm hoping to get pointed in a correct direction. Predicates ...
1
vote
1answer
37 views

Should this be conditional or biconditional?

You can access Internet from campus only if you are a CS major or you are not a freshman How can the above English sentence be translated into a logical expression? I think this is ...
-1
votes
1answer
27 views

Transcribing a piece of English into set-theoretic notation

Suppose I've got the following model M = <D, S, i> where D is a non-empty set {John, Jane, Jonathan, Julia}, S = {L, a, b, c, d} where L is a binary ...