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

learn more… | top users | synonyms

1
vote
1answer
14 views

Quantifiers and Predicates in Discrete Mathematics

I was doing midterm review and I came across these formulas $$\forall x \big( P(x) \to Q (x))$$ and $$\forall x P (x) \to \forall x Q (x)$$ I wanted to know what the difference was in terms of $x$ ...
-4
votes
0answers
14 views

prove the proposition using formal logic [on hold]

prove using formal logic $\forall x ( \neg P(x) \lor Q(x)) \vdash \forall x ( \neg H(x) \lor Q(x)) \lor \exists x ( H(x)\wedge \neg P(x))$
1
vote
0answers
35 views

Need help with translating English sentence to predicate logic

I am struggling with one task in assignment. The task asks to translate sentences to predicate logic, but the sentences are so complicated that Googling for help does not seem to help that much. The ...
0
votes
0answers
26 views

Predicate logic example..

I've got this predicate symbol: $(\forall x R(x,y)) \implies (\forall y Q(x,y))$ $R=\{(x,y) \in Q \times Q \hspace{0,2cm}|\hspace{0,2cm} x<y\}$ $Q=\{(x,y) \in Q \times Q ...
0
votes
0answers
23 views

proof : the set of all logical consequences $S,\{F:S \models F\} $ is a maximal set. [on hold]

prove that the set of all logic consequences $S,\{F:S \models F\} $ is a maximal set.
1
vote
0answers
7 views

in finite structure formula true

P is a two digits relation-symbol and $\phi$ the formula: $(\forall x Pxx \wedge \forall x \forall y \forall z(Pxy \wedge P yz \rightarrow P xz) \wedge \forall x \forall y (Pxy \vee Pyx) \rightarrow ...
1
vote
0answers
20 views

Deductive closure from Completeness

the prompt asks to show that if $\Sigma$ is complete, then it is deductively closed. I know that deductive closure means $\Delta \vdash \sigma$ implies that $\sigma \in \Delta$. and that since ...
0
votes
1answer
22 views

Proving a theorem in predicate logic without the use of metatheorems

I'm trying to prove: $$\forall x (\phi \rightarrow \psi) \rightarrow (\forall x (\phi) \rightarrow \forall x (\psi))$$ and $$\forall x \forall y (\phi) \rightarrow \forall y \forall x (\phi) $$ using ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
0
votes
0answers
17 views

Help with some predicate Calculus arguments

I just need a little help finishing off this proof, not sure where to go from here with introducing (∀x) (∀x) F(x) ⇒ G(x), (∃x) F(x) ⊢ (∀x) G(x) 1 (1) (∀x) F(x) ⇒ G(x) A 2 (2) (∃x) F(x) A ...
0
votes
0answers
9 views

pradicate logic, validity,

$L=\{E\}$, for a realtionsymbol E (2 digits). Be $x,y,z,x_1,x_2..$ different variables. A graph is a L-structure $\mathcal{G}=(G, E^{\mathcal{G}})$ with $E^{\mathcal{G}}$ irreflexive and symmetric ...
2
votes
2answers
36 views

Is the universal quantification symbol $\forall\;$ known as “for any x” or “for all x” in First Order Logic & why is this different to Discrete Math?

I'm reading a book by Mark Tarver called Logic, Proof and Computation. Chapter 8 (starting p71) is about First Order Logic. On page 77 (of Chapter 8) the author writes: For any value for 'x', in ...
0
votes
1answer
22 views

what types of biconditionals are there?

I take it there's more than one, as the logic book I am studying mentioned the 'material biconditional', and that the term material can be dropped for just biconditional in general. So presumably, ...
17
votes
3answers
1k views

Why does what I've written fail to define truth?

I stumbled across a set of axioms for first order logic a bit ago. Intrigued, I decided to try to write it all down and organise what I read. After I did that, it seemed to me as though one could ...
0
votes
1answer
29 views

Translating “some student asked every faculty member a question” into a logical expression.

$ S(x) $ is the predicate "$x$ is a student" $F(x)$ is the predicate "$x$ is a faculty member" $A(x,y)$ is the predicate $x$ asked $y$ a question I need to translate this sentence into logic: Some ...
0
votes
0answers
25 views

A certain question about elementary logic and functions.

I need to understand the following detail. Suppose we know the following is true(we know that composition for functions $\theta, \sigma$ and $\tau$ is well-defined): There is a unque isomorphism ...
2
votes
0answers
29 views

Describe a set with FOL formula

This is a problem from Introduction to Mathematical Logic course A structure $\mathscr{A}$ with domain $\mathbb{N}^k$ is for FOL language $\mathscr{L}$ with $k$ predicate symbols $p_1, \ldots, p_k$ ...
0
votes
1answer
22 views

Predicate Logic - Software Testing

This is a section from Logic Coverage in Software Testing, I don't understand how the logic of the image below is resolved. Assuming that the value of b is true, (true <-> b) should resolve to ...
0
votes
2answers
23 views

Rectified prenex form conversion algorithm inconsistencies

I've looked at these two different RPF conversion algorithms where the first step of each, say 1 and 1', states: 1.Remove all “$\to$”s using the fact that $\alpha\to\beta ≡ \neg\alpha\lor\beta.$ ...
0
votes
0answers
27 views

First Order Logic Tableau Multiple Universal Identifiers

I've been looking into tableau lately and I have come across multiple Universal Identifiers which I am not used to. How do I approach these to validate/invalidate with these identifiers and provide an ...
1
vote
2answers
60 views

Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite

I got the following exercise: Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite. I already tried to prove this ...
2
votes
1answer
45 views

Corollary to Fermat's Little Theorem

A consequence of Fermat's Little Theorem If $p$ is prime and $a \in \mathbb{Z}$ not divisible by $p$, $a^{p-1} \equiv_{p} 1 $ is If $p$ is prime and $a \in \mathbb{Z}$ then ...
0
votes
2answers
43 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
37 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
39 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
61 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
27 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
32 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
22 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
38 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
31 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
49 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
21 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
71 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
34 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
40 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
23 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
45 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
17 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 ...