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

learn more… | top users | synonyms

1
vote
0answers
16 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
26 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
33 views

Proof by Resolution and Skolemization

I have this question where i have to prove the conclusion using the given premises : ...
1
vote
1answer
40 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
39 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 ...
1
vote
2answers
18 views

Translating a sentence into predicate logic

"A dragon is happy only if it has a green child". Have I translated this statement correctly into logic (below)? $\forall X \cdot dragon(X) \wedge happy(X) \Rightarrow \exists Y \cdot childOf(Y,X) ...
0
votes
1answer
50 views

Question about understanding an Interpretation definition in First Order Logic

I am trying to understand a definition within First Order Logic using interpretation. Below is the specific interpretation definition We define the truth value of a formula A in an interpretation I. ...
0
votes
3answers
45 views

Why if for all x, p(x) and for all x not p(x) is not a contradiction?

$\forall x: p(x) \equiv1$ and $\forall x: \neg p(x) \equiv 1$ is not a contradiction? I have this doubt after a logic contest, and I cant see why. My thoughs was that this is not a contradiction ...
2
votes
1answer
25 views

Did I analyze the logical form of a statement well?

Analyze the logical forms of the following statements. You may use the symbols ∈, !∈, =, !=, ∧, ∨, →, ↔, ∀, and ∃ in your answers, but not ⊆, ⊆, P , ∩, ∪, \, {, }, or ¬. (Thus, you must write ...
3
votes
1answer
69 views

Models of the successor function

I would like to ask a few questions about models of the succesor function (s(x)=x+1), intact that is a bit vague, consider $T_{S}$ to be the set of axioms given by; S1: $\forall xy[s(x)=s(y) ...
2
votes
1answer
99 views

A problem in the first-order predicate calculus.

So the teacher decided to make our life harder by giving us an extra-credit problem: Use the language of the first-order predicate calculus to express that in a group $ S $ of elements with a ...
1
vote
1answer
37 views

Translate proposition into formal language

Knowing that predicate $P(x)$ means '$x$ is a prime number' and $a/b$ denotes '$a$ is a divisor of $b$' express the following using logical operators, quantifiers, etc: 'number $z$ is a divisor of the ...
3
votes
2answers
32 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
1
vote
0answers
36 views

If $\nvDash\phi$ must it be $\vDash\lnot\phi$? If $\nvDash\phi$ where $\phi$ first order sentence must it be $\vDash\lnot\phi$?

I am stucked at this problem: Determine wether the following sentences are true or false in first order logic: (1) If $\nvDash\phi$ must it be the case that $\vDash\lnot\phi$? (2) If ...
1
vote
1answer
20 views

A problem of decidability (predicate metalogic)

I have been stumped by the following and would greatly appreciate any hints or advice as to how to proceed: For some first-order predicate logic system: Let Γ be a decidable set of wffs such that ...
0
votes
1answer
44 views

Discrete Math Validating Argument Using Deduction Method

I am lost trying prove that the expression below is a valid argument using the deduction method (that is using equivalences and rules of inference in a proof sequence). ...
1
vote
1answer
37 views

Discrete Math Predicate Logic with Balls

Attempting to use the predicate symbols shown and appropriate quantifiers, write each English language statement as a predicate wff. (The domain is the whole world.) I want to know if this is correct. ...
0
votes
0answers
16 views

Is this an instance of the base-rate fallacy?

The following line of probability reasoning is supposedly fallacious, and is an instance of the base-rate fallacy. The argument is that $(1)-(3)$ don't give us enough reason to conclude that $(C)$. ...
4
votes
5answers
34 views

True or false: The negation of $∃x : P(x)$ is $∃x, \neg P(x)$

I am trying to understand the negation of propositional logic with regards to universal and existential quantifiers. I want to know if the negation of $∃x, P(x)$ is $∃x, \neg P(x)$ is true or false. ...
0
votes
1answer
26 views

Unique readability showing an $\mathcal{L}$-formula

Question: Show the string $$\forall v_1\forall v_2(Pv_1\rightarrow Pv_2\rightarrow\equiv fv_1v_2c)$$ is not an $\mathcal{L}$-formula Answer: Assume for contradiction that $\forall v_1\forall ...
1
vote
1answer
39 views

Hilbert-calculus, formal proof

I have to give a formal proof in the Hilbert calculus for $(\forall x\,\,\phi)\rightarrow (\forall y\,\, \phi\frac{y}{x})$, if $x$ is free for $y$ in $\phi$ and $y$ is not free in $\phi$. ...
0
votes
0answers
10 views

Predicate logic of sorting algorithm

I'm confusing with this question. How can we tranlate a sorting algorithm for a list of N numbers to predicate logic, especially for insertion sort? Thank you very much!
1
vote
0answers
32 views

Logical Equivalence: $\exists x((P(x) \land \lnot Q(x))\Leftrightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$

I am trying to show LHS equivalent to RHS however, but I am unsure on this specific example. Any help would be appreciated. $$\exists x((P(x) \land \lnot Q(x))\Rightarrow R(x)) \iff (\forall ...
0
votes
1answer
7 views

Conversion to predicates including number

How can i convert these sentences into predicates, I'm a little bit confused since it includes numbers in the sentences? How can i represent the count operation? $f_1$ : There are $500$ employees in ...
0
votes
2answers
30 views

Predicate logic translation

Given: $Sx: x$ is a sith $Kxy: x$ kills $y$ $Dx: x$ succumbs to the dark side. Translate: Not everyone who kills a Sith succumbs to the dark side.
-1
votes
0answers
23 views

Proof in predicate calculus

Let, 1) m be a constant 2) P ,K be one place operation symbols 3) F be two places operation symbol 4) H,G be two places predicate symbols Let, the following assumptions: 1) $\forall A\forall B [ ...
0
votes
1answer
37 views

Can I define a predicate over a set and use it in the definition of another one?

Let's say I have two sets $A$ and $B$, and a relation $R \subseteq A \times B$. $R' \subset R$. Can I define a predicate $P(R) = \forall a \in A, \exists b \in B, (a,b) \not\in R$ And then define ...
1
vote
2answers
33 views

Find a logical predicate for some given conditions

I am trying to give an example of a predicate $P(x, y)$ such that $\exists x$ $\forall y$ $P(x, y)$ and $\forall y$ $\exists x$ $P(x, y)$ have different truth values. I am struggling to think of such ...
1
vote
1answer
24 views

If $Q(c) \iff \Sigma \vdash \phi[c]$, is $\lnot Q(c) \iff \Sigma \not\vdash \phi[c]$?

$Q$ is a relation as described above, $\Sigma$ is consistent, and $\phi$ is a formula with one variable. I think the relation in above holds because if $c$ does not belong in $Q$, then by the relation ...
1
vote
2answers
47 views

What sequent does this derivation prove?

Trying to learn sequent calculus and so I am trying to work thru some examples to get a better grip/understanding but the following question is not answered at the back of the book. I wrote my guess ...
6
votes
2answers
120 views

If $a=b$ then $a+c=b+c$? [duplicate]

A friend of mine just asked me how to prove that if $a=b$ then $a+c=b+c$, where $a,b$ and $c$ are real numbers, I'm not sure what I should answer. I have a book called introduction to logic and to the ...
3
votes
2answers
59 views

Help in proving a tautology

I am having real trouble deriving this tautology: $\forall(x) ((x=a) \lor (x\neq a))$ It is easy to solve this by assuming the negation, unpack the negation with DeMorgan's Law, and derive from ...
0
votes
1answer
26 views

Can First Order Logic identify that two variables are the same object?

Supposed I defined: $Px$ = $x$ is a person $Lxy$ = $x$ loves $y$ And I expressed that everyone loves someone: $$(∀x)(Px \implies (∃y)(Py ∧ Lxy))$$ However I want to formally exclude narcissists ...
3
votes
1answer
80 views

Hilbert–Bernays provability conditions

Let "provability formula" ${\rm Prf}(x, y)$ written in the manner that provability operator $\square A$ defined as $\exists x\ {\rm Prf}(x, \overline A)$ satisfying Hilbert–Bernays axioms: If ZF ...
3
votes
1answer
70 views

Does “Everyone loves all kittens” imply “Everyone loves a kitten”?

In my logic class, we explored whether various quantified statements implied others. We agreed that the statement "Everyone loves everyone" implies that "Everyone loves someone": $Px$ = $x$ is a ...
0
votes
0answers
45 views

Validity of a first-order formula

How can I see (and prove) whether the given first-order formula $\varphi$ is valid or not? $\varphi = \forall x \forall y [ (r(x,y) \rightarrow (p(x) \rightarrow p(y))) \land (r(x,y) \rightarrow ...
1
vote
1answer
30 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
0
votes
1answer
45 views

Bound Variable and Free Variable, A Questions and one Example?

I see a Local Contest Question as : for statement $ \forall x [ \exists y ( x<y+z) \to \exists z (x < y+z)] $ two following axiom is True: I) $ y, z$ is free and $x$ is bounded. II) ...
0
votes
1answer
48 views

Rewrite predicate formulas in propositional calculus

Suppose that the universe of discourse of the atomic formula P(x,y) is the set {0,1,2,3,4,5}. Write each of the following propositions using dis-junctions, conjunctions and only one negation: 1) ∃x ...
0
votes
0answers
12 views

How to use a predicate function when formalizing predicate propositions?

I've tried the following question from my maths assesment but not sure if I'm using the predicate, fool(p,t) correctly. Can anyone advise on if I'm using it ...
1
vote
1answer
49 views

If there are Predicates before Predicate Calculus, why is it called such?

In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False" Well, propositional calculus comes before predicate calculus, and ...
2
votes
1answer
76 views

How show $ S \models \forall x ( \alpha \Leftrightarrow \beta)$?

I read some notes on Logic Course. I read that we can conclude: $$ S \models \forall x ( \alpha \Leftrightarrow \beta)$$ if and only if $ S \models \forall\, x\, \alpha$ has conclusion $ S ...
0
votes
2answers
84 views

Why $ M\models \forall x ( \alpha \to \beta)$ Is False? [closed]

if M be a model and $\alpha$ and $ \beta$ be two formula the following is False: $ M \models \forall x ( \alpha \to \beta)$ if and only if $ M \models \forall x \alpha$ has conclusion $ M \models ...
0
votes
1answer
38 views

Equivalence of $\forall x (L(p,x) \implies \neg L(s,x))$

"Everyone who Patricia likes, Sue doesn't like" Let $L(x,y)$ stand for "$x$ likes $y$" and $p,s$ for Patricia and Sue, respectively. Then the statement in logic is: $\forall x (L(p,x) ...
1
vote
1answer
36 views

How do logicians notate a proposition that posits the instantiation of a property?

In The Oxford Companion to Philosophy, the entry on existence includes this paragraph. It is often held that ‘exist’ is not a firstlevel predicate. What this means is that ‘exist’ does not ...
0
votes
1answer
28 views

Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

just curious if there is a formal name for the results that: a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F} b) Two wffs A,B in ...
2
votes
1answer
126 views

I need help understanding Frege's definition of number

I have really been trying to understand Frege's definition of a number or at least gain a strong intuition of it. However, my attempts have not been fruitful. If someone could help me it would be much ...
3
votes
1answer
43 views

How to prove $(\forall x,y\in\mathbb{Z})(5\nmid xy\to(5\nmid x\land 5\nmid y))$

Question: Prove $x,y\in\mathbb{Z},\Bigl((5\nmid xy)\to(5\nmid x\land 5\nmid y)\Bigr)$ where $\forall a,b\in\mathbb{Z},\bigl((a\nmid b)\leftrightarrow(\forall k\in\mathbb{Z},b\neq ak)\bigr)$ and ...
1
vote
2answers
46 views

Predicate Logic and Calculus

Question of the week came up in my schools logic club but there is not much information to it. Here is the question: Show that $$ \exists x\,[R(x)\wedge \lnot Q(x)],\ \forall x\,[P(x)\to Q(x)],\, ...