Questions tagged [predicate-logic]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
23 views

Prenex Form for this type?

I'm trying to solve a problem of first order logic considering the Prenex Normal Form. Namely, I have to convert this type in Prenex Form and I can't find a solution. Can you please help me? $$(∀x)A(...
0
votes
1answer
19 views

Some terminology: differences of term, formula, and expression in logic?

In the wikipedia article on logical terms it is written: In analogy to natural language, where a noun phrase refers to an object and a whole sentence refers to a fact, in mathematical logic, a ...
1
vote
0answers
62 views

Goal of the form $\forall x P(x)$ and universal generalization

When we're proving a statement with a goal of the form $\forall x P(x)$, we usually begin our proof by expanding the universal quantifier to the entire formula. Afterwards, we proceed with the common ...
3
votes
1answer
57 views

Predicate Logic: Exists-proof

I've entered my proof on this website and I don't understand why following proof isn't okay. As you can see, the proof checker tells me that I've used the rule for $\exists$ in a wrong way. Is this ...
0
votes
1answer
46 views

Are sets predicates?

In so many different instances we need to be able to construct sets of functions. The first axiom of set theory (at least in the order that I learned) says that $a\in b$ is only a proposition if a and ...
-2
votes
1answer
36 views

For every $x$ and $y$ there exists $z$ such that $x + y = z$ [closed]

How to verify the truth validity of this predicate in the domain of $\mathbb{N}$ and then with $\mathbb{Z}$? I know that it is true, because there always exists such $z$, but how to write it down ...
0
votes
2answers
21 views

Predicate logic: Negation

My book says that the negation of "Everyone likes coffee" is "Not everyone likes coffee". But if i apply that to quantors (c = likes coffee), then... $\neg(\forall x(c(x))) \Longleftrightarrow \...
0
votes
1answer
25 views

First order logic translation from the sentence “Nobody who loves every dog loves any armadillo.”

i'm new to first order logic and i'm having some confusion with translating the sentence above. My solution for the sentence is : ∀x ∀y ∀z ((DOG(y) ∧ LOVES(x, y) ∧ ARMADILLO(z)) → ¬LOVES(x, z)) (1) ...
0
votes
0answers
28 views

RFC: Proposed Axiomatization of Mathematics using Predicate Logic

I have been partially inspired by questions here to attempt to create a good axiomatization for the integers, the real numbers, and the complex numbers. Anyone interested can find the result of my ...
0
votes
0answers
21 views

Is there a language that checks the validity of a proof?

Is there a language/interpreter, that checks the validity of a proof with which you can define a model and use whole predicate logic?
0
votes
1answer
48 views

Quantifiers and empty set

Let $X$ and $Y$ be sets. Suposse that $X=\varnothing$ and $Y\neq \varnothing$. Is $$(\forall x\in X) (\exists y\in Y)\;p(x,y)$$ TRUE?
0
votes
1answer
31 views

Why is this epistemic logic situation valid

So this is epistemic logic and as far as I know this is similar to predicate logic so that is the reason for tagging this this way. So I can see that $p$ is indeed true in worlds $w,s$, but I don't ...
0
votes
1answer
45 views

Can anyone help me in explaining this first order model with the following condition

what is the explanation for not finding the following first order model such that model $N$ with domain $\{i,j,k,l\}$ and, $N ⊨ ∀xB(h(x) ....(1)$ $N ⊨ ∃x¬B(x).... (2) $ while function h in this ...
1
vote
1answer
35 views

Is it “propositional function” or simply “proposition”

I was going through the text "Discrete Mathematics and Its Application" by Kenneth H Rosen (5th Edition) where I came across the use of $P(n)$ in the mathematical induction chapter and felt difficulty ...
1
vote
1answer
53 views

given $o(k), \neg o(n), \neg y(j), \forall x(y(x)\Rightarrow \neg o(x)), \exists x(y(x))$ prove $y(n)$ using Stanford university fitch system

Context: This is related to another question I've recently asked BUT it is a different formulation of the same problem. The orihinal problem is given here. Solving the puzzle is very easy, my goal is ...
2
votes
1answer
81 views

How to translate this statement into a mathematical one(using appropriate quantifiers)?

The statement I'd like to translate into a mathematical one is "Every American has a dream". Let $A$ and $D$ denote the set of all Americans and the set of all dreams, respectively, and $P(a,d)$ ...
2
votes
1answer
55 views

Why is the boolean “OR” operator denoted as “+”?

I learnt boolean algebra as part of a computer hardware course where the focus was very much on using it as a foundation for creating digital logic blocks out of gates, so there was very early on ...
1
vote
1answer
49 views

Confusion regarding $\models \forall x A \equiv \forall y A[y/x]$

I have some confusion regarding the following statement given in Jean H. Gallier's book "Logic for Computer Science". It says, For every formula $A$ $$\models \forall x A \equiv \forall y A[y/x]$$ ...
3
votes
1answer
52 views

Convert a DNF logic expression into a NOR normal form expression.

I want to convert the logic expression $(a +b) \cdot c \cdot \overline{d}$ into a NOR Normalform. I tried to this by first changing the expression into a DNF and then into the NOR Normalform. Here's ...
2
votes
1answer
65 views

Help to understand the validness of relation in a model

In my assignment I have the following question: Find a model $M$ with domain $\{a, b, c, d\}$ so that: $M\vDash R(\overline{a},\overline{b})\land R(\overline{b},\overline{a})\land\neg Q(\overline{...
1
vote
2answers
51 views

How is $(∀x)(Px∧Qx)→(∀x)(Px)$ not a tautology?

I read that using the truth tree method (analytic tableaux) “a statement α is tautological just in case any truth tree for ~α closes". A truth tree for $¬(∀x(Px∧Qx)→∀xPx)$ closes so how this is not ...
1
vote
1answer
35 views

Converse seems to be logically equivalent to conditional?

This is part of a question (PS: the question just asked me to write converse, inverse, contrapositive counterparts. My question is not related to the question itself): Statement: ∀n ∈ Z, if (6 | n),...
2
votes
1answer
59 views

What is the difference between an atom and a term? (logic)

When I read on Wikipedia about atomic formula, it reads that an atomic formula can also be called an atom. As I interpret the text, the atom is something that is evaluated to be true or false such as "...
0
votes
0answers
13 views

First Order Logic: Write a sentence which makes the domain a square number [duplicate]

The language has three unary function symbols f,g and h. The domain is a square if the model is a model of this sentence and the domain is finite.
1
vote
2answers
64 views

Confusion on definition of predicate

I'm currently reading up on Predicates(Logic) and have come to understand that predicates are a finite set of variables that become propositions when the variable(s) are substituted in with ...
1
vote
2answers
62 views

English translation to First Order Logic

I have to create a scenario using FOL and i am having confusions for this particular sentence. Sentence: 9. If someone gets a seat in engineering, he will not get a seat in CS. Which of the ...
0
votes
0answers
25 views

Predicate logic and domain of variables

if x and y share the same domain, let's say non-negative integers and the predicate is: For all of x, there exists a y such that y > x. Is this true? Since the domain of non-negative integers is ...
2
votes
3answers
92 views

Doubt - Negation of “all” [duplicate]

I am a high schooler just reading logic when this doubt popped up Let's take a statement All balls are black. Then the negation should be- Some balls are not black. But why can't it be- All balls are ...
2
votes
1answer
42 views

Universal Quantifier in Intuitionistic Logic

I have a very basic question about $\forall$ in intuitionistic first-order logic (IQL). It is well-known that in intuitionistic propositional logic (IPL), (\ref{dnlem}) and (\ref{dndne}) are both ...
0
votes
0answers
18 views

Show that ${\Delta(\Gamma)}$ is the intersection of all maximal consistent ${\Sigma}$ containing ${\Gamma}$ [duplicate]

In this question, we are dealing with predicate logic, where we have access to the deduction theorem, the soundness theorem, and the completeness theorem. The context of this question is the following:...
1
vote
1answer
61 views

First Order Logic: How to transform to prenex conjunctive normal form and Skolem form?

This is the sentence that needs to be transformed: ∃x∀y(Ax → (Bxy ∨ ¬Cy)) → ∀x∃y(Py → Qyx) I have gotten to the point where I eliminated all occurrences of → and imported all negations inside all ...
0
votes
1answer
38 views

Proof of ⊨∃x(Px⇒∀xPx) (Drinker's Paradox) [duplicate]

⊨∃x(Px⇒∀xPx) I was trying to solve the above drinker's paradox by contradiction and came up with the below expression by negating the above expression - ⊨ ∀x ( Px ∧ ¬ ∀x Px ) This is where I got ...
0
votes
3answers
32 views

What is the negation of the given statement in metric space

Let $(X,d)$ be a metric space and $T:X\to X$ be a mapping. $\bf{P:}$ "There exists a map $\phi:\Bbb R^+ \to \Bbb R$ such that $\displaystyle d(Tx,Ty)\le \phi(d(x,y))$ for all $x,y\in X$." What is ...
0
votes
0answers
23 views

Can these sentences be the same premise?

I have these two sentences: Blonde girls have some dolls Only blonde girls have some dolls and I have reached the same point: ∀x (G(x)∧B(x)→ ∃y (H(x, y)∧D(y)) ) ...
1
vote
1answer
57 views

Given $\forall X\, p(X)$, use the Fitch System to prove $\lnot \exists X\, \lnot p(X)$

I've tried to solve this exercise based on a similar question that was asked some years ago, but I'm stuck in step 5. Any help? Thanks in advance. By the way I'm using Stanford's system. ...
2
votes
1answer
97 views

Given $∃y.∀x.p(x,y)$, use the Fitch system to prove $∀x.∃y.p(x,y)$

Given $\exists y. \forall x. p(x,y)$, use Fitch-style natural deduction system to prove $\forall x.\exists y.p(x,y)$. I know this question has been asked before, but based on that answer I'm not able ...
4
votes
2answers
83 views

Logically, deductively, tautologically, semantically, syntactically valid arguments, what is the difference?

I've read 4 logic books in total but i'm getting crazy with all these xxxally valid argument what is the difference?? What is the difference between Logically, deductively, tautologically, ...
0
votes
1answer
50 views

Given $\exists x.\lnot p(x)$, use the Fitch System to prove $\lnot \forall x.p(x)$ [duplicate]

This is what I've come up with so far, but I'm stuck at step 11: \begin{align} &(1)\quad \exists x.\lnot p(x) & \text{Premise}\\ &(2)\quad \lnot p(x) & \text{Assumption}\\ & (3)\...
2
votes
0answers
47 views

Modal Logic Translation to other Logics

I am doing an introductory work which is basically a survey of the connections modal logic has with other logics. I am following the article developed by Professor Moshe Vardi - Why is Modal Logic so ...
2
votes
3answers
49 views

Translation of $[\forall xP(x) \rightarrow (\forall x) Q(x)] \rightarrow (\forall x) [P(x) \rightarrow Q(x)]$ to English

I am having trouble translating the following statement to English. $$[(\forall x)P(x) \rightarrow (\forall x)Q(x)] \rightarrow (\forall x)[P(x) \rightarrow Q(x)]$$ I am being asked to perform some ...
0
votes
1answer
34 views

Help With Predicate Logic Proof $(\exists x)[R(x) \vee S(x)] \rightarrow (\exists x)R(x) \vee (\exists x)S(x)$

I am having trouble getting started with predicate logic proof. The task is to either prove that the statement is valid, or provide a valid example of where its false. Here's the statement: $(\exists ...
0
votes
0answers
18 views

Definition of 'term t is free for v in $\phi$' in predicate logic [duplicate]

I'm trying to get my head around the expression "term $t$ is free for variable $v$ in formula $\phi$". This is defined in many sources as: (Def 1)"$t$ is free for $v$ in $\phi$ if there is no ...
0
votes
1answer
33 views

How do I interpret this answer?

I have the following predicate exersice: Explain why the two following sentences have different meanings (by a description of a situation in which the sentences have a different truth-value) ...
2
votes
1answer
81 views

Proof of $x = y \leftrightarrow x \in \{y\}$

Considering x and y are variables, to prove $x \in \{y\} \rightarrow x = y$, we have to assume the uniqueness of the element in $\{y\}$, which means $\forall z[z \in \{y\} \rightarrow z = y]$, and ...
0
votes
1answer
36 views

Logic proofs using Tableau method (symmetry of a predicate)

I do not quite understand yet how the proof of a formula works in first order logic. I am currently having the following problem that I assume it is due to lack of comprehension. The problem is as ...
0
votes
1answer
22 views

Substitution of identicals in predicate logic

Given a variable $x$ and a variable $y$, is it correct to state that $P(x)$ is equivalent to $P(y) \land x = y$? That the latter implies the former seems clear to me due to the rule of substitution. ...
1
vote
1answer
45 views

What is the key point or “ nervus probandi” of the proof of Godel-Henkin's Completeness of Predicate Logic? (Attempted outline).

Context in Crossley's book : PC, a predicate calculus consisting in " a denumerable set of individual variables" one predicate : $P(x,y) $ a quantifier : $\exists$ two connectives : $\land$ , $\neg$...
0
votes
1answer
30 views

Decucibility of FOL well formed formulas

Problem The problem is in the attached image. I know how to evaluate the truth table for (Exy $\Rightarrow$ Txy), Exy, Txy. I'm confused by the description of the problem as if p, q, are the same in ...
0
votes
0answers
23 views

Does a definite predicate logic have multiple ways to proof

This is my homework and the problem is to translate below into predicated logic and prove it with different methods: Determine if the following argument is a valid inference.“all the mammals are ...
1
vote
1answer
13 views

translating informal language to predicate logic; existential vs universal quantifier

I am analysing some problems in the Hurley Logic Text book (12th edition) and I confused about a couple of answers he gives. Here are two related statements that he translates differently (taken ...

1
2 3 4 5
63