Tagged Questions
3
votes
1answer
82 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
31 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) ~ ...
3
votes
3answers
84 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)$.
...
9
votes
1answer
108 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
31 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 ...
2
votes
1answer
49 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 ...
3
votes
1answer
105 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 ...
1
vote
1answer
66 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.
2
votes
1answer
49 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 ...
1
vote
2answers
90 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 ...
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 ...
3
votes
1answer
68 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 ...
2
votes
1answer
130 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
79 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
85 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
74 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 ...
4
votes
2answers
77 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 ...
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 ...
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
113 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 ...
3
votes
1answer
140 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 ...
4
votes
2answers
107 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 ...
4
votes
3answers
107 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 ...
2
votes
2answers
106 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}
...
0
votes
1answer
47 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
62 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)]$
...
3
votes
1answer
97 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 ...
