Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

1
vote
0answers
24 views

Why is recursion theory suffering from terminological bloat?

Several questions on MSE in recent months and most recently this one have made me feel that recursion theory is suffering from terminology bloat. Why have so many synonyms for "recursive" and ...
0
votes
1answer
14 views

Trouble with step 2 resolution calculus

I need to prove T ⊨ A v B with the resolution calculus from a set T. Step 1 Transform T into a set of clauses (CNF). Clause 1 = A v ¬C Clause 2 = C v A v B Step 2 Try to find a resolution ...
0
votes
1answer
15 views

How to convert sentence into logic formula

Hi I wanted to know if I have converted this sentence into propositional logic correctly. This is the sentence At least two of the propositions $p$, $q$ and $r$ are true. and this is my answer ...
1
vote
3answers
27 views

Logical question with a balance and flour

The problem is: I have a balance of $9$ kgs of flour and two weights; $250$g and $50$g. In the matter of $3$ steps I have to divide them into $2$ bags of $7$ and $2$ kg, respectively. I know that ...
0
votes
2answers
33 views

How to demonstrate this tautology using equivalences?

I have this tautology $(P \wedge (P \rightarrow Q) \wedge (Q \rightarrow R)) \rightarrow R$ I couldnt prove it by using equivalences. Using Definition of implication and then using negative ...
1
vote
1answer
31 views

consistency strength

I am just beginning to read about consistency strength, and wondered if someone could clarify the relation between a two kinds of claims that I'm encountering. (1) A theory, T, proves the consistency ...
1
vote
2answers
41 views

What is exactly the difference between $\forall x \neg P(x)$ and $\neg \forall xP(x)$?

What is the difference between $\forall x \neg P(x)$ and $\neg \forall xP(x)$ or $\exists x\neg P(x)$ and $\neg \exists x P(x)$ ?
1
vote
1answer
36 views

Proof that every non-empty subset of a woset (X, $\leq$) has a unique minimal element.

I want to prove that every nonempty subset of a woset (X, $\leq$) has a unique minimal element. What I’m looking for: clarification and/or hints. I want to solve it on my own, but this is all the ...
0
votes
1answer
39 views

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use ...
0
votes
1answer
13 views

Propositional variables in semantic equivalence

I'm learning the semantic equivalence rules/laws in propositional logic, but I'm confused by what the propositional variables in the rules are supposed to represent. For example, the associative ...
1
vote
1answer
23 views

Is solvability of diophantine equations over a p-adic field decidable?

As far as I understand, the decidability of solvability of diophantine equations over the rationals is an open problem. What about the decidability of solvability over a given p-adic field?
0
votes
1answer
29 views

Resolution calculus converting into set of clauses

Here is $T$: $a \lor \neg b$ $\neg a \lor (c \land d)$ $b$ I am suppose to use resolution calculus to prove that $T \models d \land b$ holds. As in the first step, we translate $T$ ...
0
votes
0answers
16 views

Is (A v C) v B in conjunctive normal form?

I need T to be a set of clauses in conjunctive normal form. T = { (¬A ^ ¬C) → B } T = { ¬(¬A ^ ¬C) v B } T = { (A v C) v B } I 'simplified' it to T = { (A v C) v B }, is it in CNF? ...
9
votes
1answer
107 views

What's an Isomorphism?

I'm familiar with the definition (inverses and bijections, preserving operations) in the context of groups and vector spaces, the hoeomorphism of topological spaces, and have some feeling for the ...
0
votes
3answers
29 views

Prove that the following statements are all logically equivalent.

Prove that the following statements are logically equivalent: $A \subseteq B$ $A \cap B = A$ $A \cup B = B$ $B^c \subseteq A^c$ Here is what I have so far. I am not sure how ...
0
votes
0answers
34 views

Does Gödel sentence depend on numbering?

If we change Gödel's numbering definition of the $Prov$ predicate will change as well, but the meaning won't. How is that going to affect $G$? It seems to me like it will change as it is actually ...
0
votes
2answers
20 views

Express each of the following statements as expression using quantified predicates and the domain“People.”

Here are two questions confused me. Express each of the following statements as expression using quantified predicates and the domain "People." 1) Some high school students are not enrolled in class ...
2
votes
1answer
46 views

Deductive logic counter-intuitive result

I am working on a small proof in deductive logic. Here is what must be proved: $(\exists x \in T \mid A \implies P(x)) \implies A \implies (\forall x \in T \mid P(x))$ To me that looks unprovable ...
2
votes
3answers
60 views

$a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent.

Suppose a,b,c and d are statements such that $a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent. Hey, Im ...
1
vote
0answers
31 views

Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
0
votes
1answer
40 views

sets with quantifiers

My professor wrote the following theorems and definitions on the blackboard. ...
2
votes
2answers
45 views

Can you represent other logical operations using only $\neg$ and $\Leftrightarrow$ (not and equivalence)? [duplicate]

I can check on WolframAlpha for how to represent some logical operations using others, but I don't see anything for $\Leftrightarrow$. Is it because it is impossible? ...
0
votes
1answer
17 views

One place predicates and expressing them as strings of propositions

How do you express a quantified one-place predicate with a variable, such as ∃x[SING(x)] as a string of connected propositions?
3
votes
1answer
37 views

How many possible ways are there to make $\exists x \exists y \,\mathrm{Loves}(x,y)$ true, with five elements in the domain?

I'm a professional philosopher, not a mathematician, so I got myself stumped and hope somebody here will be kind enough to help me. When I'm explaining the universal and existential quantifiers to ...
4
votes
1answer
30 views

No simplifying identities for any single nonzero number under addition.

Consider the structure $(\mathbb{R}, +, r)$, where r is a nonzero real number. Are the commutative and associative identities already sufficient to derive all universally valid equations in that ...
0
votes
2answers
37 views

Algebraically transform logic expression

Algebraically transform: $\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ to $\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$ Justify each step with one or more ...
2
votes
1answer
43 views

Definition of “substitutable” in Mathematical Logic

I'm reading Leary's Mathematical Logic text where it defines the phrase "substitutable" and most of it is sensible: $t$ is substitutable for $x$ in $\phi$ if $\phi$ is atomic. $\phi := ...
-1
votes
2answers
44 views

LOGICALLY EQUIVALENT: NAND and NOR [on hold]

Is there a way to represent "p NOR q" using "NAND" with logical equivalence?
0
votes
1answer
21 views

On the functional-completeness of the sheffer stroke

I have seen functional-completeness (in regards to boolean functions) defined as: A set X of truth-functions (of 2-valued logic) is functionally complete if and only if for each of the five ...
1
vote
3answers
61 views

Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
2
votes
1answer
26 views

Show that a sequence of elements each realizing an isolated type over the previous realizes an isolated type

I'm trying to prove the following result which seems correct to me, but I'm not sure how to proceed. The proposition is: Let $M$ be a structure, $A\subseteq M$, $(a_1,\dots,a_n)$ be a sequence ...
1
vote
1answer
34 views

Logical form of a set-theoretic statement.

From Velleman's 'How to Prove it' book, there is one statement - written below - of which I don't know how to write the logical form of, and I'm wondering if somebody could write it out. The ...
2
votes
2answers
53 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is defined, and its truth values are given by the following table: \begin{array}{c|ccc} ...
-2
votes
1answer
39 views

Propositional-Calculus/ Set Theory Proof using Identities [on hold]

$$(\sim P\,\lor \sim Q)\equiv (Q\to (\sim P\,\lor\sim Q))\land ((\sim P\,\lor \sim Q)\to Q) $$ Can someone demonstrate the identity proof here? I've been trying to figure this out, but with no ...
0
votes
1answer
39 views

Translate the following into predicate calculus. State assumed universe of discourse

This is my first assignment on these, so I would greatly appreciate your help. Translate the following into predicate calculus. For each answer, also state the assumed universe of discourse. ...
4
votes
0answers
38 views

Group orderable iff all its finitely-generated subgroups are orderable

I want to proof this specifically using the Compactness Theorem from propositional logic (this is an exercise from Model Theory, Hodges). $G$ orderable means there is a total ordering s. t. $g\leq h$ ...
0
votes
1answer
43 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
0
votes
1answer
13 views

Minimal Model, from formula

{p2 ^ p3 -> p1, p3 ^ p4 -> p2, .... p9 ^ p10 -> p8} Find the minimal model. My professor told me the answer is the empty set, but aren't these minimal models too?: {p1}, {p2}, {p3}, {p4}, {p5}, ...
2
votes
1answer
36 views

Proof using formal deduction, how to introduce a conclusion?

Prove that $(E \land G) \lor ( G \rightarrow F )$ is formally deducible from $(E \lor F)$ where: "$\land$" means AND "$\lor$" means OR "$\rightarrow$" denotes an implication This is what I have ...
3
votes
0answers
34 views

N body computer

Which mathematical questions can be answered with an n-body computer? An n-body computer is an arrangement of n-bodies moving under mutual gravitation that is prepared in an initial state to answer a ...
0
votes
0answers
12 views

Find a formula of predicate logic for not decreasing and increasing sequences

There is a language $L = \{+, s\}$ with "=" + is func symbol behaving like this $(a_0, a_1, ....) + (b_0, b_1,...) = (a_0+ b_0, a_1 + b_1,...)$ s - shifts sequence to the left, i.e $s((a_0, ...
3
votes
0answers
45 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
-1
votes
1answer
43 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
0
votes
1answer
52 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) ...
1
vote
1answer
38 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...
1
vote
2answers
36 views

Recall that $ p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this be used as an explanation for how to use proof by contradiction.

Recall that $p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this equivalence be used as an explanation for how to use proof by contradiction. I'm having a hard time answering this ...
1
vote
3answers
52 views

How to prove that $A⊆B$ means that $A∪B=B$ [duplicate]

How does one prove that $A⊆B$ means that $A∪B=B$ ? I can understand it in my head but I don't know how you'd put down in logic notation.
0
votes
2answers
37 views

How can I express the NOT in terms of AND, XOR, XNOR [duplicate]

I need to figure out how to express the NOT operator in terms of the operators AND, XOR, XNOR. I need to show that this set is functionally complete, which I'm trying to do by showing that I can ...
0
votes
1answer
13 views

Simplify Conjunctive Normal Form?

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying: (P or Q) and P and (Q or R) and (P or notP or R) and ...
1
vote
1answer
22 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...