Questions concerning predicate calculus, i.e. the logic of quantifiers.
3
votes
0answers
34 views
Definition(s) for variable binding in first-order logic
The following statement made me realize that variable binding can be defined in first-order logic:
The same holds for λ terms to define functions. There is no reason that they could not be ...
2
votes
2answers
35 views
proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3
I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers:
$$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
3
votes
1answer
85 views
Equivalence of first-order formulas
The following are elementary truths for arbitrary formulas $\phi, \psi$ of first-order logic in which all variables but $x$ are bound:
$\vdash \forall x \phi(x) \wedge \forall x \psi(x) ...
2
votes
2answers
35 views
Translate the following sentences into predicate logic language.
Translate the following sentences into predicate logic language. Use
the following translation key:
a ~ Anne
b ~ Bob
M(x) ~ x is male
G(x,y) ~ x is married to y
C(x,y) ~ ...
0
votes
0answers
13 views
predicate based indexing
Let the set of plain texts to be $E=\Bbb Z_N^n$
The class of predicates to be $F=\{f_\vec v\mid\vec v\in\Bbb Z_N^n\}$
where $f_\vec v (\vec x)=1$
iff $\langle \vec v,\vec x \rangle =0$
where ...
3
votes
3answers
89 views
How to logically analyze the statement: “Nobody in the calculus class is smarter than everybody in the discrete math class.”
I am self-studying Daniel Velleman's "How to Prove It."
In the exercises for section 2.1, for question # 1b, I got a different answer than he did (his answer is in the back of the book).
I think ...
3
votes
1answer
44 views
Elementary existence proof in first order logic
Please forgive my dullness but I just don't know how to - formally - show that
$$\lbrace \forall x\ \phi(x), \exists x\ x = x \rbrace \vdash \exists x\ \phi(x)$$
for an arbitrary formula $\phi(x)$.
...
10
votes
1answer
111 views
Any branch of math can be expressed within set theory, is the reverse true?
Set theory seems to have the property of being "universal", in the sense that any branch of math can be expressed on its language. Is there any other branch of math with this property?
I am asking ...
3
votes
0answers
34 views
Evaluate signatures logic
I need some help of the logic experts. I would like to evaluate the following signatures $\sigma$, such that $|\sigma^{Op}|=2$ and $t$ is a $\sigma$ term. Sometimes there are no solutions and ...
0
votes
1answer
29 views
Show that one cannot prove the following formula by natural deduction
Show that one cannot prove the following formula by natural deduction:
$∃x∀yR0(x,y)→∀x∃yR0(x,y)$
So I have to find a case where I get truth values $1 \rightarrow 0$, right?
1
vote
2answers
38 views
Show that the following inference is not correct
Show that the following inference is not correct:
Suppose every day that is not rainy is not windy, and some day is windy. Then every day is rainy.
$$\forall x (\lnot R(x)\rightarrow \lnot ...
0
votes
1answer
29 views
Show that one cannot infer from the formula ∃xR0(x,c) the formula ∃xR0(c,x)
"Show that one cannot infer from the formula ∃xR0(x,c) the formula ∃xR0(c,x)".
I'm looking for help understanding the difference between the formulas
2
votes
1answer
55 views
Need help/tips for putting formulas in prenex normal form
I have the formula's $\forall x \space P(x) \rightarrow Q(x)$ and $\forall x \space P(x) \rightarrow Q(y)$.
Solving one:
$\forall x \space P(x) \rightarrow Q(y)$
$\neg \forall x \space P(x) \vee ...
3
votes
2answers
71 views
proving two statements are equivalent
Let $X$ be a set, ler $R$ be a binary relation on $X$, let $PX$ be the set of subsets of $X$, then 1) and 2) are equivalent:
1) $\forall a\in X\ \forall A\in PX(\forall f\in X(aRf\rightarrow f\in ...
4
votes
1answer
114 views
Why is quantified propositional logic not part of first-order logic?
If propositional logic is extended by quantifiers ($\forall$ and $\exists$) without adding functions and relations (or even objects and equality, i.e. we quantify over propositional-variables), the ...
10
votes
1answer
185 views
Using $\bigvee$ and $\bigwedge$ instead $\exists$ and $\forall$
My professor of Algebra use some "strange" notation for me. He uses $\bigvee$ instead $\exists$ and $\bigwedge$ instead $\forall$. For example $$\displaystyle\bigwedge_{x\in \mathbb{Z}}\bigwedge_{m\in ...
1
vote
1answer
74 views
First order logic, CNF
What steps do I need to follow to convert the next statements into CNF? Wich are the resulting clauses?
H<->CvD
R->¬D
RandH
H<->C
Thank you.
3
votes
2answers
42 views
Proving that it is not the case that a one-place predicate is not derivable from an infinite set
I'm trying to prove that it's not the case that $\Sigma \vdash \bigwedge_x F_x$, where $\Sigma= \{FA_1, FA_2, FA_3, \ldots , FA_n,\ldots\}$
I started to prove by contradiction. So assume that ...
2
votes
1answer
51 views
Are Horn clauses always universally quantified?
I know that the original publication ' Alfred Horn (1951), "On sentences which are true of direct unions of algebras" ' didn't require universal quantification. However, it didn't call these Horn ...
3
votes
2answers
40 views
Translation of : The disjunction of two contingencies can be a tautology.
The statement is: "The disjunction of two contingencies can be a tautology."
The predicates are:
$C(x)$: "$x$ is a contradiction."
$T(x)$: "$x$ is a tautology."
The book says the answer is
...
7
votes
1answer
56 views
Difference between “There is one” vs “there is at least one”
Is there a difference between the two?
I want to say there isn't, but discrete math sometimes doesn't make a whole lot of sense to me.
Just wanted to verify.
2
votes
2answers
83 views
Help understanding $\exists x \exists y (x\neq y \wedge \forall z ((z=y)\vee (z=x)))$
I'm not sure how to interpret this problem.
Find a domain for the qunatifiers in:
$$\exists{x} \exists{y}(x\neq y \wedge \forall{z}((z=y)\ \lor(z=x))) $$
such that this statement is false.
So, the ...
2
votes
2answers
85 views
Prove for all sequences $\{a_n\}$ and $\{b_n\}$, if $\lim a_n = a$ and $\lim b_n = b$, then $\lim a_n + b_n = a+b$ entirely in first-order logic
I already know how to prove this statement in "English," but I would to see a proof of it entirely in first-order logic. Here is the English proof:
(1) Let $\{a_n\}$ and $\{b_n\}$ be arbitrary ...
0
votes
0answers
31 views
Please test this logical equivalence sequence
I am working hard with predicate logic, but have some problems with the next equivalence:
$$ \left[\exists xP(x) \rightarrow \exists xQ(x) \right]
\leftrightarrow \left[ \forall xP(x) \rightarrow ...
3
votes
1answer
69 views
What does it mean that a set S tautologically implies wff $\tau$
What does it mean that a set $S$ tautologically implies wff $ \tau$ ?
in Enderton introduction to mathematical logic , in page 23 ,
it define that a set $S$ tautologically implies wff $ \tau$ iff ...
1
vote
0answers
30 views
Translation Sentence with Four Predicates
Not sure if I am to continue asking questions in my old question thread or post a new one since I'm new here so please forgive any perceived spamming on my part.
Given the following predicates and ...
2
votes
1answer
135 views
Translating a sentence into symbolic form.
If G(x) = "x is green" and the sentence is "Some animals are green and some are not green."
Then is my symbolic sentence correct? $$\exists x G(x) \land \exists y \lnot G(y)$$
1
vote
1answer
83 views
The truth value of quantified statements
I just took an exam and the following problems were asked:
Determine the truth value of each of these statements if the domain
consists of all real numbers.
$\forall x \forall y \; ...
5
votes
1answer
86 views
First order logic - how to prove a specific part of the completeness theorem?
I am working with the proof system for FOL described in Chang and Keisler. It contains the following axiom schemes:
$\alpha \to (\beta \to \alpha)$
...
1
vote
1answer
75 views
Translating statements into Predicate Logic
I am facing problem in translating these statements to logic statements.
Some horses are gentle only if they have been well trained.
Some horses are gentle if they have been well trained.
I am not ...
2
votes
2answers
88 views
Trivial question about nested quantifiers.
Reading my textbook, I came across exercises for nested quantifiers.
The question: Let $L(x, y)$ be the statement “$x$ loves $y$,” where the domain for both $x$ and $y$ consists of all people in the ...
0
votes
1answer
53 views
what is the difference between formula and the abbrevation of a formula?
there is a problem which is asking me to determine whether a string is a formula or an abbrevation of a formula
but i don't know the diffrence of formula and the abbrevation of a formula
i know ...
1
vote
2answers
93 views
what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$?
what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$ ?
can you give me the definition supported with some simple examples ?
i read the definition in ...
4
votes
2answers
79 views
What are the rules for the use of dots rather than parentheses in logical formulae?
What are the rules of omission of parentheses of formulas in mathematical logic ?
in my text , first order logic mathematical logic by angelo margaris ed 1990 dover , the paretheses is omitted
for ...
3
votes
2answers
86 views
Show that there is a false statement of the form:
Show that there is a false statement of the form:
$$\big(\exists xG(x)\land\exists xH(x)\big)\to\exists x\big(G(x)\land H(x)\big)$$
my question is ,
is the $ x $ in $H(x) $ must be the same $x$ ...
-1
votes
2answers
115 views
On Conditional Connective , how does “ if P then Q ” have the same meaning with “ Q only if P ”?
in all lectures i had watched in mathematical logic , and in my text
they said that
when we say , $P \Rightarrow Q$ , this has the same meaning as , $\text{if $P$ then $Q$}$ , and this has the ...
0
votes
2answers
46 views
How to translate the following to predicate logic language?
(1)- Define the notion: "a real sequence is bounded" in predicate logic language.
(2)- If $f$, $g$ are two bounded real sequences, then so is $f+g$.
The proof is trivial. But the predicate logic ...
0
votes
0answers
82 views
Strong induction implies weak induction
I know how weak induction implies strong induction
ie. proving strong induction with weak induction
Let Q(n) be P(1) ∨ P(2) ∨...∨ P(n)
Base case: Q(1) = P(1) by definition
Inductive step:
Q(k) -> ...
1
vote
1answer
70 views
Equivalence of strong and weak induction
What is a simple way of proving strong induction implies weak induction and vice versa using simple predicate logic and quantifiers?
4
votes
2answers
111 views
Is “reflexive transitive closure of relation $R$” a first-order property?
Suppose I have a language with two binary relation symbols $R$ and $R^\ast$. Suppose I have a first-order theory $T$ which says some things about $R$, but nothing about $R^\ast$. Is there a set of ...
3
votes
1answer
142 views
How to use the Rules of Inference to a statement from two premises
The problem is as follows: Given the premise ∀x(P (x) ∨ Q(x)) and ∀x((¬P (x) ∧ Q(x)) → R(x)) is true, use the rules of inference to show that ∀x(¬R(x) → P(x)) is also true. (The domains of all ...
2
votes
2answers
112 views
Proof of transitivity in Hilbert Style
We can use the following axioms:
$$\begin{align}
&A\to(B\to A)&\tag{A1}\\
&[A\to(B\to C)]\to[(A\to B)\to(A\to C)]&\tag{A2}\\
&(\lnot A\to\lnot B)\to(B\to A)&\tag{A3}
...
4
votes
3answers
108 views
To solve an equation
This might seem as a silly question. The reason why I ask it is basically because I am interested to know the formal and correct way of expressing equations as exercises.
This question arised in a ...
0
votes
1answer
49 views
A consistent Formula Example
I am asked to provide an example of a consistent Formula $\psi(x)$ with one free variable $x$ (meaning that the set {$\psi(x)$} is consistent) but $\forall x\psi(x)$ is not consistent.
I'm at a loss ...
1
vote
1answer
26 views
Axiom of Equivalence For test..
We have the axioms:
$\vdash x = y \to (A\to A')$
where $A'$ is the formula which is created by replacing some of the free apperances of $x$ in $A$ by $y$
$\vdash x=x$ for all $x$
We need to prove ...
1
vote
1answer
63 views
How to verify if a compound logical statement is a tautology using substitution
I have two examples to figure out, and I've verified the first. The second one is giving me trouble, though. Here is the statement:
$[(p \lor q)\to r] \leftrightarrow [\lnot r \to \lnot(p \lor q)]$
...
1
vote
1answer
113 views
How would one prove this in predicate logic
$\forall x \in \mathbb{R}$, $\exists y \in \mathbb{R}$, $(x^2-y < 100)$
how would one go about proving this?
should one use a direct proof or proof by contraposition?
how can one prove this for ...
3
votes
1answer
99 views
Negation of a quantified statement
I would like to negate the following:
$\exists x, \forall y, \forall z ((F(x,y) \land G(x,z)) \rightarrow H(y,z))$
Would the following proposed solution be correct?
(1) First simplify what is in ...
