Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [predicate-logic]

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

1
vote
0answers
19 views

What is the precise definition of a free and a bound variable?

I've only recently started learning this topic and I'm confused about these definitions: I found two definitions for each type of variable which seemed to make sense: Free variable 1: In mathematics,...
0
votes
1answer
11 views

Dual of powerset is not a complete Heyting algebra

The following excerpt comes from Sheaves and Logic by Fourman and Scott (Applications of Sheaves (1977), pag. 304): I can't figure out where those two rules play a role in the proof that the powerset ...
0
votes
2answers
26 views

What does the existential quantifier imply about the variable it comes before?

For example, what does the statement imply about x? Is x a free variable (if so, isn't the set of real numbers imposing a restriction on x?)? or is it a bound variable with the domain of discourse ...
1
vote
2answers
36 views

How should logic notations be used when solving an equation?

This is what I found in one of my books (High school books; so probably not very mathematically accurate): I believe that the calculation itself is accurate; however, regarding the logic notations ...
1
vote
1answer
36 views

Prove or give counter example: $\forall x \exists y(Q(y)\wedge P(x))\vDash \exists y\forall x(Q(y)\wedge P(x))$

Prove or give counter example: $\forall x \exists y(Q(y)\wedge P(x))\vDash \exists y\forall x(Q(y)\wedge P(x))$ I think this statment is true: $x$ and $y$ are not free, so I can use the following ...
0
votes
2answers
21 views

Discrete Maths:Predicate Logic Negation

Let's say we have ∀xR(x). Is ¬(∀xR(x)) the same as ¬∀xR(x)? Does that mean that the negation goes only to the quantitative indicator?
1
vote
1answer
39 views

Predicate logic, models

I'm trying to understand predicate logic and models. I have an old exam question where we are supposed to find a model that shows that the formula does not hold: $$ \exists x(P(x) \land \neg M(x)), \ ...
1
vote
2answers
35 views

Is $\lnot\forall x(Px \lor Qx) \equiv \lnot(\forall x(Px \lor Qx))?$

Is $\lnot\forall x(Px \lor Qx) \equiv \lnot(\forall x(Px \lor Qx))? $ I'm trying to figure out how to apply the distributive law for universal quantifiers when the universal quantifier is negated, ...
1
vote
1answer
35 views

Quantifying a free variable in an example from “How To Prove It” by Velleman

This is an example from How To Prove It by Daniel J. Velleman (2nd Ed., p. 71): Example 2.2.3. Analyze the logical forms of the following statements. Statements about the natural numbers. ...
0
votes
3answers
92 views

Unambiguous set abstraction (set-builder) notations with parameters

I know two common variants of set abstraction notation. An examples of the first variant is $$ \{\,(x, y)\in\mathbf{R}^2\,|\,x^2 + y^2 = 1\,\} $$ (it is reminiscent of the axiom schema of ...
3
votes
1answer
68 views

“There is only” in first order logic

I'm trying to translate the statement "There is only three things that are not small" into first order logic. I'm using some software to verify my sentences, but I feel like I don't understand what "...
1
vote
1answer
64 views

Difference between these logical expressions of “if P, then Q”

What's the difference between these expressions? $P\Rightarrow Q$ $P\vdash Q$ $P\vDash Q$ $P \over Q$
3
votes
4answers
61 views

Why is $∧$ used in the right-hand side of $¬(∀x, P(x) → (Q(x) ∧ R(x))) ≡ ∃x, P(x) ∧ (¬Q(x) ∨ ¬R(x))$?

According to my textbook, the negation of $\forall x, P(x) \to (Q(x) \land R(x))$ is $\exists x, P(x) \land (\lnot Q(x) \lor \lnot R(x))$, so $\lnot(\forall x, P(x) \to (Q(x) \land R(x))) \equiv \...
7
votes
2answers
669 views

Are these formal formulas equivalent?

My textbook gave the following $ \forall x_0 (\exists x_1 \ x_0=(\mathbf{O''} \cdot x_1) \vee \exists x_1 \ x_0=((\mathbf{O''} \cdot x_1)+\mathbf{O'})) $, then commented on the syntax and why the ...
6
votes
2answers
73 views

How do I properly use a logical implication sign when solving an equation?

I was reading a book on mathematical logic, and I was confronted with the following question: $ $ $\sqrt{2x+1}=\sqrt x-5 ⇒ 2x+1=(\sqrt x-5)^2$ $⇔ 2x+1=x-10\sqrt x+25$ $ ⇔ 10\sqrt x=24-x$ $ ⇒ ...
-1
votes
0answers
49 views

Satisfying the Criterion of Non-Creativity When Defining an Operator

When defining a new operator in logic, we must satisfy the criterion of eliminability and non-creativity. I'm trying to satisfy the latter. Criterion of Non-Creativity: A formula P introducing a ...
10
votes
4answers
165 views

Problems teaching introductory logic. Is this a statement? “If x is an integer, then…”

Consider the claim, "If $x$ is an integer, then $x^3>0$". Is this a statement? My text defines a statement as "a declarative sentence which is true or false, but not both." At first it seemed ...
2
votes
2answers
98 views

Doubts about Goedel Completeness Theorem

My book (Mendelson) states this theorem the following way: (1) A logically valid formula of a first order theory is a theorem. On Wikipedia the statement is a little more general: (2) For any ...
1
vote
1answer
67 views

Is this well-formed formula for predicate logic?

Which of the following expressions are formulas of predicate logic? (i) $\forall X \, \forall Y \ (X \subseteq Y \leftrightarrow (\forall x \ x \in X \to x \in Y))$ (ii) $\forall P \ P(0) \...
5
votes
4answers
566 views

Is $ \forall x \in \emptyset. (P(x) \land \lnot P(x)) $ true?

I have searched the forums but haven't found any answers to this question, so I thought I'd ask it myself. Let $P(x)$ be an arbitrary predicate. Does the following statement evaluate to true or false?...
2
votes
1answer
52 views

Which one of the following equivalence is wrong [closed]

$$ 1) \forall z \ C(z,y) \ → B(t) \iff \forall z \ ( C(z,y) → B(t)) $$ $$ 2) \forall z \forall u \ (\forall x \ A(x,u) → \forall x \ B(x,z)) \iff \forall x \forall u \ A(x,u) → \forall z \forall x \ B(...
0
votes
1answer
43 views

Is $\forall I: I(f)=1$ where $f$ stands for a formula the meaning / definition of a tautology?

I have a question about the following formula. Is $\forall I: I(f)=1$ where $f$ stands for a formula and I for an interpretation the meaning / valid definition of tautology?
1
vote
1answer
57 views

Logical Formalization of: “Children don't eat pasta with spinach or mushrooms on it”

I want to formalize the following sentence in predicate logic: If a children has spinach or mushrooms on its pasta then it will not eat its pasta. The headline contains a shorter version. I have ...
-1
votes
0answers
14 views

Can I define the concept Tautology as: forall I: I(f)=1 where f is a formula [duplicate]

Can I define the concept Tautology as: forall I: I(f)=1 where f is a formula Tautology is $$\forall I: I(f)=1$$
0
votes
0answers
36 views

checking validity of given first order logic

Apologies if this question is already posted.As it is hard to search $\LaTeX$ in google and first order logic in nothing without $\LaTeX$ .But i am sure i have different doubt than that of already ...
3
votes
2answers
34 views

Which of the following logic statements are true

Question $S_1: \,\,\forall x \,\exists y \, \forall z\,(x+y=z)$ $S_2: \,\, \exists x \, \forall y \, \exists z\,(x+y=z)$ where $x,y, \text{and} \,\,z $ are real numbers. Which of the ...
1
vote
0answers
29 views

Are these formalization in predicate logic correct?

The sentence I want to formalize is the following: Every Italian likes to eat pizza. I come up with the following solutions: $$\forall x \forall y(Italian(x) \land Pizza(y) \implies LikeToEat(x,y)...
2
votes
0answers
74 views

Paradox,shortest proof

I have read somewhere that the shortest proof of a certain formula in the language of natural numbers contains some kind of paradox. I cannot remember what this paradox was nor where I've read it. It ...
2
votes
1answer
24 views

sequent calculus for first order logic

I've just started learning sequent calculus. Now I'm trying to prove the formula below: $$ \exists x (P → Q) ⊨ P → \forall x Q $$ My approach to the problem: $$ \underline{_⊢\exists x (P → Q) , _⊣ P ...
0
votes
0answers
23 views

Can truth of a single predicate be defined by another language that only shares that predicate?

I have been looking at Tarski's work and asked a question here: Can truth be defined by a 'same-level' language according to Tarski's undefinability theorem? I am trying to refine my ...
1
vote
2answers
34 views

Are these predicate formulas equivalent?

Are these first-order formulas equivalent? $$(\forall x)[(Ax \to Bx)\to(Cx \to Dx)]\tag{1}$$ $$(\forall x)(Ax \to Bx)\to (\forall x)(Cx \to Dx)\tag{2}$$ $$(\forall x)(Ax \to Bx)\to (\forall y)(Cy \to ...
1
vote
1answer
71 views

Proof of the deduction theorem in sequent calculus

Can anybody recommend me a text, where the deduction theorem for predicate logic is proved in LK? I mean the following proposition: if $A$ is a closed formula, and $B$ is arbitrary, then the ...
2
votes
2answers
23 views

What is the difference in meaning between these two antecedents …?

$$ (\forall x)(Mx \to Wx) \to \quad... \tag{1} $$ $$ (\forall x)(Mx \land Wx) \to \quad... \tag{2} $$ The consequent is clear: $\, (\exists y)(Fy \land Sy)$ The statement is: If every member of ...
3
votes
2answers
48 views

Sequences Eventually and Frequently in a Set

A sequence $(a_n)$ is eventually in an set $A \subseteq \mathbb R$ if there exists an $N \in \mathbb N$ such that $a_n \in A$ for all $n \ge N.$ A sequence $(a_n)$ is frequently in an set $A \...
0
votes
1answer
39 views

justify the truth value of quantifed statement

recently i have come across a question that required the translation of statement " all comedians are funny" in to a quantified statement. the answer to this question was " for all (x) ( comedian (X) ...
0
votes
2answers
36 views

Verification of the translation of English sentences into predicate logic.

I want to translate some sentences into predicate logic [based off the text "Language, Proof and Logic" (Barwise, Etchemendy) 1st ed]. The sentences are as follows: Only in front of large objects is ...
2
votes
1answer
29 views

Complete theory with quantifier elimination has finite boolean algebra

I have the following problem written down: If $\mathcal{L}$ has a finite signature, with no functions, and $T$ is a complete theory with quantifier elimination, then the boolean algebra of $\mathcal{...
0
votes
2answers
37 views

Transform a formula via prenex normal form to to Skolem normal form

I need to transform the expression $(\exists x \forall y \ r_1(x,g(y)) \lor \neg \forall x \ r_2(x,u))$ via prenex normal form to skolem normal form. I have encountered prenex normal form on one ...
2
votes
2answers
132 views

How to convert … to logical symbols?

If Bluenose is guilty then no witness is lying unless he is fearful. There is a witness who is fearful. Therefore, Bluenose is not guilty. $$B\to[(\forall x)(\,(Wx\land\lnot Fx)\to(\lnot Lx)\,)] \...
1
vote
0answers
15 views

Prove or disprove: Given signature and structures, isomorphism… Then the structure is unique

Prove or disprove: Let $\Sigma = (U; f_1,..,f_n)$ be a signature, let $S,R$ be $\Sigma-$structures, let $S$ be unique. Let $\phi: U_S \rightarrow U_R$ be an isomorphism. Then $R$ is unique. I ...
0
votes
0answers
25 views

How to express the ellipsis in predicate logic?

Consider a statement like: the graph G has an infinite path. I'm trying to translate that into predicate logic. I keep finding myself relying on the crutch of the ellipsis, e.g. expressing a path as $...
0
votes
1answer
63 views

If a theorem is $\kappa$-categorical and has a model of order $\kappa$ when $\kappa<\aleph_0$ , then it's complete [FALSE CLAIM]

For a theory $\Sigma$, if it has a finite model $M$ of order $\kappa$ which is $\kappa$-categorical, then $\Sigma$ is complete. It was mentioned in a class, but I wasn't able to find a proof, neither ...
-4
votes
3answers
143 views

What quantifier I need between $\in$ and $\notin$? [closed]

Seems that it is impossible to have an antitransitive relation that is also reflexive: Let $S$ be a set. $\mathcal R \subseteq S \times S$ be a relation on $S$ Let $R$ be antitransitive. Then $R$ is ...
1
vote
2answers
98 views

Exercise 0.6 in Algebra by Roger Godement

Let $R,S$ be two relations and $x$ a letter not contained in $R$. Show that the relation $$ (\forall x)(R \lor S) \iff (R \lor (\forall x)S) $$ is true. I am just working on the "$\Rightarrow$" case ...
1
vote
4answers
959 views

Can I justify removing a universal quantifier in this proof?

I am trying to prove that the connex property implies reflexivity. $\vdash (\forall x,\forall y : (xRy \lor yRx)) \Rightarrow (\forall x : xRx)$ Here is my attempt \begin{align*} &~~~~~(1)...
-1
votes
1answer
53 views

Expert opinion needed on a Syllogism Problem

Q) Given the statement here. Which of these conclusions logically follow: Statement: All A are B. Conclusions: All A are B Some A are B All A being B is a possibility Some A being B is a ...
2
votes
1answer
20 views

Is this transformation process of a predicate logic formula into Prenex normal form correct?

I want to transform this formula: $$(\forall a \exists b \exists c S(a,b) \land T(b,c)) \land (\neg \forall b U(b))$$ in Prenex normal form (PNF). Therefore, I do the following steps: Rename second ...
0
votes
0answers
41 views

How do I formalize such sentences in predicate logic?

How do I formalize such sentences in predicate logic? ...
0
votes
2answers
59 views

Why does the unique existential quantifier seem to allow weird behaviour?

I'm currently reading through an introductory book to proofs and have just stumled upon the unique existential quantifier $\exists!$ On the book as well as on Wikipedia it says that $\exists!$ has the ...
2
votes
2answers
100 views

Classical logic is the strongest consistent logical system

I vaguely remember reading somewhere about a theorem which states that classical logic is the strongest logical system in some sense. Unfortunately, after much search, I cannot find any reference. I’...