Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I think that you want to write every propositional statement using the connective not,or ,and (an equivalent one) –  Amr Dec 16 '12 at 23:30
    
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". –  xavierm02 Dec 16 '12 at 23:34
    
they all boil down to the 3 operators. nothing drastic escaping your eye. –  ashley Dec 16 '12 at 23:53

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
1  
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$). –  Code-Guru Dec 17 '12 at 1:28
1  
@Code-Guru Yes, of course! –  amWhy Dec 17 '12 at 1:31
    
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 ;-) –  Code-Guru Dec 17 '12 at 1:35
1  
@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! –  amWhy Dec 17 '12 at 1:43
    
Wholeheartedly agreed! –  Code-Guru Dec 17 '12 at 1:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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