Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [predicate-logic]

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

0
votes
0answers
8 views

Creating a predicate checking if a string is a subsequence of another string

I've been trying to come up with a predicate that takes in two strings and checks whether the first string is a subsequence of the second string. Subsequence(a, b): predicate to check is 'a' is a ...
0
votes
0answers
30 views

Is there an error in this proof the the “strong induction” theorem?

The following is from BBFSK Vol I, page 101. $$a<b+1\iff a\le b.\tag{1}$$ From the principle of induction we can now derive the following modified principle of induction: If the number $m$ is ...
0
votes
1answer
27 views

How to transform a sequent notation to rule form?

I can write this proposition in sequent notation: $$(P\rightarrow Q)\rightarrow (\neg P \lor Q)$$ as this one in rule form (see here): $$\frac{(P\rightarrow Q)}{(\neg P \lor Q)}$$ But how can I ...
0
votes
0answers
31 views

Logic of predicates over predicates?

Is there logic, that allow to form predicates over predicates (or even formulas), I.e. derive is-interesting-statment(is(I, liar)). Of course, the model operators in the modal logic can take ...
0
votes
0answers
16 views

How can one prove that the domains of Kripke models are constant by making use of the constant domain axiom in predicate intuitionistic logic?

I am currently looking into Kripke completeness results for intuitionistic and intermediate logics. It is claimed that the constant domain axiom $\forall x (A(x) \lor B) \rightarrow (\forall x A(x) \...
1
vote
2answers
35 views

Usage of (x, 1) (1) in natural deduction

When neither one of premises and conclusion includes a number like "1", like the following, I could at least proceed to some extent (although I don't know how to connect Q(y) of the first premise and ...
0
votes
2answers
41 views

If the language has only one predicate, can we simplify the quantifiers?

Assume that our language has only one predicate symbol. Then $(\forall x_1 \forall x_2 )(\phi)$ is equivalent to $(\forall x)(\phi')$ where $\phi'$ is a formula obtained by replacing all occurrences ...
0
votes
0answers
30 views

Rewriting statements in full detail with logical operators, but without quantifiers

I've been given the following question: Let P and Q be predicates on the set S, where S has two elements, say S={a, b}. Then the statement $\forall xP(x)$ can also be written in full detail as $P(a) \...
0
votes
1answer
37 views

How to translate the following predicates with quantifiers into English?

Q(x, z) = "x has z followers on Twitter" Universe of discourse for x, y = all students Universe of discourse for z = non-negative integers How would I properly write the following in English? $$\...
1
vote
1answer
29 views

Logical statements with multiple quantifiers - discrete math

So I have some questions below that I don't understand because I'm struggling with solving questions that involve multiple quantifiers. I was wondering if someone could walk me through how to do these?...
2
votes
2answers
76 views

When are we allowed to use the $\exists$ elimination rule in first-order natural deduction?

I don't really understand when we're allowed to use $\exists$-elimination when making first-order natural deduction proofs. I understand that the criteria are that the variable must be free in the ...
2
votes
1answer
33 views

Discrete math: Inverse, converse, contrapositive - simplifying expressions

State the inverse, converse, and contrapositive of the following implication expression as English sentences. Ensure that you list the symbols you will use for each ATOMIC predicate. You must also ...
-1
votes
0answers
18 views

Translation of sentences into logical predicate [closed]

I want to get translate some sentences into predicate logic [Logic in Computer Science: Modelling and reasoning about systems] The sentences are as follows: Credentials MUST NOT be forced by the ...
0
votes
0answers
39 views

Stuck in this Proof of the Completeness Theorem for Predicate Logic

I'm studying a proof of the completeness theorem for predicate logic shown in this lecture and I'm caught in an obstacle. It proceeds by showing that if a theory is consistent, then it has a model, ...
0
votes
0answers
18 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
3
votes
1answer
44 views

$\forall x (P(x) \wedge \neg Q(x)) \equiv \forall x P(x) \wedge \neg \exists x Q(x)$

I'm supposed to determine whether or not these equivalences are valid for all predicates P and Q. I've written my assumptions but I've never done anything like this so it almost seems too simple and I ...
1
vote
0answers
46 views

First Order Logic Soundness Equivalent in Enderton An Introduction to Mathematical Logic 2001, p134.

Enderton 2001, An Introduction to Mathematical Logic, states on page 134 : Corollary 25E : If $\Gamma$ is satisfiable then $\Gamma$ is consistent and then comments "This corollary is actually ...
0
votes
1answer
20 views

Predicate logic deciding whether atomic formulae hold in interpretations

Consider the formula $\varphi $ of First-order logic defined as $\forall x\forall y((B(x,y) \land B(y,x)) \rightarrow (A(x)\land C(y)))$ State whether it holds in the following interpretations: ...
0
votes
1answer
30 views

Discrete math - negate proposition using the quantifier negation

I'm asked to negate the following proposition using the quantifier negation rules. No negation operations are to appear before any of the quantifiers in the expression that is created. The issue is I'...
2
votes
1answer
19 views

Discrete math predicate logic - which of my answers are correct?

Let $F(x)$ be the predicate “x is a frog”, $T(x)$ be “x has a long tongue”, and $J(x)$ be the predicate “x likes to jump”. The universe of discourse is all animals. I'm asked to write: Every frog ...
1
vote
1answer
23 views

Proving the axioms of $HFOL$ are semantic tautologies for $FOL$

We wish to construct an axiomatic system similar to $HPC$ i.e. Hilbert System for Propositional Calculus, for first order languages, denoted as $HFOL$. We wish to prove the following axioms of $HFOL$...
1
vote
2answers
32 views

Fitch natural deduction proof of $\forall x (P(x) \to Q(x)) \to (\forall x (P(x)) \to \forall x (Q(x))$

My logic exam is coming up and I'm pretty happy with my natural deductions, but I found this 'gem' in an old exam paper and for the life of me I cannot figure it out. You need to prove $$ \forall x (...
1
vote
1answer
57 views

Syntactical proof of universal instantiation rule

First: I am not mathematician but philosopher. I understand why the universal instantiation rule is working. $\frac{\vdash\forall xA}{\vdash A^x_t}$ But is there actually a serious proof in a ...
0
votes
1answer
38 views

Is there a definition for free and bound variables in logic?

That makes me crazy to think about it because my book and other pages on the web talks about free and bound variables without any definition. I think everything in mathematics has a definition so ...
0
votes
1answer
38 views

How can I deny the formula $(\exists x)(p(x)\vee(\forall y)h(y)) \leftrightarrow q $

Can anyone explain me how can I deny this propositional formula? $$(\exists x)(p(x)\vee(\forall y)h(y)) \;\leftrightarrow\; q $$ According to my textbook, the answer would be: $$(\forall x)(\sim p(x)...
0
votes
0answers
12 views

Computability: Primitive Recursive Predicate Existence iff computation is defined

If T is a primitive recursive predicate. How do I prove that if comp(p,x) is defined ⇔ ∃y. T(p,x,y) I thought of a function with x as input for each q,y, if the T(q,y,x) holds then it is defined, ...
0
votes
2answers
28 views

What is a k-ary relation?

Im reading the book Theory of Computation by Michael Sipser and I came across this part that's giving me some trouble. "A property whose domain is a set of k-tuples A × · · · × A is called a relation,...
0
votes
1answer
23 views

How to use of the constant “ False” in a predicate logic implication appearing in a proof of : X included in EmptySet <=> X is empty

While trying to prove the basic fact that : any set included in the EmptySet is empty, I was led to use the propositional constant " false" in a conditional quantified statement. Is the following ...
0
votes
1answer
35 views

Why do we have to rename variables to get the Skolem normal form?

I am trying to derive the Skolem normal form of $∀x[P(x) \land ∀y ∃x( \neg (Q(x,y)) → ∀zR(a,x,y))]$ $\rightsquigarrow ∀x[P(x) \land ∀y ∃x( Q(x,y) \lor ∀zR(a,x,y) )]$ And when it was solved in the ...
2
votes
1answer
27 views

Is a statement with a quantified function variable considered to be of second-order logic?

Here $\mathbb{N}=\left\{n\in\mathbb{Z}:0<n\right\},$ function parameter lists are delimited as $\left[\dots\right],$ and $\underline{\exists}$ means there exists exactly one. One way to state ...
2
votes
1answer
33 views

What property is captured by this third statement defining a structure?

I am currently reading a book, Tame Topology and O-minimal Structures by van den Dries. He defines a structure on a nonempty set $R$ to be a sequence $\mathcal{S}=(\mathcal{S}_m)_{m\in\mathbb{N}}$ ...
1
vote
1answer
25 views

Nested Quantifiers: Domain of subjects shared?

I have been trying to find some similar questions but couldn't find one. My question is the following predicate: $\forall$x$\forall$yP(x,y). Suppose P(x, y):x has written an email to y, my question ...
0
votes
0answers
6 views

Is it possible to show that this set of L-sentences in the structure $(\omega, +, \cdot, S, <, 0)$ is decidable?

Suppose that $\Sigma$ is a consistent set of L-sentences such that there is an L-formula $\phi$ such that for all L-sentences $\psi$, $\Sigma \vdash \psi \iff \phi(\ulcorner\psi\urcorner)$. Is it ...
0
votes
3answers
44 views

Use of “any” in predicate logic?

How would you translate these two sentences into predicate logic? "X does not know anything" vs. "x does not know everything?" Both sentences seem quite similar. Hence the confusion.
0
votes
1answer
31 views

Predicate logic & quantifiers question to write in symbolic form

I'm practising for my math finals... Question: Using D(x, y) to mean "x uses y". Write the following sentence in symbolic form. Make sure to specify the domain of all variables used. Let c = {...
0
votes
2answers
96 views

how can i know if a student was in the campus? edit: using first order logic(logic)

i don't understand this at all. how can i deduct if a student was at the campus? EDIT: i tried to convert all of the following into a first order logic in a closed domain (and some closed world ...
0
votes
2answers
45 views

The expression “otherwise” in predicate logic

I'm currently working on the following problems, and wondering how I can express "otherwise" in predicate logic in a sentence like (d) below. ...
0
votes
1answer
30 views
3
votes
1answer
136 views

Simplest axiom that entails the existence of an infinite set

Let $\phi$ be a formula in first-order logic without equality and with the binary relation $\in$. Let the size $s(\phi)$ of a formula $\phi$ be given by the following inductive definition on the ...
1
vote
2answers
93 views

Is it true that the statement: “ $\frac{1}{0}$=5 is false statement ” is unprovable statement?

I had a conversation on this site about some question, and a claim had been made by one of the users on this site that the truth value of this statement(" $\frac{1}{0}$=5 is false statement " ) is ...
-1
votes
1answer
56 views

First-order logic sentences that consist of 2 clauses

When predicates are given as the following, ...
-1
votes
1answer
43 views

Doubt on mathematical Logic

Consider the following first order logic statement $I)\forall x\forall yP\left ( x,y \right )$ $II)\forall x\exists yP\left ( x,y \right )$ $III)\exists x\exists yP\left ( x,y \right )$ $III)\...
0
votes
2answers
54 views

Bracketing and multiple negated quantifiers in predicate logic

Do bracketing and placement affect quantifiers in predicate logic? I.e., are the following two propositions equivalent (where x and y are variables and P and T predicates) ¬∃x (¬∃y Pxy → (∀z ¬(Pzx → ...
0
votes
1answer
53 views

Understanding of “Somewhat Surprising” First Order Logic Expression in E.J.Lemmon, Beginning Logic

In "Beginning Logic" by E.J.Lemmon, Page 126, Theorem 118 (1994 Reprint) a "somewhat surprising" inter-derivability result in Predicate Calculus is proved: $$( (\exists x\, Hx) \implies P) \dashv \...
2
votes
1answer
22 views

First-order logic task with limited clauses

I have the following axioms The sum of a natural number x and 0 is equal to x. The sum of a natural number x and the successor of a natural number y is equal to the successor of the sum of x and y. ...
0
votes
1answer
19 views

Help to prove this formula (Sequent calculus for predicate logic)

I have a formula: $$¬(\exists x)ϕ(x) ⇒ (∀x)¬ϕ(x) $$ to prove. If the "$(∃x)ϕ(x)$" was in brackets like this $¬((∃x)ϕ(x))$, I could easily prove this formula, but without it I'm stucked. Can you ...
2
votes
3answers
55 views

Logic: “the cubic root of a rational number is also a rational number”

I was attempting an online logical and mathematical statements self-test from the University of Toronto and came across the following statement in question 1: The cubic root of a rational number is ...
1
vote
1answer
64 views

What are the features that make this proof constructive?

Below is an inductive proof of an integer square root theorem from a previous posting. $\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x < (y+1)^2))$ The proof was done using ...
3
votes
1answer
48 views

Notation: $P(x)$ iff $x$ has property $P$

In set theory (for example), people write $P(x)$ to indicate that $x$ has property $P$. What is the meaning of this "expression" formally? Is $P$ a predicate (a Boolean-valued function on some set [...
0
votes
1answer
16 views

Need help with relation properties using logical operators

I was wondering how should I proceed to determine what will be in the relation and what will not given these properties. Operating with integers: $R: \{(a, b)|(a= 0∧b= 0)∨ GCD(a, b) = 5\}$