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

Questions tagged [predicate-logic]

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

1
vote
1answer
21 views

English statement to logic

If anyone cheats, everyone suffers. $S1:\forall x(cheat(x) \rightarrow \forall y\, suffer(y))$ $S2:\forall x \forall y(cheat(x) \rightarrow suffer(y))$ I thought Both S1 and S2 are wrong because ...
1
vote
1answer
8 views

Prove falsity of argument schemas in predicate logic

I have to give a counterexample for the following argument schema: ∃x (Px ∧ Qx) ⊨ ∀x (Px ∨ Qx) by definig its domain and the interpretation function, which is where I have some slight problems. On ...
0
votes
1answer
17 views

Predicate Calculus and Statement

I'm having a hard time to understand predicate Calculus, Statement and Prolog programming. Let $male$ be a unary predicate symbol with the indicated meaning. Let $parent$, $son$, $sibling$, and $...
1
vote
1answer
25 views

proof by finding suitable instances and resolution

I am trying to proof by resolution the following: 1) Given a language with the binary relation symbols $<, <<, <<<$ and the binary function symbols $+, *$ and the constant symbols ...
0
votes
1answer
46 views

Why $∀x(P(x)→Q)$ is equivalent to $∃xP(x)→Q$

Given $x$ occurs free in $P$. If $x$ does not occur free in $Q$, then $∀x(P(x)→Q)$ is semantically equivalent with $∃xP(x)→Q$. How to understand this statement. And also, need an example to show that ...
2
votes
1answer
21 views

Writing “Someone has visited every country in the world except Libya” using quantifiers.

Someone has visited every country in the world except Libya. Let $B(x,y)-x\,has\,visited\,country\,y$ Domain for x is all people and for y is all countries is $\exists x \forall y [B(x,y) \land (y \...
0
votes
1answer
24 views

$Pa\rightarrow \exists y Qy \vdash \exists y (Pa\rightarrow Qy)$ using natural deduction

$Pa\rightarrow \exists y Qy \vdash \exists y (Pa\rightarrow Qy)$ My friend asked me to prove this using natural deduction. He knows I studied logic but I know little about natural deduction since I ...
0
votes
0answers
15 views

Predicate logic - logically imply

Consider the following predicate formulas. $F1: \forall x \exists y ( P(x) \to Q(y) ).$ $F2: \exists x \forall y ( P(x) \to Q(y) ).$ $F3: \forall x P(x) \to \exists y Q(y).$ $F4: \exists x P(x) \...
0
votes
1answer
29 views

Prove this A∆B=C <=> B∆C=A

$A∆B=C <=> B∆A=C$ I don't idea. Is this correct task? Maybe the <=> means something else i don't know?
0
votes
0answers
23 views

Predicate Logic Quantifiers Question

I'm kinda confused regarding predicate quantifiers. Firstly, what's the difference between $\forall x .Tourist(x)$ and $\forall x \in Tourists$ I mean I understand that the first is a predicate ...
1
vote
1answer
34 views

Prove that the topological closure of a set is definable if the set is definable

Let $L$ be the language $L=\{<,=,+,-,\cdot, 0,1\}$, with standard interpretations, and let $\mathcal{A}=\langle\mathbb{R}, <,=,+,-,\cdot,0,1\rangle$. Let $S\subseteq\mathbb{R}^n$. Show that if $...
0
votes
1answer
18 views

Question with Predicate logic

I have the question: "Translate the following argument into the language of predicate logic. Determine if it is valid or invalid. Justify your answer by providing either an interpretation or a proof. ...
-1
votes
0answers
11 views

Predicate Logic Translation clarify person

I'm currently studying predicate logic and have a question regarding the translation for sentence. For example, when I have the sentence "Someone has borrowed a motorbike and is riding it." one ...
-1
votes
0answers
14 views

Does the following lambda state have the following beta reduction?

Does the following lambda state have the following beta reduction? = λT.λy. T ( λz.runs(y,z)) = λy.λz.runs(y,z)
0
votes
2answers
30 views

why is $\exists z \forall x \forall y (x-y=z+2)$ false?

In the rational numbers Q, is it true that: $$ \exists z \forall x \forall y \space (x-y=z+2) $$ This question showed up on my last test in discrete mathematics, and I have no idea why the right ...
2
votes
1answer
46 views

$T \vdash \forall x (f(x)=x \vee \dots \vee f^{n}(x)=x)$ for $\omega$-categorical theories

Let $T$ a $L$-theory $\omega$-categorical such that $f \in L$ is a symbol unary of function. I want to show \begin{equation} T \vdash \forall x (f(x)=x \vee \dots \vee f^{n}(x)=x) \end{equation} for ...
0
votes
1answer
31 views

logical equivalence between statements

I get confused when i think about logical equivalence between conditional statements. For example saying that ∼(P⇒Q)=P∧∼Q. If there is variables involved then the statement on the left says that ...
1
vote
1answer
48 views

consistent Henkin theory with language that has only one constant symbol

as the title says, I am looking for a consistent Henking theory (either a complete or an incomplete one, or both of them) whose language has only one constant symbol (but may have more predicate- and/...
0
votes
1answer
60 views

infinite and uncountable structures in specific classes of structures

I'd appreciate your help with proofing one or both of the following statements: 1) let $M$ be an infinite countable structure. We want to show that there's an uncountable structure in $Mod(Th(M))$, ...
1
vote
1answer
34 views

Show that $(\exists x. P_1(x) \to P_2(x)) \to ((\forall y.P_1(y)) \to \exists z.P_2(z))$ is a true statement.

We're covering Prepositional Logic in our class and I'm a little confused as to how the entire concept actually works. My understanding is that prepositional logic is used to study ways of combining ...
0
votes
1answer
23 views

Formalisation of a given sentence using quantiifiers

The question is: Minesweeper is a single-player computer game invented by Robert Donner in 1989. A unary predicate mine is defined, where $mine(x)$ means that the cell $x$ contains a mine ...
0
votes
2answers
47 views

What does it mean for a set of L-sentences $\Sigma$ to be computable?

I was reading these notes and found the definition of computable set of L-sentences (page 101 paper pdf): $$ \ulcorner \Sigma \urcorner = \{ \ulcorner \sigma\urcorner : \sigma \in \Sigma \}$$ where ...
0
votes
0answers
36 views

How does one show that the Godel number of $L-$terms are computable?

I was reading these (page 100 paper pdf) notes and was trying to show the Godel number of $L-$terms are computable. The structural recursion they have for this: I will use the symbol $g(t) = \...
1
vote
1answer
17 views

Why is $Th(\Sigma) := \{ \sigma : \Sigma \vdash \sigma \}$ an L-theory?

I was told that: $$ Th(\Sigma) := \{ \sigma : \Sigma \vdash \sigma \} $$ is an L-theory (i.e. its closed under provability i.e. $if T \vdash \sigma \implies \sigma \in T$). I feel it should be a ...
0
votes
1answer
26 views

Why is a relation that is $\Sigma-$representable not an IFF condition?

I was reading these notes and the definition of $\Sigma-$representability of a relation. It's as followings. $R$ is $\Sigma$ representable if $\forall a \in \mathbf N^m$ (where $a_i = S^{a_i} 0$ and $...
0
votes
2answers
35 views

Natural deduction: predicate logic proof (Prenex form)

I'm pretty familiar with proofs in propositional logic, but not so much with predicate logic. I'm trying to prove the following (which can be used during construction of prenex normal form). If x is ...
2
votes
3answers
66 views

Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\neg\varphi\}$ is inconsistent.

I am stuck at the following problem: Let $\varphi$ be a sentence in a predicate calculus $T$ and $\Sigma$ a set of sentences in $T$. Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\...
0
votes
0answers
31 views

Parentheses for quantifiers in First-Order Logic affect logical operators normally?

I'm sure this is a very simple question, but I cannot manage to find it explictly answered anywhere. Do parentheses used for quantifiers also affect logical operators normally? For example, if ...
0
votes
1answer
38 views

Problem in understanding the meaning of a quantified conditional statement based on the position of the negation operator. [closed]

Let the universe of discourse be the set of all human beings. $M(x)$ is an open statement which stands for "x is a man" and $B(x)$ stands for "x has black hair". I have problem understanding how the ...
0
votes
1answer
57 views

show that for every consistent theory there is a complete consistent theory

Let $\mathcal{L}$ be any language of predicate logic, $\Sigma_0$ a consistent theory in $\mathcal{L}$. Let P be the set of all consistent theories $\Sigma \supseteq \Sigma_0$ in $\mathcal{L}$. With ...
0
votes
0answers
41 views

What is the reason for the specific assumption on the nature of the variables?

In Angelo Margaris's book First Order Mathematical Logic we have the following theorem (see pp. 84), The equivalence theorem. Let $U$ and $V$ be two formulas (of First Order Predicate Calculus). ...
2
votes
1answer
82 views

proof of formula with Peano-axioms

For all natural numbers n define $\Delta_n$ as: $\Delta_0$ is the constant $0$ and $\Delta_{n+1}$ is $S(\Delta_n)$. Here is S the function for the follower, i.e. $\forall x: S(x) = x+1$. 1)I want ...
6
votes
1answer
170 views

How to show $(\exists x)( \forall y)\varphi\rightarrow( \forall y)(\exists x)\varphi $ is logically valid

How to show $(\exists x)( \forall y)\varphi\rightarrow( \forall y)(\exists x)\varphi $ is logically valid Here is my attempt: Assume it's not logically valid. Then, there's an interpretation $\...
0
votes
1answer
25 views

Statement to predicate formula

Let B(x) mean “x is a bird”, let W(x) mean “x is a worm”, let E(x, y) mean “x eats y”. There is a statement "Only birds eat worms". If we translate this statement to predicate formula it will ...
1
vote
2answers
41 views

how to prove ∃x(∃yA(y) → A(x)) is valid in classical logic

∃x(∃yA(y) → A(x)) i know how to prove it by natural deduction. but it requires to use model theoretical approach. so i'm not sure how we can prove the validity. can anyone help me please ?
0
votes
0answers
29 views

How to prove by equational proof

⊢(∃x)A≡(∃z)A[x:=z] where z is fresh for A rules same as here I proved via hilbert style to prove ⊢(∀x) A ≡ (∀z) A [x:=z] where z is fresh for A but struggling with equational proof for ⊢(∃x)A≡(∃z)A[...
0
votes
1answer
38 views

What does x is free for substitution for y in $\varphi$, but not for z means?

I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables. If x is free for substitution for y in $\varphi$, but not for z, where $\...
0
votes
1answer
29 views

First-Order-Logic: Structure of an extended language

Let $A$ be a structure in the language $L$ and $c_1,c_2...,c_n$ new constants. Show that $A$ can be extended to a structure in the language $L' = L $ $\cup$ $\{c_1,c_2...,c_n\}$. I know that for ...
0
votes
2answers
60 views

What inference rules are invalid in empty L-structures?

I want to understand why empty L-structures are illegal/not allowed in classical FOL. I read here but didn't understand the answer. It seems to be that there is some inference rule in FOL (as ...
0
votes
1answer
49 views

What is the formal definition in first order logic of the informal statement $\exists x \in A : Qx$?

tl;dr: Is the right translation of the informal statement $ \exists x \in A:Q(x)$ into formal FOL $\exists x (\varphi^A(x)\to Qx)$? Or $\lor_{x \in A} Qx$? Are they equivalent? Or perhaps something ...
0
votes
1answer
34 views

Proving $\exists k \in \mathbb{Z}: \forall l \in \mathbb{Z}: \lnot(k \mid l) $?

$$\exists k \in \mathbb{Z}: \forall l \in \mathbb{Z}: \lnot(k \mid l) $$ I have no idea how to approach this problem? If true, prove it, and if false prove the the negation. With its negation being: ...
0
votes
1answer
364 views

Is the reason that vacuous statements are True because empty L-structures are illegal?

I was learning mathematical logic in the context of (some) model theory and FOL using the language of L-structures (or just structures). Recall the definition of an L-structure. Its a set together ...
0
votes
0answers
21 views

If $\mathcal{A}\models \Phi$, then for $\phi\in \Phi$, $\mathcal{A} \models \phi [\alpha]$ for all assignments $\alpha$?

If a structure $\mathcal{A}$ satisfies a set of formulas $\Phi$, then for $\phi\in \Phi$, does $\mathcal{A} \models \phi [\alpha]$ for all assignments $\alpha$? I apologize if this question may be ...
0
votes
0answers
28 views

Creating a single formula $\phi$ in the pure language of equality.

I am trying to build a formula $\phi$ in the pure language of equality with variables $x,y,z$ such that 1. $x$ is free for substitution for $y$ but not for $z$, 2. $y$ is not free for substitution for ...
3
votes
2answers
52 views

What is the correct formalization of the statement: “Zero is the only neutral element in respect to addition”

In my home work assignment I was asked to formalize different statements. One of them was (assuming that we are talking about whole numbers): "Zero is the only neutral element in respect to addition." ...
1
vote
0answers
29 views

Elementary substructure and existentially closed

Definition. We say that $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{M}\subseteq \mathcal{N}$, and $\mathcal{N}\models \exists x \phi(x, a)$, where $a ...
0
votes
1answer
46 views

How does one formally show that bounded search with some property $R(a,x)$ is computable i.e. $\exists x \in \mathbf N (x < y \to R(a,x) )$?

Everything here is in the L-structure $\mathbb N = (\mathbf N;0,S,+,\cdot,<)$. I was following these notes and got stuck with the lemma 5.1.11 page 84 of paper (88 pdf): In this context we assume ...
0
votes
0answers
17 views

Find Interpretation for predicate logical formula

I Have to find a Interpretation so that $\Im (\alpha)$ is true. But how can i do that? $$ \alpha1 = \forall x \exists y \exists z (S(x,b) \to Q(x,y,z) \land \forall v (R(v,y) \to T(v,y))), \omega = \...
1
vote
0answers
63 views

Predicate Logic Hilbert Proof

In the Hilbert proof system for predicate logic, prove that the formula: $\exists x~\big(B(x)\to C(x)\big)\to\big(\forall x~B(x)\to\exists x~C(x)\big)$ I'm awful with Hilbert Proofs and have no idea ...
3
votes
0answers
61 views

Formal proof of $\exists x (\exists y P(y) \rightarrow P(x))$ and $(\forall x \exists y R(x,y))\rightarrow (\forall y \exists x R(y,x))$

within the following axiomatic system I've beeb trying to proof the formulas (1) $\forall x \exists y R(x,y) \rightarrow \forall y \exists x R(y,x) \\$ and (2) $\\ \exists x (\exists y P(y) \...