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)

0
votes
0answers
30 views

Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
0
votes
0answers
25 views

Understanding direct proofs and proofs by cases?

I'm reviewing my book Mathematical Proofs a Transition to Advanced Mathematics and looking to understand things at a deeper level. I will try to explain what I've considered so far in regards to this ...
0
votes
2answers
39 views

Prove that ∀n≥1, (1/(1⋅3))+(1/(3⋅5))+(1/(5⋅7))+…+(1/(2n−1)(2n+1)) =( n/(2n+1))| [on hold]

Prove that ∀n≥1, (1/(1⋅3))+(1/(3⋅5))+(1/(5⋅7))+...+(1/(2n−1)(2n+1)) =( n/(2n+1))| So, I understand that the proof must display that (1/(2n−1)(2n+1) is equivalent to (1/(2n−1)(2n+1). Would I solve ...
0
votes
1answer
20 views

model definitions for tautology, contradiction, and connectives quantify too much, no?

Occasionally I come across a definition based on what will happen in all models, for example, that a contradiction is a statement that is false in all models, that a tautology is a statement that is ...
1
vote
1answer
51 views

Is there a formal way to show that $X \cap Y \subseteq X$.

The question is in the title. It is trivial that $X \cap Y \subseteq X$. Because $X \cap Y$ only contains elements that are both in $X$ and in $Y$. So every element in $X \cap Y$ is also an element of ...
1
vote
1answer
28 views

Two questions about first order theories having only finite models.

Let T be a consistent theory formalized in the first order predicate calculus, all of whose models are finite and have cardinal numbers less than some positive integer n(T). Is T necessarily decidable?...
1
vote
3answers
94 views

When is the Law of the Excluded Middle Valid/Not Valid?

Sometimes, you can use the Law of the Excluded Middle (LEM) to validly prove things by contradiction (e.g. irrationality of sqrt(2)). However, at other times, you can not, for example when you have ...
3
votes
2answers
97 views

What are “words”?

Related but not duplicate. I am reading Classical Mathematical Logic by Richard L. Epstein, page $3$: B. Types When we reason together, we assume that words will continue to be used in the ...
1
vote
1answer
29 views

Difference between set theory proof and logic proof of complete induction

Set theory proof: Let $\mathbf{A}$ be the set such that $\{0,1,2,...,n\} \subset \mathbf{A} \implies n+1 \in \mathbf{A}$. Our goal is to show that $\mathbf{A} = \mathbb{N}$. To do this, we construct ...
-2
votes
1answer
17 views

Chain of implications shows equivalence of several conditions

In mathematical articles, theorems frequently have the following form: The following (conditions) are equivalent: (first condition) (second condition) (third condition) ... ...
1
vote
1answer
66 views

Does anyone know a no-nonsense intro to “logic for mathematics” that I can give to a Year 11 student?

I'm looking for material on propositional and first-order logic to give to a Year 11 student that explains how they're used "in practice." For example, I want to be able to write the null-factor law ...
0
votes
0answers
24 views

Limits to the principle of explosion

In propositional logic, the principle of explosion can be proven in the following way. $\phi \wedge \neg\phi$ (hypothesis) $\phi$ (simplification, 1) $\phi \vee \psi$ (disjunction introduction, 2)...
1
vote
3answers
64 views

Is there a 'definition' of truth based on sets of true statements?

been thinking a fair bit about how to think about truth recently. I at one point came up with a deficient theory of truth based on provability, and was directed to Tarski's semantic theory of truth ...
0
votes
1answer
82 views

Can we take definability and existence as primitive notions of a theory?

One of my friend tries to develop an alternative viewpoint of Set Theory. For this he has taken the terms binary relation, set, existence and definability as primitive notions of his Set Theory. After ...
0
votes
2answers
65 views

How could we formalize the introduction of new notation?

What I am thinking about is how in a textbook/proof/theorem/discussion/definition one states that from now on a new notation will be used in the appropriate scope. Example: Let $V^*$ denote the ...
0
votes
1answer
386 views

Show that equivalence can be derived

Show that the equivalence $$p \land \neg p \equiv F$$ can be derived using resolution together with the fact that a conditional statement with a false hypothesis is true. [Hint: Let $q=r=F$ in ...
-2
votes
1answer
30 views

How to translate this statement to First Order Logic?

“Thus there exists a pet in this house being a cat or a dog” I am unsure of how this statements should be translated.
0
votes
2answers
84 views

Is there an error in this textbook about Peano Arithmetic?

I encountered this doubt in an online intro-logic open course offered by Stanford Uni. Under the section 9.4 of this textbook here: http://logic.stanford.edu/intrologic/secondary/notes/chapter_09....
2
votes
1answer
519 views

Puzzle : Truant List of Statements

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question: The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the ...
0
votes
1answer
57 views

Olympiad Books for Primary Students

I am a teacher of gifted program in primary school and currently I am developing Olympiad Curriculum (topic-wise) for my students. I have those topics that could need some help in terms of questions: ...
-3
votes
0answers
18 views

Math logic which contains sum

I want say the following sentence in math logic but I don't know how to address the sum in the logic. The sentence is: Correlation(x->y) equals to (For all C as clusters, for all exists members in C ...
0
votes
2answers
659 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
1
vote
2answers
134 views

Convert form from CNF to DNF

I have a few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can I convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can I convert this to CNF $(p \wedge q) \...
4
votes
2answers
68 views

Write $(p↔q)$ in DNF

I have the following formula: $(p↔q)$ and I have to write in DNF (disjunctive normal form) This is where I got so far: $(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$ but here I got stuck. How ...
2
votes
1answer
53 views

Turning CNF into DNF

I have a formula $(L\Leftrightarrow (A\vee J))$ and I am to turn it into DNF and CNF. When I use de Morgan rules and so on, the formula looks like $(L\Rightarrow (A\vee J))\wedge ((A\vee J)\...
5
votes
4answers
8k views

What is the difference between an axiom and a postulate?

I hear about axioms in set theory and postulates in geometry, but they seem like the same thing. Do they mean the same thing but then are used in different instances or what? Is one word more ...
2
votes
2answers
3k views

From DNF to CNF

What is the most efficient way to switch from DNF to CNF?.
11
votes
1answer
179 views

Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?

I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me. In discussing matters around and about the ...
1
vote
3answers
167 views

Virtues of Presentation of FO Logic in Kleene's Mathematical Logic

I refer to Stephen Cole Kleene, Mathematical Logic (1967 - Dover reprint : 2002). What are the "pedagogical benefits" (if any) of the presentation chosen by Kleene, mixing Natural Deduction and ...
0
votes
1answer
33 views

Can someone explain to me this logic sentence using entailment?

Can someone please explain me what does it exactly mean? $KB \wedge B^- \not\models\square$ I understand the entailment symbol in this example here : $T \models A $ is if there's no model of $FS$ ...
1
vote
2answers
185 views

Largest number definable

If $a_n$ is defined as the largest integer definable using $n$ characters in some standard theory like PA or $Z_2$. Can we prove or disprove that there is some finite integer $k$, such that for all $...
1
vote
1answer
54 views

Resolution Algorithms and one Example Problems?

We have a problem in one Resolution question. There is $5$ clauses, and want to prove the $6$th clause is true. which of the following clause is need more than one times to prove $6$th clause? $t$ ...
0
votes
2answers
77 views

Determining the correctness of a formal proof

Is the following formal proof, proving $\forall A\forall B \forall C[A+C=B+C\Longrightarrow A=B]$ correct?? Proof 1) $a+c=b+c$.............................................................Hypothesis ...
10
votes
4answers
172 views

How do we know logic works? [duplicate]

Every time I read about a theory in mathematics, it usually starts with axiomatizing the most fundamental concepts that are going to be treated. Recently, I have started finding this troubling. In ...
2
votes
2answers
88 views

A 3-valued mathematical logic?

Classical propositional logic is consistent and in conformity with human language. A formal statement is true or not true and it is possible to develope rules with which it is possible decide which ...
3
votes
1answer
31 views

uppersemilattice end extensions

I'm trying to modify an argument in Jockush and Slaman's paper On the $\Sigma_2$ theory of the upper semilattice of the Turing degrees. One of the major hurdles is that I don't actually see why a ...
0
votes
2answers
23 views

Chartrand Mathematical Proofs 3e Exercise 5.45

I am self-studying this book, and I'm not sure if there is a typo in this question, or there is a gap in my understanding. The question is: Let $R(x)$ be an open sentence over a domain S. Suppose ...
5
votes
2answers
94 views

Meta proof-searching

Suppose you have a particular theory (ex: $ZFC$) in which you want to prove a statement $\phi$. One can attempt to find a proof of $\phi$ that can be verified, but another tactic can be to find a ...
2
votes
2answers
124 views

Universal and existential quantifiers

Are there any examples of a unary predicate $P(x)$ such that the truth value of $P(x)$ remains invariant under exchange of the universal quantifier $\forall$ and the existential quantifier $\exists$? ...
1
vote
1answer
55 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
1
vote
1answer
422 views

First order logic, CNF

What steps do I need to follow to convert the next statements into CNF? Wich are the resulting clauses? $H \leftrightarrow C \vee D$ $R \rightarrow \neg D$ $R \wedge H$ $H \leftrightarrow C$ Thank ...
3
votes
4answers
88 views

Why does “if and only if” mean the exact same thing as “precisely when”?

The proposition "A precisely when B" states that A has the same truth value as B. The proposition "A if and only if B" states that A is true if B is true and that A is true only if B is true. ...
1
vote
1answer
38 views

Formalizing a self referential sentence

In The logic of provability, by G. Boolos, we are asked to ponder about this statement: If this statement is consistent, then you will have an exam tomorrow, but you cannot deduce from this ...
3
votes
3answers
59 views

Prove that $(p \to q) \to (\neg q \to \neg p)$ is a tautology using the law of logical equivalence

I'm new to discrete maths and I have been trying to solve this: Decide whether $$(p \to q) \to (\neg q \to \neg p)$$ is a tautology or not by using the law of logical equivalence I have ...
1
vote
1answer
23 views

Sequents: if-introduction and discharging assumptions

I am reading through "Mathematical Logic by Ian Chiswell & Wilfred Hodges"(amazon, and publisher) for context I am reading through this for self-study, so I don't have the normal support of a ...
-2
votes
1answer
49 views

Are the conditionals equivalent: $p → q ≡ q → p$?

I know that a conditional is if $p$ then $q$, but is that equivalent to saying if $q$ then $p$? Is $p → q$ saying the same as $q → p$?
1
vote
1answer
35 views

Proving a formula is valid

Let a formula $A$, and a term $t$ such that $x\in FV(t)$. Show that $\varphi = A\{t/x\}\to \exists x (x=t\to A)$ is valid. So let's assume by contradiction that the formula isn't valid. Therefore ...
2
votes
2answers
45 views

Axiomatizing stacks and queues using first-order logic

In the textbook I'm using to prepare the logic exam says that first order logic may be used to implement axiomatize data structures. There is an example of that: "Stack": uses a language that ...
2
votes
3answers
64 views

Negating the statement $\exists x \in \Bbb R$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$

There exists a real number $x$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$. I would like clarification on how to negate this. My idea of negation is ...
2
votes
1answer
45 views

First Order Logic Double Implication [closed]

I have a Logic Assignment of First Order Logic that I have to prove an initial claim, but one of the equations is kind of confusing for me because it has double implication and quantifiers. $$\...