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
1answer
14 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\}$
0
votes
1answer
24 views

How would you notate that something is not in the domain of discourse?

For example, saying that something is specifically not in the domain of integers (not sure how to write the 'N' symbol).
0
votes
0answers
17 views

Converting to Prenex Normal Form.

I need convert $ \forall x \forall y(P(x,y) \sim Q(x,y)) \vee \exists x \exists y(P(x,y) \sim Q(y))$ into Prenex Normal Form. Can I use this formula: $(\exists x\phi )\lor \psi $ is equivalent ...
-1
votes
4answers
74 views

Why $\forall$ is not a predicate [closed]

There is a reason why existence can not be a predicate, namely: Let's prove that unicorns exist. It is sufficient to prove that there is an existing unicorn. There are two possibilities: either an ...
-2
votes
0answers
20 views

prove syllogism is valid

I have a question where I have this syllogism in a set-theory notation: x ∈ p x ∈ h - - - - p ∩ h ≠ θ I translated it into predicate notation ...
1
vote
1answer
29 views

In FOL, can we define equality for two predicate symbols?

In FOL, I think equality is always used for two variable or constant symbols. Can we define equality for two predicate symbols? If not, why? (Do we need higher order logic to use such a concept?)
0
votes
0answers
26 views

Predicate logic proof (some a are b, some a are c, therefore there exists some c)

For the syllogism: Some A are B Some A are C ------------ There exists C Something like: My cake is pink, My cake is round, there exist things that are round We ...
0
votes
3answers
56 views

Name of the basic property of equalities that if a=b then f(a)=f(b).

A basic, fundamental property of equalities is that, if one applies a function on both sides of an equality, the equality still holds. Formally: for any two objects $a$ and $b$ of type $T$ and a ...
0
votes
1answer
23 views

Nonintuitve logical equivalence in the predicate calculus

In the first order predicate calculus as usually constructed the formula $ ((\forall x Ax) \implies B ) $ is logically equivalent to $( \exists x(Ax \implies B))$. It is not clear to me why these ...
0
votes
0answers
24 views

tricky theoretical question about input resolution(logic)

i happen to have a theoretical question about input resolution in logic. so in input resolution we can use the resolution rule/theorem if at least one out of two clauses in the resolution are from ...
2
votes
0answers
50 views

First Order Predicate Logic with only one operator?

It's fairly well known that Propositional Logic can be expressed with only one operator -- either the Sheffer Stroke (aka NAND, a dyadic operator written infix as $\vert$); or Peirce's Arrow (aka NOR, ...
0
votes
1answer
30 views

Prove the following by deduction rules for qualifiers and implication

I am having trouble with the following proof. First, some basic definitions: Def. Given two statements $\alpha$ and $\beta$, the statement \begin{equation}\alpha \implies \beta ,\end{equation} read ...
1
vote
1answer
36 views

Prove the following for a general binary operation

I need some help with the following proof, please. First, a definition below: A binary operation $p$ on a set $X$ is a function of two variables, whose values lie in $X$: it assigns to each ordered ...
0
votes
1answer
311 views

Proofs with predicates and syllogism

Need some help with this question. Prove that the following syllogism is valid by following the steps below. ...
0
votes
1answer
18 views

Help with Relational Predication Logic

Translate into predicate form. (Relational predication is required.) Every animal lives somewhere. Mars lives nowhere. So, Mars is not animal. [A = “is a animal”, L = “lives”, P = “is a place”, M = ...
2
votes
3answers
91 views

Are there paradoxical/ counter-intuitive laws in predicate logic? ( beyond the Drinker Paradox)

Preliminary remarks. (1) The term "paradoxical" is not used in a negative sense here. What is " para-doxical" is literally what disagrees with the general and uninformed " opinion": it could be argued ...
-1
votes
1answer
63 views

Proving Proposition with Predicate Logic

If we have the proposition \begin{align} &\text{Bob is a Babylonian}\\ &\text{Bob is a Human}\\ &\text{Therefore, some Humans are Babylonians} \end{align} which translates to \begin{...
0
votes
1answer
49 views

How to state sentences for KB ∧ ¬ α given existing KB?

How do I state the sentences for KB ∧ ¬ α when I already have KB. KB: ∀xTourist(x) => Person(x): Every tourist is a person. ∀xTourist(x) ∧ visits(x, Malaysia) => walksCanopy(x): Every tourist who ...
0
votes
0answers
13 views

What is an algorithm to determine when two sentences in predicate logic are equivalent?

Are there references for algorithms which can determine whether or not two sentences in predicate logic are equivalent? For instance, if we have some domain $D$ and predicates $P,Q$ defined on $D$, ...
-1
votes
1answer
34 views

Predicates and mathematical objects

I'm reflecting about mathematical objects as numbers, sets/classes, graphs and so on. Any class correspond to a predicate in one variable and any graph correspond to a predicate in two variables. ...
4
votes
1answer
99 views

Conversion from Propositional Logic to Predicate Logic

I came across a proposition which I'm having a hard time converting into predicate logic. It has been a long while since I have touched the topic. The proposition reads \begin{align} &\text{...
0
votes
0answers
19 views

Question involving the truth value of two logic statements

Context: Previous multiple choice question from uni exam Statement 1: There exists a real number $x$ such that for all real numbers $y$, the sum of $x$ and $y$ is greater than or equal to $1$. ...
2
votes
1answer
46 views

Does (∀x(r → p)) ∧ (∀x(p → q)) imply ∀x(r → q)?

So the frustrating thing is that I am asked to decide whether the first implies the second, but I was given no deduction rules for predicate logic except the fact that $ ∀x(r(x) → p(x)) $ implies $ ∀x(...
1
vote
1answer
33 views

Is there a non-empty domain such that its constant terms satisfy a conclusion?

The actual full question: If there are free variables in the premises of a natural deduction that doesn't lead to contradiction, then is there a non-empty domain such that its constant terms satisfy ...
0
votes
0answers
40 views

Is there some way to transform statements in predicate logic/ first order logic to an expression in the integers mod2 and evaluate?

As the title says, I want to turn a statement such as (P AND(P->Q)) - >Q into a multivariable polynomial in the field Z/2Z and evaluate using the rules of modular arithmetic to get (hopefully) 1, ...
2
votes
1answer
53 views

Show $\neg(\forall x\phi)\vdash \exists x(\neg \phi)$ using an ND-derivation

I'm trying to show that $\neg(\forall x\phi)\vdash \exists x(\neg \phi)$ through a natural deduction (ND) derivation. I'm kind of stuck, because I don't see how I can find some $t$ such that we have $...
0
votes
1answer
26 views

Gentzen Natural Deduction Quantifier Problem!

I am having a problem with $$\exists x \ T(x),\quad \forall x \ (T(x) \to P(x)) \quad \text{leads to} \quad \exists y\ (T(y) \land P(y))... \tag 1$$ It is using $$\forall \text{intro,elim} \ \...
2
votes
1answer
45 views

Proof of satisfaction given the same free variable interpretation

I am reading Enderton's A Mathematical Introduction to Logic (here a link to its second edition) and I am not sure I understand this proof, could anyone help please? What I don't understand is what ...
-1
votes
0answers
18 views

Relational predication translation help

Translate into predicate form. (Relational predication is required.) [P = “eat penguin”] Neither Bob nor Mary like to eat penguin. ∼P_b & ∼P_m Translate into predicate form. (Relational ...
0
votes
1answer
22 views

Help with predicate logic translation

Translate into predicate form. No one hates Bob. [H = “is hate”] ∼∃x∀y H_b Translate into predicate form. Dogs are not reptiles. [D = “is a dog”, R = “is a reptile”] ∀x(Dx⟶ ∼Rx) Translate into ...
3
votes
1answer
32 views

$\Gamma\subseteq \text{Sent}(\mathcal{L})$ is maximal consistent iff it has models, and any two models are elementarily equivalent.

This note comes in my lecture notes after the Löwenheim-Skolem Theorem and a remark on the equivalence of "$\Gamma \subseteq \text{Sent}(\mathcal{L})$ is strongly maximal consistent (i.e. for any $\...
2
votes
1answer
39 views

First order logic: Difference between sentences

My task is to translate the following 2 sentences to first-order logic. I can't figure if my proposed solution is also correct even though it doesn't match the professor's solution. $1$. No student ...
1
vote
1answer
40 views

Not sure when to use Distributive Law in specific Proofs question.

I'm currently using "How to Prove It" by Velleman, and I'm stuck on Chapter 2.2 question 6. I found the solution online on how to do it, but I don't understand it. Here's the question: ...
0
votes
0answers
21 views

Solving a certain universal claim in natural deduction for predicate logic. [duplicate]

I am having a lot of trouble coming up with a solution for the following predicate Logic Natural Deduction question: $$⊢P(a) → ∀x(P(x) ∨ ¬(x = a))$$ I have spent almost all day working on it and ...
1
vote
3answers
79 views

Show $\vdash P(a) \to \forall x(P(x) \lor \lnot(x=a))$ using natural deduction

Can somebody help me with this question? The question is to show $$\vdash P(a) \to \forall x(P(x) \lor \lnot(x=a))$$ using natural deduction. Here is my attempt: I think I am going half-way ...
0
votes
2answers
35 views

How Would We Translate this Sentence Into Logic?

I am trying to do a proof by resolution but I don't think I have the correct translation into logic for one of the sentences given. Sentence: There is a SUV that is bigger than every car. My current ...
1
vote
3answers
41 views

Ordering and comma use in predicate logic

Use of commas and ordering in notations of logic confuse the hell out of me especially when variables of different sets are concerned. What I'm trying to formalize is that $G\left(a,b,r\right)=-G\...
2
votes
1answer
38 views

Deciding if Valid FOL Sentence

I am doing a HW assignment for First Order Logic with english sentences and this is one of the questions. Not exactly sure of how to approach it and to answer it. Q1. [10] Decide each sentence is ...
2
votes
1answer
30 views

MGU - most general unifier for skolem functions?

I have trouble understanding MGU for functions, especially skolem functions. Is it correct that in order to find MGU for 2 functions, say f(x) and g(y) then they ...
0
votes
0answers
32 views

Express the following requirements with First Order Logic, and define terminology (predicates and functions to be used) in tables;

a) The elevator system shall accept passenger requests and provide feedback. b) The elevator system shall support all relevant fire and safety codes in effect. c) The elevator system shall have ...
3
votes
1answer
50 views

Is there a way to syntactically characterize homomorphic images and products?

Birkhoff's HSP theorem states that if a class of algebras (for a given type) is closed under products, subalgebras and homomorphic images ($\iff$ quotient), then it is actually defined by some ...
0
votes
1answer
36 views

First Order Logic Peano arithmetic Proof

I'm trying to prove: $\forall x\forall y((x=y)\longrightarrow(x\not<y)$ I tried starting off with $u=v, u+s(z) = v\vdash u = v$ $u=v, u+s(z) = v\vdash u+s(z) = v$ . . . $u=v, u+s(z) = v\vdash ...
0
votes
2answers
58 views

What is the proper way to read predicate logic?

Basically, in predicate logic, do we read from the inside outwards? In the example question, would 1a) be read as "For all values of y, there exists a value of x which divides y"? I've been told ...
0
votes
1answer
44 views

Is $A \Rightarrow \forall x(A(x))$ provable in classical predicate calculus?

My question is whether $A \Rightarrow \forall x(A(x))$ is provable in the classical predicate calculus. My intuition would say yes because using finite domain truth tables one can check (I hope I am ...
6
votes
2answers
252 views

Why is quantifier elimination desirable for a given theory?

We say that a given theory $T$ admits QE in a language $\mathcal{L}$ if for every $\mathcal{L}$-formula, there is an equivalent quantifier free $\mathcal{L}$-formula. That is for every $\mathcal{L}$-...
0
votes
0answers
32 views

About conservative extensions of first order theories?

Let $T_1$ be an effectively axiomatized first order theory whose language have only finitely many primitive symbols. Now let $L^{T_1}$ be the set of all formulas of the language of $T_1$. Let $L^{...
0
votes
0answers
14 views

Hoare triple: Loop invariant and correctness

The following Hoare triple in which variable a is an array of integers, and len, max, i, n, j and m are integer-valued variables. Provide a loop invariant (using predicate logic) suitable for proving ...
2
votes
1answer
31 views

Understanding interpretation of a predicate

This exercise is confusing me. Let $S(x,y,z):= $ $z$ is the child of $x$ and $y$, where $x$ is the mother and $y$ is the father. Express the following sentence in predicate logic using the predicate $...
0
votes
1answer
43 views

Show that Γ has an infinite model. [duplicate]

Suppose that Γ is a set of sentences with arbitrarily large finite models (that is, for every natural number n, there is some interpretation whose domain has more than n members such that every member ...
2
votes
0answers
38 views

Hoare triple: Loop invariant and partial correctness

Below there is Hoare triple in which variable a is an Array of integers, len, x, i are integer-valued variables, and r is a Boolean-valued variable. I have to provide a loop invariant (using predicate ...