How do I write equivalent formulas using only $\to$ and $\bot$?

251 Views Asked by At

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 →?

1

There are 1 best solutions below

3
On BEST ANSWER

$\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$.