Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logic]

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 following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

0
votes
0answers
13 views

how to give a formal prove to $ \vdash \exists x (P(x) \rightarrow P(y)) $

I am struggeling with giving prove for the next statement : $\vdash\exists x (P(x) \rightarrow P(y))$. This is what I have done but it fails because $\alpha$ isn't a logical sentence. $\exists x (...
0
votes
0answers
13 views

Show that a subset of N is definable in $\mathfrak{N}_{S}$ iff either it is finite or its complement (in N) is finite.

Show that a subset of $\mathbb{N}$ is definable in $\mathfrak{N}_{S} (\mathfrak{N}_{S} =(\mathbb{N};0,S).)$ iff either it is finite or its complement (in $\mathbb{N}$) is finite.
0
votes
0answers
24 views

“Exists X | P(X)” holds but for no X does P(X) hold

Is there a known case in any classical logic rich enough to obey the Incompleteness Theorem in which: $$\exists x \space | \space P(x) $$ yet at the same time: $$\forall x \space \not \exists G \...
0
votes
0answers
9 views

Desrciption Logic - Expressing Currying on Role

Currently, I am struggling with role in description logic. As far as I understand, role in DL can be thought as a function from a subset of domain to the other subset of domain, which is a unary ...
-2
votes
2answers
28 views

How to find an equivalence relation?

How can the below given relation be or not be proved to be an equivalence relation ? $$_{a}R_{b} \iff a^{2} + b^{2} = 0$$ here relation $R$ is defined on $\mathbb{Z}$(integers)
0
votes
2answers
44 views

Do Godel results still work for a semi-recursive (rather than fully recursive) set of axioms?

I am reading Computability and Logic by Boolos, Burgess, and Jeffrey. Godel's first incompleteness theorem is stated as there not being a consistent, complete, axiomatizable theory for arithmetic. ...
0
votes
1answer
23 views

Equivalence Between Law of Excluded Middle and Self-Implication

We know that $P \to Q$ is equivalent to $\neg P \lor Q$, as can be verified easily in truth table. Now suppose we have proof for self-implication below [the axiom system is Lukasiewicz's, with L1: $P ...
0
votes
1answer
21 views

First order logic question about whether variables in the same sentence are bound

Is my intuition right that $$((\exists x)Px \land (\exists x)Gx)$$ is equivalent to $$((\exists x)Px \land (\exists y)Gy)$$ or is it actually equivalent to $$(\exists x)(Px \land Gx)$$ Any help ...
0
votes
2answers
41 views

$\lnot\exists x(S(x) \Rightarrow R(x))$ VS $\forall x(S(x) \Rightarrow R(x))$ Without Using De Morgan's Law

I was doing logic exercises the other day and I encountered the following: Write this statement symbolically and verify your answer using De Morgan's Law: No squares are rectangles My ...
0
votes
0answers
31 views

Nested difference of sets in set builder notation

I am to check if $A - (A - B) \stackrel{?}{=} B$. By inspection the LHS reduces to $A \cap B$ so it's a subset of RHS. I have a problem expressing it in set builder notation though. I know that $A - B ...
2
votes
1answer
39 views

How many dismentals of set A exists?

Let A be a set, let n be a natural number and let $\langle B_0,B_1,...,B_{n-1} \rangle$ series with $n$ length of subsets of set A. We say $\langle B_0,B_1,...,B_{n-1} \rangle$ is dismental of set A ...
0
votes
1answer
20 views

How to determine a set of conclusions that can be derived from a set of premises?

Considering the following three premises. How is it possible to determine the set of conclusions that can be derived from the given set of premises. ...
-2
votes
1answer
38 views

Proving the first principle of mathematical induction [on hold]

I was asked to prove the first principle of mathematical induction without using the well ordered principle. If someone can elucidate the steps clearly it would be a great help ! Thank you!
0
votes
0answers
20 views

Logic about statements involving two variables

Let $X,Y$ be sets. Let $P(x,y), Q(x,y)$ be statements involving $x\in X,y\in Y$. Now we have the following: $P(x,y)\iff Q(x,y)$ for any $x\in X$ and $y\in Y$. For any $x\in X$ and $y\in Y$, $P(x,y)\...
2
votes
2answers
18 views

How to use the distributive law correctly in propositional logic?

Can someone explain how in propositional logic these are equivalent : A ∧ B ∧ (¬B ∨ ¬C) ≡ A ∧ B ∧ ¬C Because using the distributive law I would get: ...
3
votes
1answer
52 views

Problem with translating sets into logic

I'm starting to work through Munkres and in the first section there is an easy excercise that I have problem with when I'm formalizing it. The quesiton asks if the iff is valid or if not which way ...
1
vote
1answer
38 views

Simplifying logic formula

I'm trying to learn some alghoritms of boolean logic and I encountered a problem wich i don't understand. There is a expression and I don't understand how to simplify it. $$(A \wedge \neg B) \vee(\...
2
votes
1answer
50 views

Arithmetic - linear order of $\mathbb{Z}$-copies

Let $\mathcal{M} \equiv (\mathbb{N}, 0, S, <, +)$ and consider the equivalence relation $\sim$ defined in $M$ by: $a \sim b$ if and only if $d(a, b) < \infty$, i.e. the distance is finite. It ...
0
votes
1answer
59 views

Which square should be cut to minimize loss?

From a paper size of $950mm × 1200 mm$, squares with a side of $64 mm$ or $46 mm$ can be cut. Which square should be cut to minimize loss? My attempts: We have, for square with side 64 mm, the ...
-1
votes
1answer
28 views

Is this Proof of (P→Q)→((Q→R)→(P→R)) based on Lukasiewicz Axiom System for CPL Correct?

Given Lukasiewicz axiom system for Classical Propositional Logic (CPL): (L1) α→(β→α) (L2) (α→(β→γ))→(α→β)→(α→γ) (L3) (¬α→¬β)→(β→α) and the usual Modus ...
2
votes
5answers
82 views

What is logical about the prisoner's dilemma?

In the Wikipedia example of The Prisoner's Dilemma it states that "all purely rational self-interested prisoners will betray the other, meaning the only possible outcome for two purely rational ...
1
vote
1answer
40 views

$\mathbb{Z}+\mathbb{Z}$ is a model of $Th(\mathbb{Z}, <, =)$

$Th(\mathbb{Z})$ is the set of all closed formulas which are true in the model $\mathbb{Z}$ of the signature $\{<, =\}$ I need to prove that $Th(\mathbb{Z})$ is not countably categorical. ...
0
votes
1answer
33 views

Prove by induction on structural complexity that the following set is complete

Consider the propositional language $L$ with denumerably many sentence letters $S_1,S_2,S_3,\ldots$ and the two connectives $\lnot,\lor$. Suppose that the set of sentences $\Gamma$ is a formal theory ...
-1
votes
0answers
38 views

Show that $\sigma$ is Deductively closed [on hold]

Can someone please help me? the problem is Let $\Sigma$ be a set of sentences (i.e., formulas without free variables) in a language $\mathcal(L)$ which includes equality. Suppose: \ (a) $\Sigma$ is ...
0
votes
0answers
19 views

Formal Methods and specification of program

I have command $choose$ that assign one value from array ${x1...xn}$ to variable $x$. Every call it assigns the same value to the variable. I need to create the specification for this program. I ...
2
votes
3answers
50 views

Natural deduction on exclusive OR

How do I formulate a natural deduction rule such that the conclusion is for example; a ∨ b (∨ being exclusive OR)
0
votes
3answers
63 views

Syntactic use of “ false” . After “ false” can I write anything I want? ( Not a semantic question on “ ex falso sequitur quodlibet”)

If the proof below proof is correct, I'd like to know what is the name of the rule involving " false" that is used here. This question is not on " ex falso sequitur quodlibet". From false follows ...
-2
votes
1answer
90 views

The Tennessee Waltz paradox [duplicate]

I love to dance, and one of my favorite dances is the Waltz, and a beautiful waltz to dance to is “The Tennessee Waltz” which was a monster hit for Patti Page in 1950. An unusual feature of this song ...
0
votes
0answers
20 views

laws of logic - having issues with identifying if some propositions and what law is used

(~q∨q)∧r⇔(q∨~q)∧r (q∨~q)∧r⇔r∧(q∨~q) To me looking over all the laws the only one that I think that makes sense to me is the Commutative law. Unless I am just way ...
0
votes
1answer
42 views

How to transform a sequent notation to rule form?

I can write this proposition in sequent notation: $$(P\rightarrow Q)\rightarrow (\neg P \lor Q)$$ as this one in rule form (see here): $$\frac{(P\rightarrow Q)}{(\neg P \lor Q)}$$ But how can I ...
0
votes
1answer
28 views

Venn diagram - How to choose the right conclusion with the given statements? [on hold]

In the following question, three statements along with a set of four conclusions are given. Select the correct answer from the options given. Statements ...
0
votes
0answers
26 views

Set Theory Logic Complement

Hi just doing some homework on set theory and I'm unsure of what this answer would be. I just need some reassurance that I have understood it correctly. U = { 1, 2, 3, 4, 5, 6, 7 } A = {2, 5, 6, 7 } ...
-1
votes
2answers
58 views

Pigeonhole Principle - Consecutive Days [on hold]

If an athlete trains for 20 days in a 31-day month, how can I prove that he/she will need to train on consecutive days at least once using the Pigeonhole Principle?
4
votes
3answers
295 views

How do the consequences of Russell's paradox extend beyond universal comprehension principle as far as the set of all sets problem? [duplicate]

I think I understand the way in which Russell's paradox shows that the following principle is wrong: " for every predicate, there is a set having as elements all the objects that satisfy this ...
0
votes
0answers
32 views

Logic of predicates over predicates?

Is there logic, that allow to form predicates over predicates (or even formulas), I.e. derive is-interesting-statment(is(I, liar)). Of course, the model operators in the modal logic can take ...
3
votes
3answers
59 views

Natural deduction proof: $C, (C \land D)↔F \vdash (D \land E) \to F$

I'm having trouble with proving C, (C Λ D) ↔ F |- (D Λ E) → F If it were $\lor$ instead of $\land$, then I would be able to do it. If I can prove that $(C ...
0
votes
2answers
47 views

Usage of (x, 1) (1) in natural deduction

When neither one of premises and conclusion includes a number like "1", like the following, I could at least proceed to some extent (although I don't know how to connect Q(y) of the first premise and ...
0
votes
2answers
43 views

If the language has only one predicate, can we simplify the quantifiers?

Assume that our language has only one predicate symbol. Then $(\forall x_1 \forall x_2 )(\phi)$ is equivalent to $(\forall x)(\phi')$ where $\phi'$ is a formula obtained by replacing all occurrences ...
0
votes
0answers
30 views

Rewriting statements in full detail with logical operators, but without quantifiers

I've been given the following question: Let P and Q be predicates on the set S, where S has two elements, say S={a, b}. Then the statement $\forall xP(x)$ can also be written in full detail as $P(a) \...
0
votes
1answer
37 views

What is the general formal definition of ordinal definable sets?

The following Wikipedia article about OD sets, mentions the informal definition of ordinal definable sets, yet it says that it cannot be captured formally in first order logic. I just want to make ...
2
votes
2answers
65 views

Arithmetical formalization of “F is sound”

In How subtle is Gödel's theorem? More on Roger Penrose, Martin Davis points out the fact that the statement F is sound $\implies$ G(F) is true where F is some recursively axiomizable extension ...
2
votes
1answer
66 views

Are the integers definable in $\mathbb{Z}_{(p)}$?

I am familiar with the statement (not the proof) of Robinson's definition of $\mathbb{Z}$ in $\mathbb{Q}$ in the language of rings. I would like to ask the same question for $\mathbb{Z}_{(p)}$ in ...
0
votes
1answer
33 views

Usage of adjective and imperative in statement logic

I think I know how to form sentences in statement logic if it's an "if statement" like (A) and (B) below, but how do I express adjective like "not so easy" or imperative like "Choose X or Y", as shown ...
0
votes
1answer
27 views

How resolution methods' rules apply in proofs

I understand that resolution methods are used to prove something by disproving its negation (proof by contradiction), but I don't understand how this idea is implemented in formulas. The following ...
0
votes
5answers
43 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...
0
votes
0answers
32 views

Boolean function: prime implicants - disjunctive minimal form

I applied the Quine-McCluskey method to determine the respective prime implicants for a boolean functions and find a disjunctive minimal form. We have the function \begin{equation*}f(x_1, x_2, x_3, ...
2
votes
1answer
70 views

The technique that uses the Chinese Remainder theorem, to express 1st order arithmetical statements encoding statements about infinite sets of numbers

I know this technique is heavily used in Number Theory, in Combinatorics (e.g. for phrasing Ramsey's theorems in a first order language of arithmetic), and in some related realms. However, ...
0
votes
1answer
70 views

About a famous assertion by B. Russell on mathematical truths considered as conditional truths. Is this claim also true of axioms?

In Mysticism and Logic, Russell says that : "Pure mathematics consists entirely of assertions to the effect that, if such and such a proposition is true of anything, then such and such another ...
1
vote
1answer
230 views

“ Logic does not allow you to say this”: is this assertion outdated?

I think one cannot say nowadays without further qualification " geometry does not allow you to say that the sum of a triangle's angles is less than 180 degrees". The sentence concerning the sum of ...
0
votes
1answer
67 views

How to prove $\vdash p\to\neg\neg p$ in this system?

I was asked to prove $\vdash p\to\neg\neg p$ in this system. Axioms: $(\mathcal A_1)\vdash p\to(q\to p)$ $(\mathcal A_2)\vdash (p\to(q\to r))\to((p\to q)\to (p\to r))$ $(\mathcal A_3)\vdash \...