Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
0answers
18 views

Mathematical Expressions: Proofs

Prove or disprove the claim, and prove or disprove the converse: Claim 1: ∀n ∈ ℕ, (Ǝk ∈ ℕ, n = 5k + 2) ⇒ (Ǝj ∈ ℕ, n2 = 5j + 4) Claim 2: ...
1
vote
1answer
18 views

How to prove the validity of this argument?

I have an assignment where I have to prove the validity of a statement, but I am not sure about what I am doing. This is the assignment: Is the statement $(A \wedge B \wedge C) \to D$ a valid ...
0
votes
0answers
13 views

A symbolic logic problem generator, or at least a huge ready-made collection?

I am an amateur student of formal logic, and I was wondering other Gensler's LogiCola program, is there anything out there that produces logic proof problems? For example, the LogiCola program I am ...
1
vote
0answers
18 views

Mathematical expressions: Proving logic statements

For x ∈ ℝ, define by: ⌊x⌋ ∈ ℤ ∧ ⌊x⌋ ≤ x ∧ (∀z ∈ ℤ, z ≤ x ⇒ z ≤ ⌊x⌋). Use this definition to prove or disprove the following with a structured proof technique: ∀x ∈ ℝ,∀x ∈ ℝ, ∀e ∈ ℝ+, Ǝd ∈ ℝ+, ∀w ...
1
vote
2answers
43 views

Proving logic statements

For x ∈ ℝ, define by: ⌊x⌋ ∈ ℤ ∧ ⌊x⌋ ≤ x ∧ (∀z ∈ ℤ, z ≤ x ⇒ z ≤ ⌊x⌋). Use this definition to prove or disprove the following with a structured proof technique: ∀x ∈ ℝ, ∀y ∈ ℝ, x > y ⇒ ⌊x⌋ ≥ ⌊y⌋. ...
1
vote
2answers
23 views

Proving $\forall x (A\to B) \to(A \to \forall x B):x\notin \mbox{free}(A)$ in a Hilbert system where it is not an axiom

I have no idea whether this question is way too specific or whether something similar has already been asked (we still need to work out a way to search for formulas I guess). Anyways here I go: I ...
0
votes
2answers
32 views

For any set of formulas in propositional logic, there is an equivalent and independent set

A set of formulas is independent if no proper subset is logically equivalent to it. Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.
0
votes
0answers
12 views

finite state machine rows and columns

Knowing that the FSM has 23 states, 4 input bits, and 3 output bits, how do you calculate how many rows and columns will be needed to represent the truth table? I know that the answer is 512 rows and ...
2
votes
1answer
28 views

Show that $(\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A)$.

Let $A, B,$ and $C$ be sets. Show that: $$ (\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A) $$ I’ve simplified to the following: $$ (\overline A ∪ B) ∩ (\overline{C \cup A}) = ...
3
votes
3answers
70 views

Formal notion of computational content

In constructive mathematics we often hear expressions such as "extracting computational content from proofs", "the constructivity of mathematics lies in its computational content", "realizability ...
0
votes
0answers
8 views

how to do that function $n \rightarrow h(f(n),g(n))$ is URM [on hold]

if $f:N\rightarrow N$ ,$g:N\rightarrow N$ , $h:N^{2}\rightarrow N$ are URM computable then so is the function $n \rightarrow h(f(n),g(n))$.
3
votes
3answers
48 views

High school geometry proofs and first order logic?

I am a student of logic who recently came across two column geometry proofs which seem to be the bane of many a high-school student. My main question though, is that is there any way of doing these ...
1
vote
1answer
18 views

Boolean Logic Converting DNF to CNF

I'm confused on how to convert DNF to CNF. On the answer sheet my teacher gave me, she just convert it right away with no explanation. So my teacher convert $F: (A \wedge \neg B) \vee (B \wedge D)$ ...
0
votes
1answer
40 views

Any substructure of $(\mathbb{N}; 0, 1, +, \cdot)$ is itself

Consider a substructure $\mathcal{M} \subseteq \mathcal{N} = (\mathbb{N}; 0, 1, +, \cdot)$. Prove that $\mathcal{M} = \mathcal{N}$. EDIT: This result seems intuitively easy, but I'm having trouble ...
2
votes
4answers
26 views

Question About Notation Nested Quantifiers.

It's a pretty simple question on nested quantifiers but I didn't see anything about it on my Textbook or on Google so I wanted to give this a shot. So let's say you have $P(x)$ and $P(y)$ and you ...
1
vote
1answer
20 views

Distribute ANDs over ORs in this sentence

Can someone explain how we turn the sentence $$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because ...
1
vote
3answers
39 views

Reverse of Deduction Theorem

Why is it "easy to see" that if $S \vdash (A\to B)$ then $S \cup\{A\} \vdash B$?
0
votes
2answers
23 views

how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$ I tried doing it with a truth ...
2
votes
3answers
36 views

Is this formula satisfiable?

I am confused whether or not my explanation for whether or not this formula is satisfiable is correct. Note that the question state it should be Brief and it should not be necessary to write down a ...
-4
votes
1answer
21 views

what can be considered the winning points? [on hold]

2 people play a matchstick game. When it is your turn you can remove 1, 2 or 5 matches from the pile. You lose if you can not make a move. Develop a winning strategy for this game.
1
vote
2answers
32 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
1
vote
2answers
46 views

Is it true that if not $\alpha \vDash D$ implies $\alpha \vDash \neg D$?

If it is not true that $\alpha \vDash D$, with $D$ arbitrary formula, is it true that $\alpha \vDash \neg D$? I think that this assertion is false, but I cannot find counterexamples. Thanks in ...
3
votes
0answers
57 views

Intuition for the choice of background (set) theory

Problem From the formalist point of view, any mathematical statement should ultimately be an assertion about the derivability of a certain formula in a certain formal system, call it the background ...
0
votes
1answer
8 views

Write Propostion using Quantifier

Write the proposition “Every pair of strangers has a common friend” using connectives and quantifiers. Use F(x, y) for “x is friends with y.” (Two people are strangers if they are not friends.) My ...
5
votes
1answer
31 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
1
vote
1answer
35 views

Proof of Soundness Lemma

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$ We are given the hint to ...
1
vote
1answer
18 views

Inference Lemma Proof?

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$. Proof: Let $\langle ...
2
votes
2answers
83 views

Beautiful combinatorial painting problem

Mark paints squares of a white $10 \times 10$ board. He can either paints some vertical row of squares blue or some horizontal row red.(Every row is painted at most once). If blue paint is put on ...
1
vote
1answer
40 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
55 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...
1
vote
1answer
48 views

Prove: $\{α_1,…,α_n\} ⊨ α$ iff $\{α_1,…,α_{n−1}\} ⊨ (α_n→α)$.

Recently began my second logic course and have been surprised at how very, very different it is from the first one. My main struggle is that we have to prove things all the time, and I've never learnt ...
1
vote
2answers
38 views

What are the rules for negating quantifiers in propositional logic in general, is the “NOT” distributive?

I was wondering what the general rules for negating quantifiers was. I was reading that they follow this rule holds: $$NOT(\forall x. P(x)) \iff \exists x. NOT(P(x))$$ Which makes sense to me. ...
3
votes
2answers
43 views

Why does changing the order of quantifiers in Goldbach's conjecture changes its meaning and truth value?

Goldbach's conjecture in English reads: “Every even integer greater than 2 is the sum of two primes.” Which can be written in terms of quantifiers as: $$\forall n \in Even. \exists p \in ...
1
vote
2answers
25 views

What operation is done first in the following exercise…

Here I have such an exercise: I have to simplify the form of the following expression:$$(p\lor \lnot q)\land(\lnot p \lor q )\lor (p \lor \lnot r)\lor \lnot q$$. I know how to simplify it, but what ...
0
votes
0answers
13 views

Conditional Probability Semantics

I am studying conditional probability, and have a question on the semantics of a problem. I have the following belief network: ...
2
votes
1answer
44 views

Convert one proof into another

For a long time I have been investigating this question on my own, but it seems impenetrable. The question is this: To find a method whereby it becomes possible to convert proof A into proof B, where ...
0
votes
0answers
20 views

how to describe an $\mathcal{L}-$model that has its univers $R$? [on hold]

this language consisting of one constant , synbole , one 3-ary function symbole and one binary relation symbole :$\mathcal{L}$ is $\{\flat \; \natural \; \sharp\}$. how to describe an ...
0
votes
0answers
18 views

Translating sentences into sentential calculus [on hold]

William Shakespeare was William Shakespeare if and only if he wasn’t Francis Bacon.
0
votes
2answers
58 views

Show that the following statement is a theorem.

Suppose h is not a counting number and h is greater than 1, then there is a counting number n such that h is between n and n + 1. I am working through "Creative Mathematics" by H.S. Wall. The book ...
0
votes
3answers
37 views

Prove $\neg A \wedge \neg B$ using the following rules

S1: $A \leftrightarrow(B\vee E)$ S2: $E \rightarrow D$ S3: $C \wedge F \rightarrow \neg B$ S4: $E \rightarrow B$ S5: $B \rightarrow F$ S6: $B \rightarrow C$ I'm not quite sure how logical proofs ...
0
votes
1answer
46 views

Why do you only need to show validity in one world when using trees in institutionist/constructivist logic?

Depicted below, my prof used a tree to prove that an argument is valid according to intuitionist logic. However, I can't find a contradiction in world 0. Why is invalidity ascertained when all ...
2
votes
1answer
42 views

Beautiful logical combinatorics problem

TV series were aired for 5 years. Every day at most 2 episodes were shown. Every year, starting from the second one, either 40% more, or 40% less episodes, than the previous year, were aired. The ...
1
vote
3answers
46 views

Logical implication

I'm stuck with a logic problem like this I eat ice cream if I am sad. I am not sad. Therefore I am not eating ice cream. Is this conclusion logical? The first sentence can be ...
2
votes
1answer
38 views

An example of a formula with infinite Morley Rank

Given a Theory and a Model, you can define the Morley Rank of formulas with parameters from the model. I'd like you to give me an example of a formula (with theory and model) with infinite Morley ...
0
votes
1answer
37 views

Beautiful problem about 11 statements

11 pieces of paper are on a line. On each of them one of 11 statements is written (all are different on each paper): 1)No false pieces of paper to the left 2)Exactly 1 false paper to the left ...
0
votes
1answer
31 views

Find the free variables in the given sentences.

How to find free variables? 1)$(\forall x)$$(\forall y)$$x+y=2$ 2)$x+y<x$$\vee $$(\forall z)$$z<0$ 3)$((\forall y)(y<x))$$\vee $$((\forall x)(x<y))$ please guide me?
3
votes
2answers
203 views

Proof that expression is a tautology

I'm studying to my exam and I have some doubts. The expression: $$¬(P \Leftrightarrow Q) \Leftrightarrow P \oplus Q$$ The objective is to know if it is a tautology. I don't know the result. I made ...
2
votes
1answer
75 views

True but unprovable?

I would like to ask a question about Gödel's Incompleteness Theorems which I've had in the back of my head for some time. Since I'm a student working in a completely different area of maths (my usual ...
0
votes
1answer
25 views

Propositional Logic meta-variable notation abuse

When defining Formation Sequence, van Dalen (4th edition page 9) says: A sequence $(\varphi_0,\varphi_1,...,\varphi_n)$ is called a formation sequence of $\varphi$ if $\varphi_n=\varphi$ and: ...
0
votes
0answers
36 views

what is the formula statemaent of the twin primes conjecture? [closed]

The language of number Theory is $\mathcal{L}_{NT}=\{0,S,+,.,E,<\}$ such that $S$ is the succesor function and $E$ stands for exponentiation 1) give a formula to express that $P$ is a prime ...