0
votes
1answer
29 views

Show that | and $\downarrow$ are the only binary connectives \$ such that {$} is functionally complete.

I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks ...
4
votes
1answer
122 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
25
votes
3answers
787 views

**Ended Competition:** What is the shortest proof of $\exists x \forall y (D(x) \to D(y)) $?

The competition has ended 6 june 2014 22:00 GMT The winner is Bryan Well done ! When I was rereading the proof of the drinkers paradox (see Proof of Drinker paradox I realised that $\exists x ...
1
vote
5answers
69 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
4answers
123 views

Solution of $\dfrac{a}{b}=\dfrac{a'}{b'}$ if $a,b,a',b' \in \mathbb{N}$

Let $\dfrac{a}{b}=\dfrac{a'}{b'}$ , $a,b,a',b' \in \mathbb{N}$ s.t. $a$ and $b$ have no common factors and it is presumed that $a'>a$ and $b'>b$. How can we show that the only solution to this ...
0
votes
2answers
63 views

How do I show that these are the same logical statement?

I know that if I wanna show that the following statement are the same, I may use some rules in Logic: $$P\Longrightarrow Q,\quad [P \text{ and } (\sim Q)]\Longrightarrow [R\text{ and }\sim R]$$ Is ...
1
vote
0answers
73 views

Maximally Consistent Set (Proof by Contradiction)

Yesterday, I asked about feedback for a proof of the following theorem For all $\phi$, $\phi \in \Gamma^{*}$ if and only if $\Gamma^{*} \vdash \phi$. My main concern was the first part $(\to)$, which ...
1
vote
2answers
232 views

Hard proof concerning the periodicity of trigonometrical functions. Is that a challenge or just trivial

i want to know if exist or if you can develop or give me ideas of a proof to show that the least number for which sine is periodic is $2\pi$ $$\neg \{\exists n\in \mathbb{R} \wedge n < 2\pi: ...
3
votes
1answer
381 views

Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive. Let $E$ be the set of even natural numbers. The function $f$ defined ...