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)

-1
votes
1answer
20 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ [duplicate]

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
1
vote
1answer
22 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) ...
1
vote
1answer
32 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...
1
vote
2answers
29 views

Recall that $ p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this be used as an explanation for how to use proof by contradiction.

Recall that $p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this equivalence be used as an explanation for how to use proof by contradiction. I'm having a hard time answering this ...
1
vote
3answers
49 views

How to prove that $A⊆B$ means that $A∪B=B$ [duplicate]

How does one prove that $A⊆B$ means that $A∪B=B$ ? I can understand it in my head but I don't know how you'd put down in logic notation.
0
votes
2answers
32 views

How can I express the NOT in terms of AND, XOR, XNOR [duplicate]

I need to figure out how to express the NOT operator in terms of the operators AND, XOR, XNOR. I need to show that this set is functionally complete, which I'm trying to do by showing that I can ...
0
votes
1answer
10 views

Simplify Conjunctive Normal Form?

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying: (P or Q) and P and (Q or R) and (P or notP or R) and ...
1
vote
1answer
19 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...
1
vote
0answers
34 views

Differenct axiomatizations of set equality

I've seen two definitions (or axioms?) of set equality: $a=b \Leftrightarrow (\forall x : x \in a \Leftrightarrow x \in b)$ $a=b \Leftrightarrow (\forall x : a \in x \Leftrightarrow b \in x)$ That ...
0
votes
0answers
30 views

Peano Arithmetic and Riemann Hypothesis.

I recently learnt from an MO post that, if the negation of the Riemann Hypothesis is not provable in Peano arirhmetic, then the Riemann Hypothesis is true. But is there any reference of this result ? ...
-1
votes
0answers
36 views

Question regarding tautologies [on hold]

Argue that the collection of tautologies is closed under conjunction, disjunction, implication, and the biconditional.
1
vote
0answers
19 views

How can we prove a statement is provable?

Given a concrete mathematical statement, such as BSD conjecture(https://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture), do we know if it is provable?
1
vote
2answers
40 views

Existance of an (in)finite theory having infinite model

Please help me to study the following simple cases: Let $P$ be a binary predicate symbol. I am trying to find out, if there exists a satisfiable $T$ having infinite models only, for the following ...
0
votes
1answer
16 views

Translation of arguments into symbolic logic

If all men were good, there would be no wars. Some men are not good. Therefore, there will be wars. *I am confused on what sign to use on the some part
0
votes
1answer
19 views

Binary to Gray code using XOR boolean expressions

I have a question which asks to design a circuit to convert from binary to gray code, using a boolean expression. Now I understand you have to use XOR to achieve this. And I understand that XOR ...
1
vote
4answers
30 views

How can this inverse of conditional statement be equivalent?

"A positive integer is a prime only if it has no divisors other than one and itself." The inverse of this conditional statement is : " A positive integer is not prime if it has divisors other than one ...
0
votes
0answers
20 views

Modal Logic translation example

I have an argument that I want to prove is valid, but my repeated failures at this have me worried that I did not translate the argument correctly. Here it is: Necessarily, "The sky is blue and the ...
0
votes
0answers
36 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
1
vote
0answers
15 views

How to solve this equation using semantic equivlence

Hi I am trying to workout the solution to this propositional logic formula using the below semantic equivalence formula but I am stuck. Could someone please help me out. These are the rules ...
0
votes
1answer
57 views

Is it possible to create a software to find formal proofs?

Let's say I have a Hilbert style system, with a few axioms and rules of inference, and I want to find a proof for some formula $\varphi$, is it possible to create an algorithm that would find a proof ...
0
votes
3answers
39 views

How would I translate this sentence into a predicate formula

A dragon is green if at least one of its parents is green I have ∀X⋅dragon(X) ∧ green (X) ⇒ ∃Y⋅childOf(Y,X)∧green(X) Is this correct?
0
votes
1answer
23 views

natural deduction problem using the connective not

I am having problems understanding how the connective not works in natural deduction. We were given the below example but I cannot workout how the lecturer got the values in table. If someone could ...
1
vote
1answer
14 views

Translate quantification into English and give the truth value

The problem is: $\exists x \in \mathbb{R} (x^3 = -1)$ I understand the following: $\exists x$ = There exists an $x$ $\in$ = shows the element before it is a member of a set after it $\mathbb{R}$ = ...
0
votes
2answers
32 views

Find all models of given theory

$\def\imp{\Rightarrow}$I have a theory $T=\{p \imp \neg q, \neg q, r \imp q, r \imp \neg p\}$ over $P=\{p, q, r\}$ I need to find all models of theory $T$. My question is whether I could use any ...
0
votes
1answer
28 views

number of ways of arranging balls so that there are exactly two pairs of green balls

There are $5$ identical red balls and $6$ identical green balls. In how manys we can arrange them so that there are exactly two pairs of green balls. Let red balls be $R,R,R,R,R$ and green be ...
0
votes
1answer
31 views

If a is odd, how do I prove that 3a is also odd?

I know that if something is odd then $\exists k \in \mathbb{Z}: a = 2k + 1$. But what I get is: $n = 2k + 1$ $3n = 3(2k+1)$ $3n = 6k + 3 $ But i can't factor 6k + 3 to give me 2k + 1 ! Any ...
0
votes
2answers
29 views

Triangle Inequality?

I'm having trouble proving the following claim: $\forall a, b, c \in \mathbb{R}_+: T(a, b, c) \Rightarrow [|a − b| < c$ and $|b − c| < a$ and $|a − c| < b]$ Where $T(a, b, c)$ is a ...
0
votes
0answers
45 views

Reference request for a very particular problem solving skill

I want to start with an apology for a very verbose description of my question but if there is a way to cut it down, please let know and I will do so right away. I have been trying to get better at ...
0
votes
2answers
31 views

Discrete Math: Determining if Argument is Valid

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
1
vote
2answers
31 views

Does a statement need to be a biconditional statement to prove by the contrapositive

I am trying to write a proof and was wondering if a then b, the converse if b then a might not be true. This leads me to wonder if the statement needs to be an if and only if statement if it can be ...
1
vote
1answer
37 views

Tautological Proof Help

I've been having some trouble with proving or disproving tautologies. I am very new to proofs and am hoping I am on the right track. The question asks to show that: If ψ → φ is a ...
0
votes
1answer
21 views

Determining if Argument is Valid via Short-Cut Method

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
0
votes
1answer
25 views

How to use natural deduction for introducing implication

I am doing some propositional logic and we learned about the natural deduction rule. Everything was going fine until the rule of introducing implication arose. I am slightly confused as to how it ...
0
votes
0answers
20 views

Are these two formulas theorems in the mendelson system of prop. calc? [on hold]

Are $$((a\rightarrow b)\rightarrow (\neg\neg a \rightarrow \neg \neg b))$$ and $$((a\rightarrow \neg b) \rightarrow (\neg \neg a \rightarrow \neg b))$$ theorems in the mendelson system? I really ...
1
vote
1answer
36 views

Help understanding a particular proof of the compactness theorem for Propositional Calculus.

I've reading through this proof, I don't understand the last part: the claim $\tau \models \Sigma$. Note: I'll use $AP(\varphi)$ and $\text{Var}(\varphi)$ interchangeably, to mean the variables that ...
31
votes
5answers
2k views

Proving the existence of a proof without actually giving a proof

In some areas of mathematics it is everyday practice to prove the existence of things by entirely non-constructive arguments that say nothing about the object in question other than it exists, e.g. ...
0
votes
2answers
27 views

Logical Implication on set of statements

All birds are animals. All animals are four legged. Implications a. All animals which are four legged are birds. b. All birds are four legged c. Some birds are four legged d. ...
1
vote
2answers
27 views

How can I negate this conditional statement? [on hold]

The conditional statement is: If today is February 1, then tomorrow is Ground Hog's Day. I need to negate this but I am confused. Would it just be If today is not February 1, then tomorrow is not ...
0
votes
1answer
16 views

Direct proofs involving disjunctions

I've just started a logic and proof class, and I'm confused about what we learned. Given a proof of the form $$(P \lor Q) \rightarrow R$$ why is it true that you only have to show $$P \rightarrow R$$ ...
0
votes
3answers
28 views

Help with logical quantifiers

Let $L(x,x)$ be "$x$ loves $y$". Then is the statement: "Nobody loves everybody" equivalent to $$∀x ∀y \overline{L(x,y)} $$
2
votes
3answers
71 views

Trying to prove for all integers: $n \ge 1 \implies \frac{2n+1}{2n+2} \ge \frac{\sqrt{n}}{\sqrt{n+1}}$

Been racking my brain on this one.. I've tried some things but not sure if it flows logically: $\forall x \in \mathbb{Z}: n \ge 1$ $n+2 \ge 1$ $2n+2 \ge n+1$ $\frac{2n+1}{2n+2} \ge ...
1
vote
1answer
41 views

Why doesn't Cantor's diagonalization work on integers? [duplicate]

Why can't you use Cantor's diagonalization argument to prove that the integers are countably infinite? i.e. 1: 12345.... 2: 42345.... 3: 56903... 4: 46234... 5: 23421... etc. Then we could ...
5
votes
1answer
982 views

Which is the most powerful language, set theory or category theory? [on hold]

As far as I know, mathematics is written based on a language which can be for example set theory or category theory. My concern is about the power of these languages. How can we realize which language ...
-1
votes
0answers
22 views

Significance of rules of inference [on hold]

I was just wondering about the significance of the rules of inference and about Modus Tollens and Modeus Ponens when validity of expressions like p=>q can be checked by checking if p->q or ~p+q is ...
0
votes
2answers
21 views

Can I do universal instantiation on this predicate?

Can I do universal instantiation on the following predicate : $ \forall x\;S(x)\; \lor\; \forall x\;L(x)$ become $S(c)\lor L(c)$ or is it has to be $\forall x\; ((S(x) \lor L(x))$ to be able to do ...
-1
votes
3answers
57 views

Showing $k^2 + m^2$ is odd when $k$ is odd and $m$ is even [on hold]

Prove that if $k$ is any odd integer and $m$ is any even integer, then, $k^2 + m^2$ is odd.
3
votes
2answers
41 views

$ x \ge 0\text{ and } y \ge 0 \implies \frac{x+y}{2} \ge \sqrt{xy} $ [duplicate]

The above applies $\forall x,y \in \mathbb{R}$ I've tried: $x + y \ge 0$ $$x + y \ge x$$ $$ (x + y)^2 \ge 2xy$$ $$\frac{(x + y)^2}{2} \ge xy$$ But the closest I get is $\dfrac{x+y}{\sqrt{2}} \ge ...
1
vote
1answer
17 views

Do the inputs to a boolean-function need to be boolean variables?

That is, say we had the following: define a set, $A$, as: $A = \{x,y,z\}$ If we had a function which only takes the elements of $A$ as its inputs, and returns "true" if $x$ is an input and false if ...
0
votes
0answers
18 views

canonical to algebraic form with don't cares [on hold]

How do I transform the canonical form of a logic expression to its algebraical equivalent? For example: $$ f(a,b,c) = \sum \{3,7\} = \not abc + abc $$ But what would it look like for: $$ ...
5
votes
2answers
79 views

Is there a first order formula $\varphi[x]$ in $(\mathbb Q, +, \cdot, 0)$ such that $x≥0$ iff $\varphi[x]$?

In the first-order language $\mathscr L$ having $(+, \cdot, 0)$ as signature, it is easy to define a formula $\phi[x]$, namely $\exists y \; x = y^2$, satisfying : $$\text{for all } x \in \Bbb R, ...