Stack Exchange Network

Stack Exchange network consists of 174 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.

3
votes
2answers
28 views

First order logic difference bettwen using exists and for all

I am trying to write the following statements in first-order logic. I have been given the functions: DirectorOf(A, B), IsMovie(A), and Equals(A, B): 1) All movies have an director. 2) No movies were ...
1
vote
1answer
14 views

Show that $(\phi(\tau)\to\exists x\phi(x))$ is universally valid where $\tau$ is freely substitutable for $x$

I want to show that $(\phi(\tau)\to\exists x\phi(x))$ is universally valid where $\tau$ is freely substitutable for $x$. I think a relevant theorem is the following: Let $\phi$ be a formula, $x_1$...
3
votes
2answers
59 views

Why does my proof fail to show the logical equivalence of (∀x)(Fx v Gx) ⊢ (∀x)Fx v (∀x)Gx?

Apparently (∀x)(Fx v Gx) is not equivalent to (∀x)Fx v (∀x)Gx, however I seem to be able to prove it syntactically: (∀x)(Fx v Gx) ⊬ (∀x)Fx v (∀x)Gx (1) (∀x)(Fx V Gx)-----premise (2) Fa v Ga----------...
1
vote
1answer
24 views

Formally how does one show that if $\Sigma$ is consistent and $\Sigma \vdash p$ then $\Sigma \cup \{ p\}$?

I think intuitively its obvious. If we have a collection of sentences that never proved $\bot$ and we add a new sentence that proves $p$, there should be no reason that the new set of proposition/...
1
vote
1answer
44 views

Logic: Can the computation of a predicate “leave” the universe of discourse and still be valid?

In other words, does the universe of discourse limit the interpretation of the predicate? So for example, say the universe of discourse is $\mathbb{Z}^+$ (positive integers). Let $P(x)$ be "$\sin(x) ...
-4
votes
1answer
25 views

convert the following English words to predicate logic. [closed]

I have been battling with some questions to convert them to predicate logic form. on the internet, no one knows who you are all rabbits are faster than all tortoise some birds are angry Thanks so ...
1
vote
1answer
30 views

Express $x\geq 0$ in the specified language

I have to express $x\geq 0$ given only the binary operations of addition ($*$) and multiplication ($\circ$) on the reals, and equality. For example, I could say that $x=0$ by writing $\forall y(x\circ ...
0
votes
1answer
47 views

Weakest theory equi-consistent to ZFC

I've recently read that ZF is equi-consistent to ZFC. From what I understand, to establish this we transform a formal proof of a contradiction in ZFC into a formal proof of a contradiction in ZF. We ...
1
vote
1answer
25 views

What are some examples of ∃x (P(x) <-> Q(x)) and (∃xP(x)) <-> (∃xQ(x)) not being logically equivalent to each other

I just can't think of any examples for P(x) and Q(x) where this would work out. I can think of it the other way around, for examples if p(x) was x>5 and q(x) was x<2 , then they can never be ...
-1
votes
0answers
38 views

Help in understanding how to translate the following into predicate logic… [closed]

english to predicate logic translation question I'm having trouble understand how would this be represented in propositional logic. Just from reading the statement I know a and b should be ...
-1
votes
0answers
29 views

help translating english statements into predicate logic [closed]

english translation to predicate logic help I can't wrap my head around as to why when you swap the hypothesis with the conclusion of the implication part of this statement, this wouldn't make sense....
1
vote
1answer
37 views

Unexpected definition of structure in predicate logic

From "Logic for Computer Scientists" by Uwe Schoning: A function symbol of arity 0 will also be called a constant. A structure is a pair $\mathcal{A} = (U_{\mathcal{A}}, I_{\mathcal{A}})$ where $U_{\...
2
votes
1answer
39 views

Is $[[\varphi]]$ a common notation for the set of $x$ satisfying a predicate $\varphi(x)$ in a specified model?

This question is merely about notation. Let $\varphi(x)$ be a predicate, i.e. a formula of first order logic, written in a given language, and having exactly one free variable denoted by $x$. Let ...
0
votes
1answer
26 views

logical equivalence in predicate logic

I was studying discrete mathematics, one of the basic subjects in cs department. In particular, studying the chapter "Logics", I came to have some trouble. While solving problem saying " Let $S(x)$ ...
0
votes
2answers
44 views

Understanding requirement of logic question [closed]

I have a statement like this: if 4x - 3 is even then x is odd. What does providing the predicate for the starting assumption and the predicate for the concluding assumption for a proof by ...
2
votes
1answer
71 views

Impredicativity in first order logic

There have been many debates about impredicative definitions in set theory, trying to judge whether they are good or bad. I'm not sure I understand them, because first-order logic theories can be ...
0
votes
1answer
18 views

Predicates and true statements

Georges (x) means "Georges knows x" Math (x) means "x is a math student" I can only use those symbols : ∧, ∨, ¬, ∀, ∃, →, ↔ 1) Georges knows some student who isn't a Math student 2) The only ...
0
votes
1answer
94 views

Expressing “Every even number is the difference of two primes” in symbols

Consider this conjecture: "Every even number is the difference of two primes." Express this statement in terms of quantifiers, variables, equality/inequality symbols, logical operators, and the ...
0
votes
1answer
25 views

Relation between depth and lenght of a formula in First-Order Logic

I'm currently reading Mathematical Logic by Helmut Schwichtenberg, and he introduces the concepts of length and depth of formulas like this [see page 3] : Definition. The depth $dp(A)$ of a formula $...
1
vote
2answers
48 views

Negating first order logic

I am struggling to understand how to really negate in first order logic. Take the following examples: "Somebody loves everybody" Negating this would be: "It is not the case that somebody loves ...
8
votes
1answer
63 views

Semantic proofs to syntactic proofs

Given a first-order logic theory $T$ and and a formula $F$, suppose I have semantically proved that $T\vdash F$. That is, I have proved that any model $M$ of $T$ satisfies $F$ and I conclude by Gödel'...
0
votes
1answer
35 views

Pull Existential Quantifier to front in a FO formula

Consider a First order (FO) formula $\phi = \exists^*\forall^*\exists^* \psi$ where $\psi$ is quantifier free and function free (No n-ary functions, $n \geq 1$) matrix. I am searching for a formula (...
0
votes
1answer
26 views

Which statements is necessarily true for Models in first-order logic sentence given?

This questin is asked in GATE EXAM. Consider the first-order logic sentence φ≡∃s∃t∃u∀v∀w∀x∀yψ(s,t,u,v,w,x,y) where ψ(s,t,u,v,w,x,y,) is a quantifier-free first-order logic formula using only ...
5
votes
1answer
65 views

Necessity of universal quantifier in predicate calculus

I am reading Kleene's "Introduction to Metamathematics". There in Chapter 7 Section 32 he mentions two interpretations of free variables in predicate calculus. One of them is that "For the generality ...
1
vote
2answers
41 views

Why does it matter when we do a substitution of a free variable that some L-formulas don't preserve validity?

I was following these notes and there was a section where they showed the following formula: $$ \varphi(y) = \exists x (x \ne y)$$ and if one replaces the free variable $y$ with the variable $x$: $$...
1
vote
2answers
39 views

Basic Question about Universal Quantifiers in Predicate Logic

so I'm doing some predicate logic and I've stumbled upon a little confusion. $∀c(R(c) \implies Y(c))$ $\neg Y(z)$ Therefore: $\neg R(z)$ I don't understand how that works. What I ...
1
vote
2answers
47 views

How does one show that an intersection of set of propositions is provable iff each proposition is individually provable?

I was going through these notes and wanted to prove the following: if $\Sigma \vdash \varphi_i, i \in [n] \iff \Sigma \vdash \varphi_1 \land \dots \land \varphi_n$ (without completeness of ...
1
vote
1answer
32 views

How does one show that every L-tautology $\varphi$ is provable $\vdash \varphi$?

I was following these notes and I tried doing exercise (5) on page 42: If $\varphi$ is an L-tautology, then $\vdash \varphi$ (without thm 2.7.4, completeness of predicate logic) intuitively it ...
0
votes
0answers
18 views

Predicate Logic Negating a WFF, do signs cancel?

I'm working through an example for my course and I'm wondering if signs need to be canceled for this negation to be correct. The original question is as follows -- (∀x)P(x) Λ Q(x)(R(x)-->W(x)) I ...
-1
votes
0answers
18 views

Sentence to Predicate logic

Rewrite the following arguments using quantifiers,variables,and Predicate symbols. i) Not all birds can fly. ii) There is a student who likes MFCS but not Applied Mechanics.
0
votes
1answer
24 views

How does one prove that evaluating an L-term returns the recursive evaluation of all L-terms?

I was trying to do exercise 1 on page 30 from some logic notes. The question was to show: $$ {t^*}^{\mathcal A}(a_1,\dots,a_n) = t^{\mathcal A}(\tau_1^{\mathcal A}(a_1,\dots,a_n),\dots,\tau_m^{\...
1
vote
0answers
59 views

Contradiction in defining a new symbol, where's the error?

The theorem states the following: Let $T$ be a theory, $F(x_1,...,x_n,w)$ be a formula containing only $x_1,...,x_n,w$ free, $f(x_1,...,x_n)$ be a new function symbol that is not in both $T$ and $P(.....
0
votes
0answers
10 views

are there any tips or general tips to translate human language to predicate logic and vice versa?

The only tips I've seen are about the general stuffs about the predicate logic in general : http://legacy.earlham.edu/~peters/courses/log/transtip.htm by Peter Suber from Irving Copi's book Are ...
4
votes
1answer
54 views

How does one get all substructures of the Integers?

Consider the L-structure: $$ \mathcal Z = (\mathbb Z; 0,-,+)$$ I wanted to find all substructures (because I was trying to find out if it was possible to have an algorithm for finding all ...
0
votes
1answer
15 views

predicate logic - translating from human language

"Everyone in the world love themselves" "Someone loves their own self" x, y are everyone in the world 1) ∀x∃y(love(x, y) /\ (x=y)) 2)∃x∃y(love(x, y) /\ (x=y)) I'm thinking along the lines of "...
2
votes
1answer
41 views

What is “the quantifier axioms of L” and why are they true in all L-structures?

I was going through these notes for logic. They started describing the axioms for predicate logic and said the following: The quantifer axioms of L are the formulas $\varphi(t/y) \to \exists y \...
3
votes
1answer
37 views

Contraposition and contradiction

I have some questions about mathematical logic. 1) About reasoning by contraposition : If we have two predicates $P(x)$ and $Q(x)$ on a set $A$, do we have the following equivalence between the ...
-1
votes
0answers
43 views

How to prove these two problem?

How to prove these two problems? $\exists_x(p(x)→q(x)) \vdash \exists_xp(x)→\exists_xq(x)$ $\exists_xp(x)→\exists_xq(x) \vdash \exists_x(p(x)→q(x))$
-1
votes
0answers
14 views

Prove two predicate quantifiers are logically equivalent

In a class in Discrete Mathematics I am for the first time introduced to predicate logic. A question in a homework assignment asks me to determine whether or not the following predicates are logically ...
-2
votes
0answers
15 views

predicate logic translations

1) "every student at Class A have visited at least one room in every building in their campus" 2) "the absolute value of the result from the addition of two integers is same to the the absolute ...
3
votes
2answers
82 views

Induction where statement has different cases

Suppose that I have a statement of the form: $$ P(m,n) = \begin{cases} P_1(m,n) , \ m \leq n \\ P_2(m,n), \ m \geq n \end{cases}$$ I want to show that $P(m,n)$ is true for all $n,m$ by taking an ...
2
votes
2answers
32 views

logic - how to translate this into predicate logic?

"the result of additon between two negative integers are negative integers too" i'm thinking of: x,y,z as negative integers ∀x∀y∃z(x+y=z) thanks in advance
0
votes
2answers
50 views

The logical equivalence of two predicates

Determine whether the predicate $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$ is logically equivalent to the predicate $\forall x P(x) \leftrightarrow \forall x Q(x)$. I would be willing to wager ...
3
votes
2answers
36 views

Predicate Is Before The Subject Is This The Correct Translation?

I'm trying to figure out what the proper translation in predicate logic would be for the example below, I'm confused because the predicate comes before the subject. So i'm wondering if I need to ...
2
votes
2answers
125 views

“Except” in predicate logic

I have a phrase that I am trying to translate into predicate logic. The phrase is as follows: All lions except old ones roar So far I have written down that: $∀x((L(x) \land \lnot O(x)) \to R(x))$...
0
votes
1answer
25 views

Hoare Logic: Consequence Rule

I can substitute $R$ in the first tuple which gives me $x$ $>$ $2$, but I don't know what $S$ is. What is $S$ in this case and how do you arrive at $x$ $>$ $2$ $\rightarrow$ $x$ $>$ $0$?
0
votes
1answer
11 views

Convert to predicate logic: the relation $R$ on the set $X$ is antisymmetric

How would I cast the following to logical symbols The relation $R$ on the set $X$ is antisymmetric.
0
votes
1answer
27 views

Converting a sentence to Predicate Logic

Need help translating this sentence to predicate logic. If a student brings a candy bar for him or herself, then that student brings a candy bar for everyone. Use $C(w)$ as the one-place predicate "$...
0
votes
1answer
19 views

Parsing a sentence using logical operators (Logical expressions)

Parse the logical structure "If everyone passes the quiz, Mr. Johnson will play his guitar." -Use q as a constant to represent the quiz -Use g as a constant to represent Mr. Johnson's guitar -Use ...
-1
votes
2answers
26 views

How should I use notation when subjects for predicates have identical first letters?

First example. "Lina is a student", "Li is a student". Please notice that "Li" is a substring of "Lina". Second example. "Vladimir is a student", "Vladislav is a student", here they partially match, ...