Stack Exchange Network

Stack Exchange network consists of 174 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
3answers
38 views

Is there any notation for testing if A is in B?

I want to do a union over sets $A_i$, but only if $A_i \in B_i$. I don't know any way to write this concisely. I was trying to write something with unions and intersections but I can never get it to ...
1
vote
2answers
18 views

3 person Knights and Knaves Problem

The problem goes as such: politicians never tell the truth and non politicians always tell the truth. A stranger meets 3 natives and asks the first of them "Are you a politician?" And he answers. The ...
1
vote
3answers
22 views

Help with quantifiers: $\forall y\in\mathbb{Z},\exists x\in\mathbb{Z},(x^2+y\geq1)$

As the title suggests, I am revisiting quantifiers and am having trouble deciphering the proper meaning. I know it is one of these two: Does it mean that for each individual $y\in\mathbb{Z}$ we can ...
-1
votes
1answer
13 views

problem in converting hex to binary dividing by 2

if i convert $ABH$ into binary by table simple its value is $1010$ $1011$. but if i convert using dividing by $2$ then why the answer is different ie $0110$ $1110$. $AB/2=55, r=0$ $55/2=27, r=1$ $...
0
votes
1answer
26 views

Propositional logic - if, then, unless, consequence [on hold]

Need help to solve the below question. I need a direction so that I can apply the same to other questions. I understand what logical consequence means, and various propositional logics. EDIT1: ...
1
vote
0answers
37 views

Legitimacy of Consistency Proofs

In this question I asked yesterday I put forward two interpretations of a statements such as "System X is consistent". (a) we can think of it as saying no finite sequence of applications of logical ...
2
votes
1answer
24 views

Definition of a structure

I found the following definition for a structure in my math course: A structure $X$ consists of a non-empty set $D_x$, the universum of $X$ and the attribution of values $r^x$ to non logical-symbols $...
-1
votes
0answers
28 views

Non truth-functional operators in mathematical logic [on hold]

How do you prove that the connective/operator "Mr. Smith believes that..." is not truth-functional? I should mention that a similar question asks how to prove that the operator "It is possible that......
3
votes
0answers
60 views

Consistency of PA from a Formalist Perspective

In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
3
votes
0answers
53 views

Godel's theorem incompleteness, truth vs.provability

I know this question has been investigated in other threads, but I would like to pose yet another question on Gödel's theorem incompleteness, and truth in 'the standard model' compared with ...
-5
votes
0answers
24 views

HELP Prove that the sentence $∀x∃y∀wR(x, y) ⇒ ∃x∀v∃w∀x[S(x, v) ⇒ R(x, f(w, y))] $ is logically equivalent to a $∀∃∀$ sentence [on hold]

A $∀∃∀$ formula is one of the form $∀x_1 . . . ∀x_n∃y_1 . . . ∃y_k∀z_1...∀z ψ$, with $ψ$ quantifier-free. Prove that the sentence $∀x∃y∀w R(x, y) \to ∃x∀v∃w∀x[S(x, v) \to R(x, f(w, y))]$ is ...
0
votes
0answers
39 views

Prove that no terminal substring of a formula is a formula. [on hold]

Question I am struggling to understand exactly what the question is asking, the terminology is abit difficult.
-4
votes
0answers
30 views

how I exactly conclude from given information [on hold]

sorry if the title wasn't clear that much about what I'm going to ask. I've serious problem and I always facing it ; lets assume I have a specific case which at that case x=y^2+3 (just a typical ...
1
vote
0answers
38 views

Does this have a name? $\vDash(a_1\to(a_2\to(\cdots(a_{n-1}\to a_{n})\cdots)))\leftrightarrow((a_1\wedge a_2\wedge\cdots\wedge a_{n-1})\to a_n)$

For all formula $\alpha_1, \alpha_2, \cdots, \alpha_n$, $$\vDash (\alpha_1\to(\alpha_2\to(\cdots(\alpha_{n-1}\to\alpha_{n})\cdots))) \leftrightarrow ((\alpha_1\wedge \alpha_2\wedge\cdots\wedge\...
0
votes
0answers
14 views

Finite sequence of quantifiers “For all” and “there exists” in a mathematical statement, dependencies of the parameters

The statement "$\forall\epsilon\exists\delta\forall x\forall y$ $:P(\epsilon,\delta,x,y)$ is true" is equivalent to the same statement with $\forall x$ and $\forall y$ swapped. And $\delta$ can ...
4
votes
0answers
69 views

How is it possible to have a model of a set theory? [duplicate]

I am trying to understand the basics of model theory. Before getting too deeply into it, I would like to know how it is even possible to construct a model, i.e. a structure that satisfies axioms of a ...
2
votes
1answer
45 views

One's Mother is one's Female parent

Is below a correct predicate in logic for the english statement "One's Mother is one's female parent" Where Mother(x,y) denotes Y is mother of X. Female(X) denotes X is a female Parent(X,Y) ...
-2
votes
0answers
47 views

How does the contemporary field of logic/mathematics feel about using contradiction as a method of proving a conjecture?

I recently read an article on Aeon (https://aeon.co/essays/the-logic-of-buddhist-philosophy-goes-beyond-simple-truth) about contradictions in mathematics. The article dives in deep between a cultural ...
0
votes
0answers
22 views

Doubt on Implication of Logical reasoning [duplicate]

Its evident that in the truth table of $p \to q$ When $p$ is False and $q$ is True, Then $p \to q$ is True. But in some instances i could not convince myself about this truth value. For example: $...
3
votes
1answer
48 views

Several questions about the incompleteness theorem

I’ve read quite a few pop math books over the years with descriptions of the incompleteness theorem and I think I understand most of the broad details, but some still elude me. Specifically, these ...
2
votes
1answer
83 views

What is the purpose of Semantics/Model theory in Mathematical Foundations?

First off I know very little model theory so apologies if I say anything very dumb or offensive to logicians/model theorists. Second I should note that a lot of what I am saying here is motivated by ...
1
vote
4answers
47 views

Is the condition $x\in\mathbb{R}$ necessary to the set statement $\{x \in\mathbb{R} \vert x> 0\}$?

Forgive my ignorance. Is the condition $x\in\mathbb{R}$ necessary to the set statement $\{x \in\mathbb{R} \vert x> 0\}$? In other words, if $x$ is greater than zero, then is it not, by definition, ...
2
votes
2answers
50 views

How to use natural deduction to show $\neg (P \land Q) \vdash \neg P \lor \neg Q$?

How to use natural deduction to show $\lnot (P \land Q) \vdash \lnot P \lor \lnot Q$? I think I need to first assume $\neg(\neg P \lor \neg Q)$ and then find a contradiction but I cannot see how to do ...
1
vote
0answers
27 views

Equivalence of strings in modal logic

I'm trying to solve a question which asks me to show that for any two finite strings $O_1$ and $O_2$ of $\square$s and $\lozenge$s, (e.g. $\square\lozenge\lozenge\square\lozenge\square)$, that i) if $...
1
vote
1answer
26 views

Understanding connection between terms tautology, contradiction, contingent, satisfiable, unsatisfiable, valid and invalid

Couple of days back I asked this question. And after reading comments and answer there, even though I knew the definitions of the different terms (tautology, contradiction, contingent, satisfiable, ...
1
vote
1answer
65 views

Why is the “axiom of extension” an axiom? [duplicate]

I think this is a definition of = because it explains the meaning of the new symbol =. However, I wonder why the set theory thinks this as an axiom rather than a definition.
3
votes
1answer
61 views

Linearly ordering the power set of a well ordered set with ZF (without AC)

As the title says, my question is, how one can use only ZF-theory to prove that the power set of A, whereby (A, <) is a well-ordering, can be linearly ordered?
1
vote
2answers
33 views

Show that [¬p ∧ (p ∨ q)] → q is a tautology [on hold]

How can I show that [¬p ∧ (p ∨ q)] → q is a tautology by using the logical equivalences?
3
votes
1answer
40 views

Validity of $(\lozenge\phi\wedge\lozenge\psi) \rightarrow (\lozenge(\phi\wedge\lozenge\psi)\vee\lozenge(\psi\wedge\lozenge\phi))$ in modal logic

I'm trying to answer a question, one part of which asks me to provide either an informal semantic argument or a counterexample to determine whether $(\lozenge\phi\wedge\lozenge\psi) \rightarrow (\...
1
vote
1answer
14 views

Closed Form Addition of BCD numbers

Binary Coded Decimal (BCD) number representation is a 4-bit encoding which maps numbers 0-9 to their counterpart binary codes. Addition of BCD numbers can be formulated as follows: z = a + b (If z &...
0
votes
1answer
42 views

Prove $p \lor q \Leftrightarrow (\neg p) \rightarrow q$, but with caveats.

In this question, the professor asks us in parts i through iii to prove using truth tables that: i. $\neg (p \lor q) \Leftrightarrow (\neg p) \land (\neg q)$ ii. $\neg (p \land q) \Leftrightarrow (\...
0
votes
3answers
50 views

What does $\forall x \phi \rightarrow \psi$ mean?

If I have a formula $\forall x \phi \rightarrow \psi$, how can I know if it means $(\forall x \phi) \rightarrow \psi$ or $\forall x (\phi \rightarrow \psi)$?
0
votes
1answer
50 views

If statement A requires B to be true, is it possible to prove A without using B?

[it is totally described in the title in fact] I have a statement A that is true only if statement B is true. Is it possible to prove A without referring to B in any way? (I mean, if you use ...
1
vote
1answer
33 views

Equivalent form of the Whitehead problem

Let $M$ be an $R$-module and consider the following statement. $M$ is projective whenever the obvious group map $\tau: \text{Hom}_R(M, R) \to \text{Hom}_R(M, {R}/{I})$ is surjective for any ideal ...
0
votes
2answers
37 views

States that reach only bad states are bad. Predicate Logic

Consider a system of states with a binary relation R. If R(x,y) holds, we say that state x reaches state y. Further, consider two unary predicates I and B where I(x) means that x is an initial state ...
1
vote
1answer
26 views

Linear order on the set N^N

Give the example of the Linear order on the set: $\mathbb N^\mathbb N$ I know that $\mathbb N^\mathbb N$ is a function from $\mathbb N$ to $\mathbb N$ and it's a string, but I'm unable to give an ...
0
votes
0answers
37 views

Amalgamation base, extending Galois type

Here on the page 12 the Observation 1.11 5) says If $M\leq_{\frak K} N$ are from ${\frak K}_{\lambda}$, $M$ is an amalgamation base and $p\in \mathscr{S}(M) \;\underline{\text{then}}$ there is $q\in ...
0
votes
2answers
28 views

What does: “for all free variables shown” mean in Set Theory.

I am reading the definition of what it means for a class $A$ to model a formula of the Language of Set Theory. It begin, Let $A$ be a class and $\phi(x_1,\ldots, x_n)$ be a formula of the Language ...
0
votes
0answers
20 views

Conjunctive NF to Disjunctive NF

I need to convert this CNF to DNF ¬(XY + ¬YZ) * ¬(XY + Y¬Z) I got this as answer, but i'm pretty sure it's wrong. ¬X¬Y¬Z + ¬Y¬Z + ¬XYZ Does anybody know the right answer and the steps to get ...
0
votes
1answer
32 views

Use Horn formula to prove that it is possible to produce carbonic acid

I don't know how to translate this problem to mathematical logic language. How am I supposed to came up with a Horn formula from this? I should easily be able to test it's satisfiability after that, ...
1
vote
1answer
50 views

Questions about basic logic (why position of “for all” makes difference)

I am reading Appendix B of "Introduction to Analysis by Arthur Mattuck 1st edition" It says that the following two sentences have different meaning. The book says that if the epsilon is introduced ...
0
votes
1answer
9 views

Inference using Biconditional statements (For each of these sets of premises, what relevant conclusion(s) can be drawn? Rosen 8th Ed

All foods that are healthy to eat do not taste good (Premise): $\forall x (H(x) \to \lnot G(x))$ Tofu is healthy to eat. (Premise): $H_{Tofu}$ You do not eat tofu (Premise): $\lnot E_{Tofu}$ ...
1
vote
1answer
25 views

Explain the rules of inference used to obtain each conclusion from the premises (Rosen 8th Ed):

I'm having a difficult time with the following - seems like a lot of work and I'm unsure if my conclusions makes sense when translated back to english. If I work, it is either sunny or partly ...
1
vote
0answers
19 views

What workbooks (guidelines) can be helpful for solving math logical exercies?

I am wondering which workbooks can be helpful in solving following task: For an individual range I = {a,b} show that: Math logic exercise As I understood, this task is connected to Horn clause, math ...
2
votes
2answers
225 views

Sixth grade math (number related) problem

We have this statement (about rational numbers, btw): If $m-n+p = p$ and $ m \neq n \neq 0$ then $ m = -n$ Is this true? a) always b) never c) sometimes The given answer is b) but: ...
1
vote
0answers
23 views

Is simplifying a complete expansion of the right hand side of a trigonometric identity sufficient to prove it?

My first question is, when proving a trigonometric identity for all real values of a variable such as $x$, is it sufficient to expand the right hand side into elementary functions and simplify until ...
0
votes
3answers
41 views

Does symmetry and transitivity imply reflexivity for nonempty binary relation?

I've seen a few answers to this, like here and but they are not satisfying to me (possibly too advanced). The definitions in my book are as follows: A binary relation $\mathrel{R}$ on two sets $A$ ...
1
vote
1answer
75 views

What is the definition of “equality”

I thought we could define "the equality on set $A$" by the relation $\{(a,a):a\in A\}\subseteq A^2$. However, no book has this definition. Moreover, some books say that this is the "diagonal relation"....
1
vote
3answers
43 views

What is the difference between “equality” and “equivalence relation”

I think equality is just an instance of equivalence relation. An equivalence relation can be defined in the set theory, but how can we define "equality"? I wonder what equality is.