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

learn more… | top users | synonyms

0
votes
0answers
17 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
0
votes
1answer
14 views

Language and Finite Models

Let us consider the language consisting of one symbol $R$ for a binary relation. Let $\sigma$ denote the following sentence: $\forall x \exists y \exists z \ x\neq y \wedge y \neq z \wedge x \neq z ...
0
votes
1answer
16 views

A predicate logic question about write down a sentence

Let $\mathcal{L}=\{f\}$ be a first-order language containing a unary function symbol f, and no other non-logical symbols. Write down sentences $φ$ and $ψ$ of $\mathcal{L}$ such that for any ...
0
votes
1answer
27 views

what is the meaning of this predicate statement

This question appeared in the GATE exam 2011 Q.32 Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate P(x) = ...
-2
votes
1answer
27 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...
0
votes
0answers
18 views
0
votes
2answers
45 views

what happens in a universal implication when the premise is false

I have just started learning Mathematical logic and couldn't figure out the answer to the above question . my question is what happens to the truth value if the premise in a universal implication is ...
2
votes
1answer
63 views

How to write “there exists an infinite number of”?

We all know that means “there exists” and ∃! means “there exists exactly one”. Is there a similar notation for existence of an ...
0
votes
2answers
38 views

Is this theory complete?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
0answers
11 views

How to translate this sentences into predicate logic? [on hold]

Alice is clever. Bobby works hard. Chuck plays tennis. Dan and John will see Erika.
0
votes
3answers
40 views

At Most Two Distinct Members of A

The quantified predicate logic statement that describes at most two distinct members of A, where A, is some arbitrary set is: $\forall$xyz( (Px $\land$ Py $\land$ Pz) $\Rightarrow$ (x=y $\lor$ x=z ...
0
votes
0answers
14 views

Predicate logic truth value same?

Consider the predicate $$P(x,y,z) = xyz = 1",$$ for $$ x,y, z \in R,$$ $$x; y; z > 0.$$ $1 - \forall x; \forall y; \exists z; P(x; y; z). $ $2 - \exists x; \forall y; \forall z; P(x; y; z). $ ...
5
votes
1answer
46 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
40 views

What we can infer from there exists x satisfying P

If it is known that there exists x satisfying P, can we infer that there also exists x not satisfying P? I ask this question since I have a problem as follows. Given three premises: (1)if a student ...
1
vote
2answers
26 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
2
votes
2answers
42 views

Have I properly used $\,\exists !\,$ in this statement?

I want to express the following in logical notation. For every natural number, there is a unique natural number that succeeds it. Does the following statement express that proposition? ...
0
votes
1answer
29 views

Prove by contrapositive: Φ∪{β} ⊨ α & Φ∪{¬β} ⊨ α iff Φ ⊨ α

We are to prove this by contrapositive (by the way: Φ is a set of formulas of predicate logic and α a formula of predicate logic) I've managed the Right to Left proof, but I struggle with the Left to ...
0
votes
0answers
39 views

Find $\varphi$ of language $L$

I have the following symbols P - functional, airity=2, N - functional, airity=0, J - functional, airity=0, V - predicate, airity=2, K = functional, airity=2. I need to find closed formula $\varphi$ ...
0
votes
1answer
36 views

Example of language implementation

I'm trying to find example of implementation $M$ of language $L$ such that $M \models \varphi_1 \land \varphi_2 \land \varphi_3 \land \varphi_4$ Where $L = \{•, \blacksquare, n\}$ is language with ...
1
vote
1answer
36 views

Prove a predicate formula in the constructive logic

Using the constructive logic (the axiom $A\lor\lnot A$ cannot be used), using quantifier axioms and Modus Ponens, and Generalization, prove the following: $\exists x(B(x) \to C(x)) \to (\forall xB(x) ...
1
vote
1answer
33 views

proving unsatisfiability in a union of closed WFF

If I am given a closed set of wff $X$ and it is unsatisfiable, then how do I show that the set $X \cup \{A\}$, where $A$ is any closed wff, is unsatisfiable?
2
votes
1answer
40 views

provide an interpretation for a given WFF

Provide a satisfying and falsifying interpretation for the following WFF: ∀x∀y(P(x,y) ↔ P(y,x)) my attempt: x,y are numbers P(x,y): x > y falsifying ...
1
vote
1answer
17 views

determining free and bounded variable occurrences in a WFF

show all variable occurrences that are free and ones that are bounded and indicate the quantifier that binds them ∀a[∃b(P(a,b,c,d)) ∧ ∀c(∃a(R(b,a,c,d)))] my ...
0
votes
0answers
27 views

In logic is there a concise way to express the quantity of things that a predicate applies to?

I have $Fxy$, where F stands for 'falls on'. I want to express the number of such relations in the world. How would I notate this in formal logic?
1
vote
1answer
82 views

How to construct a counterexample?

The question: "Let $\mathcal{L}$ be a language, let $\psi$ be a formula and let $\phi$ be a subformula of $\psi$ occurring at position p. Let $\bar\phi$ be another formula and let $\bar\psi$ be the ...
3
votes
1answer
111 views

Show that the set of all positive L-formulas is consistent.

I am given the following definition of L-formulas: "Positive formulas are defined with the following properties: (i) Every atomic formula is positive. (ii) If $\phi,\psi$ are positive that ...
0
votes
0answers
27 views

Proof of predicate logic identity using quantifiers

I am attempting to prove this identity using only basic predicate logic rules. $\left ( \forall x A \right )\rightarrow B = \exists x \left ( A\rightarrow B \right )$ I understand that in order to ...
2
votes
1answer
32 views

Disagreement over Discrete Math Property

I know I'm probably wrong, maybe someone can explain it to me. I'm doing practice problems in preparation for a test that is coming up. Let u and v be two vertices in a graph G. Show that if G ...
1
vote
1answer
42 views

Comparing Statements and predicates using Truth Tables

Consider the four statements: $∃x$ $∀y$ $p(x, y)$ $∃y$ $∀x$ $p(x, y)$ $∀x$ $∃y$ $p(x, y)$ $∀y$ $∃x$ $p(x, y)$ which we call S1, S2, S3 and S4 respectively. Does there exist a predicate p such ...
0
votes
1answer
15 views

How do you use mathematic logical notation to notate a function whose output positively correlates with the input?

Suppose the amount of weight John gains from a meal is a function of the number of calories he eats, and that John will gain X weight, such that X>A, if he consumes Y calories, such that Y>B, where A ...
0
votes
1answer
39 views

Prove: [∃xp(x)->∃xq(x)]->∃x[p(x)->q(x)]

$[∃xp(x)\to∃xq(x)]\to∃x[p(x)\to q(x)]$ So I understand that if $∃x(p(x)\to q(x))$ is false then the whole statement would be false since it is an implication. In that case $∀x p(x)\wedge∀x \neg ...
-1
votes
1answer
26 views

Trouble conceptualizing discrete math problem

I'm studying for discrete math and I'm looking for my professor's test problems and their solutions. There is one in particular I am having trouble conceptualizing, maybe someone could help me out. ...
0
votes
1answer
46 views

Re-expressing a statement in First Order Logic in Propositional Logic

From what I understand a propositional variable must represent a statement (either true or false). If so, eliminating free variables from any predicate by either: (1) Replacing free variables with ...
0
votes
1answer
22 views

Give counterexample for $\forall x (P(x) \rightarrow Q(x)), \exists x(P(x)) \vdash \forall xQ(x)$

I know this should be quite easy but I can't figure out how I have to write down a model as a counterexample for this: $\forall x (P(x) \rightarrow Q(x)), \exists x(P(x)) \vdash \forall xQ(x)$ Let's ...
-1
votes
1answer
71 views

Is this question is true? [closed]

The negation of There is an x whose square is equal to 2 is for every x whose square is equal to 2 ???
1
vote
1answer
48 views

is $P(x) \to \forall x P(x)$ satisfiable

I need to prove that this formula $P(x) \to \forall x P(x)$ is satisfiable. Can I say for example that x is even number ?
1
vote
1answer
35 views

Prove equivalence in predicate logic

I have to prove that these formulas are equivalent: $$\begin{align} \exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y) \\ \end{align}$$ Can I say that $$\begin{align} \forall y \exists x ...
1
vote
1answer
26 views

Expressing given statements using quantifiers examples

I'm new on this subject and I have answered some questions which I found. Since there are no answers for them; I couldn't be sure that my answers are true. Could you help me verify the answers or ...
-1
votes
1answer
47 views

Is $\exists x \forall y \exists z P(x,y,z)$ satisfiable? [closed]

I have this formula: $$\begin{align} \exists x \forall y \exists z P(x,y,z) \\ \end{align}$$ How to check whether it is satisfiable? I know that I have to find a structure in which it is true.
0
votes
1answer
15 views

Predicate formula to propositional formula

I have: $$\begin{align} \exists x \forall y P(x,y) \\ \end{align}$$ where $$\begin{align} M=\{a,b\} \\ \end{align}$$ I need to convert this formula to propositional logic. I know that if ...
0
votes
1answer
37 views

Need alternative proof to $ \exists x (k(x) \rightarrow t)$ entails $\forall x (k(x)) \rightarrow t $

I tried to prove $ \exists x (k(x) \rightarrow t)$ entails $\forall x (k(x)) \rightarrow t $ as; $ \exists x (k(x) \rightarrow t)$ $ \exists x (\neg k(x) \lor t)$ $ \exists x (\neg k(x)) \lor ...
1
vote
3answers
50 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
2
votes
3answers
55 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
1
vote
3answers
39 views

Predicate logic translation $\exists y \exists x \neg P(x,y)$

Let P be the predicate P(x,y) "x owns y" where x represents people; y represents objects. $$\exists y \exists x \neg P(x,y)$$ I am trying to convert the above statement into plain english, for some ...
0
votes
1answer
69 views

Mathematical Expressions: Proofs

Prove or disprove the claim, and prove or disprove the converse: Claim 1: ∀n ∈ ℕ, (Ǝk ∈ ℕ, n = 5k + 2) ⇒ (Ǝj ∈ ℕ, n^2 = 5j + 4) Claim 2: ...
1
vote
0answers
32 views

A symbolic logic problem generator, or at least a huge ready-made collection?

I am an amateur student of formal logic, and I was wondering other Gensler's LogiCola program, is there anything out there that produces logic proof problems? For example, the LogiCola program I am ...
1
vote
2answers
41 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
1
vote
1answer
65 views

Example of first order logic,equivalence class,categoricity,abstract elementary classes

I have problems in a paper about AEC,with an example. In fact,I need to explain most of the details in that example. Let $\tau$ contain infinitely many unary predicates $P_n$ and one binary predicate ...
1
vote
1answer
50 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
57 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...