example also contains an application of demorgan' law this law helps us deal with negationsfor it states that the negation of statement of the form " or qis "not and not likewiseit states that the negation of statement of the form " and qis "not or not qcontradiction another negative justification technique is justification by contradictionwhich also often involves using demorgan' law in applying the justification by contradicti on techniquewe establish that statement is true by first supposing that is false and then showing that this assumption leads to contradiction (such as or by reaching such contradictionwe show that no consistent situation exists with being falseso must be true of coursein order to reach this conclusionwe must be sure our situation is consistent before we assume is false example let and be integers if ab is oddthen is odd and is odd justificationlet ab be odd we wish to show that is odd and is odd sowith the hope of leading to contradictionlet us assume the oppositenamelysuppose is even or is even in factwithout loss of generalitywe can assume that is even (since the case for is symmetricthen for some integer henceab ( ) (ib)that isab is even but this is contradictionab cannot simultaneously be odd and even therefore is odd and is odd induction and loop invariants most of the claims we make about running time or space bound involve an integer parameter (usually denoting an intuitive notion of the "sizeof the problemmoreovermost of these claims are equivalent to saying some statement (nis true "for all > since this is making claim about an infinite set of numberswe cannot justify this exhaustively in direct fashion induction we can often justify claims such as those above as truehoweverby using the technique of induction this technique amounts to showing thatfor any particular > there is finite sequence of implications that starts with something known to be true and ultimately leads to showing that (nis true specificallywe begin justification by induction by showing that (nis true for (and possibly some other values , kfor some constant kthen