5
$\begingroup$

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful one.

But for whatever reason, it seems like I'm discovering these random helpful things rather, well, randomly. And if I Google for a list of boolean identities, all I seem to find is pages describing DeMorgan's Law, Distributive Law and whatnot, which is not what I'm looking for.

Can anyone offer me some formulas or a link to them?

$\endgroup$
3
  • $\begingroup$ I think that you want to write every propositional statement using the connective not,or ,and (an equivalent one) $\endgroup$
    – Amr
    Dec 16, 2012 at 23:30
  • $\begingroup$ The thing is that on booleans, you only have $\lnot$, $\land$, $\lor$... Whereas is you talking about logical propositions, you can have $\Leftrightarrow$ and $\Rightarrow$. So google for "propositional logic". $\endgroup$
    – xavierm02
    Dec 16, 2012 at 23:34
  • $\begingroup$ they all boil down to the 3 operators. nothing drastic escaping your eye. $\endgroup$
    – ashley
    Dec 16, 2012 at 23:53

1 Answer 1

Reset to default
9
$\begingroup$

First, it's crucial you develop an understanding as to WHY the identities hold, by understanding the truth-functional nature of the logical connectives and the propositions on which they operate.
Simply memorizing identities (or "laws" or "rules"), without understanding why they hold isn't going to work in the long run. On the other hand, understanding the equivalencies (the "why") will go a long way in helping you to remember them!

So you might want to test the following out, using say, truth-tables. That said:

Conjunction and disjunction are each both commutative and associative,

$$p \land q \equiv q \land p\;\text{ and} \;\;p \lor q \equiv q \lor p\tag{commutativity}$$ $$p \land(q\land r) \equiv (p\land q) \land r\;\text{ and}\;\; p\lor (q \lor r) \equiv (p \lor q) \lor r\tag{associativity}$$ AND you do want to know the distributive laws and DeMorgan's laws (and how and when to apply them, as these define equivalencies (identities), and are indispensable in proofs.

Distributive Laws: $$p \land(q \lor r) \equiv (p\land q) \lor (p \land r)$$ $$p \lor (q\land r) \equiv (p \lor q) \land (p \lor r)$$

DeMorgan's Laws: $$\lnot(p \land q) \equiv \lnot p \lor \lnot q$$ $$\lnot (p\lor q) \equiv \lnot p \land \lnot q$$

You'll also want to know that "An implication is equivalent to its contrapositive": $$p \rightarrow q \equiv \lnot q \rightarrow \lnot p$$

enter image description here

Also important are the following:

The first two are identity laws, the second two domination laws (T: any true statement or tautology; F: any false statement or contradiction):

$$p \land T \equiv p$$ $$p \lor F \equiv p$$ $$p \lor T \equiv T$$ $$p \land F \equiv F$$

Two final identities worth mentioning are those related to complementation:

$$p \land \lnot p \equiv F$$ $$p \lor \lnot p \equiv T$$

There are other equivalences, but if you know what you've already listed, and you know DeMorgan's and Distributive Laws, and understand why the above "laws" are, in fact, equivalences, you can pretty much obtain most equivalencies you'll need to use.

Also, you might want to read Propositional Calculus, as this entry fills in gaps, and includes the use of rules of inference in natural deduction.

$\endgroup$
5
  • 1
    $\begingroup$ Don't forget the commutative laws ($p \wedge q \equiv q \wedge p$ and $p \vee q \equiv q \vee p$) and associative laws ($(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$ and $(p \vee q) \vee r \equiv p \vee (q \vee r$). $\endgroup$
    – Code-Guru
    Dec 17, 2012 at 1:28
  • 1
    $\begingroup$ @Code-Guru Yes, of course! $\endgroup$
    – amWhy
    Dec 17, 2012 at 1:31
  • $\begingroup$ I was first going to suggest permutations on the identity and domination laws, but the commutative law covers it and is good to have on its own ;-) $\endgroup$
    – Code-Guru
    Dec 17, 2012 at 1:35
  • 1
    $\begingroup$ @Code-Guru It's good to simply have the building-blocks and from there, the knowledge of (and practice in) how to use them to "build" from there! $\endgroup$
    – amWhy
    Dec 17, 2012 at 1:43
  • $\begingroup$ Wholeheartedly agreed! $\endgroup$
    – Code-Guru
    Dec 17, 2012 at 1:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .