2
$\begingroup$

for following formulas in propositional logic, how do I write equivalent formulas using only logical symbols → and $\bot$:

$\alpha$ $\land$ $\beta$

$\alpha$ $\lor$ $\beta$

$¬\alpha$

Is it something like:

$¬\alpha$ is equivalent to $\alpha$$\bot$

$\alpha$ $\lor$ $\beta$ is equivalent to $¬\alpha$$\beta$ therefore ($\alpha$$\bot$) → $\beta$

$\alpha$ $\land$ $\beta$ is equivalent to $¬\alpha$ $\lor$ $¬\beta$ and is therefore $\alpha$$¬\beta$ and therefore $\alpha$ → ($\beta$$\bot$)

Also, how do we prove that there is no proposition $\alpha$ such that ($\alpha$ $↔$ ($¬\beta$)) is tautology, using only propositional variable $\alpha$ and →?

$\endgroup$
2
$\begingroup$

$\alpha \equiv \alpha \to \bot$ is correct.
$\alpha \lor \beta \equiv \neg \alpha \to \beta \equiv (\alpha \to \bot) \to \beta$ is also correct.
$\alpha \land \beta \equiv \neg \alpha \lor \neg \beta$ is incorrect. This owuld mean that at least one out of $\alpha$ and $\beta$ must be false, but we want none of them to be false. Instead, we want to say "neither not $\alpha$ nor not $\beta$", so the desired formula is the negation of your statement, $\neg (\neg \alpha \lor \neg \beta)$, so the equilalence we end up with is $(\alpha \to (\beta \to \bot)) \to \bot$.


There is no propositional variable $\alpha$ such that $(\alpha \leftrightarrow (\neg \beta)).$

I don't know what is meant by "only using $\to$" given that the proof to be presented has to be an informal semantic one" (you can't prove a statement such as "there exists no "\alpha" such that" by using truth tables or logical equivalences), so I assume this was a typo:
With the restriction that $\alpha$ be a propositional variable, there are only two cases to distinguish:
1. $\alpha = \beta$, i.e. $\alpha$ and $\beta$ are the same variable, and have the same value under any assignment function. Then obviously, by the definition of $\neg$ under no assignment can $\alpha$ and $\neg \beta$ the same truth value, which contradicts the semantics of $\leftrightarrow$ which demands that $\alpha$ and $\beta$ be true under all the same assignments.
2. $\alpha \neq \beta$, i.e. $\alpha$ and $\beta$ are different propositional variables. Then there exists an assignment under which $\alpha$ and $\beta$ have the same truth value, which again contradicts the definition of $\leftrightarrow$.

$\endgroup$
  • $\begingroup$ "¬(¬α∨¬β), so the equilalence we end up with is (α→(β→⊥))→⊥." I think you forgot a $\bot$. $\endgroup$ – Doug Spoonwood Apr 28 at 11:41
  • $\begingroup$ @Doub Spoonwood No, the truth table checks out fine. $\endgroup$ – lemontree Apr 28 at 21:28
  • $\begingroup$ You're right. I misread the $\lor$ as a $\rightarrow$ I think. $\endgroup$ – Doug Spoonwood Apr 29 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.