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
1answer
23 views

Prove the Transitivity of $\vdash$

I've reviewed the following answer Proving transitivity of $\vDash$ and and $\vdash$ and I'm having trouble grasping the concept. I've tried to recreate the Proof below: Let $\Gamma \vdash B_1, \...
-1
votes
0answers
24 views

Propositional Logic; Problem: Tautologies and Contradictions

I have this task which I am stuck with trying to solve it. I am aware of the fact that the truth table would always yield a "false" in the last column in case of a contradiction, and always a "true" ...
0
votes
0answers
16 views

Show that $\Gamma \vDash_{taut} B \leftrightarrow \Gamma \cup \{\lnot B\}$ is unsatisfiable.

I'm going through an example proof, and I'm unclear why it's important to write: Let $\Gamma \cup \{\lnot B\}=A_1,...A_n,\lnot B$, why not let $\Gamma \cup \{\lnot B\}=\lnot B$. By definition of $\...
1
vote
0answers
13 views

Show that $A_1,…,A_n\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to …\to A_n\to B$

I'm having a hard time understanding the iff part of this proof by induction (is this vacuously true?), below is my attempt: Base Case: Let $n = 1$, therefore $A_1\vDash_{taut} B \leftrightarrow \...
0
votes
2answers
22 views

Proving a Floor Function is Onto

I know that the function $f(x) = \lfloor 4 \sqrt{x} \rfloor$ is onto, but I can't figure out how to prove it. The function is from $\mathbf{Q^+} \cup \{0\} \to \mathbf{N}$. I can't figure out how to ...
5
votes
3answers
315 views

Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?

Below, an attempt at solving a knight/knave puzzle using the truth table method. Are there other methods? Source : https://en.wikipedia.org/wiki/Knights_and_Knaves
0
votes
1answer
16 views

Can variable-containing statements (propositional functions) contain propositional variables?

My understanding of a propositional function (like P(x)) is that it is a declaration that contains one or more variables, so that when values are substituted in for the variables, a proposition (a ...
0
votes
1answer
31 views

Which of the following is the best way to define a new predicate in first-order logic?

Here are a few different ways of defining the same predicate: $$\forall x, y \in \mathbb{R}, P(x, y): x = y \tag{1}$$ $$P(x, y): x = y \text{, where $x$ and $y$ are real numbers} \tag{2}$$ $$\text{...
0
votes
1answer
20 views

Total number of ways to arrange objects subject to constraint [duplicate]

Suppose that you are ticket collector in Cinema office. It cost 50 dollars to watch a movie. There are 20 people in line. 10 people in that line have exactly 100 dollar bills and 10 people have ...
1
vote
0answers
24 views

Propositional logic with implicit equations

I've been playing around with the idea of performing logic with implicit equations. For example, given the implicit equations $$\begin{matrix} A:\; \; F(x,y,z,\dots) = F = 0 \\ B:\; \; G(x,y,z,\dots) =...
-1
votes
0answers
90 views

How do we say this using the notation conventions of mathematical logic? [on hold]

What it the most conventional way to formalize this? (1) Γ is a set of WFF of F (2) C is a WFF of F (3) Every element of Γ is true (4) C is provable from Γ Assuming Higher Order Logic: this is my ...
1
vote
0answers
27 views

Challenge : Finding the right minimized order of points.

There's stolen diamonds in a lot of different places. The places are on a coordinate system (x,y) where each place is named after a number and have an d-time for example: ...
0
votes
2answers
55 views

Frege's argument for the existence of abstract mathematical objects

I have some trouble understanding Freges argument in particular as presented here, https://stanford.library.sydney.edu.au/entries/platonism-mathematics/#FreArgForExi In particular the first premise i....
0
votes
0answers
45 views

Where can I find examples of absolutely detailed formal mathematical proofs?

I know that many mathematical proofs omit many explanatory logical rules of inference and principles of deduction for the sake of conciseness (for example, most proofs refrain from expressing the use ...
2
votes
1answer
29 views

Prove $(R \implies W) \wedge (R \implies \neg S) = R \implies (\neg S \wedge W)$

Prove $(R \implies W) \wedge (R \implies \neg S) = R \implies (\neg S \wedge W)$. Here is my work so far: $$(R \implies W) \wedge (R \implies \neg S) \\ \equiv ((\neg R \vee W) \wedge (\neg R \vee \...
1
vote
1answer
40 views

What is the name of the rule that allows us to infer the truth of an equation from the truth of another equation?

I am wondering if there is a particular named rule or principle in mathematics/formal logic (that can be listed as justification in a formal proof) that allows one to conclude the truth of an equation ...
2
votes
1answer
51 views

Example for Hilbert quote

Hilbert famously said The art of doing mathematics consists in finding that special case which contains all the germs of generality. Can you give an example of a situation in mathematics where ...
6
votes
2answers
70 views

understanding one step of Gödel's theorem

I'm trying to understand this proof of Gödel's theorem: https://mat.iitm.ac.in/home/asingh/public_html/papers/goedel.pdf At page 3 it says: Let $B_1(n), B_2(n), ...$ be an enumeration of all ...
0
votes
2answers
65 views

What is the difference between a definition and an equivalence class?

In what way is 'the definition of $x$ is $y$' ($x:=y$) not the same as '$x$ is equivalent to $y$' ($x=y$)? I can find no justification for making the distinction aside from 'it feels right'. It seems ...
-2
votes
1answer
32 views

The principle of extreme

What is the minimum number of colors you can paint all natural numbers so that any two natural numbers that differ in 4 or 8 times, were painted in different colors?
-2
votes
0answers
32 views

How to prove the following rule in predicate calculus? [on hold]

does anyone know how to prove : $(\exists x) F(x) \vdash ~ (\forall x) F(x) $ and $(\forall x) F(x) \vdash (\exists x) F(x) $ ?
0
votes
0answers
41 views

Is completeness inherited upwardly?

Language: first order logic with equality and membership and the omega set rule (see below). Define: $set(x) \iff \exists y (x \in y)$ Axioms: $\sf ID$ axioms + Extensionality: $\forall z (z \in x \...
0
votes
0answers
42 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 (...
-1
votes
0answers
28 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. [on hold]

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
1answer
45 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
14 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
40 views

How to find an equivalence relation? [on hold]

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)
1
vote
2answers
49 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
36 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
27 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
48 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
36 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
55 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
23 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. ...
0
votes
0answers
27 views

Logic about statements involving two variables [on hold]

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
22 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
59 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
44 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
52 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
60 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
32 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
83 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
41 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
34 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
20 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
54 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
92 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
21 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 ...