Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

Give a useful written negation of the statement

I am struggling a bit with giving the useful negation and the written statement: For (b) below: (i) Assign a universal set to each variable, label each component statement with a symbol; (ii) write ...
2
votes
1answer
20 views

Show that: $\sum \models p_1 \lor p_2 \lor … \lor p_n$ for some $n\in \mathbb{N}$

The question states: Suppose that, for each $i \in \mathbb{N}$, $p_i$ is a propositional variable. Let $\sum$ be a set of sentences of the propositional calculus . Suppose that all truth assignments ...
0
votes
1answer
24 views

The relation between equivalence and tautology [on hold]

Is the formula $p \leftrightarrow q$ a tautology? Thanks for any insight.
-1
votes
2answers
80 views

What is a mathematical statement? [on hold]

What is a mathematical statement? And what makes a mathematical statement different from another mathematical statement? For example, is "$2^3=7$" a different statement than "$2\times(2\times2)=7$"?
2
votes
1answer
25 views

Show that are logically equivalent

Show that are logically equivalent (without truth table) (p → r) ∧ (q → r) and (p ∨ q) → r My solution: ...
0
votes
2answers
20 views

How to transform the following logical expression into English

I don't fully understand the semantics of changing logical expressions into English Transform the following predicate calculus statements into English. Let $A(x)$ represent the statement that $x$ is ...
1
vote
2answers
29 views

Determine whether {¬q∧(p→q)}→¬p is tautology

Determine whether $\{¬q∧(p→q)\}→¬p$ is tautology . this my solution : \begin{align} \{¬q∧(p→q)\}→¬p & ≡¬\{¬q∧(¬p∨q)\}∨¬p \\ &≡q∨(p∧¬q)∨¬p≡(q∨p)∧(¬q∨¬p) \\ &≡(q∨¬q)∧(p∨¬p) ≡T∧ T \\ ...
0
votes
1answer
42 views

How to simplify these identities?

I have to verfiy the following identities $(A \bigtriangleup B) \cup C = (A \cup C) \bigtriangleup (B \setminus C)$ using logic symbols, I have to say what it means to be an element of each set and ...
0
votes
3answers
44 views

Problem understanding why $P \implies (Q \implies P) \equiv T$ [on hold]

I've been through the truth table and I can see how it works but I can't exactly understand why. The proof presented in the book (Logical Reasoning: A First Course by Nederpelt and Kamareddine) says ...
0
votes
4answers
66 views

Translate these statements into English

Translate the following statements into English, where $C(x)$ means '$x$ is a comedian', $F(x)$ means '$x$ is funny' and the domain consists of all people: a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x)) c) ...
-3
votes
1answer
120 views

How to express $\oplus$ with only $\neg$ and $\implies$?

Any logical connective could expressed with NOR and therefor with $\neg$ and $\implies$. How to express XOR ($\oplus$)with only $\neg$ and $\implies$..? Note: $\wedge$ is not allowed! I tried to ...
5
votes
4answers
1k views

There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2 $$ I am stuck and I would really like to see a correct proof so I can move ...
1
vote
1answer
29 views

Show that $(\phi \rightarrow \psi), (\phi \rightarrow \neg \psi) \vdash \neg \phi$

Using the axioms: For any formula $\psi,\theta, \phi$ $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ $$2.:(\psi \rightarrow (\phi\rightarrow\theta)) ...
1
vote
3answers
44 views

Is the (first order theory) of Hilbert spaces categorical?

Suppose the axioms of a Hilbert space (i.e. vector space, inner product, completeness and separability) are formulated as a first order theory. It can be shown that any infinite dimensional Hilbert ...
2
votes
1answer
39 views

How to show $\vdash (\neg\neg p \rightarrow p)$.

Given these axioms: where $\phi, \psi, \theta$ are formulas $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ $$ 2.: ((\neg \psi \rightarrow \neg \theta) \rightarrow (\theta \rightarrow \psi))$$ ...
1
vote
3answers
27 views

How to simplify this logical expression

Full Disclaimer, this is a homework problem. Negate the following logical expression and transform it so that negations only appear before individual predicates: ∀x∃y∀z, P(x) ∧ ¬Q(x) → R(x) ∨ (R(y) ...
0
votes
1answer
19 views

How can we formalize this procedure of converting first order logic formulas into propsitional formulas?

Here is a procedure which shows us how to convert any FOL formula into a propositional formula: I wonder how to formalize this rigurously in a simple way? by that I mean, give a precise definition ...
1
vote
1answer
18 views

Does distinct subformulas in this context mean syntactically distinct or semantically different?

In Freindly introduction to mathematical logic, there is a procedure to convert the first order logic formulas into propositional formulas, this is a natural way to convert FOL's formulas into ...
0
votes
1answer
17 views

Analyse the logical form of the following statements

I am not completely sure about the request of this question: Analyze the logical form of the following statements using variables C and PASCAL are programming ...
0
votes
2answers
47 views

If no interpretations satisfy a set of formulae U, is it possible for $U\models A$?

Note: '$ \models$' denotes logical consequence, defined as If $U \models A$, then $A$ is a logical consequence of $U$, if and only if every interpretation that satisfies U also satisfies $A$, ...
0
votes
2answers
36 views

Natural deduction: given premises, conclude $M \lor E$. [on hold]

I need to prove that the following argument is valid using Natural Deduction: 1.  $[\lnot (B \lor \lnot I) \rightarrow (\lnot L \land J)]$ 2.  $[\lnot L \rightarrow (M \land B)]$ 3.  $\lnot (B ...
0
votes
4answers
75 views

If I want to avoid quantifiers?

In mathematics quantifiers always is used with restrictions $\forall x\in A$ etc and mathematicians often write: $$x\in A\implies p(x)\;\;\;\text{instead of}\;\;\;\forall x\in A:p(x).$$ Are there a ...
0
votes
3answers
38 views

Proving logical consequence of a set

Prove or disprove the following: $(P \wedge Q), (\neg Q) \vDash (\neg P)$ I don't see how $\neg P$ could be a logical consequence of the set since it isn't similiar to any of the formulae within the ...
1
vote
3answers
73 views

Can we deduce anything from the empty set of axioms?

If the set of logical axioms is empty and so is the set of non-logical axioms, then it seems we can't make any deduction.As the first formula in the deduction must belong to either sets or it it's ...
2
votes
2answers
37 views

Simplification of boolean expression with xor

I need to simplify the following boolean expression ¬(A xor B) xor (B + ¬C) I know A xor B = ¬AB + A¬B Then the expression will become ¬(¬AB + A¬B) xor (B + ¬C) However, I stuck on it and I don't ...
0
votes
1answer
33 views

Prove that $P \vDash X$ and $Q \vDash X$ implies $(P \vee Q) \vDash X$

Let $P \vDash X$ and $Q \vDash X$. Prove that $(P \vee Q) \vDash X$. This may seem to obvious but is there a formal way to prove this? couldn't I just state that $(P \vee Q) \vDash X$ is true since ...
0
votes
1answer
51 views

Is every natural number even or odd?

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx = 0)$. MA has finite models and every infinite model of MA must ...
0
votes
2answers
52 views

How to prove that for all $x$ there exists some $y$ where $ (x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
2
votes
1answer
61 views

Predicate logic proof problem

Where the domain of the variables are Real Numbers, determine the truth value for the following: $$ \forall x \exists y(y^2-x<200) $$ I don't understand how to formally prove this problem. Since ...
-1
votes
0answers
32 views

Properties that only hold for 'small' infinities

I don't know the right terminology, so I'll pose it this way: Let $\alpha_1=|\mathbb{N}|$ e.a. countable. Let $\alpha_2=|2^\mathbb{N} | = |\mathbb {R}|$ There are a lot of properties that hold only ...
1
vote
2answers
58 views

How to prove that we can switch two $\forall$?

This is true? See a simple proof (High-school level) Thanks e.g: $$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$
-1
votes
0answers
32 views

How to deduce from an equivalence a conditional? [on hold]

Using the tautology $$\left(A\implies B\right)\iff\left(\overline{B}\implies\overline{A}\right),$$ we have: $$((\forall x\in\mathbb{R}):x\ne0\implies x+\sqrt{x+1}-1\ne0)\iff((\forall ...
0
votes
1answer
34 views

¬p ⊬ ⎕(p → q): Where's the mistake in my proof?

My professor noted on one of his slides that ¬p ⊬ ⎕(p → q). Intuitively, this seems correct; however, I can only prove that it is false. I suspect I've made a mistake in my proof. Where have I gone ...
2
votes
2answers
51 views

Is replacing $y$ by $x$ formally a valid substitution in the formula $\forall x\exists y ¬(x=y)$?

In “Friendly introduction to mathematical logic” by Leary, an example is mentioned to demonstrate the importance of defining substitutions and then substitutability as follows: let $\sigma$ be the ...
0
votes
0answers
15 views

Implement using switches the following logic functions

Implement using switches the following logic functions: F(a,b,c,d)= ab + cd F(a,b,c,d)=(a + bc)d' how can i do it ? Digital System
-2
votes
1answer
47 views

Propositional Logic questions, need help answering [on hold]

I have attached below a list of questions regarding propositional logic and valid arguments. I am having great difficulty answering these questions and I am not sure about my answers. I was hoping one ...
0
votes
2answers
77 views

Does axiom of foundation/regularity protect against Russell-like paradoxes?

In ZF set theory the axiom of regularity (also called axiom of foundation) says that: In all nonempty sets x there is an element y such that x∩y=∅ As I been told that the intention of the axiom ...
0
votes
3answers
35 views

proving a logical consequence when subtracting a tautology from a set

IfI have a set X of Well-formed formulae and a Formula P. I know that X ⊨ P. If i am givin a tautology Q then prove that X - {Q} ⊨ P I don't understand why subtracting the set Q wouldn't make a ...
1
vote
1answer
18 views

How can I interpret this question?

Question is as follows. There are two parents and three children. "Set, A, must contain at least one parent and two children." My interpretation is that A has to have at least one parent, and only ...
1
vote
0answers
28 views

Ordinal arithmetic and functions

I have two function $G$ and $F$ defined on ordinals and I know that $$G(\alpha +\omega )\subseteq F(\gamma +\alpha+\omega)$$ when $G(\alpha)\subseteq F(\gamma)$ and $\alpha$ is a limit ordinal. I ...
0
votes
0answers
10 views

Simplify Boolean Function F(w,x,y,z) = wx' + y'z' + w'yz' using Karnaugh map?

Given: F(w,x,y,z) = wx' + y'z' + w'yz' How would I simplify it? Also given the first term wx' would that translate to 10 or would I have to incorporate y and z ...
2
votes
1answer
32 views

Which negation of the definition of a null sequence is correct?

A Cauchy sequence $a_n$ is said to be a null sequence if for every $\varepsilon>0,$ there exists an integer $N$ s.t. $\forall n >N, \lvert a_n \rvert < \varepsilon$. I thought the negation ...
0
votes
1answer
26 views

Understanding triple mixed quantifiers

I'm having a hard time understanding mixed quantifiers of this form: $$\forall x\exists y\forall z(...)$$ and similarly $$\exists x\forall y\exists z(...)$$ It really hurts my head to think about ...
-1
votes
1answer
87 views

Does Mathematics exists apart from the mathematician? [on hold]

Does Mathematics exists apart from the mathematician? Explain yourself. Mathematics seems to be a projection of the mind. But from where the mind originates? Can the source of the mind be known or you ...
0
votes
2answers
40 views

Formal logic and current language

What is the negation (logically speaking) of the following proposition: Today I will do this task.
0
votes
1answer
38 views

3 Knights and Knaves

I have been struggling with this problem: Knights always tell the truth but knaves never tell the truth. In a group of three individuals (who we will label as N1, N2, and N3) each is either a knight ...
0
votes
0answers
39 views

What are algorithm? Can we relate algorithm using set theory concepts?

What really algorithm are? Can we define algorithm as functions or in terms of set theory (I think it is foolish what am I writing) But can we reconvert proof using algorithm in set theory concept.For ...
1
vote
1answer
55 views

Are all transcendental numbers theoretically accessible?

I apologize if the title (and the body) of this question is worded incorrectly, but I have no real experience in (transcendental) number theory, so it's probably the best I can do. I've been thinking ...
0
votes
2answers
60 views

Proof of induction principle

Theorem 1.1.3 (induction principle) of Dirk Van Dalen "Logic and Structure" states: Let $A$ be a property, then $A(\phi)$ holds for all $\phi \in PROP$ if: $A(p_i)$, for all i; $A(\phi),A(\psi) ...
1
vote
1answer
38 views

“Commutativity” of quantifiers

I'm learning logic from Suppes' Introduction to Logic. I can show within his system of rules, that $\models (\forall x)(\forall y)(Pxy) \rightarrow (\forall y)(\forall x)(Pxy)$ and similarly for the ...