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

learn more… | top users | synonyms

1
vote
1answer
18 views

In set builder notation, must the predicate have only one free variable?

question about set theory here, probably quite elementary. When we use the notation $t\in\{x \mid \Phi(x) \}$, whether in an actual set theory or just as an abbreviation for $\Phi (t)$, must it be ...
1
vote
1answer
38 views

Having an algorithm given a set of axioms and a sentence, can it prove all possible thorems?

Suppose we have an algorithm which, given a set of axioms $A$ and a sentence $P$ can prove if $A \implies P$. Would such algorithm be able to prove any possible theorem implied by these axioms? Is ...
0
votes
1answer
27 views

Confused by a step in the 'Rule C' proof in Mendelson's Logic Textbook

I've been working through 'Introduction to Mathematical Logic, 5th Ed' by Mendelson, and I've found a step in the proof of proposition 2.10 (Rule C) that I cannot understand. In the proof of this ...
0
votes
1answer
27 views

Predicate Calculus help

Working on predicate calculus this week, and was hoping I've got these correct, but I'm sure I've made some mistakes for sure.. All programmers enjoy discrete structures not all integers are ...
1
vote
0answers
21 views

Predicate Logic Statement Requirements

If I want to translate the following sentences to predicate logic: All students enjoy math. is it ok to specify $x$ are students and just do the following? $$M(x) = x \text{ enjoys math}$$ so ...
3
votes
1answer
58 views

Translate “If any cat is shy, then it is not happy” into predicate logic

Given $C(x)$ is “$x$ is a cat” $S(x)$ is “$x$ is shy” $T(x)$ is “$x$ is happy” translate the following sentence to predicate logic If any cat is shy, then it is not happy. This is what I ...
1
vote
1answer
55 views

Resolution Algorithms and one Example Problems?

We have a problem in one Resolution question. There is $5$ clauses, and want to prove the $6$th clause is true. which of the following clause is need more than one times to prove $6$th clause? $t$ ...
0
votes
2answers
25 views

Chartrand Mathematical Proofs 3e Exercise 5.45

I am self-studying this book, and I'm not sure if there is a typo in this question, or there is a gap in my understanding. The question is: Let $R(x)$ be an open sentence over a domain S. Suppose ...
2
votes
1answer
57 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
2
votes
3answers
65 views

Negating the statement $\exists x \in \Bbb R$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$

There exists a real number $x$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$. I would like clarification on how to negate this. My idea of negation is ...
1
vote
1answer
28 views

Monadic signature with constant

Consider a signature $\Sigma = \{ P^1, R^1, c\}$. Where $P^1, R^1$ are unary predicates, and $c$ is a constant. Let A be a formula in FOL over $\Sigma$. Prove/Disprove: If A is satisfiable ...
2
votes
1answer
45 views

First Order Logic Double Implication [closed]

I have a Logic Assignment of First Order Logic that I have to prove an initial claim, but one of the equations is kind of confusing for me because it has double implication and quantifiers. $$\...
2
votes
2answers
47 views

Axiomatizing stacks and queues using first-order logic

In the textbook I'm using to prepare the logic exam says that first order logic may be used to implement axiomatize data structures. There is an example of that: "Stack": uses a language that ...
3
votes
2answers
31 views

Quantification = statement about an open sentence?

The book I'm reading is talking about quantification being a method to convert open sentences into statements. From what I can see this method boils down to making a statement about the solution set ...
3
votes
2answers
83 views

What is the exact role of logic in the foundations of mathematics?

At high school and in the beginning of my university studies, I used to believe the following "equation": Foundations of mathematics = Logic + Set Theory Of course, this "equation" does not hold ...
1
vote
1answer
21 views

translating algorithm to preserve validity?

Let two languages $\Sigma_1 = \{R^2, P^1, =^2\}$ and $\Sigma_2 = \{c, f^1, =^2\}$. Prove or disprove: There's an algorithm (procedure that halts) which gets as an input a formula $A$ above $\Sigma_2$ ...
0
votes
0answers
110 views

Writing a set of first order clauses to define a predicate

I need some help on where to begin with the following question: We say that a list (term) represents the natural number $k$ in binary if it consists of constants 0 and 1 and the digits of the ...
0
votes
1answer
38 views

Model for first order formula

I need to find a model for the following formula: $$(\forall x \forall y \forall z.R(x,y) \wedge R(y,z) \Rightarrow R(x,z)) \wedge (\forall x\forall y.\neg R(x,y) \Leftrightarrow R(y,x))$$ So I ...
0
votes
0answers
22 views

Putting this formula in Prenex Normal Form

Given this well formed first order logic form: $\forall x (\mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \mathcal A_2^2(x,y)) \Rightarrow (\forall x \ \mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \forall ...
1
vote
3answers
55 views

Why does $p$ (is true) strictly agree with $p$ while $p$ (is false) strictly disagrees?

Let's make the truth table: $$\begin{array}{|c|c|c|} \hline p&(p) \text{ is true}&(p) \text{ is false}\\ \hline T&T&F\\ F&F&T\\\hline \end{array}$$ "$p$ is true" strictly ...
1
vote
1answer
22 views

$\vDash \phi \Rightarrow\, \vDash \psi$

How can I prove the last part of the following exercise. Show that $R\vDash \phi \Rightarrow R\vDash\psi$ for all structure $R$ implies $\vDash \phi \Rightarrow\, \vDash \psi$, but not vice versa. ...
1
vote
1answer
31 views

Logical equivalences of quantifiers

This is an excerpt from the Kenneth Rosen book of Discrete Mathematics. Show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent (where the same domain is used throughout). This ...
0
votes
1answer
31 views

What is objective and observer in logic?

I am a beginner at logic and took a elementary course in it... Could someone help me in the elementary definition of some part of a proposition that build the semantic part of a programming language ...
2
votes
0answers
19 views

Do automorphisms generate any specific equivalence?

I am thinking about a structure (in terms of predicate logic), where we have a carrier set A and some relations over A (no functions). I am thinking about all the automorphisms for that structure. I ...
0
votes
1answer
28 views

Invalid Application of Universal Introduction

The following is my attempt to formalize Berkeley's argument that it's not possible for a sensible object to exist without conceiving it. Line $3$ involves a meta-argument which I believe might be ...
3
votes
1answer
34 views

Confusion about there exist and forall

Which of the following is a correct predicate logic statement for "every natural number has [at least] one successor?" \begin{align*} A: \quad & \forall x\exists y\left(\operatorname{succ}(x,y)\...
0
votes
1answer
24 views

Logic determine whether a set is consistent

I got a question regarding defining whether a set of formulas is consistent in predicate logic. For example if we have the following sets: ...
0
votes
0answers
38 views

How is this a logical truth?

I've just been reading some lecture notes and it is claimed that the following is an example of a logical truth in first order logic (classically understood): $\exists$x $\neg$ (x=x) If this were a ...
0
votes
1answer
29 views

Showing validity of a formula in first order logic [duplicate]

So I'm trying to prove the validity of this formula and I am a bit lost, not sure how to start. I know generally speaking a valid formula is one where if all the premises are true, then the conclusion ...
2
votes
1answer
28 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
1
vote
2answers
33 views

Are those statements Tautology?

a.$$\forall x\forall y \exists z (x\neq y)\rightarrow (x\neq z)$$ b. $$\neg\exists x\forall y \forall z (x=y)\rightarrow (x=z)$$ To revoke a. we need to find a case of $(x\neq z)\land (x=y)$ and ...
0
votes
1answer
18 views

How can I translate this sentence into predicates and quantifiers?

sentence : Every cube is larger than something else. My Working: P(x) = x is larger than something else ∀xP(x) But the answer is something completely different. ∀x (A(x) → B(x)) : the answer ...
0
votes
1answer
35 views

Predicate Logic - Archimedes' Library

Problem: Our class takes a field-trip to Archimedes’ Library. Before entering the library, your tour guide makes you notice the sign on the main doors which reads: “Observe the Rule of Archimedes’ ...
1
vote
2answers
42 views

order of multiple quantifiers

Problem: For a, b, c, d restricted to the universe of positive integers, explain why ∀a ∃b ∀c ∃d a/b = c/d is true, but ∀a ∃d ∀c ∃b a/b = c/d is false. I understand that the order of ...
-1
votes
2answers
26 views

semantically equivalent

question about : $( (\forall x A) \lor B )$ is semantically equivalent to $( \forall x(A \lor B) )$ with condition that $x$ is not free in $B$. i have thought about structure , $U = \{ k , h \}$ ... ...
3
votes
2answers
32 views

Contrapositive of the statement involving “for every” and “there exists”

I have a statement (∃x.(P(x) -> (∀y.P(y)))) I am trying to formulate and understand the contrapositive of the formula. ...
2
votes
1answer
29 views

Predicate logic problem using natural deduction

I have the following clauses: $1. \forall x ({Ax \rightarrow Bx})$ $2. \forall x (({{Cx \wedge Bx }) \rightarrow Dx})$ $3. \forall x \exists y ({Cy \wedge Ryx})$ $4. \forall x \forall y ({({Ryx \...
1
vote
1answer
32 views

Reasoning informally about $\{x \in B \mid x \notin C\} \in \mathscr P(A)$

Attempting to apply more flexible, informal reasoning to predicate logic as demonstrated helpfully to me by another user in answer to my last question. $\{x \in B \mid x \notin C\} \in \mathscr P(A)$ ...
3
votes
2answers
23 views

Rewriting $\mathscr P(\bigcup_{i \in I} A_i)\not\subset\bigcup_{i \in I} \mathscr P(A_i)$ in more fundamental terms.

Working through Velleman's "How to Prove It" and currently having a bit of difficulty with a problem where I'm asked to rewrite this: $$\mathscr P\left(\bigcup_{i\in I} A_i\right)\not\subset\bigcup_{...
0
votes
0answers
14 views

Unary relation in a logical sentence

I'd appreciate help with this sentence: Let there be a language L and a structure M, and I need to prove the following sentence is logically false: $$\varphi :\exists xR(x)\rightarrow \forall yR(y)$$ ...
0
votes
1answer
25 views

True or falsehood of open formula under a fixed interpretation

Given the open formula: $\alpha =(\exists{{x}_{2}})({P}^{1}({x}_{1},{x}_{2}))$ And consider the interpretation $I$ where the domain is the natural numbers, and ${P}^{1}$ means equality. Is $\alpha$ ...
0
votes
1answer
26 views

Using separators as functional symbols in first order logic

Suppose we have the following definition of a term: A $term$ is: $x$, where "$x$" is a variable $c$, where "$c$" is a constant symbol $f(\tau_1,...,\tau_n)$, where "$f$" is a ...
1
vote
2answers
29 views

Predicate logic: $(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi))$

Given $L$ language and $\varphi$ and $\psi$ are formulas. Needs to show that is happening in general: $$(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi)...
0
votes
1answer
29 views

How can I express each of these quantifications in English?

Let T(x) be the statement "x has visited Tashkent" where the domain consists of all students of my school. How can I express each of these quantifications in English? ...
1
vote
2answers
34 views

What is the negation of ∀x∃y¬P(x,y) without using ¬?

Found it to be ∃x∀yP(x,y). Is this right?
1
vote
0answers
32 views

Negation of double universal quantifications

In logic, when I want to negate the formula $$\forall x \forall y( F(y) \land A(y) \to \neg G(x,y))$$ what is the correct equivalent? Intuitively, I think it gives $$\exists x \forall y (F(y) \land ...
1
vote
1answer
83 views

Logic: Who doesn't eat meat, is vegetarian

How to translate "Who doesn't eat meat, is vegetarian" into a formula with predicate letters Lx meaning x is meat, Exy meaning x eats y, and Vx meaning x is vegetarian? I tried, "for every x and for ...
0
votes
0answers
21 views

Calculating a likely position in 0.5 seconds with only the knowledge of the last second (x,y coordinates)

I have x,y coordinates for football players (22) at a rate of 10 records per second - for an entire football match. I have created an animation of the match with the player locations updates at a ...
0
votes
1answer
44 views

Express statement with predicates and quantifiers.

Ex: A student must take at least $60$ course hours, or at least $45$ course hours and write a masters thesis, and receive a grade no lower than a B in all required courses, to receive a masters degree....
-1
votes
1answer
33 views

Express the statement using predicates and quantifiers.

Ex: A passenger on an airline qualifies as a frequent flier if the passenger flies more than $25,000$ miles in one year or takes more than $25$ flights during that year. I started and made up these ...