Articles of logic

Every $n$-ary logical connective has a DNF

I’m trying to solve the following exercise: Let $A_1,…,A_n$ be propositions, $n \in \mathbb N$. Show that every $n$-ary logical connective $J(A_1,…,A_n)$ considered as a function $J:\{t,f\}^n \to \{t,f\}$ ($t$ is true, $f$ is false) has a disjunctive normal form, in other words can be represented as a disjunction $Y_1,…Y_k$ of a suitable amount of […]

Discrete Maths Logically Equivalent

Just have a question on logically equivalency specifically the logical equivalency. Question find a simple expression using $p$ and $q$, logically equivalent to $q \iff(\neg p\lor \neg q)$. Im not really sure but could it be: $p \iff (\neg q \land p)$? Thanks.

Does $(\neg R\to R)\to R$ give rise to a proof strategy?

Take for example proof by contradiction, it can be viewed as a certain deduction in logic which can be used outside of logic to prove many interesting propositions. My question is: can we use $(\neg R\to R)\to R$ as a similar strategy?

Proving ${\sim p}\mid{\sim q}$ implies ${\sim}(p \mathbin\& q)$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~p | ~q , that ~(p & q). Any ideas on how I should proceed?

How do I acquire an intuitive understanding of the distributive law over a disjunction?

The distributive law over a disjunction is given to be: $ P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R) $ I want an intuitive understanding of this statement, in order to do I tend to write these logical statements out in words and use concrete examples. Statements $P=$ I will […]

Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this correctly. Usually I have no idea which rules to use and it feels like I just need to try […]

Galois, normal and separable extensions

Theorem: Every finite extension, normal and separable is a Galois extension. Is the theorem equivalent to: $\mathbb K:\mathbb F$ is Galois $\iff \mathbb K:\mathbb F$ is normal & $\mathbb K:\mathbb F$ is separable ? thus, $\mathbb K:\mathbb F$ is not a Galois extension $\iff \mathbb K:\mathbb F$ is not normal or $\mathbb K:\mathbb F$ is […]

Formalising real numbers in set theory

If I understand correctly, the real numbers can be formalised in a first-order, like in ZF. However, such a formalisation is not strong enough to ensure that all models of the reals are isomorphic. Why is being able to ensure isomorphism between models interesting? What’s significant about that? In terms of the first-order formalisation of […]

Is this a correct natural deduction proof for $\{(\phi\vee\psi),\neg\phi\}\vdash\psi$?

I’m not sure I used RAA correctly by putting $\neg\psi$ next to $\bot$ and discharging it.

Might proof by contradiction be needed for this mundane problem?

This present question is inspired by this earlier question. Consider the problem of proving that if $f\ge 0$ on an interval $I\subseteq\mathbb R$ and $\int_I f=0$, then $f$ is $0$ (almost) everywhere on $I$. Can it be proved that the only way to prove this is by contradiction? PS: How about if we consider two […]