The equivalence and negation laws, side by side
The rewrite rules every later proof leans on -- one page to check them against.
Reach for the conditional rewrites when a proof's hypothesis is awkward but its negated conclusion, or its reversed pieces, might not be -- remembering the converse is a different claim while the contrapositive is guaranteed equivalent. Reach for De Morgan's laws the moment a negation lands on an AND or an OR, and for the quantifier-negation rule the moment a negation lands on a "for all" or "there exists." Reach for modus ponens or modus tollens when an argument's validity itself is the question, not just one statement's truth value.
Rewriting a conditional
Term
converse
Swaps the two pieces -- NOT guaranteed equivalent to the original.
Swaps and negates both pieces -- the one rewrite always equivalent to the original.
Negating AND / OR (De Morgan's laws)
For any propositions p and q: \neg(p \wedge q) \equiv \neg p \vee \neg q \neg(p \vee q) \equiv \neg p \wedge \neg q
What is this saying? To deny an "and," deny at least one of its parts: "not both" means "one or the other fails." To deny an "or," deny both parts: "not either" means "neither." In each law the \neg moves onto each part, and the connective swaps.
Why should I care? These two laws are how you push a "not" inside a bracket. You need them to simplify a sentence, to put it in a normal form, and to state plainly what a denial claims.
Intuition. "Not both a towel and a mat" allows a towel alone. So it can't mean "no towel and no mat." It means "no towel, or no mat." The "and" had to turn into "or" once the "not" moved in.
Ingredients.
- p, q: any two propositions. Capital letters such as A and B work the same way.
- \neg: "not." \wedge: "and." \vee: "or."
- \equiv: the two sides have the same truth value on every row.
Example. "It's not true that the café is open and serving lunch" is equivalent to "the café is closed, or it isn't serving lunch."
What doesn't follow. The \neg does not just copy onto each part. \neg(p \wedge q) is not equivalent to \neg p \wedge \neg q: on the row p = T, q = F, the first is true and the second false.
Example
Show proof
Both are checked directly by truth table -- a finite, exhaustive check suffices since there are only 2^2=4 rows to consider for two atoms.
First law. At p=T,q=T: left side \neg(T\wedge T)=\neg T=F; right side \neg T\vee\neg T=F\vee F=F. At p=T,q=F: left side \neg(T\wedge F)=\neg F=T; right side F\vee T=T. At p=F,q=T: left side \neg(F\wedge T)=T; right side T\vee F=T. At p=F,q=F: left side \neg(F\wedge F)=T; right side T\vee T=T. Every row matches.
Second law. At p=T,q=T: left side \neg(T\vee T)=F; right side F\wedge F=F. At p=T,q=F: left side \neg(T\vee F)=F; right side F\wedge T=F. At p=F,q=T: left side \neg(F\vee T)=F; right side T\wedge F=F. At p=F,q=F: left side \neg(F\vee F)=T; right side T\wedge T=T. Every row matches.
Negating quantifiers
For a predicate P(x) over a domain D: \neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x) \neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)
Example
Show proof
First law. \forall x\, P(x) is true exactly when P(x) holds for every x \in D. So \neg(\forall x\, P(x)) is true exactly when it is NOT the case that P(x) holds for every x -- that is, when at least one x \in D fails P(x), i.e. some x satisfies \neg P(x). That is precisely the condition for \exists x\, \neg P(x) to be true. The two sides are true in exactly the same cases, so they are equivalent.
Second law. \exists x\, P(x) is true exactly when at least one x \in D satisfies P(x). So \neg(\exists x\, P(x)) is true exactly when NO x \in D satisfies P(x) -- that is, when every x \in D satisfies \neg P(x). That is precisely the condition for \forall x\, \neg P(x) to be true. Again, the two sides agree in every case.
Valid argument forms
Given p \implies q and p, conclude q. \big[(p \implies q) \wedge p\big] \implies q
What is this saying? If one thing guarantees another, and the first thing happens, then the second happens too. "If it rains, the street gets wet. It is raining. So the street is wet."
Why should I care? This is the most common step in everyday reasoning, and the first rule most proof systems give you. Its look-alike, affirming the consequent ("the street is wet, so it rained"), is a fallacy, and telling the two apart is a basic skill.
Intuition. The if–then sentence is a promise: whenever p is true, q is true. Knowing p is true puts you in the only case the promise covers, so q follows.
Ingredients.
- p, q: any statements, simple or compound.
- p \implies q: the conditional "if p then q" (also written p \to q).
- p: the antecedent, asserted on its own as a second premise.
Example
Show proof
Checked by truth table over the two atoms p, q. At p=T,q=T: the premise (p\implies q)\wedge p = T\wedge T=T, and q=T, so the whole conditional is T\implies T=T. At p=T,q=F: p\implies q=F, so the premise F\wedge T=F, making the whole conditional F\implies \text{anything}=T. At p=F,q=T: p=F makes the premise (\cdot)\wedge F=F, so the conditional is again T. At p=F,q=F: same reasoning, premise is F, conditional is T. Every row is true, so this is a tautology -- the argument form is valid regardless of what p and q actually are.
Given p \implies q and \neg q, conclude \neg p. \big[(p \implies q) \wedge \neg q\big] \implies \neg p
What is this saying? If one thing guarantees another, and the second thing did not happen, then the first did not happen either. "If it rained, the street is wet. The street is dry. So it didn't rain."
Why should I care? This is how a failed prediction counts against a claim: if the claim were true, you would see q, and you don't. Its look-alike, denying the antecedent ("it didn't rain, so the street is dry"), is a fallacy.
Intuition. Suppose p were true. Then the promise p \implies q would make q true, but you know q is false. So p can't be true.
Ingredients.
- p, q: any statements, simple or compound.
- p \implies q: the conditional "if p then q" (also written p \to q).
- \neg q: "not q," the denial of the consequent, as a second premise.
Example
Show proof
Checked by truth table. At p=T,q=T: \neg q=F, so the premise (p\implies q)\wedge\neg q = T\wedge F=F, making the conditional F\implies\text{anything}=T. At p=T,q=F: p\implies q=F, so the premise is F\wedge T=F, conditional is T. At p=F,q=T: \neg q=F, premise is F, conditional is T. At p=F,q=F: p\implies q=T, \neg q=T, premise is T\wedge T=T; the conclusion \neg p=T here too, so the conditional is T\implies T=T. Every row is true, confirming this argument form is valid for every p, q.