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

learn more… | top users | synonyms

1
vote
1answer
31 views

$\kappa$-categoricity in the language of identity

I have the following exercise from Dirk Van Dalen's Logic and Structure: Here with language of identity we mean the language with no extralogical symbols (i.e. no symbols of predicates, functions ...
0
votes
1answer
33 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
-1
votes
0answers
33 views

Universum, interpretation few question.

i have few questin about predicate logic and interpretation : I have formula like this: 1) $(\forall x: \neg p(x) \vee q(x)) \Leftrightarrow \neg (p(x) \wedge q(x))$ No i must choose is either of ...
0
votes
1answer
27 views

Satisfiable formula only over even structares

In First order Logics, what formula can I cook up, that's satisfiable over all even structures, and only even structures. (even structure means it has an even number of elements in its domain).
0
votes
1answer
25 views

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement I've done this so far, from $[(P→Q)∧P)]→Q$ to $[(~P∧Q)∧P)]→Q$ by Mat. Imp. to $[P∧(~P∧Q))]→Q$ by Commutation. After that ...
0
votes
0answers
32 views

Skolem normal form - difference form different thinking?

i found two tutorials which transfer this formula to Skolem form: $\forall x \exists y: \neg p(x,y) \vee \forall w \exists z: p(w,z)$ First case 1: $\forall x \exists y: \neg p(x,y) \vee \forall w ...
2
votes
1answer
43 views

Basic First Order Logic Question

Which one of the following well formed formulae is a tautology? (A) $\forall x\exists yR(x,y)\iff\exists y\forall xR(x,y)$ (B) $[(\forall x\exists y(p(x,y)\Rightarrow R(x,y))]\Rightarrow ...
0
votes
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
1
vote
0answers
46 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
1
vote
2answers
28 views

Confused on negation?

My textbook has the following (see Page 8 of Eccles's An Introduction to Mathematical Reasoning): Consider the following statement about a polynomial $f(x)$ with real coefficients, such as $x^2 + ...
0
votes
1answer
41 views

Predicates spimple tautology or not. [closed]

i'm not sure if am i doing it right. 1) $\exists x: p(x) \Rightarrow \forall x: p(x)$ <<--Tautology 2) $\forall x: p(x) \Rightarrow p(x) $ <<--- Here i can use instruduction universal ...
0
votes
4answers
70 views

Proof to be tautology

$\forall x : (p(x) \wedge \neg q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)$ The problem is: i know this is tautology but i don;t know how to proof it. Is anybody can help me?
1
vote
2answers
53 views

Can I prove set propositions using first-order logic?

I'm studying logic and sets and I have to say there's a strong similarity between the two. Most boolean/logic axioms also apply to sets. At the end of my course I also studied first-order logic (or ...
1
vote
2answers
28 views

Nested Quantifiers Doubt: “If $xy$ is equal to $x$ for all $y$, then $x=0$”

If $P(x,y,z)$ represents $xy=z$. Then represent the following statement using quantifiers,connectives etc. "If $xy$ is equal to $x$ for all $y$, then $x=0$". The answer given is $\forall x[ \forall ...
0
votes
2answers
35 views

Another basic Logic Question

Translate this statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) ∀x(C(x) → F(x)) The answer given in the book is:"Every ...
0
votes
1answer
55 views

Very Basic Logic Question

Given a set $S=\{-1,0,-5,-4\}$.Then is the following proposition true? $\forall x, (x>0 \implies x^2>0)$.
2
votes
2answers
51 views

Predicate logic by resolution

I've been trying to study logic lately, as part of my AI course, and I've been going through some old, simple exam questions from my school. There is one question about resolution in particular that I ...
-1
votes
1answer
15 views

$\{(\forall(x))P(x) \implies(\forall(x))Q(x)\} \implies (\forall(x))(P(x) \implies Q(x))$

$(\forall(x))(P(x) \implies Q(x)) \implies \{(\forall(x))P(x) \implies (\forall(x))Q(x) \}$ why this is not valid and how the converse of this is valid?
1
vote
1answer
27 views

Finite extension of decidable theory is decidable

Exactly what it says on the tin. I'm trying to prove that if T2 is a finite extension of decidable theory T1, then T2 is decidable.
2
votes
2answers
58 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
1
vote
1answer
49 views

Introduction to Symbolic Logic: 'Understanding Symbolic Logic, 2nd Edition,' by Virginia Klenk, Page 294

I read this passage in my textbook: ...if there is a counterexample in a domain with $m$ individuals, then there is also a counterexample in all larger domains. It follows by contraposition (and ...
2
votes
1answer
29 views

Semi decision procedures for Peano arithmetic?

Is there an efficient semi-decision procedure (i.e. an algorithm that sometimes works and sometimes not) for -at least- elementary problems in peano arithmetic? I am not talking about weak fragments ...
2
votes
3answers
88 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
1
vote
1answer
19 views

Using predicate logic to see if P(X) holds

Suppose We have a set called ${A}$ and we let it equal to $A = \{a \in \mathbb{Z} \mid a^2 = 3\}$ and we let ${P(x)}$ be the predicate ${x \in \mathbb{Z} }$ Problems: 1.) ${\forall x \in A }, P(x)$ ...
0
votes
0answers
13 views

Convert integer based ranking system into trueskill

I have an existing ranking system with 16 individual ranks, numbered from 1-16. These ranks are accurate (although extremely imprecise). As in, a rank 14 will almost always beat a rank 12 or below, ...
2
votes
2answers
40 views

Difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$

Existential quantifier confusion: what is the difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$? What are the differences between those two ...
0
votes
0answers
62 views

Determining a suitable universe of discourse

The question is this: Question: Identify a suitable universe of discourse such that the predicate z2 + 4 = 0 has existential import. Now if you try to factor this equation, you will see that it is ...
12
votes
1answer
171 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
2
votes
2answers
53 views

Finite fields properties

I had to solve a question in Logics, disprove the fact that "if two statements without free variables are satisfiable in the same finite structures, then they are logically equivalent". The only ...
3
votes
1answer
43 views

How to show that a logical argument is valid?

How to show that this argument is valid? $(\exists x) [p(x) \to q(x)] \to [(\forall x) p(x) \to (\exists x) q(x)]$ I started by showing that $\exists$x [p(x) $\to$ q(x)] is the premise. But I ...
0
votes
2answers
35 views

confusion about 2 first order logic wff's - they seem not equal, but instructor says they are =

I had a question about two first order logic formulas given in this lecture in the series on Discrete Mathematical Structures from IIT. The instructor says (at 36:19 in the video) that the ...
1
vote
1answer
42 views

$(Ǝx)H(x) \dashv \vdash (Ǝy)H(y)$?

I can prove the statement using the natural deduction, but I keep getting confused about this sequent, so it would be very thankful if someone can help me to understand this concept of predicate ...
1
vote
1answer
43 views

There exists a pair of positive ints $(m,n)$ such that $(m,n$ and $m+n)$ are all perfect squares

The only thing I figured to do was just to express these three guys.. $m =a^2$ ,$ n=b^2 $, and $m+n = a^2 + b^2$
0
votes
2answers
35 views

Existential quantifier equivalent of a universal quantifier statement.

My question is this, for the following sentence: Every pet has an owner , when translated into predicate logic gives $\forall x\enspace(P(x) \rightarrow O(x))$, but what is the equivalent with a ...
0
votes
1answer
68 views

Is “smarter than” a transitive relationship?

A logic assignment requires me to create a model in which most X's are smarter than most Y's, but most Y's are such that it is not the case that most X's are smarter than it. It's easy to do this ...
0
votes
1answer
40 views

Interpreting predicate formulas in the structure of arithmetic

Given two formulas a) $(\forall x)(\phi(x)\rightarrow\varphi)\;\;\;\;\;\;$ b)$(\forall x)\phi(x)\rightarrow\varphi\;\;\;\;\;$ Let $\;\mathbb{S}=(\mathbb{N},+,\times,\le,0,S)$ (where $S$ stands for ...
2
votes
1answer
49 views

In which direction is this statement true?

Having a hard time how I would go at this question. $\exists x \in G, P(x) \wedge Q(x) \iff (\exists x \in G, P(x)) \wedge (\exists x \in G, Q(x))$ $\forall x \in D, P(x) \vee Q(x) \iff ...
0
votes
1answer
30 views

$(\forall x)(Ax \Rightarrow Bx) \Rightarrow [(\forall x)Ax \Rightarrow (\forall x)Bx]$?

$(\forall x)(Ax \Rightarrow Bx)$ is same as $(\forall x)[(Ax \land Bx) \lor (\lnot Ax)]$ if for every $x$, $Ax \land Bx$ is true then we get $(\forall x)(Ax)$ true and $(\forall x)(Bx)$ true. We get ...
2
votes
1answer
40 views

How to prove UG is sound?

I want to show that the PL is sound for the set of rules $ S=\{P,T,C,US,UG,E \} $ That is, if $\Gamma \vdash_s \phi$, then $\Gamma \vDash \phi$ And I have already proved it except for UG If $ ...
0
votes
0answers
32 views

What will happen if there is a way predicting at a least one root of $p_{n}(x)=0$ without calculator?

let $p_{n}(x)$ be a polynomial of degree $n$ defined as follow : $p_{n}(x)=x^n +a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+.....a_{0}$ which : $a_{n-1},a_{n-2},.....,a_{0}$ are non nul real numbers coefficients. ...
2
votes
2answers
39 views

Prove using Hilbert calculus $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$, formal proof.

Prove: $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$ Using Hilbert Calculus Format of solution: Step (my understanding) Solution: (1) $\forall x(Px\rightarrow x\equiv a)\vdash ...
2
votes
0answers
34 views

Example of language $\mathcal{L}_1$ and set $\Gamma_1$ s.t. $\Gamma_1$ is Henkin but not consistent

Question: Give an example of language $\mathcal{L}_1$ and set $\Gamma_1$ of $\mathcal{L}_1$-formulae such that $\Gamma_1$ is Henkin but not consistent Answer: Let $\mathcal{L}_1$ be arbitrary and ...
-2
votes
1answer
26 views

FOL formula and check valididty of this? [closed]

I think the following is logically valid, but my TA says it's not logically valid. $ \forall x (A(x) \to B(x)) \to ( \exists x A(x) \vee \exists x B(x)) $ Who Can Clarify me about this Formula ?
3
votes
0answers
87 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all ...
1
vote
0answers
42 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
1
vote
1answer
26 views

How to prove this inference in sequent calculus?

I'm using the event-B prover to proove some proof obligations. I have a relation representing a $table: table \in 1‥n \to \mathbb{N}$. I know that in a sorted table the following property is true: ...
0
votes
2answers
28 views

Negating statements with quantifiers in them

First statement, ∀ odd integers n, ∃ an integer k such that n = 2k + 1 Second statement, ∃ m ∈ ℝ such that ∀ n ∈ ℝ, m · n = n Before the negation, I'd like to ask tips on how to translate this ...
0
votes
0answers
41 views

Proof by Resolution and Skolemization

I have this question where i have to prove the conclusion using the given premises : ...
1
vote
1answer
42 views

Transitive Closure and First Order Logic

Why is it not possible to represent transitive closure in First Order Logic? I am learning about translating from Description logic to FOL. In description logic, it is possible to have transitive ...
2
votes
1answer
45 views

How to use logical conjunction properly

On this website in equation (20) they use $$ d \, S = a \, d \, u \land d \, v $$ I have learned that $\land$ is the truth-functional operator of logical conjunction and that such logical operators ...