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)

1
vote
2answers
6 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
21 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
26 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
19 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
29 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
31 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
40 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
16 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
31 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
14 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
81 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
54 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
47 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
24 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
43 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
57 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
37 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
36 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
74 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
24 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
35 views

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

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 ...
0
votes
0answers
36 views

Non-equivalent k-DNF formula [on hold]

Let's define k-DNF. So ours formula is k-DNF, where $k \in \mathbb{N}$ if $$\bigvee^{n}_{i=1} \left(\bigwedge^{k}_{j=1} l_{ij} \right)$$ for some logic variables $l_{ij}$. ($n$ is arbitrary large, ...
0
votes
2answers
31 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: ¬(P ∨ Q) ∨ (¬P ∨ Q) The result: ¬P ∨ Q The objective is to simplify. I'm stuck at (¬P ∧ ¬Q) ∨ ¬P ∨ Q I could make the distributive, ...
0
votes
2answers
17 views

Discrete math - conjunction or disjunction in this case?

Teacher asks students if they did the homework on their own (everyone either did it on their own or copied it). He gets the following answers: Andy: Everyone didn't do their homework on their own. ...
0
votes
1answer
25 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: $$ \lnot \lnot P \land \lnot(\lnot\lnot Q \lor\lnot P) $$ The result: $$ P \land \lnot Q $$ The objective is to ...
2
votes
1answer
50 views

A fragment of Exercise 1.3.4 in _Shorter Model Theory_ by Hodges

The following is what I believe is necessary to solve Exercise 1.3.4 in Shorter Model Theory by Hodges. Given two structure $\mathcal {A, B}$ of the same signature $\tau$, a set $S$ of generators of ...
4
votes
1answer
44 views

O-minimal Theories with Non-Dense Order Type

In this paper, Knight, Pillay, and Steinhorn prove that for any O-minimal structure $\mathfrak{A}$, in which the underlying order types is dense, and if $\mathfrak{B} \equiv \mathfrak{A}$, then ...
1
vote
1answer
26 views

Strange Absorption Behavior in Discrete Math

I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example: ...
0
votes
1answer
22 views

Natural Deduction for sets

I'm a student of logic and I have a question, want to prove The Following sets by natual deduction, but do not know how to proceed. $$\begin{align} a) A \cap (B \cup C) ≡ (A \cap B) \cup (A \cap C) ...
0
votes
1answer
51 views

Discrete Math Formula Equivalence Proof

How can I prove that the following two statements are equivalent, using Formula Equivalence laws? f(x) and (g(x) and h(x)) (f(x) and g(x)) and (f(x) and h(x)) I ...
1
vote
1answer
23 views

Why is Skolem normal form equisatisfiable while the second order form equivalent?

I asked in another question when is it appropriate to de-Skolemize a statement. The answer, I'm not sure I'm satisfied with yet, relies on a second order logical equivelance, but Skolem normal form ...
-1
votes
2answers
20 views

Boolean Simplification of a large problem

I am unsure where to even start on this problem. My intuition that what ever can be done to the original problem can be done over and over to simplify the whole thing. Please help with some guidance. ...
1
vote
1answer
17 views

Boolean Simplification of $ (a+b) \cdot (a \cdot c + a \cdot \overline{c}) + a \cdot b + b $

Below is my simplification, but my truth tables don't line up, but I can't find my error. $ (a+b) \cdot (a \cdot c + a \cdot \overline{c}) + a \cdot b + b $ $ (a+b) \cdot a \cdot (c + \overline{c}) ...
0
votes
1answer
43 views

Universe of discourse in $A \subseteq B$

In the following logical analysis: $A \subseteq B $ $\forall x(x \in A \implies x \in B)$ Is the universe of discourse for the above logical form is A since the ...
2
votes
2answers
43 views

The truth table shows the following statement is a tautology, but it doesn't make sense.

the truth table of the sentence $$(p \rightarrow q) \vee (q \rightarrow p)$$ is \begin{array}{ c c l } p & q & (p \rightarrow q) \vee (q \rightarrow p) \\ \hline T & T & \, ...
1
vote
0answers
36 views

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3.

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3. My only idea is to assume the opposite, make some needed arrangement, and to show that changing the ...
1
vote
2answers
34 views

Boolean Simplification of $(\overline{a+b+c})+a\cdot(b+ \overline{c})$

I'm lost, when checking my answer via truth tables, my simplified form does not match the original equation. My work, with reasoning step by step is below. Can you help me figure out where I'm wrong, ...