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

learn more… | top users | synonyms

0
votes
1answer
25 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
27 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
32 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
16 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
33 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
40 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
24 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
29 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. ...
-1
votes
0answers
29 views

Use quantifiers to express each of these statements. [on hold]

Let $L(x,y)$ be the statement “$x \space\text{loves}\space y$,” where the domain for both $x$ and $y$ consists of all people in the world. Use quantifiers to express each of these statements. There ...
2
votes
1answer
26 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
13 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
28 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
33 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
31 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
77 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
42 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
31 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 ...
1
vote
2answers
26 views

Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this ...
0
votes
0answers
44 views

What rules should I use to rewrite equations?

For a homework assignment I have to prove the following: Using: \begin{align} &[A_1]\quad \text{found} = (∃k : 0 \le k \lt i : b[k])\\ & [A2] \quad0 \le i \le N\\ &[A3]\quad i < N \\ &...
0
votes
4answers
89 views

why is $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$

I'm having a hard time wrapping my head around why $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$
1
vote
0answers
51 views

Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
1
vote
1answer
47 views

Compound Quantifier

Can any one help me what will be the universe discourse of these two statements? if both statement has natural numbers or same universe of discourse what will be values, that makes 1st statement true ...
1
vote
2answers
38 views

Every finite subset of $\Gamma$ is consistent implies $\Gamma$ is consistent

Thm: If every finite subset of $\Gamma$ is consistent then $\Gamma$ is consistent. My notes claims that it can be implied from compactness of $\vdash$. Meaning: If $\Gamma \vdash A$ then there's a ...
0
votes
1answer
15 views

Monotonicity property of logical systems

Suppose we have a logical system $s$. Now, the monotonicity property tells us that: $\Gamma \vdash A$ and $\Gamma \subseteq \Delta$ implies that $\Delta \vdash A$. I see this definition somewhat ...
1
vote
2answers
38 views

Is there a finite set of sentences, $\Gamma$ which is satisfiable?

Prove/ Disprove: There's a finite satisfiable set of sentences above $\Sigma$ a monadic-language, $\Gamma$ such that $\Gamma $ is satisfiable only for structures with size larger than $5$. ...
1
vote
1answer
43 views

Different definitions on closure under logical consequence

I am confronted with two (at first glance) different definitions on closure under logical consequence and would like to know whether they are equivalent and, if not, which is the one that would match ...
0
votes
0answers
27 views

Translate common language to formally

I am learning sentence logic( again) and I have an exercise which I'm not sure If I did it wrong or right: Let $(A,\leq)$ be an totally ordered set. Translate to formal language: "Any totally ordered ...
0
votes
1answer
25 views

$A,B$ satisfies on the same finite structures implies $A,B$ are logically equivalent?

$A,B$ are two sentences in Predicate Logic, such that for every finite structure $A$ is satisified iff $B$ is satisfied. Prove/ Disprove: $A$, $B$ are logically equivalent. I assume this ...
3
votes
2answers
30 views

prove or disprove logical inference

I need to prove or disprove the logical inference of the formula b from formula a: $$ a = \exists y (\forall x P(x) \implies Q(y)) $$ $$ b = \forall x (P(x) \implies \exists y Q(y)) $$ $$ P(x) \...
0
votes
1answer
21 views

Logical Arithmetic: Distribution

Hi I'm reading through "How to Prove it" and I was doing one of the practice problems. The question asks you to simplify as far as possible and they give you the following: $$\neg(\neg p \vee q)\vee (...
0
votes
0answers
22 views

Prove or disprove a FOL sentence using relevant domain diagrams: $\exists x (a.x\to b.x) \to (\forall x\,\, ax \to \exists b.x)$

Prove or disprove the FOL sentence using relevant domain diagrams: $$\exists x (a.x\to b.x) \to (\forall x\,\, a.x \to \exists x\, b.x)$$ Can you suggest me a way to prove or disprove above two ...
2
votes
2answers
79 views

Changing Hilbert-style axioms

Consider the following system for Hilbert-style deduction: Axioms: $A \rightarrow (B \rightarrow A)$ $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ ...
0
votes
1answer
35 views

First order predicate logic for “Every bike is a two wheeler manufactured by Hero”.

Let $A(x)=x$ is a two wheeler $B(x)=x$ is a bike $C(x)=x$ is manufactured by hero. Which of the following is first order predicate logic for statement Every bike is a two wheeler manufactured ...
0
votes
1answer
25 views

Concerning substitution and existential elimination in classic natural deduction using sequents

I am trying to prove $\exists x(P\lor Q)\vdash \exists x P \lor \exists x Q$, so I have: $$\begin{array}{r l l} (1) ~&~~ \exists x (P \lor Q) ~&~ \mbox{[premise]} \\ (2) ~&~ \quad (P \...
1
vote
1answer
43 views

Second-order logic and Russell's Paradox

I know that in first-order logic the following holds [see e.g. George Tourlakis, Lectures in Logic and Set Theory. Volume 2: Set Theory (2003), page 121] : $\vdash \lnot ∃y \ ∀x \ [A(x,y) \...
1
vote
0answers
33 views

Consistency Lemma in Lindenbaum's Theorem

Let $\Lambda$ be a modal logic, we say that a formula $\varphi$ is $\Lambda$-inconsistent if $\vdash_\Lambda (\neg \varphi)$ and is consistent otherwise. Similarly we say that a set of modal formulas $...
2
votes
1answer
26 views

How to express the following statement with Quantifiers and Predicates

Use quantifiers and predicates with more than one variable to express this statement: There is a student in this class who has taken every course offered by one of the departments in this school ...
1
vote
2answers
30 views

Can a propositional function have quantifiers?

According to Wikipedia, an open formula is a WFF without quantifiers. I have read that a propositional function is the same as open formula. Are both of these statements correct? Is it true that ...
1
vote
1answer
58 views

Given list of 10 statement , 8th statement is “Exactly 8 statements in list are false” . Then what is complement of 8th statement

I'm confused during solving this question means if 8th statement is false then what the 8th statement became ? does it became 1.Exactly 8 statements in list are true. or 2.This is not the case ...
1
vote
1answer
19 views

Understanding predicate logic given symbolic notation?

I'm having trouble understanding predicate logic. Question J is that saying "All broken windows are in the garage"? Is K. saying "for every x in the garage the x has a broken window" L.) "there ...
1
vote
1answer
38 views

For every $x$ and $y$ there exists $z$ such that $x-y=z$

If I have the statement. For every $x$ and $y$ there exists $z$ such that $x-y=z$ What would the predicate be for that statement? And how would it be written in symbolic notation? I can't seem ...
0
votes
2answers
105 views

Need help in assignment task in logic proof field!

We are currently struggling with this task in an exercise session. The problem is that none of us are that much familiar with proofing and this seems quite difficult. The task it self says: A list ...
1
vote
2answers
28 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$ ...
0
votes
0answers
29 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 \hspace{0,2cm}|\hspace{0,...