Prove logical equivalence \begin{gather}
(p \to q) \equiv (\lnot p \lor q) \\
\lnot(p \land q) \equiv (\lnot p \lor \lnot q)
\end{gather}
Can these be proven without truth tables?
 A: Both statements are logical identities in propositional logic, typically taken as "axioms": In fact, we define the material conditional $p \rightarrow q$ to be equivalent to $\lnot p \lor q$: the implication is true whenever $p$ is false or whenever $q$ is true. The second is one of the equivalencies resulting from DeMorgan's Laws. 
The best way to prove the given equivalencies is to show that they are equivalent for each possible assignment of truth values to $p$ and $q$ (and in the first case, they are identiclal merely by definition of the material conditional.)  This is precisely what a what a truth-table does: a "proof-by-cases" so to speak: in each of the above, there are four cases to consider: each row of the truth-tables represent one possible case; together, the rows exhibit only and all such cases. Once we prove that these identities are true in this manner, we are done, and we can accept them, and use them validly when proving more complicated equivalencies.
Note: depending on one's "formal system", the equivalencies taken as "axioms" i.e., as "most basic", may vary:
See Propositional Calculus for a more thorough explanation. But to start,: 

In general terms, a propositional calculus is a formal system that consists of a set of syntactic expressions (well-formed formulæ or wffs), a distinguished subset of these expressions (axioms), plus a set of formal rules that define a specific binary relation, intended to be interpreted as logical equivalence, on the space of expressions.

A: amWhy provided an answer for axiomatic systems where the equivalences are taken as definitional.  However, in natural deduction systems, which typically don't have axioms per se, or have fewer, these equivalences, if understood as biconditionals, can be proven.  For sake of example, here's the first one:


*

*
*

*Assume $p \to q$.


*
*

*
*

*Assume $\lnot(\lnot p \lor q)$.



*
*

*
*

*
*

*Assume $p$.




*
*

*
*

*
*

*$q$ by modus ponens with 1 and 2.




*
*

*
*

*
*

*$\lnot p \lor q$ by disjunction introduction with 4.




*
*

*
*

*
*

*$\bot$ by falsum introduction with 2 and 5.




*
*

*
*

*$\lnot p$ by negation introduction with 3–6.



*
*

*
*

*$\lnot p \lor q$ by disjunction introduction with 7.



*
*

*
*

*$\bot$ by falsum introduction with 2 and 8.



*
*

*$\lnot p \lor q$ by negation elimination 2–9.


*
*

*Assume $\lnot p \lor q$.


*
*

*
*

*Assume $p$.



*
*

*
*

*
*

*Assume $\lnot p$.




*
*

*
*

*
*

*$\bot$ by falsum introduction with 12 and 13.




*
*

*
*

*
*

*$q$ by falsum elimination with 14.




*
*

*
*

*
*

*Assume $q$.




*
*

*
*

*
*

*$q$ by reiteration with 16.




*
*

*
*

*$q$ by disjunction elimination with 11, 13–15, and 16–17.



*
*

*$p \to q$ by conditional introduction with 12–18.


*$(p \to q) \leftrightarrow (\lnot p \lor q)$ by biconditional introduction with 1–10 and 11–19.


The second has a similar structure (prove each of $\lnot(p \land q)$ and $\lnot p \lor \lnot q$ from the other, and then use biconditional introduction with the respective subproofs). 
So, while using truth tables might be a very direct way to check whether two propositional formulae are equivalent, truth tables are not the only option.  
