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

learn more… | top users | synonyms

-2
votes
0answers
40 views

Boole's functions' domain is D = {1, 2, 3, 4}. Find ∃xF(x, 2), when F(x, y) = 1100 1111 0011 0101. [on hold]

The problem is, I actually do not understand this problem very well. When the logical function is given, making truth table is not a problem for me at all. I wonder, if this exercise requires to make ...
1
vote
1answer
29 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ...
0
votes
1answer
39 views

Show that $ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $ is, in general, NOT a theorem.

Show that $$ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $$ is, in general, NOT a theorem. My answer: First, I got the abstraction of the formula which is $ p \rightarrow A \lor q$ then ...
1
vote
1answer
46 views

Give an equational proof $ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$

Give an equational proof $$ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$$ I don't know where to start. Maybe I could start with $ (\forall x)(A ...
2
votes
2answers
49 views

Give a Hilbert-style proof $ \vdash ( x=y \rightarrow y = x) $

Give a Hilbert-style proof $$ \vdash ( x=y \rightarrow y = x) $$ I don't know where to start. I thought maybe I can use Ax5 (Identity axiom) $ x = x $ as a starting point. See George Tourlakis, ...
3
votes
1answer
36 views

Give an equational proof $ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $

Give an equational proof $$ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $$ What I tried $(\exists x)(A \lor B)$ Applying Definition of $\exists$ $\lnot (\forall ...
2
votes
1answer
64 views

How to write negation of statements? [on hold]

How to write negation of following statements in words? ...
1
vote
1answer
49 views

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema?

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema ? If you think 'yes', then give a proof. If you think 'no', construct a counter model ...
0
votes
1answer
26 views

What is “Standardizing variables” in the procedure of converting First Order Logic to CNF?

What is meant by the step "Standardize variables" in the procedure of converting First Order Logic to CNF? The 6 all steps can be listed as, ...
1
vote
1answer
34 views

Converting statements with term 'only' and 'any' to predicate logic

How to convert following statement into predicate logic? 1)"Only dogs are mammals" 2)"Any dog is a mammal" Is there a difference between "Any dog is a mammal" ...
0
votes
1answer
33 views

Applying substitutions on formulae in logic

Do the following substitutions. If undefined, explain why. $ (p \land \top \equiv r)[\bot := r] $ $((\forall x)(\forall y)(\forall z)(g(x,y) = z))[z := f(x) = y ]$ $(p \rightarrow q \land \bot)[p := ...
1
vote
2answers
77 views

Give an equational proof $ \vdash (\forall x)(A \rightarrow B) \equiv ((\exists x) A) \rightarrow B$

Give an equational proof of $ \vdash (\forall x)(A \rightarrow B) \equiv ((\exists x) A) \rightarrow B$ I tried and used ping pong theorem to split it into two implications to prove $$ \vdash ...
1
vote
0answers
18 views

Is the formula an absolute theorem schema?

Is $ (\forall x)(A \rightarrow B) \vdash (\forall x)A \rightarrow (\forall x)B $ an absolute theorem schema ? If you think yes, then give a proof. If you think no, construct a counter model or prove ...
0
votes
1answer
31 views

Use the auxiliary variable metatheorem to proof

Use the auxiliary variable metatheorem to show that $$ \vdash (\exists x)(A \land B \land C) \rightarrow (\exists x)(A \rightarrow C \rightarrow B)$$ My answer : By using the deduction theorem we ...
1
vote
1answer
14 views

Give abstraction to formula and use the definition of tautological implication.

(a) Give the abstraction of $$ (\lnot((\forall x)(\varnothing(x) \land p)) \rightarrow \lnot q) \rightarrow (\lnot ((\forall x)(\varnothing (x) \land p)) \rightarrow q) \rightarrow ((\forall ...
0
votes
0answers
13 views

How to prove that a predicate is decidable?

Prove the following predicates are decidable knowing that A and B are decidable predicates: ~A A or B I am supposed to prove this by writing a program or using some other way that a predicate is ...
0
votes
1answer
44 views

Is the following schema a derived rule of our logic?

Is the following schema a derived rule of our logic? $$ A \rightarrow B \vdash A \rightarrow (\forall x)B, \text{ provided $x$ is not free in $A$ }$$ If yes, then give a proof. if no, show why by ...
3
votes
2answers
59 views

How to interpret $\exists x (\forall x \Phi (x))$?

It's clear to me what the interpretation is when we have something like: $$\exists x (\forall y \Phi(x, y))$$ or even how to interpret the formula when x or y are not variables in the expression ...
1
vote
1answer
67 views

How to extract the sets “produced” by a axiomatic set theory, into some newly introduced collection?

Say I know well how to reason in a set theory, which for the sake of this question I'll call $\bf{ST}$, say one of those, it can by $\bf ZFC$. It's principally written down via first order logic and ...
1
vote
1answer
67 views

Predicate Calculus English Translation

I'm having difficulty translating the following English sentences into predicate logic. Any help would be greatly appreciated. $B:\qquad$_ is a book $A:\qquad$_ is an author $H:\qquad$_ is a ...
2
votes
1answer
62 views

Predicate logic proof

Prove the following formula. $$ \vdash (\exists x)(A \land B) \lor (\exists x)(A \land C) \equiv (\exists x)(A \land (B \lor C))$$ The question is number 10 in chapter 6 in "Mathematical Logic" by ...
1
vote
1answer
24 views

What does rule schematic mean?

While I'm studying the mathematical logic, the book says "Each rule of such a calculus either says that certain strings belong to $Z$, or else permits the passage from certain strings ...
1
vote
1answer
62 views

Prove formula in Predicate Logic

Prove the following $$ \vdash A \land (\exists x) (B \rightarrow C) \equiv (\exists x)(B \rightarrow (A \land C)) $$ as long as $ x$ not free in $A$. This is question number 9 chapter 6 in ...
0
votes
0answers
10 views

How do Boolean-valued functions work?

Consider this function: P: X→ {true, false} There's nothing in that expression that says when X is true and when it is not true. How do these work?
1
vote
1answer
19 views

How do atomic formulas with negated subjects translate into English?

I'm reading about negative normal forms. My text talks about transforming H¬x to 'negative normal form' so it reads ¬Hx. If the two sentences are interchangeable, then they mean the same thing. So, ...
1
vote
0answers
48 views

Question about accessibility of category of free abelian groups.

I've read, that the accessibility of the category of all free abelian groups is independent on basic set theory (say ZFC). What is the reason for that? And how can I interpret this result? Does it ...
1
vote
0answers
35 views

Is this predicate logic true?

∃ x ∈ R, ∀ y ∈ R x ≥ y Write the statement in English. A complete answer will not use any mathematical notation, nor the symbols x and y. Write down the truth value of the statement. Write down the ...
0
votes
1answer
73 views

Proving formula in predicate logic

Give a proof of $ \vdash (\forall x)(\forall y)x=y \rightarrow (\forall y)y=y$ How could i prove this one ?
1
vote
1answer
14 views

Definition set of axioma's

The definition is: "A set of formula's $\Sigma$ axiomizes $Th(M)$ if for all sentences $\phi$ the following applies: $\phi \in Th(M) \Leftrightarrow \Sigma \models \phi$" Where $Th(M) = \{ \phi | ...
0
votes
2answers
51 views

Convert this solution to inference notation

This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ...
0
votes
0answers
22 views

What is are the differences and similarities between quantifiers and assignments/mappings?

In predicate logic, you have quantifiers, a structure and a model, and something called (in Dutch) "een bedeling", which I will call "mapping" (since I have no idea what it is called in English). This ...
1
vote
2answers
34 views

Contraposition of an implication with quantifiers

I am trying to prove a theorem, and a method is by using contraposition. What is the contraposition of the phrase: $\exists x$ satisfying P $\Rightarrow$ $\forall y$ satisfy P I thought it as ...
1
vote
0answers
39 views

General (Set Builder) definition for a relation composed with itself n times

Questions What does the set builder notation for $S\circ R$ look like? I'm having the most trouble knowing when there is too much information or not enough information on either side of the 'such ...
0
votes
1answer
19 views

Predicate logic describing a function that is not onto.

I'm trying to understand how to write predicate logic describing a function that is not onto. A function is onto if every element in the codomain gets mapped to by some element in the domain using ...
3
votes
2answers
195 views

How do commas and brackets affect the meaning of quantifiers?

My logic class didn't introduce us to multiple quantifiers. I've seen a few variations that seem to have distinct meanings: $$ \forall x, \forall y(...) $$ $$ \forall x \forall y(...) $$ $$ \left( ...
5
votes
3answers
157 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
2
votes
2answers
92 views

How to show tautologies in FOL using truth definitions?

Anyone know how to prove these tautologies by way of truth definition? I take it that to solve a), I need to disprove a minimal counter example to the formula/sentence given? If so, how to formally ...
0
votes
1answer
66 views

the sum of two odd integers is even

How do I represent this statement using symbolic notation? This is my attempt at it. $$ \forall n \in \Bbb{Z}, \forall m \in \Bbb{Z}, (n = 2q + 1) \wedge (m = 2k + 1) \Longrightarrow (m + n = 2l) $$ ...
1
vote
1answer
90 views

Prove $\forall x~\forall y~\forall z (x+y)+z=x+(y+z), \forall x~\forall~y\exists z~ x=y+z, \forall x~\forall z \exists y x=y+z ⊢ ∃y∀x x+y=x$

I need help using the standard rules of predicate logic with quantifiers to prove $~\forall x~\forall y~\forall z ~~(x+y)+z=x+(y+z), ~\forall x~\forall y~\exists z ~~x=y+z, ~\forall x~\forall z~ ...
0
votes
0answers
11 views

How to notate truth conditional functions

My semantics professor uses functions to teach her class. She wrote the following sentence and three examples in one of her slides. [[smile]] is a function that takes something, let’s call it x, and ...
0
votes
2answers
29 views

Prove that ∀Z · ∃Q · (p(Q) → p(Z)) ⊨ ∀Z · (∃Q · p(Q)) → p(Z) does not hold by giving a suitable structure

Prove that ∀Z · ∃Q · (p(Q) → p(Z)) ⊨ ∀Z · (∃Q · p(Q)) → p(Z) does not hold by giving a suitable structure I am working on this problem but am frankly stumped. I read this as "for All Z such that ...
4
votes
2answers
74 views

Why is $\alpha \rightarrow \forall x(\alpha)$ not generally correct in first-order logic?

Why is $\alpha \rightarrow \forall x(\alpha)$ not generally correct in first-order logic? i.e., when there are free occurrences of $x$ in $\alpha$, and, on the same point, why is the formula scheme ...
1
vote
2answers
12 views

predicate logic truth value

I have a structure of predicate logic given by taking the set of natural numbers, 0,1,2... as the domain of discourse ∃X · ∀Y · X < Y Do you read this as there exists an X such that for all Y X ...
0
votes
3answers
72 views

What is a formal definition of “predicate logic”?

I'm currently trying to get clear about some terms that are often used in computer science (I'm a computer science student), but were never formally introduced. Especially, I would like to know what a ...
2
votes
1answer
44 views

How do I use rules of inferences to imply a conclusion from 4 premises?

I am a little confused on how to use 4 premises to prove a conclusion. Can you please tell me if my logic is sound for the following proof: ...
2
votes
2answers
27 views

Qualification of a Universal Quantification

Let us say I have a predicate, $P(n)$, and I want to say that it holds for every integer greater than $2$ (an example would be $P(n) = 2n>2+n$). Let us furthermore say that the UOD (universe of ...
2
votes
1answer
33 views

Correct Way to Write a Statement in First-Order Logic

I am teaching myself set theory. I am at a point where the set of rationals, $\mathbb{Q}$, has been defined, along with its ordering relation, $<_\mathbb{Q}$. Now, working towards a definition of a ...
0
votes
3answers
42 views

Question about axiomatic scheme of predicate logic

I'm reading a chapter on axiomatic theories for predicate logic, which has three axiomatic schemes. One of them is: $\forall x \varphi \rightarrow [t/x]\varphi$ (in which the term t is free for x in ...
3
votes
4answers
113 views

When do free variables occur? Why allow them? What is the intuition behind them?

In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound. Why would one write such a formula? Why are free variables allowed? What is the intuition for allowing free variables?
0
votes
1answer
34 views

How to express in Propositional Logic

If A(S;C) is the propositional function (predicate) and student S who takes course C receives an A grade and the domain is a set of student belonging to university x. How to express "There are ...